International Association
for Cryptologic Research

The authors give the definition 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 the correctness of the decryption algorithm, deduce the probability that a plaintext solution is nonunique is nearly zero, and analyze the security of the cryptoscheme against extracting a private key from a public key, and recovering a plaintext from a ciphertext on the assumption that IFP, DLP, and SSP 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.