Count Me In! Extendability for Threshold Ring Signatures
Aranha, Diego F. ; Hall-Andersen, Mathias ; Nitulescu, Anca ; Pagnin, Elena LU
and Yakoubov, Sophia
(2022)
25th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2022
In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
13178.
p.379-406
- Abstract
Ring signatures enable a signer to sign a message on behalf of a group anonymously, without revealing her identity. Similarly, threshold ring signatures allow several signers to sign the same message on behalf of a group; while the combined signature reveals that some threshold t of the group members signed the message, it does not leak anything else about the signers’ identities. Anonymity is a central feature in threshold ring signature applications, such as whistleblowing, e-voting and privacy-preserving cryptocurrencies: it is often crucial for signers to remain anonymous even from their fellow signers. When the generation of a signature requires interaction, this is difficult to achieve. There exist threshold ring signatures with... (More)
Ring signatures enable a signer to sign a message on behalf of a group anonymously, without revealing her identity. Similarly, threshold ring signatures allow several signers to sign the same message on behalf of a group; while the combined signature reveals that some threshold t of the group members signed the message, it does not leak anything else about the signers’ identities. Anonymity is a central feature in threshold ring signature applications, such as whistleblowing, e-voting and privacy-preserving cryptocurrencies: it is often crucial for signers to remain anonymous even from their fellow signers. When the generation of a signature requires interaction, this is difficult to achieve. There exist threshold ring signatures with non-interactive signing—where signers locally produce partial signatures which can then be aggregated—but a limitation of existing threshold ring signature constructions is that all of the signers must agree on the group on whose behalf they are signing, which implicitly assumes some coordination amongst them. The need to agree on a group before generating a signature also prevents others—from outside that group—from endorsing a message by adding their signature to the statement post-factum. We overcome this limitation by introducing extendability for ring signatures, same-message linkable ring signatures, and threshold ring signatures. Extendability allows an untrusted third party to take a signature, and extend it by enlarging the anonymity set to a larger set. In the extendable threshold ring signature, two signatures on the same message which have been extended to the same anonymity set can then be combined into one signature with a higher threshold. This enhances signers’ anonymity, and enables new signers to anonymously support a statement already made by others. For each of those primitives, we formalize the syntax and provide a meaningful security model which includes different flavors of anonymous extendability. In addition, we present concrete realizations of each primitive and formally prove their security relying on signatures of knowledge and the hardness of the discrete logarithm problem. We also describe a generic transformation to obtain extendable threshold ring signatures from same-message-linkable extendable ring signatures. Finally, we implement and benchmark our constructions.
(Less)
- author
- Aranha, Diego F.
; Hall-Andersen, Mathias
; Nitulescu, Anca
; Pagnin, Elena
LU
and Yakoubov, Sophia
- organization
- publishing date
- 2022
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- Anonymity, Extendability, Threshold ring signatures
- host publication
- Public-Key Cryptography - PKC 2022 : 25th IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings, Part II - 25th IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings, Part II
- series title
- Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
- editor
- Hanaoka, Goichiro ; Shikata, Junji and Watanabe, Yohei
- volume
- 13178
- pages
- 28 pages
- publisher
- Springer
- conference name
- 25th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2022
- conference location
- Virtual, Online
- conference dates
- 2022-03-08 - 2022-03-11
- external identifiers
-
- scopus:85126236217
- ISSN
- 1611-3349
- 0302-9743
- ISBN
- 9783030971304
- 9783030971311
- DOI
- 10.1007/978-3-030-97131-1_13
- project
- Säkra mjukvaruuppdateringar för den smarta staden
- language
- English
- LU publication?
- yes
- additional info
- Publisher Copyright: © 2022, International Association for Cryptologic Research.
- id
- a5e38975-d984-411e-b190-5dc321fe60a0
- date added to LUP
- 2022-05-20 16:06:24
- date last changed
- 2024-07-11 15:27:11
@inproceedings{a5e38975-d984-411e-b190-5dc321fe60a0,
abstract = {{<p>Ring signatures enable a signer to sign a message on behalf of a group anonymously, without revealing her identity. Similarly, threshold ring signatures allow several signers to sign the same message on behalf of a group; while the combined signature reveals that some threshold t of the group members signed the message, it does not leak anything else about the signers’ identities. Anonymity is a central feature in threshold ring signature applications, such as whistleblowing, e-voting and privacy-preserving cryptocurrencies: it is often crucial for signers to remain anonymous even from their fellow signers. When the generation of a signature requires interaction, this is difficult to achieve. There exist threshold ring signatures with non-interactive signing—where signers locally produce partial signatures which can then be aggregated—but a limitation of existing threshold ring signature constructions is that all of the signers must agree on the group on whose behalf they are signing, which implicitly assumes some coordination amongst them. The need to agree on a group before generating a signature also prevents others—from outside that group—from endorsing a message by adding their signature to the statement post-factum. We overcome this limitation by introducing extendability for ring signatures, same-message linkable ring signatures, and threshold ring signatures. Extendability allows an untrusted third party to take a signature, and extend it by enlarging the anonymity set to a larger set. In the extendable threshold ring signature, two signatures on the same message which have been extended to the same anonymity set can then be combined into one signature with a higher threshold. This enhances signers’ anonymity, and enables new signers to anonymously support a statement already made by others. For each of those primitives, we formalize the syntax and provide a meaningful security model which includes different flavors of anonymous extendability. In addition, we present concrete realizations of each primitive and formally prove their security relying on signatures of knowledge and the hardness of the discrete logarithm problem. We also describe a generic transformation to obtain extendable threshold ring signatures from same-message-linkable extendable ring signatures. Finally, we implement and benchmark our constructions.</p>}},
author = {{Aranha, Diego F. and Hall-Andersen, Mathias and Nitulescu, Anca and Pagnin, Elena and Yakoubov, Sophia}},
booktitle = {{Public-Key Cryptography - PKC 2022 : 25th IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings, Part II}},
editor = {{Hanaoka, Goichiro and Shikata, Junji and Watanabe, Yohei}},
isbn = {{9783030971304}},
issn = {{1611-3349}},
keywords = {{Anonymity; Extendability; Threshold ring signatures}},
language = {{eng}},
pages = {{379--406}},
publisher = {{Springer}},
series = {{Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)}},
title = {{Count Me In! Extendability for Threshold Ring Signatures}},
url = {{http://dx.doi.org/10.1007/978-3-030-97131-1_13}},
doi = {{10.1007/978-3-030-97131-1_13}},
volume = {{13178}},
year = {{2022}},
}