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
EncryptionSecurity proofsDLP
Contact author(s)
david naccache @ ens fr
History
2017-05-22: received
Short URL
https://ia.cr/2017/421
License
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2017/421}},
      url = {https://eprint.iacr.org/2017/421}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.