Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / optimization, Naccache-Stern cryptosystem

Original Publication (in the same form): Journal of Cryptographic Engineering

Date: received 20 Mar 2018, last revised 20 Mar 2018

Contact author: remi geraud at ens fr

Available format(s): PDF | BibTeX Citation

Note: (minor typo)

Version: 20180322:163157 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]