Paper 2019/389

Achieving secure and efficient lattice-based public-key encryption: the impact of the secret-key distribution

Sauvik Bhattacharya, Oscar Garcia-Morchon, Rachel Player, and Ludo Tolhuizen

Abstract

Lattice-based public-key encryption has a large number of design choices that can be combined in diverse ways to obtain different tradeoffs. One of these choices is the distribution from which secret keys are sampled. Numerous secret-key distributions exist in the state of the art, including (discrete) Gaussian, binomial, ternary, and fixed-weight ternary. Although the secret-key distribution impacts both the concrete security and the performance of the schemes, it has not been compared in a detailed way how the choice of secret-key distribution affects this tradeoff. In this paper, we compare different aspects of secret-key distributions from submissions to the NIST post-quantum standardization effort. We consider their impact on concrete security (influenced by the entropy and variance of the distribution), and on decryption failures and IND-CCA2 security (influenced by the probability of sampling keys with ``non average, large'' norm). Next, we select concrete parameters of an encryption scheme instantiated with the above distributions %optimized for key sizes, to identify which distribution(s) offer the best tradeoffs between security and key sizes. The conclusions of the paper are: first, the above optimization shows that fixed-weight ternary secret keys result in the smallest key sizes in the analyzed scheme. The reason is that such secret keys reduce the decryption failure rate and hence allow for a higher noise-to-modulus ratio, alleviating the slight increase in lattice dimension required for countering specialized attacks that apply in this case. Second, compared to secret keys with independently sampled components, secret keys with a fixed composition (i.e., the number of secret key components equal to any possible value is fixed) result in the scheme becoming more secure against active attacks based on decryption failures.

Note: Results extended and more generalized. Added related work.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Lattice cryptographyPublic-key encryptionNoisy ElGamalSecret keysDecryption failureHybrid attack
Contact author(s)
sauvik bhattacharya @ philips com
History
2019-05-03: revised
2019-04-18: received
See all versions
Short URL
https://ia.cr/2019/389
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/389,
      author = {Sauvik Bhattacharya and Oscar Garcia-Morchon and Rachel Player and Ludo Tolhuizen},
      title = {Achieving secure and efficient lattice-based public-key encryption: the impact of the secret-key distribution},
      howpublished = {Cryptology ePrint Archive, Paper 2019/389},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/389}},
      url = {https://eprint.iacr.org/2019/389}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.