1. bookVolume 2021 (2021): Issue 4 (October 2021)
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
access type Open Access

Mercurial Signatures for Variable-Length Messages

Published Online: 23 Jul 2021
Page range: 441 - 463
Received: 28 Feb 2021
Accepted: 16 Jun 2021
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
Abstract

Mercurial signatures are a useful building block for privacy-preserving schemes, such as anonymous credentials, delegatable anonymous credentials, and related applications. They allow a signature σ on a message m under a public key pk to be transformed into a signature σ′ on an equivalent message m′ under an equivalent public key pk′ for an appropriate notion of equivalence. For example, pk and pk′ may be unlinkable pseudonyms of the same user, and m and m′ may be unlinkable pseudonyms of a user to whom some capability is delegated. The only previously known construction of mercurial signatures suffers a severe limitation: in order to sign messages of length , the signer’s public key must also be of length . In this paper, we eliminate this restriction and provide an interactive signing protocol that admits messages of any length. We prove our scheme existentially unforgeable under chosen open message attacks (EUF-CoMA) under a variant of the asymmetric bilinear decisional Diffie-Hellman assumption (ABDDH).

Keywords

[1] M. Backes, L. Hanzlik, K. Kluczniak, and J. Schneider. Signatures with flexible public key: Introducing equivalence classes for public keys. In T. Peyrin and S. D. Galbraith, editors, ASIACRYPT 2018, Brisbane, QLD, Australia, December 2-6, 2018, Part II, volume 11273 of LNCS, pages 405–434. Springer, 2018. Search in Google Scholar

[2] M. Belenkiy, J. Camenisch, M. Chase, M. Kohlweiss, A. Lysyanskaya, and H. Shacham. Randomizable proofs and delegatable anonymous credentials. In S. Halevi, editor, CRYPTO 2009, Santa Barbara, CA, USA, August 16-20, 2009, volume 5677, pages 108–125. Springer, 2009. Search in Google Scholar

[3] D. Bernhard, M. Fischlin, and B. Warinschi. Adaptive proofs of knowledge in the random oracle model. In J. Katz, editor, PKC 2015, Gaithersburg, MD, USA, March 30 - April 1, 2015, volume 9020 of LNCS, pages 629–649. Springer, 2015. Search in Google Scholar

[4] E. F. Brickell, J. Camenisch, and L. Chen. Direct anonymous attestation. In V. Atluri, B. Pfitzmann, and P. D. McDaniel, editors, CCS 2004, Washington, DC, USA, October 25-29, 2004, pages 132–145. ACM, 2004. Search in Google Scholar

[5] J. Camenisch, M. Dubovitskaya, K. Haralambiev, and M. Kohlweiss. Composable and modular anonymous credentials: Definitions and practical constructions. In T. Iwata and J. H. Cheon, editors, ASIACRYPT 2015, Auckland, New Zealand, November 29 - December 3, 2015, Part II, volume 9453 of LNCS, pages 262–288. Springer, 2015. Search in Google Scholar

[6] J. Camenisch, S. Krenn, A. Lehmann, G. L. Mikkelsen, G. Neven, and M. Ø. Pedersen. Formal treatment of privacy-enhancing credential systems. IACR Cryptol. ePrint Arch., 2014:708, 2014. Search in Google Scholar

[7] J. Camenisch and A. Lysyanskaya. An efficient system for non-transferable anonymous credentials with optional anonymity revocation. In B. Pfitzmann, editor, EUROCRYPT 2001, Innsbruck, Austria, May 6-10, 2001, Proceeding, volume 2045 of LNCS, pages 93–118. Springer, 2001. Search in Google Scholar

[8] J. Camenisch and A. Lysyanskaya. Signature schemes and anonymous credentials from bilinear maps. In M. K. Franklin, editor, CRYPTO 2004, Santa Barbara, California, USA, August 15-19, 2004, volume 3152 of LNCS, pages 56–72. Springer, 2004. Search in Google Scholar

[9] J. Camenisch and M. Michels. Proving in zero-knowledge that a number is the product of two safe primes. In J. Stern, editor, Advances in Cryptology - EUROCRYPT 1999, Prague, Czech Republic, May 2-6, 1999, volume 1592 of LNCS, pages 107–122. Springer, 1999. Search in Google Scholar

[10] J. Camenisch and V. Shoup. Practical verifiable encryption and decryption of discrete logarithms. In D. Boneh, editor, CRYPTO 2003, Santa Barbara, California, USA, August 17-21, 2003, volume 2729 of LNCS, pages 126–144. Springer, 2003. Search in Google Scholar

[11] R. Canetti. Universally composable security: A new paradigm for cryptographic protocols. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pages 136–145. IEEE Computer Society, 2001. Search in Google Scholar

[12] M. Chase, M. Kohlweiss, A. Lysyanskaya, and S. Meiklejohn. Malleable signatures: Complex unary transformations and delegatable anonymous credentials. IACR Cryptol. ePrint Arch., 2013:179, 2013. Search in Google Scholar

[13] M. Chase and A. Lysyanskaya. On signatures of knowledge. In C. Dwork, editor, CRYPTO 2006, California, USA, August 20-24, 2006, volume 4117 of LNCS, pages 78–96. Springer, 2006. Search in Google Scholar

[14] D. Chaum. Showing credentials without identification: Signatures transferred between unconditionally unlinkable pseudonyms. In F. Pichler, editor, EUROCRYPT ’85, Linz, Austria, April 1985, volume 219 of LNCS, pages 241–244. Springer, 1985. Search in Google Scholar

[15] E. C. Crites and A. Lysyanskaya. Delegatable anonymous credentials from mercurial signatures. In M. Matsui, editor, CT-RSA 2019, San Francisco, CA, USA, March 4-8, 2019, volume 11405 of LNCS, pages 535–555. Springer, 2019. Search in Google Scholar

[16] I. Damgård. On sigma-protocols, 2002. Search in Google Scholar

[17] Y. Dodis, V. Shoup, and S. Walfish. Efficient constructions of composable commitments and zero-knowledge proofs. In D. A. Wagner, editor, CRYPTO 2008, Santa Barbara, CA, USA, August 17-21, 2008., volume 5157 of LNCS, pages 515–535. Springer, 2008. Search in Google Scholar

[18] A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. In A. M. Odlyzko, editor, Advances in Cryptology - CRYPTO ’86, Santa Barbara, California, USA, 1986, volume 263 of LNCS, pages 186–194. Springer, 1986. Search in Google Scholar

[19] M. Fischlin. Communication-efficient non-interactive proofs of knowledge with online extractors. In V. Shoup, editor, CRYPTO 2005, Santa Barbara, California, USA, August 14-18, 2005, volume 3621 of LNCS, pages 152–168. Springer, 2005. Search in Google Scholar

[20] G. Fuchsbauer and R. Gay. Weakly secure equivalence-class signatures from standard assumptions. In M. Abdalla and R. Dahab, editors, PKC 2018, Rio de Janeiro, Brazil, March 25-29, 2018, Part II, volume 10770 of LNCS, pages 153–183. Springer, 2018. Search in Google Scholar

[21] G. Fuchsbauer, C. Hanser, C. Kamath, and D. Slamanig. Practical round-optimal blind signatures in the standard model from weaker assumptions. In V. Zikas and R. D. Prisco, editors, SCN 2016, Amalfi, Italy, August 31 -September 2, 2016, volume 9841 of LNCS, pages 391–408. Springer, 2016. Search in Google Scholar

[22] G. Fuchsbauer, C. Hanser, and D. Slamanig. Structure-preserving signatures on equivalence classes and constantsize anonymous credentials. J. Cryptol., 32(2):498–546, 2019. Search in Google Scholar

[23] J. Groth and A. Sahai. Efficient non-interactive proof systems for bilinear groups. In N. P. Smart, editor, Advances in Cryptology - EUROCRYPT 2008, Istanbul, Turkey, April 13-17, 2008, volume 4965 of LNCS, pages 415–432. Springer, 2008. Search in Google Scholar

[24] A. Lysyanskaya. Signature schemes and applications to cryptographic protocol design. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA, 2002. Search in Google Scholar

[25] A. Lysyanskaya, R. L. Rivest, A. Sahai, and S. Wolf. Pseudonym systems. In H. M. Heys and C. M. Adams, editors, SAC 1999, Kingston, Ontario, Canada, August 9-10, 1999, volume 1758 of LNCS, pages 184–199. Springer, 1999. Search in Google Scholar

[26] S. Meiklejohn, C. C. Erway, A. Küpçü, T. Hinkle, and A. Lysyanskaya. ZKPDL: A language-based system for efficient zero-knowledge proofs and electronic cash. In 19th USENIX Security Symposium, Washington, DC, USA, August 11-13, 2010, pages 193–206. USENIX Association, 2010. Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo