Exploring Naccache-Stern Knapsack Encryption

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

Paper 2017/421

Exploring Naccache-Stern Knapsack Encryption

Éric Brier, 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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: Encryption Security proofs DLP
Contact author(s): david naccache @ ens fr
History: 2017-05-22: received
Short URL: https://ia.cr/2017/421
License: CC BY

BibTeX

@misc{cryptoeprint:2017/421,
      author = {Éric Brier and Rémi Géraud and David Naccache},
      title = {Exploring Naccache-Stern Knapsack Encryption},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/421},
      year = {2017},
      url = {https://eprint.iacr.org/2017/421}
}