Mixed-radix Naccache-Stern encryption

Rémi Géraud; David Naccache

Paper 2018/278

Mixed-radix Naccache-Stern encryption

Rémi Géraud and David Naccache

Abstract

In this work we explore a combinatorial optimization problem stemming from the Naccache-Stern cryptosystem. We show that solving this problem results in bandwidth improvements, and suggest a polynomial-time approximation algorithm to find an optimal solution. Our work suggests that using optimal radix encoding results in an asymptotic 50% increase in bandwidth.

Note: (minor typo)

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Journal of Cryptographic Engineering
DOI: 10.1007/s13389-018-0188-7
Keywords: optimization Naccache-Stern cryptosystem
Contact author(s): remi geraud @ ens fr
History: 2018-03-22: received
Short URL: https://ia.cr/2018/278
License: CC BY

BibTeX

@misc{cryptoeprint:2018/278,
      author = {Rémi Géraud and David Naccache},
      title = {Mixed-radix Naccache-Stern encryption},
      howpublished = {Cryptology {ePrint} Archive, Paper 2018/278},
      year = {2018},
      doi = {10.1007/s13389-018-0188-7},
      url = {https://eprint.iacr.org/2018/278}
}