Paper 2013/394

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.

Note: Minor revision.