A Guide to Fully Homomorphic Encryption
eprint.iacr.org
A Guide to Fully Homomorphic Encryption
1–10 of 32 posts
Re: A Guide to Fully Homomorphic Encryption
#2This may be a silly question, but whats the current point of creating more efficient methods of encryption when 20-30 years down the road we'll have things like quantum computing with 10^N processing?
Wouldn't that then essentially make modern encryption methods obsolete?
I'd like to hear a more educated viewpoint on this, because most of the sources I've read gloss over everything and make it seem like magic and this seems like a good thread to ask.
Edit: Thanks for the responses, I think I get it a bit better now :D
Re: A Guide to Fully Homomorphic Encryption
#3This may be a silly question, but whats the current point of creating more efficient methods of encryption when 20-30 years down the road we'll have things like quantum computing with 10^N processing? Wouldn't that then essentially make modern encryption methods obsolete? I'd like to hear a more educated viewpoint on this, because most of the sources I've read gloss over everything and make it seem like magic and thi…
To address just one of your points, quantum computation is not a silver bullet. It does not work the way one might think it works. Not many researchers are saying that they will replace classical computers, and for good reason. For many, or even most, computational tasks there is no way to get a large quantum speedup. (And classical computers have had a lot more R&D put into them.) Although easy integer factoring will break quite a few popular crypto schemes, like RSA, the risks of quantum computers are heavily overplayed. For example, I don't believe there is any known quantum attack against AES, which is a good start in a post-quantum world. (I can't think of an asymmetric encryption scheme that I'm sure is resistant to quantum attacks off the top of my head, since I'm no expert, but I'm positive some do exist.)
Re: A Guide to Fully Homomorphic Encryption
#4This may be a silly question, but whats the current point of creating more efficient methods of encryption when 20-30 years down the road we'll have things like quantum computing with 10^N processing? Wouldn't that then essentially make modern encryption methods obsolete? I'd like to hear a more educated viewpoint on this, because most of the sources I've read gloss over everything and make it seem like magic and thi…
To address just one of your points, quantum computation is not a silver bullet. It does not work the way one might think it works. Not many researchers are saying that they will replace classical computers, and for good reason. For many, or even most, computational tasks there is no way to get a large quantum speedup. (And classical computers have had a lot more R&D put into them.) Although easy integer factoring wil…
AES (and other symmetric ciphers) are vulnerable to Grover's algorithm (https://en.wikipedia.org/wiki/Grover%27s_algorithm), which effectively cuts key sizes in half. AES-128 would be reduced to 64-bit security. This isn't a big problem in practice, since we can just switch to 256-bit ciphers like AES-256 and ChaCha20.
Public-key schemes based on factoring and discrete logarithms are undone by Shor's algorithm (https://en.wikipedia.org/wiki/Shor%27s_algorithm), but there are asymmetric systems not known to be vulnerable to quantum algorithms. They are less mature, but researchers are working it.
There's some good high-level information at http://pqcrypto.org/ and in this paper: http://pqcrypto.eu/docs/initial-recommendations.pdf.
Re: A Guide to Fully Homomorphic Encryption
#5This may be a silly question, but whats the current point of creating more efficient methods of encryption when 20-30 years down the road we'll have things like quantum computing with 10^N processing? Wouldn't that then essentially make modern encryption methods obsolete? I'd like to hear a more educated viewpoint on this, because most of the sources I've read gloss over everything and make it seem like magic and thi…
NTRU is another quantum-secure (i.e. thought to be quantum-secure) cryptosystem. It can do most things we demand from public-key cryptosystems. More generally, there is no known quantum attack that significantly breaks lattice-based cryptosystems.
Re: A Guide to Fully Homomorphic Encryption
#6This may be a silly question, but whats the current point of creating more efficient methods of encryption when 20-30 years down the road we'll have things like quantum computing with 10^N processing? Wouldn't that then essentially make modern encryption methods obsolete? I'd like to hear a more educated viewpoint on this, because most of the sources I've read gloss over everything and make it seem like magic and thi…
[deleted]
Re: A Guide to Fully Homomorphic Encryption
#7This may be a silly question, but whats the current point of creating more efficient methods of encryption when 20-30 years down the road we'll have things like quantum computing with 10^N processing? Wouldn't that then essentially make modern encryption methods obsolete? I'd like to hear a more educated viewpoint on this, because most of the sources I've read gloss over everything and make it seem like magic and thi…
To address just one of your points, quantum computation is not a silver bullet. It does not work the way one might think it works. Not many researchers are saying that they will replace classical computers, and for good reason. For many, or even most, computational tasks there is no way to get a large quantum speedup. (And classical computers have had a lot more R&D put into them.) Although easy integer factoring wil…
The (provably) best "general purpose" quantum algorithm is Grover's algorithm. The problem it solves is as follows:
Given an arbitrary function f(x), and a desired output k, find the unique input z such that f(z)=k.
We can see that using classical computers, this problem is O(n), where n is the size of the domain of f. However, Grover's algorithm can solve this problem in O(sqrt(n)). It has been shown that O(sqrt(n)) is the best possible solution to this problem on a quantum computer.
This means that quantum computers effectively halve the key-size for a brute force attack (and probably most other types), but doing any better than this would require exploiting some structure of the cryptosystem you are trying to break. To my knowledge, no such structure has been demonstrated for any major symmetric encryption algorithms.
Re: A Guide to Fully Homomorphic Encryption
#8This may be a silly question, but whats the current point of creating more efficient methods of encryption when 20-30 years down the road we'll have things like quantum computing with 10^N processing? Wouldn't that then essentially make modern encryption methods obsolete? I'd like to hear a more educated viewpoint on this, because most of the sources I've read gloss over everything and make it seem like magic and thi…
my simple answer is, encryption works by creating a function which is vastly more costly in one direction (encryption) than the other (cracking).
for any computing power available, if you apply x seconds of computation to encrypt with a complex key, it will take a multiple of x years to crack it.
as long as that multiple remains, which cryptology seeks to improve, just applying more computing power will never obsolete modern encryption methods.
Re: A Guide to Fully Homomorphic Encryption
#9Earlier quoted context omitted.
To address just one of your points, quantum computation is not a silver bullet. It does not work the way one might think it works. Not many researchers are saying that they will replace classical computers, and for good reason. For many, or even most, computational tasks there is no way to get a large quantum speedup. (And classical computers have had a lot more R&D put into them.) Although easy integer factoring wil…
The (provably) best "general purpose" quantum algorithm is Grover's algorithm. The problem it solves is as follows: Given an arbitrary function f(x), and a desired output k, find the unique input z such that f(z)=k. We can see that using classical computers, this problem is O(n), where n is the size of the domain of f. However, Grover's algorithm can solve this problem in O(sqrt(n)). It has been shown that O(sqrt(n))…
That's really interesting! I have only a passing education in quantum computers, which is why my comment is so devoid of detail... I really should learn more.
Re: A Guide to Fully Homomorphic Encryption
#10This may be a silly question, but whats the current point of creating more efficient methods of encryption when 20-30 years down the road we'll have things like quantum computing with 10^N processing? Wouldn't that then essentially make modern encryption methods obsolete? I'd like to hear a more educated viewpoint on this, because most of the sources I've read gloss over everything and make it seem like magic and thi…
To address just one of your points, quantum computation is not a silver bullet. It does not work the way one might think it works. Not many researchers are saying that they will replace classical computers, and for good reason. For many, or even most, computational tasks there is no way to get a large quantum speedup. (And classical computers have had a lot more R&D put into them.) Although easy integer factoring wil…
Yeah, we have some public key schemes that are conjectured to be resistant to quantum attacks. This one in particular is fun because of the connection to machine learning. (https://en.wikipedia.org/wiki/Learning_with_errors)
Basically, it uses the result that it should be 'hard' to learn a linear function with sufficient noise rate to create a cryptosystem.