Mixed-radix Naccache-Stern encryption

Rémi Géraud; David Naccache

Paper 2018/278 Original: eprint.iacr.org/2018/278 ↗

Mixed-radix Naccache-Stern encryption

Rémi Géraud

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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
History: 2018-03-22: last updated; 2018-03-22: published
Short URL: https://ia.cr/2018/278
License: https://creativecommons.org/licenses/by/4.0/

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},
      url = {https://eprint.iacr.org/2018/278}
}