Cryptology ePrint Archive: Report 2017/421

Exploring Naccache-Stern Knapsack Encryption

Éric Brier and Rémi Géraud and David Naccache

Abstract: The Naccache–Stern public-key cryptosystem (NS) relies on the conjectured hardness of the modular multiplicative knapsack problem: Given $p,\{v_i\},\prod v_i^{m_i} \bmod p$, find the $\{m_i\}$.

Given this scheme's algebraic structure it is interesting to systematically explore its variants and generalizations. In particular it might be useful to enhance NS with features such as semantic security, re-randomizability or an extension to higher-residues.

This paper addresses these questions and proposes several such variants.

Category / Keywords: public-key cryptography / Encryption, Security proofs, DLP

Date: received 16 May 2017, last revised 16 May 2017

Contact author: david naccache at ens fr

Available format(s): PDF | BibTeX Citation

Version: 20170522:212241 (All versions of this report)

Short URL: ia.cr/2017/421