**A Public Key Cryptoscheme Using Bit-pair Shadows**

*Shenghui Su and Shuwang Lü and Maozhi Xu and Tao Xie*

**Abstract: **This paper gives the definition and property of a bit-pair shadow, and devises the three algorithms of a public key cryptoscheme called JUOAN that is based on a multivariate permutation problem and an anomalous subset product problem to which no subexponential time solutions are found so far, and regards a bit-pair as a manipulation unit. The authors demonstrate that the decryption algorithm is correct, deduce the probability that a plaintext solution is nonunique is nearly zero, analyze the security of the new cryptoscheme against extracting a private key from a public key and recovering a plaintext from a ciphertext on the assumption that an integer factorization problem, a discrete logarithm problem, and a low-density subset sum problem can be solved efficiently, and prove that the new cryptoscheme using random padding and random permutation is semantically secure. The analysis shows that the bit-pair method increases the density D of a related knapsack to a number more than 1, and decreases the modulus length lgM of the new cryptoscheme to 464, 544, or 640.

**Category / Keywords: **Public key cryptoscheme; Semantical security; Bit-pair shadow; Random padding Anomalous subset sum problem; Compact sequence

**Original Publication**** (with minor differences): **Theoretical Computer Science, v654, Nov 2016, pp.113–127.

**Date: **received 17 Jun 2013, last revised 29 Apr 2017

**Contact author: **reesse at 126 com

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

**Note: **The content has no essential change.

**Version: **20170430:040524 (All versions of this report)

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

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

[ Cryptology ePrint archive ]