Multisignatures secure under the discrete logarithm assumption and a generalized forking lemma

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.

REFERENCES

• 1: Ali Bagherzandi , Stanisław Jarecki, Multisignatures Using Proofs of Secret Key Possession, as Secure as the Diffie-Hellman Problem, Proceedings of the 6th international conference on Security and Cryptography for Networks, September 10-12, 2008, Amalfi, Italy [doi>10.1007/978-3-540-85855-3_15]
• 2: M. Bellare, C. Namprempre, and G. Neven. Unrestricted aggregate signatures. Cryptology ePrint Archive, 2006/285.
• 3: Mihir Bellare , Gregory Neven, Multi-signatures in the plain public-Key model and a general forking lemma, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180453]
• 4: D. Boneh, C. Gentry, B. Lynn, and H. Shacham. Aggregate and verifiably encrypted signature from bilinear maps. In Eurocrypt'03.
• 5: Dan Boneh , Ben Lynn , Hovav Shacham, Short Signatures from the Weil Pairing, Journal of Cryptology, v.17 n.4, p.297-319, September 2004 [doi>10.1007/s00145-004-0314-9]
• 6: Claude Castelluccia , Stanisław Jarecki , Jihye Kim , Gene Tsudik, Secure acknowledgment aggregation and multisignatures with limited robustness, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.10, p.1639-1652, 14 July 2006 [doi>10.1016/j.comnet.2005.09.021]
• 7: I. Damgård. Efficient concurrent zero-knowledge in the auxiliary string model. In Eurocrypt'00.
• 8: A. DeSantis and G. Persiano. Zero knowledge proofs of knowledge without interaction. In FOCS'92.
• 9: M. Fischlin. Communication-efficient non-interactive proofs of knowledge with online extractors. In Crypto'05.
• 10: J. Groth. Evaluating security of voting schemes in the universal composability framework. Cryptology ePrint Archive, 2002/002.
• 11: Jihye Kim , Gene Tsudik, SRDP: Securing Route Discovery in DSR, Proceedings of the The Second Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, p.247-260, July 17-21, 2005 [doi>10.1109/MOBIQUITOUS.2005.54]
• 12: Silvio Micali , Kazuo Ohta , Leonid Reyzin, Accountable-subgroup multisignatures: extended abstract, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502017]
• 13: Torben P. Pedersen, Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.129-140, August 11-15, 1991
• 14: D. Pointcheval and J. Stern. Security arguments for digital signatures and blind signatures. J. Cryptology, 13(3):361--396, 2000.
• 15: Thomas Ristenpart , Scott Yilek, The Power of Proofs-of-Possession: Securing Multiparty Signatures against Rogue-Key Attacks, Proceedings of the 26th annual international conference on Advances in Cryptology, p.228-245, May 20-24, 2007, Barcelona, Spain [doi>10.1007/978-3-540-72540-4_13]
• 16: Claus-Peter Schnorr, Efficient Identification and Signatures for Smart Cards, Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.239-252, August 20-24, 1989
• 17: V. Shoup and R. Gennaro. Securing threshold cryptosystems against chosen ciphertext attack. J. Cryptology, 15(2):75--96, 2002.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Distributed data structures

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

General Terms:
Algorithms, Reliability, Security

Keywords:
concurrent proofs of knowledge, equiocable homomorphic commitment, forking lemma, multisignatures