**A Public Key Cryptoscheme Using the Bit-pair Method**

*Shenghui Su and Maozhi Xu and Tao Xie and Shuwang Lu*

**Abstract: **The authors give the definition and property of a bit-pair shadow, and design the three algorithms of a public key cryptoscheme called JUNA which regards a bit-pair as an operation unit, and is based on the multivariate permutation problem (MPP) and the anomalous subset product problem (ASPP). Then, demonstrate that the decryption algorithm is correct, deduce the probability that a plaintext solution is nonunique is nearly zeroth, dissect the time complexities of the algorithms, and analyze the security of the cryptoscheme against extracting a private key from a public key, and recovering a plaintext from a ciphertext by LLL lattice base reduction, adaptive-chosen-ciphertext manner, and meet-in-the-middle dichotomy on the assumption that the IFP, DLP, and SSP of low density can be solved efficiently. Besides, give the conversion from the ASPP to the anomalous subset sum problem (ASSP) through a discrete logarithm. The facts show the bit-pair method increases the density of a related ASSP knapsack with D > 1, and decreases the length of modulus of the cryptoscheme with lg M = 384, 464, 544, or 640 corresponding to n = 80, 96, 112, or 128.

**Category / Keywords: **public-key cryptography / Public key cryptoscheme; Anomalous subset sum problem; Bit-pair shadow string; Compact sequence; Lever function

**Date: **received 17 Jun 2013, last revised 6 Oct 2013

**Contact author: **reesse at 126 com

**Available format(s): **PDF | BibTeX Citation

**Note: **Minor revision.

**Version: **20131007:031348 (All versions of this report)

**Short URL: **ia.cr/2013/394

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]