Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDesign and Analysis of the REESSE1+ Public Key Cryptosystem v2.21
164
0
0.0
(
0
)
Added by
Shenghui Su
Publication date
2007
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic 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 lgM = 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.
rate research
Read More
We illustrate through example 1 and 2 that the condition at theorem 1 in [8] dissatisfies necessity, and the converse proposition of fact 1.1 in [8] does not hold, namely the condition Z/M - L/Ak < 1/(2 Ak^2) is not sufficient for f(i) + f(j) = f(k). Illuminate through an analysis and ex.3 that there is a logic error during deduction of fact 1.2, which causes each of fact 1.2, 1.3, 4 to be invalid. Demonstrate through ex.4 and 5 that each or the combination of qu+1 > qu * D at fact 4 and table 1 at fact 2.2 is not sufficient for f(i) + f(j) = f(k), property 1, 2, 3, 4, 5 each are invalid, and alg.1 based on fact 4 and alg.2 based on table 1 are disordered and wrong logically. Further, manifest through a repeated experiment and ex.5 that the data at table 2 is falsified, and the example in [8] is woven elaborately. We explain why Cx = Ax * W^f(x) (% M) is changed to Cx = (Ax * W^f(x))^d (% M) in REESSE1+ v2.1. To the signature fraud, we point out that [8] misunderstands the existence of T^-1 and Q^-1 % (M-1), and forging of Q can be easily avoided through moving H. Therefore, the conclusion of [8] that REESSE1+ is not secure at all (which connotes that [8] can extract a related private key from any public key in REESSE1+) is fully incorrect, and as long as the parameter Omega is fitly selected, REESSE1+ with Cx = Ax * W^f(x) (% M) is secure.
This paper gives the definitions of an anomalous super-increasing sequence and an anomalous subset sum separately, proves the two properties of an anomalous super-increasing sequence, and proposes the REESSE2+ public-key encryption scheme which includes the three algorithms for key generation, encryption and decryption. The paper discusses the necessity and sufficiency of the lever function for preventing the Shamir extremum attack, analyzes the security of REESSE2+ against extracting a private key from a public key through the exhaustive search, recovering a plaintext from a ciphertext plus a knapsack of high density through the L3 lattice basis reduction method, and heuristically obtaining a plaintext through the meet-in-the-middle attack or the adaptive-chosen-ciphertext attack. The authors evaluate the time complexity of REESSE2+ encryption and decryption algorithms, compare REESSE2+ with ECC and NTRU, and find that the encryption speed of REESSE2+ is ten thousand times faster than ECC and NTRU bearing the equivalent security, and the decryption speed of REESSE2+ is roughly equivalent to ECC and NTRU respectively.
An important problem of modern cryptography concerns secret public-key computations in algebraic structures. We construct homomorphic cryptosystems being (secret) epimorphisms f:G --> H, where G, H are (publically known) groups and H is finite. A letter of a message to be encrypted is an element h element of H, while its encryption g element of G is such that f(g)=h. A homomorphic cryptosystem allows one to perform computations (operating in a group G) with encrypted information (without knowing the original message over H). In this paper certain homomorphic cryptosystems are constructed for the first time for non-abelian groups H (earlier, homomorphic cryptosystems were known only in the Abelian case). In fact, we present such a system for any solvable (fixed) group H.
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.
As distributed ledgers, blockchains run consensus protocols which trade capacity for consistency, especially in non-ideal networks with incomplete connectivity and erroneous links. Existing studies on the tradeoff between capacity and consistency are only qualitative or rely on specific assumptions. This paper presents discrete-time Markov chain models to quantify the capacity of Proof-of-Work based public blockchains in non-ideal networks. The comprehensive model is collapsed to be ergodic under the eventual consistency of blockchains, achieving tractability and efficient evaluations of blockchain capacity. A closed-form expression for the capacity is derived in the case of two miners. Another important aspect is that we extend the ergodic model to analyze the capacity under strong consistency, evaluating the robustness of blockchains against double-spending attacks. Validated by simulations, the proposed models are accurate and reveal the effect of link quality and the distribution of mining rates on blockchain capacity and the ratio of stale blocks.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
