有界单向函数的通用求逆算法研究(英文)

Universal Inverting Algorithms for Bounded One-Way Functions

有界单向函数是一个新的密码学概念.有界单向函数是为了研究设计更为灵活、更实用的密码系统的基础而提出的.该文的作者在以前的文章中,对有界单向函数与一般单向函数的关系进行了探讨,从而得到一般单向函数的一个刻画.由于单向函数的存在性与计算机科学中一系列重要未决的问题相联系,其本身的存在性是一个未决的问题.有界单向函数的研究对一般单向函数存在性的研究提供了一个新的途径.从它们之间的关系来看,如果对任意正整数c,存在c-单向函数,那么一定存在单向函数.鉴于现代密码学对单向函数的依赖性,对单向函数的存在性的研究具有重要的意义.该文进一步探讨有界单向函数的困难性.由于单向函数的存在性被规约到了有界单向函数的存在性,该文章着眼于固定的有界单向函数的研究.文中的主要结果是:对任意正整数c,存在一个被称为关于所有c-有界单向函数的通用c-有界算法,满足对于充分大的n,这个算法求逆的成功概率是所有c-有界算法求逆的成功概率的上界.从而给出了一个关于c-单向函数的刻画.

Bounded one-way function is a new cryptographic primitive proposed for the foundation of practical cryptography. The relation between general one-way function and bounded oneway function is given by authors previously. The existence of one-way function is an open problem, which is related to some important open problems in computer science, such as NP problem. Bounded one-way function gives a new insight in the one-way function. From the relation between bounded and general one-way function, it is clear that if there exists a c-bounded one-way function for any positive integer c, then there exists a one-way function. While modern cryptography theory depends on the existence of one-way function, it is deserved continuing to investi gate the hardness of one-way function. The authors explore, in this paper, the hardness of bounded one-way functions. The authors concentrate ourselves to the c-bounded one-way function for a fixed integer c. The main result in this paper is that for any integer c〉0, there exists an algorithm of c-bounded called universal algorithm for all c-bounded one-way functions, such that, its success probability bounds up success probability of any inverting algorithm of c-bounded for sufficient large n. This is a uniform bound for c-bounded inverters, and hence a characterization for c-bounded one-way func tions.