弱规则单向函数及其应用

单向函数的存在性是密码学的最基本假设,也是绝大多数对称密码学算法的充分必要条件.作为一个计算复杂性问题,单向函数可以用来构造伪随机产生器进而构成流密码算法,或是在伪随机产生器的基础上进一步构造伪随机函数和伪随机置换从而用作分组加密算法.规则单向函数是一类具有特殊结构的单向函数,该函数的每个像都有相同个数的原像.基于单向函数的密码学组件(如伪随机产生器)构造研究主要有两种思路:一是从任意单向函数出发来设计组件,其优点是具有通用性,不需要使用单向函数的特有结构;另一种是从具有特定结构的单向函数(比如单向置换、规则单向函数等)出发来设计组件,其优点是构造出来的密码学组件效率较高(比如种子长度更短、单向函数调用次数更少等).学界一直感兴趣于怎样在两者之间取得折中:即寻找既能够适用于范围更广的单向函数、又具有高效性的构造方法.本文提出了弱规则单向函数的概念,规则单向函数仅是弱规则单向函数的一种特殊情况.如果一个函数不是弱规则函数的话,那么这种反例的构造需要人工刻意设计.本文进一步通过具体构造说明,基于规则单向函数的密码学组件构造(伪随机产生器)可以推广至基于弱规则单向函数的情况.与HILL型产生器相比,基于弱规则单向函数的伪随机产生器构造兼具种子长度更短和保持安全性的优点.基于弱规则单向函数的通用单向哈希函数构造则推广了学界基于未知规则单向函数构造的研究工作,具有密钥长度为O(nlogn)、输出长度为Θ(n)的特点.