Paper 2017/421 Original: eprint.iacr.org/2017/421 ↗
Exploring Naccache-Stern Knapsack Encryption
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.
- History
- 2017-05-22: last updated
- 2017-05-22: published
- Short URL
- https://ia.cr/2017/421
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}