You are looking at a specific version 20141101:105220 of this paper. See the latest version.

Paper 2006/420

The REESSE1+ Public Key Cryptosystem v 2.21

Shenghui Su and Shuwang Lv

Abstract

In this paper, the authors give the definitions of a coprime sequence and a lever function, and describe the five algorithms and six characteristics of a prototypal public key cryptosystem which is used for encryption and signature, and based on three new problems and one existent problem: the multivariate permutation problem (MPP), the anomalous subset product problem (ASPP), the transcendental logarithm problem (TLP), and the polynomial root finding problem (PRFP). Prove by reduction that MPP, ASPP, and TLP are computationally at least equivalent to the discrete logarithm problem (DLP) in the same prime field, and meanwhile find some evidence which inclines people to believe that the new problems are harder than DLP each, namely unsolvable in DLP subexponential time. Demonstrate the correctness of the decryption and the verification, deduce the probability of a plaintext solution being nonunique is nearly zero, and analyze the exact securities of the cryptosystem against recovering a plaintext from a ciphertext, extracting a private key from a public key or a signature, and forging a signature through known signatures, public keys, and messages on the assumption that IFP, DLP, and LSSP can be solved. Studies manifest that the running times of effectual attack tasks are greater than or equal to O(2^n) so far when n = 80, 96, 112, or 128 with lg M = 696, 864, 1030, or 1216. As viewed from utility, it should be researched further how to decrease the length of a modulus and to increase the speed of the decryption.

Note: Appendix B and C are modified.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. Theoretical Computer Science, v426-427, Apr. 2012, pp. 91-117.
Keywords
Coprime sequenceLever functionBit shadowDigital SignatureDouble congruence theoremTranscendental logarithm problemProvable SecurityPolynomial time Turing reduction
Contact author(s)
reesse @ 126 com
History
2014-11-01: last of 18 revisions
2006-11-19: received
See all versions
Short URL
https://ia.cr/2006/420
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.