Cryptology ePrint Archive: Report 2013/246

A Lever Function to a New Codomain with Adequate Indeterminacy

Shenghui Su and Maozhi Xu and Shuwang Lu

Abstract: The key transforms of the REESSE1+ cryptosystem is Ci = (Ai * W ^ l(i)) ^ d (% M) with l(i) in O = {5, 7, …, 2n + 3} for i = 1, …, n, where l(i) is called a lever function. In this paper, the authors give a new codomain O± from {±5, …, ±(n + 4)} and subjected to x + y != 0 for any x, y in O±, where “±x” means the coexistence of “+x” and “-x”, which indicates that O± is indeterminate. Then, discuss the necessity and sufficiency of l(.) to W± for resisting continued fraction attack (CFA), prove indeterminacy and other properties of l(.) to O±, illustrate the ineffectualness of CFA by using two examples which show that some conditions are only necessary but not sufficient for the counteraction of powers of W and W ^ -1 even though O± = {5, …, n + 4} is selected and known, analyze the time complexities of CFA and root finding attack with guess, and expound a relation between a lever function and a random oracle. Our research manifests that l(.) to W± makes it generally impossible to extract a private key from a flat public key Ci = Ai * W ^ l(i)(% M) for i = 1, …, n in polynomial time.

Category / Keywords: public-key cryptography / Public key cryptosystem; Coprime sequence; Lever function; Continued fraction attack; Random oracle

Date: received 1 May 2013

Contact author: sheenway at 126 com

Available formats: PDF | BibTeX Citation

Version: 20130503:082651 (All versions of this report)

Discussion forum: Show discussion | Start new discussion