The Fiat-Shamir Zoo : Relating the Security of Different Signature Variants
(2018) 23rd Nordic Conference on Secure IT Systems, NordSec 2018 In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 11252 LNCS. p.154-170- Abstract
The Fiat-Shamir paradigm encompasses many different ways of turning a given identification scheme into a signature scheme. Security proofs pertain sometimes to one variant, sometimes to another. We systematically study three variants that we call the challenge (signature is challenge and response), commit (signature is commitment and response), and transcript (signature is challenge, commitment and response) variants. Our framework captures the variants via transforms that determine the signature scheme as a function of not only the identification scheme and hash function (to cover both standard and random oracle model hashing), but also what we call a signing algorithm, to cover both classical and with-abort signing. We relate the... (More)
The Fiat-Shamir paradigm encompasses many different ways of turning a given identification scheme into a signature scheme. Security proofs pertain sometimes to one variant, sometimes to another. We systematically study three variants that we call the challenge (signature is challenge and response), commit (signature is commitment and response), and transcript (signature is challenge, commitment and response) variants. Our framework captures the variants via transforms that determine the signature scheme as a function of not only the identification scheme and hash function (to cover both standard and random oracle model hashing), but also what we call a signing algorithm, to cover both classical and with-abort signing. We relate the security of the signature schemes produced by these transforms, giving minimal conditions under which uf-security of one transfers to the other. To apply this comprehensively, we formalize linear identification schemes, show that many schemes in the literature are linear, and show that any linear scheme meets our conditions for the signature schemes given by the three transforms to have equivalent uf-security. Our results give a comprehensive picture of the Fiat-Shamir zoo and allow proofs of security in the literature to be transferred automatically from one variant to another.
(Less)
- author
- Backendal, Matilda ; Bellare, Mihir ; Sorrell, Jessica and Sun, Jiahao
- publishing date
- 2018
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- Secure IT Systems - 23rd Nordic Conference, NordSec 2018, Proceedings
- series title
- Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
- editor
- Gruschka, Nils
- volume
- 11252 LNCS
- pages
- 154 - 170
- publisher
- Springer
- conference name
- 23rd Nordic Conference on Secure IT Systems, NordSec 2018
- conference location
- Oslo, Norway
- conference dates
- 2018-11-28 - 2018-11-30
- external identifiers
-
- scopus:85057413876
- ISSN
- 1611-3349
- 0302-9743
- ISBN
- 9783030036379
- DOI
- 10.1007/978-3-030-03638-6_10
- language
- English
- LU publication?
- no
- id
- 308e68e1-363a-45b8-aeb3-2c82973642fd
- date added to LUP
- 2018-12-20 13:48:09
- date last changed
- 2024-03-18 21:52:57
@inproceedings{308e68e1-363a-45b8-aeb3-2c82973642fd,
abstract = {{<p>The Fiat-Shamir paradigm encompasses many different ways of turning a given identification scheme into a signature scheme. Security proofs pertain sometimes to one variant, sometimes to another. We systematically study three variants that we call the challenge (signature is challenge and response), commit (signature is commitment and response), and transcript (signature is challenge, commitment and response) variants. Our framework captures the variants via transforms that determine the signature scheme as a function of not only the identification scheme and hash function (to cover both standard and random oracle model hashing), but also what we call a signing algorithm, to cover both classical and with-abort signing. We relate the security of the signature schemes produced by these transforms, giving minimal conditions under which uf-security of one transfers to the other. To apply this comprehensively, we formalize linear identification schemes, show that many schemes in the literature are linear, and show that any linear scheme meets our conditions for the signature schemes given by the three transforms to have equivalent uf-security. Our results give a comprehensive picture of the Fiat-Shamir zoo and allow proofs of security in the literature to be transferred automatically from one variant to another.</p>}},
author = {{Backendal, Matilda and Bellare, Mihir and Sorrell, Jessica and Sun, Jiahao}},
booktitle = {{Secure IT Systems - 23rd Nordic Conference, NordSec 2018, Proceedings}},
editor = {{Gruschka, Nils}},
isbn = {{9783030036379}},
issn = {{1611-3349}},
language = {{eng}},
pages = {{154--170}},
publisher = {{Springer}},
series = {{Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)}},
title = {{The Fiat-Shamir Zoo : Relating the Security of Different Signature Variants}},
url = {{http://dx.doi.org/10.1007/978-3-030-03638-6_10}},
doi = {{10.1007/978-3-030-03638-6_10}},
volume = {{11252 LNCS}},
year = {{2018}},
}