Provably Secure Code-Based Signature Schemes via Fiat-Shamir Transform with Theoretical and Practical Analysis on Hash Encodings

摘要

In this paper, we propose signature schemes constructed from code-based identification scheme proposed by Stern via Fiat-Shamir transform. In Fiat-Shamir transform, the "challenge" part of the identification is substituted with the output of hash function. However, our observation reveals that the "challenge" part of Stern's identification scheme is taken from the set of {0,1,2}, while all standard hash functions, e.g., SHA-1, SHA-256, outputs a sequence of bits or values in {0,1}. We define two explicit different encodings of the hash function's outputs into the "challenge" part and based on them, we build two different constructions of signature schemes. We discover that these encodings are not Only giving impacts on the implementation cost in practical side, but also giving non-negligible amount of impacts on the security parameter for achieving provable security in theoretical side. As a rough illustration, letting e denote the success probability of breaking decisional version of syndrome decoding problem and r be the number of rounds required to guarantee the soundness of identification scheme, we show that one type of encoding gives a scheme with probability of successful signing half and adversary's success probability approximately upper bounded by ε+(2/3)~r, while the other one gives a scheme with probability of successful signing one and adversary's success probability approximately upper bounded by ε + (3/4)~r.