mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2012-09-08, 19:24   #1
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

3·7·19·29 Posts
Default Metrosexual/Bi-Curious Cryptography article

Brian Hayes has an interesting piece about this in his latest American Scientist computing-science column:

Alice and Bob in Cipherspace: A new form of encryption allows you to compute with data you cannot read
Quote:
Alice hands bob a locked suitcase and asks him to count the money inside. “Sure,” Bob says. “Give me the key.” Alice shakes her head; she has known Bob for many years, but she’s just not a trusting person. Bob lifts the suitcase to judge its weight, rocks it back and forth and listens as the contents shift inside; but all this reveals very little. “It can’t be done,” he says. “I can’t count what I can’t see.”

Alice and Bob, fondly known as the first couple of cryptography, are really more interested in computational suitcases than physical ones. Suppose Alice gives Bob a securely encrypted computer file and asks him to sum a list of numbers she has put inside. Without the decryption key, this task also seems impossible. The encrypted file is just as opaque and impenetrable as the locked suitcase. “Can’t be done,” Bob concludes again.

But Bob is wrong. Because Alice has chosen a very special encryption scheme, Bob can carry out her request. He can compute with data he can’t inspect. The numbers in the file remain encrypted at all times, so Bob cannot learn anything about them. Nevertheless, he can run computer programs on the encrypted data, performing operations such as summation. The output of the programs is also encrypted; Bob can’t read it. But when he gives the results back to Alice, she can extract the answer with her decryption key.

The technique that makes this magic trick possible is called fully homomorphic encryption, or FHE. It’s not exactly a new idea, but for many years it was viewed as a fantasy that would never come true. That changed in 2009, with a breakthrough discovery by Craig Gentry, who was then a graduate student at Stanford University. (He is now at IBM Research.) Since then, further refinements and more new ideas have been coming at a rapid pace.

Homomorphic encryption is not quite ready for everyday use. The methods have been shown to work in principle, but they still impose a heavy penalty of inefficiency. If the system can be made more practical, however, there are applications ready and waiting for it. Many organizations are eager to outsource computation: Instead of maintaining their own hardware and software, they would like to run programs on servers “in the cloud,” a phrase meant to suggest that physical location is unimportant. But letting sensitive data float around in the cloud raises concerns about security and privacy. Practical homomorphic encryption would address those worries, protecting the data against eavesdroppers and intruders and even hiding it from the operators of the cloud service.
So this promises - if it can be made efficient enough to allow for bulk en-and-decryption (which is a highly nontrivial 'if') - to make cloud computing safe, which would be a very big deal.
ewmayer is offline   Reply With Quote
Old 2012-09-09, 02:40   #2
Jeff Gilchrist
 
Jeff Gilchrist's Avatar
 
Jun 2003
Ottawa, Canada

49116 Posts
Default

Very interesting, thanks for posting.
Jeff Gilchrist is offline   Reply With Quote
Old 2012-09-09, 02:58   #3
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

2×5×19×31 Posts
Default

Mathematically speaking this is a nice advancement. But practically speaking what is so enticing about cloud computing? Even if this can be made more efficient the user would still need a local computer available to encrypt the input before sending and later decrypt the output after receiving. So why not just run it natively and forget about all the extra steps required to get someone else to compute it?
retina is online now   Reply With Quote
Old 2012-09-09, 05:40   #4
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

22·132 Posts
Default

Quote:
Originally Posted by retina View Post
Mathematically speaking this is a nice advancement. But practically speaking what is so enticing about cloud computing? Even if this can be made more efficient the user would still need a local computer available to encrypt the input before sending and later decrypt the output after receiving. So why not just run it natively and forget about all the extra steps required to get someone else to compute it?
I think it's not about avoiding computers in general, but the costly and complicated systems. For the FEM and CFD stuff I'm doing one high end PC is enough to do all the pre- and postprocessing. But the computation itself requires days of runtime on dozens or even hundreds of cores on a cluster designed to run that kind of stuff. The workplace machine I'd need anyway for office work, just not as powerful. But that's not much of a difference regarding cost and administration. Getting rid of the clusters and everything that's needed to run them might sound enticing to the guys in the controlling department though.
Puzzle-Peter is offline   Reply With Quote
Old 2012-09-09, 06:43   #5
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default

Quote:
Originally Posted by ewmayer View Post
So this promises - if it can be made efficient enough to allow for bulk en-and-decryption (which is a highly nontrivial 'if') - to make cloud computing safe, which would be a very big deal.
The efficiency consideration reminds me of an encryption method I encountered in the late 1980s.

I was working for a company that sold electronic financial transaction software and services. One day I was asked to analyze the feasibility of incorporating an encryption method that enabled Alice to compute one category of keys used in communication with Bob, without having those keys actually transmitted between Alice and Bob, by substituting a special sequence of sixteen en-/decryptions operating on data that Alice (& Bob) already had. Sounds wacky, but though I forget the details, it wasn't just some method of hiding the key among the other data or using other data as a pseudorandom number generator's seed.

The analysis boiled down to determining how many instruction cycles the extra sixteen-layer 'cryption sequence required on an IBM mainframe and how that would affect transaction processing time.

Last fiddled with by cheesehead on 2012-09-09 at 06:46
cheesehead is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
..New algorithm shakes up cryptography"? jwaltos Operation Kibibit 5 2016-01-30 09:33
CUDA and cryptography ET_ GPU Computing 10 2012-09-24 10:27
GIMPS and cryptography Rodrigo Lounge 4 2012-07-31 16:03
new ECPP article R. Gerbicz GMP-ECM 2 2006-09-13 16:24
Distributed Internet Cryptography ewmayer Math 1 2006-08-21 20:53

All times are UTC. The time now is 03:28.

Sat Dec 5 03:28:15 UTC 2020 up 1 day, 23:39, 0 users, load averages: 1.81, 1.68, 1.62

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.