On Dual Lattice Attacks Against Small-Secret LWE and Parameter Choices in HElib and SEAL. / Albrecht, Martin.

Annual International Conference on the Theory and Applications of Cryptographic Techniques: EUROCRYPT 2017: Advances in Cryptology . Springer, 2017. p. 103-129 (Lecture Notes in Computer Science; Vol. 10210).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Published

Standard

On Dual Lattice Attacks Against Small-Secret LWE and Parameter Choices in HElib and SEAL. / Albrecht, Martin.

Annual International Conference on the Theory and Applications of Cryptographic Techniques: EUROCRYPT 2017: Advances in Cryptology . Springer, 2017. p. 103-129 (Lecture Notes in Computer Science; Vol. 10210).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Harvard

Albrecht, M 2017, On Dual Lattice Attacks Against Small-Secret LWE and Parameter Choices in HElib and SEAL. in Annual International Conference on the Theory and Applications of Cryptographic Techniques: EUROCRYPT 2017: Advances in Cryptology . Lecture Notes in Computer Science, vol. 10210, Springer, pp. 103-129. https://doi.org/10.1007/978-3-319-56614-6_4

APA

Albrecht, M. (2017). On Dual Lattice Attacks Against Small-Secret LWE and Parameter Choices in HElib and SEAL. In Annual International Conference on the Theory and Applications of Cryptographic Techniques: EUROCRYPT 2017: Advances in Cryptology (pp. 103-129). (Lecture Notes in Computer Science; Vol. 10210). Springer. https://doi.org/10.1007/978-3-319-56614-6_4

Vancouver

Albrecht M. On Dual Lattice Attacks Against Small-Secret LWE and Parameter Choices in HElib and SEAL. In Annual International Conference on the Theory and Applications of Cryptographic Techniques: EUROCRYPT 2017: Advances in Cryptology . Springer. 2017. p. 103-129. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-56614-6_4

Author

Albrecht, Martin. / On Dual Lattice Attacks Against Small-Secret LWE and Parameter Choices in HElib and SEAL. Annual International Conference on the Theory and Applications of Cryptographic Techniques: EUROCRYPT 2017: Advances in Cryptology . Springer, 2017. pp. 103-129 (Lecture Notes in Computer Science).

BibTeX

@inproceedings{867effc5f74a4322ad48c1ff1acbbf0f,
title = "On Dual Lattice Attacks Against Small-Secret LWE and Parameter Choices in HElib and SEAL",
abstract = "We present novel variants of the dual-lattice attack against LWE in the presence of an unusually short secret. These variants are informed by recent progress in BKW-style algorithms for solving LWE. Applying them to parameter sets suggested by the homomorphic encryption libraries HElib and SEAL yields revised security estimates. Our techniques scale the exponent of the dual-lattice attack by a factor of (2L)/(2L+1)(2L)/(2L+1) when logq=Θ(Llogn)log⁡q=Θ(Llog⁡n), when the secret has constant hamming weight hh and where LL is the maximum depth of supported circuits. They also allow to half the dimension of the lattice under consideration at a multiplicative cost of 2h2h operations. Moreover, our techniques yield revised concrete security estimates. For example, both libraries promise 80 bits of security for LWE instances with n=1024n=1024 and log2q≈47log2⁡q≈47, while the techniques described in this work lead to estimated costs of 68 bits (SEAL) and 62 bits (HElib).",
author = "Martin Albrecht",
year = "2017",
doi = "10.1007/978-3-319-56614-6_4",
language = "English",
isbn = "978-3-319-56619-1",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "103--129",
booktitle = "Annual International Conference on the Theory and Applications of Cryptographic Techniques",

}

RIS

TY - GEN

T1 - On Dual Lattice Attacks Against Small-Secret LWE and Parameter Choices in HElib and SEAL

AU - Albrecht, Martin

PY - 2017

Y1 - 2017

N2 - We present novel variants of the dual-lattice attack against LWE in the presence of an unusually short secret. These variants are informed by recent progress in BKW-style algorithms for solving LWE. Applying them to parameter sets suggested by the homomorphic encryption libraries HElib and SEAL yields revised security estimates. Our techniques scale the exponent of the dual-lattice attack by a factor of (2L)/(2L+1)(2L)/(2L+1) when logq=Θ(Llogn)log⁡q=Θ(Llog⁡n), when the secret has constant hamming weight hh and where LL is the maximum depth of supported circuits. They also allow to half the dimension of the lattice under consideration at a multiplicative cost of 2h2h operations. Moreover, our techniques yield revised concrete security estimates. For example, both libraries promise 80 bits of security for LWE instances with n=1024n=1024 and log2q≈47log2⁡q≈47, while the techniques described in this work lead to estimated costs of 68 bits (SEAL) and 62 bits (HElib).

AB - We present novel variants of the dual-lattice attack against LWE in the presence of an unusually short secret. These variants are informed by recent progress in BKW-style algorithms for solving LWE. Applying them to parameter sets suggested by the homomorphic encryption libraries HElib and SEAL yields revised security estimates. Our techniques scale the exponent of the dual-lattice attack by a factor of (2L)/(2L+1)(2L)/(2L+1) when logq=Θ(Llogn)log⁡q=Θ(Llog⁡n), when the secret has constant hamming weight hh and where LL is the maximum depth of supported circuits. They also allow to half the dimension of the lattice under consideration at a multiplicative cost of 2h2h operations. Moreover, our techniques yield revised concrete security estimates. For example, both libraries promise 80 bits of security for LWE instances with n=1024n=1024 and log2q≈47log2⁡q≈47, while the techniques described in this work lead to estimated costs of 68 bits (SEAL) and 62 bits (HElib).

U2 - 10.1007/978-3-319-56614-6_4

DO - 10.1007/978-3-319-56614-6_4

M3 - Conference contribution

SN - 978-3-319-56619-1

T3 - Lecture Notes in Computer Science

SP - 103

EP - 129

BT - Annual International Conference on the Theory and Applications of Cryptographic Techniques

PB - Springer

ER -