Tightly-Secure Signatures from Five-Move Identification Protocols
We carry out a concrete security analysis of signature schemes obtained from five-move identification protocols via the Fiat-Shamir transform. Concretely, we obtain tightly-secure signatures based on the computational Diffie-Hellman (CDH), the short-expon
- PDF / 513,336 Bytes
- 27 Pages / 439.37 x 666.142 pts Page_size
- 102 Downloads / 181 Views
2
Ruhr-Universit¨ at Bochum, Bochum, Germany {eike.kiltz,julian.loss}@rub.de Karlsruher Institut f¨ ur Technologie, Karlsruhe, Germany [email protected]
Abstract. We carry out a concrete security analysis of signature schemes obtained from five-move identification protocols via the FiatShamir transform. Concretely, we obtain tightly-secure signatures based on the computational Diffie-Hellman (CDH), the short-exponent CDH, and the Factoring (FAC) assumptions. All our signature schemes have tight reductions to search problems, which is in stark contrast to all known signature schemes obtained from the classical Fiat-Shamir transform (based on three-move identification protocols), which either have a non-tight reduction to a search problem, or a tight reduction to a (potentially) stronger decisional problem. Surprisingly, our CDH-based scheme turns out to be (a slight simplification of) the Chevallier-Mames signature scheme (CRYPTO 05), thereby providing a theoretical explanation of its tight security proof via five-move identification protocols.
Keywords: Signatures Fiat-Shamir · Tightness
1
·
Five-move
identification
protocols
·
Introduction
The security of public-key cryptographic primitives is commonly analyzed via a security reduction to a suitable cryptographic assumption (such as the factoring assumption). Concretely, a security reduction converts a successful adversary A against the cryptographic scheme’s security into a successful solver B against the hardness of the underlying assumption. If the reduction provides the bound εA ≤ L · εB (where εA is A’s success probability and εB is B’s success probability) then L is called the (multiplicative) security loss of the reduction.1 Clearly, it is desirable to have the security loss L as small as a constant so that εA ≈ εB . If furthermore the running times of A and B are approximately the same, then
1
E. Kiltz was partially supported by ERC Project ERCC (FP7/615074) and by DFG SPP 1736 Big Data. J. Loss was supported by ERC Project ERCC (FP7/615074). J. Pan was supported by the DFG grant HO 4534/4-1. We ignore the additive negligible terms to simplify our discussion.
c International Association for Cryptologic Research 2017 T. Takagi and T. Peyrin (Eds.): ASIACRYPT 2017, Part III, LNCS 10626, pp. 68–94, 2017. https://doi.org/10.1007/978-3-319-70700-6_3
Tightly-Secure Signatures from Five-Move Identification Protocols
69
the reduction is said to be tight. Cryptographic schemes with tight reductions recently drew a large amount of attention (e.g., [4,12,13,18,29–31]) due to the fact that tightly-secure schemes do not need to compensate for the security loss with increased parameters. Digital signature schemes are one of the most important public-key cryptographic primitives. They have numerous applications and often serve as a building block for advanced cryptographic protocols. Ideally, we desire to have signature schemes with short signature sizes, efficient signing and verification algorithms, and tight security based on weak, well studied assumptions. Ti
Data Loading...
