I was wondering if there is a security difference between Lattice based homomorphic encryption schemes versus an partially homomorphic encryption scheme like Paillier, and El Gamal encryption schemes especially with respect to the security against quantum attacks?
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ Paillier and ElGamal are really broken to a quantum attacker, lattice crypto isn't broken as immediately / easily but can still be broken badly by qunatum attackers, depending on the scheme details. $\endgroup$– SEJPMJul 4, 2016 at 19:53
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
6
Sure there's a difference between Paillier and ElGamal as opposed to lattice-based cryptography regarding quantum attackers.
Paillier's security is broken as soon as you can efficiently factor large integers which is "easy" using Shor's algorithm. This is caused by the fact that you can easily recover the private from the public key by factoring $n$.
ElGamal's security is broken as soon as you can efficiently compute discrete logarithms which is "easy" using Shor's algorithm. This is caused by the fact that you can easily recover the private from the public key by finding the $x$ such that $\alpha^x\equiv \beta\pmod p$ given everything but $x$.
With lattice-based schemes it's a bit more interesting. Some schemes, like NTRU, can hold up against quantum attackers, while others not so much, like one invented and broken by GCHQ (PDF).
-
$\begingroup$ But does NTRU has provable security against quantum computers? Or is it quantum secure because no one knows a polynomial quantum algorithm to break NTRU like LWE? $\endgroup$– RickJul 6, 2016 at 1:01
-
$\begingroup$ @user2764478 AFAIK there are no known algorithms with provable quantum resistance (except the OTP maybe), just like we don't have algorithms with provable classical computer resistance. $\endgroup$– SEJPMJul 6, 2016 at 8:57
-
$\begingroup$ Well AFAIK signature schemes like TESLA and SPHINCS claim provable quantum security. And also if per our current understandings of P and NP models Lattice based schemes are provable hard for classical computers. $\endgroup$– RickJul 7, 2016 at 17:32
-
1$\begingroup$ @user2764478, our understanding of P and NP (and their relation) is not a hard fact and thus in theory lattice crypto could break down even against classical attackers. As for SPHINCS: This is a hash-based signature scheme whiches security can be reduced to the hardness of breaking the hash (which itself can not be proven secure) and I don't know whether these reductions still hold if your attacker has quantum attack capabilities. $\endgroup$– SEJPMJul 7, 2016 at 18:57
-
$\begingroup$ Yes I agree to your first point, theoretically lattice problems can be broken and ultimately proving P=NP. But does not it also mean NTRU can be broken too. For the second part the authors of TESLA scheme claim that their scheme is provably quantum secure. eprint.iacr.org/2015/755.pdf (page 14) $\endgroup$– RickJul 8, 2016 at 0:16
$\begingroup$
$\endgroup$
1
See here for a description of factoring or computing discrete logarithms using quantum techniques.
-
3$\begingroup$ Even if the linked answer is on this site, 'link only' answers are a bad habit, which should be avoided. Here are some hints for writing good answers: crypto.stackexchange.com/help/how-to-answer $\endgroup$– tyloJul 5, 2016 at 16:07