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

Sauvik Bhattacharya; Oscar Garcia-Morchon; Rachel Player; Ludo Tolhuizen

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 cryptography Public-key encryption Noisy ElGamal Secret keys Decryption failure Hybrid 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: 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},
      url = {https://eprint.iacr.org/2019/389}
}