Ali Bagherzandi
ABSTRACT
Multisignatures allow n signers to produce a short joint signature on a single message. Multisignatures were achieved in the plain model with a non-interactive protocol in groups with bilinear maps, by Boneh et al, and by a three-round protocol under the Discrete Logarithm (DL) assumption, by Bellare and Neven, with multisignature verification cost of, respectively, O(n) pairings or exponentiations. In addition, multisignatures with O(1) verification were shown in so-called Key Verification (KV) model, where each public key is accompanied by a short proof of well-formedness, again either with a non-interactive protocol using bilinear maps, by Ristenpart and Yilek, or with a three-round protocol under the Diffie-Hellman assumption, by Bagherzandi and Jarecki.
We improve on these results in two ways: First, we show a two-round O(n)-verification multisignature secure under the DL assumption in the plain model, improving on the three-round protocol of Bellare-Neven. Second, we show a two-round O(1)-verification multisignature secure under the DL assumption in the KV model, improving on assumptions and/or communication rounds of the schemes of Ristenpart and Yilek and Bagherzandi and Jarecki. Exact security of both schemes matches (in ROM) that of Schnorr signatures. The reduced round complexity is due to a new multiplicatively homomorphic equivocable commitment scheme which can be of independent interest. Moreover, our KV model scheme is enabled by a generalized forking lemma, which shows that standard non-interactive zero-knowledge (NIZK) proofs of knowledge in ROM admit efficient simultaneous post-execution extraction of witnesses of all proof instances. As a consequence of this lemma, any DL-based multisignature secure in so-called Knowledge-of-Secret-Key model can be implemented in the KV model using standard ROM-based NIZK's of DL as proofs of key well-formedness.
- A. Bagherzandi and S. Jarecki. Multisignatures using proofs of secret key possession, as secure as the Diffie-Hellman problem. In SCN'08. Google Scholar
Digital Library
- M. Bellare, C. Namprempre, and G. Neven. Unrestricted aggregate signatures. Cryptology ePrint Archive, 2006/285.Google Scholar
- M. Bellare and G. Neven. Mult-signatures in the plain public-key model and a general forking lemma. In ACM CCS'06. Google ScholarDigital Library
- D. Boneh, C. Gentry, B. Lynn, and H. Shacham. Aggregate and verifiably encrypted signature from bilinear maps. In Eurocrypt'03.Google Scholar
- D. Boneh, B. Lynn, and H. Shacham. Short signatures from Weil pairing. J. Cryptology, 17(4):297--319, 2004. Google ScholarDigital Library
- C. Castelluccia, S. Jarecki, J. Kim, and G. Tsudik. Secure acknowledgment aggregation and multisignatures with limited robustness. Computer Networks, 50(10):1639--1652, 2006. Google ScholarDigital Library
- I. Damgård. Efficient concurrent zero-knowledge in the auxiliary string model. In Eurocrypt'00.Google Scholar
- A. DeSantis and G. Persiano. Zero knowledge proofs of knowledge without interaction. In FOCS'92.Google Scholar
- M. Fischlin. Communication-efficient non-interactive proofs of knowledge with online extractors. In Crypto'05.Google Scholar
- J. Groth. Evaluating security of voting schemes in the universal composability framework. Cryptology ePrint Archive, 2002/002.Google Scholar
- J. Kim and G. Tsudik. SRDP: Securing route discovery in DSR. In MobiQuitous, pages 247--260, 2005. Google ScholarDigital Library
- S. Micali, K. Ohta, and L. Reyzin. Accountable subgroup multisignatures. In ACM CCS'01. Google ScholarDigital Library
- T.P. Pedersen. Non-interactive and information theoretic secure verifiable secret sharing. In Crypto'91. Google ScholarDigital Library
- D. Pointcheval and J. Stern. Security arguments for digital signatures and blind signatures. J. Cryptology, 13(3):361--396, 2000.Google ScholarDigital Library
- T. Ristenpart and S. Yilek. The power of proofs of possession: Securing multiparty signatures against rogue-key attacks. In Eurocrypt'07. Google ScholarDigital Library
- C. Schnorr. Efficient identification and signatures for smart cards. In Crypto'89. Google ScholarDigital Library
- V. Shoup and R. Gennaro. Securing threshold cryptosystems against chosen ciphertext attack. J. Cryptology, 15(2):75--96, 2002.Google ScholarDigital Library
Index Terms
- Multisignatures secure under the discrete logarithm assumption and a generalized forking lemma
Recommendations
Multi-signatures in the plain public-Key model and a general forking lemma
CCS '06: Proceedings of the 13th ACM conference on Computer and communications securityA multi-signature scheme enables a group of signers to produce a compact, joint signature on a common document, and has many potential uses. However, existing schemes impose key setup or PKI requirements that make them impractical, such as requiring a ...
Accountable-subgroup multisignatures: extended abstract
CCS '01: Proceedings of the 8th ACM conference on Computer and Communications SecurityFormal models and security proofs are especially important for multisignatures: in contrast to threshold signatures, no precise definitions were ever provided for such schemes, and some proposals were subsequently broken.In this paper, we formalize and ...
Tightly Secure Non-Interactive Multisignatures in the Plain Public Key Model
Multisignature scheme allows a group of signers to generate a compact signature on a common document that certifies they endorsed the message. However, the existing state of the art multisignatures often suffers from the following problems: impractical ...
Comments