Cryptology ePrint Archive: Report 2019/389

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

Sauvik Bhattacharya and Oscar Garcia-Morchon and 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.

Category / Keywords: public-key cryptography / Lattice cryptography, Public-key encryption, Noisy ElGamal, Secret keys, Decryption failure, Hybrid attack

Date: received 11 Apr 2019, last revised 3 May 2019

Contact author: sauvik bhattacharya at philips com

Available format(s): PDF | BibTeX Citation

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

Version: 20190503:074101 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]