A semantically secure public key cryptoscheme using bit-pair shadows

作者：Su, Shenghui^*; Lu, Shuwang; Xu, Maozhi; Xie, Tao

来源：Theoretical Computer Science, 2016, 654: 113-127.

DOI：10.1016/j.tcs.2016.04.017

• Public key cryptoscheme
• Semantical security
• Bit-pair shadow
• Random padding
• Anomalous subset sum problem
• Compact sequence

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 [1gM] of the new cryptoscheme to 464, 544, or 640.

• 出版日期2016-11-22
• 单位南京理工大学; 中国科学院大学; 中国人民解放军国防科学技术大学; 北京大学