Paper 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 with 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 O± 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 O± 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.

Note: The some words are revised.