弱规则单向函数及其应用  

Weakly Regular One-way Functions and Their Applications

作　　者：郁昱[1,2,3] 李祥学[4,3] 

机构地区：[1]上海交通大学计算机科学工程系,上海200240 [2]密码科学技术国家重点实验室,北京100878 [3]卫士通密码技术研究中心,北京100070 [4]华东师范大学计算机科学技术系,上海200241

出　　处：《密码学报》2016年第2期101-113,共13页Journal of Cryptologic Research

基　　金：国家自然科学基金项目(61472249;61572192;61572149;61571191);上海市科学技术委员会(13JC1403502;13JC1403500);陕西省国际科技合作与交流计划(2016KW-038)

摘　　要：单向函数的存在性是密码学的最基本假设,也是绝大多数对称密码学算法的充分必要条件.作为一个计算复杂性问题,单向函数可以用来构造伪随机产生器进而构成流密码算法,或是在伪随机产生器的基础上进一步构造伪随机函数和伪随机置换从而用作分组加密算法.规则单向函数是一类具有特殊结构的单向函数,该函数的每个像都有相同个数的原像.基于单向函数的密码学组件(如伪随机产生器)构造研究主要有两种思路:一是从任意单向函数出发来设计组件,其优点是具有通用性,不需要使用单向函数的特有结构;另一种是从具有特定结构的单向函数(比如单向置换、规则单向函数等)出发来设计组件,其优点是构造出来的密码学组件效率较高(比如种子长度更短、单向函数调用次数更少等).学界一直感兴趣于怎样在两者之间取得折中:即寻找既能够适用于范围更广的单向函数、又具有高效性的构造方法.本文提出了弱规则单向函数的概念,规则单向函数仅是弱规则单向函数的一种特殊情况.如果一个函数不是弱规则函数的话,那么这种反例的构造需要人工刻意设计.本文进一步通过具体构造说明,基于规则单向函数的密码学组件构造(伪随机产生器)可以推广至基于弱规则单向函数的情况.与HILL型产生器相比,基于弱规则单向函数的伪随机产生器构造兼具种子长度更短和保持安全性的优点.基于弱规则单向函数的通用单向哈希函数构造则推广了学界基于未知规则单向函数构造的研究工作,具有密钥长度为O(nlogn)、输出长度为Θ(n)的特点.The existence of one-way functions(OWFs)is one of the central results upon which modern cryptography is successfully founded.OWFs can be used to construct pseudorandom number generators(and thereby stream cipher)which can be further used to design pseudorandom functions and pseudorandom permutations(and thereby block cipher).Some OWFs are well structured,for instance,every image has the same number of preimages if the OWF is regular.There are two research lines in constructing cryptographic primitives(e.g.,pseudorandom generators,universal one-way hash functions)from one-way functions.One such research is to construct cryptographic primitives from any OWF,and its advantage is that no structure property of the underlying OWF is required in constructing the primitives.Another such of research focuses on more efficient(even nearly practical)constructions of cryptographic primitives from special structured OWFs(e.g.,one-way permutation,regular OWF,etc.),and its advantage is that improved(even optimal)parameters can be obtained(e.g.,shorter seed length,optimal calls to OWF,etc.).A challenging problem is whether we can construct some efficient(even security-preserving)primitives from a more general class of OWFs.This work introduces a more general class of OWFs called 'weakly-regular one-way functions',and regular OWFs fall into a special case.It shows that in order not to fall into weakly-regular functions,the counterexamples should be somewhat artificial.The approach that bases pseudorandom generators(PRGs)on regular OWFs can be generalized to the more general setting,and concrete PRG from weakly-regular OWFs can be much more seed-length efficient and security-preserving than the HILL-style generators.It is shown that constructing universal one-way hash function(with key length O(nlogn)and output length Θ(n))from weakly-regular OWF generalizes the state-of-the-art construction that requires an unknown-regular one-way function.

关 键 词：单向函数 规则单向函数 弱规则单向函数 伪随机产生器 通用单向哈希函数 

分 类 号：TN918.1[电子电信—通信与信息系统]