Paper 2013/246

A Lever Function to a New Codomain with Adequate Indeterminacy

Shenghui Su and Maozhi Xu and Shuwang Lv

Abstract

The key transform 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 simplified transform Ci = Ai * W^l(i) (% M) and a new lever function l(i) from {1, …, n} toO+- = {+/-5, …, +/-(n + 4)}, where “+/-” means the selection of the “+” or “-” sign, and discuss the necessity of the new ℓ(i) that a simplified private key is insecure if l(i) is only some fixed integer and the sufficiency that a simplified private key is secure at present if l(i) is a one-to-one function. The sufficiency is expounded from four aspects: indeterminacy of the new l(i), every condition for the counteraction of powers of W and W^-1 being only necessary with even O+- = {5, …, n + 4}, verification by examples, and running times of continued fraction attack and parameter intersection attack which are two most efficient algorithms so far but not determinate polynomial time ones. Last, elaborate a relation between a lever function and a random oracle.

Note: The content has no essential change.