一种高效的基于Fiat-Shamir认证协议的陷门哈希函数(英文)

An efficient trapdoor hash function based on the Fiat-Shamir identification scheme

陷门哈希函数在2000年由Krawczyk和Rabin正式描述.它是一种带有陷门密钥的哈希函数.陷门密钥的作用在于寻找函数的"碰撞".陷门哈希函数是构造变色龙签名协议和在线/离线签名协议的关键构件.现有的陷门哈希函数在计算函数值或者在寻找碰撞的运算中,均为指数运算复杂度.基于Fiat-Shamir认证协议,文章构造了一种新的陷门哈希函数.新的构造具有乘法运算复杂度,因此,大大提高了陷门哈希函数的效率.

The notion of trapdoor hash function was first formalized in 2000 by Krawczyk and Rabin. It is a type of hash function with a trapdoor key which can be used to find collisions of the function ＇ s input. The trapdoor hash function is an essential component to construct chameleon signatures and online/offline signatures. But all of them have exponential complexity either in computing the values of hash functions or in finding collisions of hash functions. Based on the Fiat-Shamir identification scheme, we propose a new construction of trapdoor hash function, which has multiplicative complexity. Therefore, our new construction highly improves the efficiency of trapdoor hash functions.