The invention discloses a construction method of a strong anti-collision chameleon
hash function, which comprises the following steps of S1, inputting a
security parameter n, and generating public andprivate key pairs (PK, SK) by a
system, the public key PK being capable of specifying a message space M, a random space R and a chameleon
hash function range Y; and S2, inputting the public key PK generated by the KGen and a message m Epsilon M, Hash
algorithm outputting Hash y Epsilon Y and random r Epsilon R; and S3, inputting a public key PK, and outputting b belongs to {0, 1} through a Hash Epsilon Y of the message m Epsilon M and a random vector r Epsilon R check
algorithm, if b = 1, then (y, r) is a valid hash of the message m, otherwise is invalid; and S4, inputting a private key SK, amessage m Epsilon M and a corresponding Hash random pair (y, r), and a new message m' Epsilon M to output a random vector r' satisfying HCheck (PK, m', y, r ') = 1. The invention also discloses a
verification method of the strong anti-collision chameleon
hash function. The method can
resist strong anti-collision attacks and can be well applied to the scene of a high-security chameleon hash function.