{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T10:03:42Z","timestamp":1784541822730,"version":"3.55.0"},"reference-count":26,"publisher":"Privacy Enhancing Technologies Symposium Advisory Board","issue":"4","license":[{"start":{"date-parts":[[2021,7,23]],"date-time":"2021-07-23T00:00:00Z","timestamp":1626998400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,10,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>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 <jats:italic>\u03c3<\/jats:italic> on a message <jats:italic>m<\/jats:italic> under a public key pk to be transformed into a signature <jats:italic>\u03c3<\/jats:italic>\u2032 on an <jats:italic>equivalent<\/jats:italic> message <jats:italic>m<\/jats:italic>\u2032 under an equivalent public key pk\u2032 for an appropriate notion of equivalence. For example, pk and pk\u2032 may be unlinkable pseudonyms of the same user, and <jats:italic>m<\/jats:italic> and <jats:italic>m<\/jats:italic>\u2032 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 <jats:italic>\u2113<\/jats:italic>, the signer\u2019s public key must also be of length <jats:italic>\u2113<\/jats:italic>. 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).<\/jats:p>","DOI":"10.2478\/popets-2021-0079","type":"journal-article","created":{"date-parts":[[2021,7,24]],"date-time":"2021-07-24T23:19:34Z","timestamp":1627168774000},"page":"441-463","source":"Crossref","is-referenced-by-count":14,"title":["Mercurial Signatures for Variable-Length Messages"],"prefix":"10.56553","volume":"2021","author":[{"given":"Elizabeth C.","family":"Crites","sequence":"first","affiliation":[{"name":"IOHK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anna","family":"Lysyanskaya","sequence":"additional","affiliation":[{"name":"Brown University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"35752","published-online":{"date-parts":[[2021,7,23]]},"reference":[{"key":"2022051409231705591_j_popets-2021-0079_ref_001","doi-asserted-by":"crossref","unstructured":"[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\u2013434. Springer, 2018.10.1007\/978-3-030-03329-3_14","DOI":"10.1007\/978-3-030-03329-3_14"},{"key":"2022051409231705591_j_popets-2021-0079_ref_002","doi-asserted-by":"crossref","unstructured":"[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\u2013125. Springer, 2009.10.1007\/978-3-642-03356-8_7","DOI":"10.1007\/978-3-642-03356-8_7"},{"key":"2022051409231705591_j_popets-2021-0079_ref_003","doi-asserted-by":"crossref","unstructured":"[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\u2013649. Springer, 2015.10.1007\/978-3-662-46447-2_28","DOI":"10.1007\/978-3-662-46447-2_28"},{"key":"2022051409231705591_j_popets-2021-0079_ref_004","unstructured":"[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\u2013145. ACM, 2004."},{"key":"2022051409231705591_j_popets-2021-0079_ref_005","doi-asserted-by":"crossref","unstructured":"[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\u2013288. Springer, 2015.10.1007\/978-3-662-48800-3_11","DOI":"10.1007\/978-3-662-48800-3_11"},{"key":"2022051409231705591_j_popets-2021-0079_ref_006","unstructured":"[6] J. Camenisch, S. Krenn, A. Lehmann, G. L. Mikkelsen, G. Neven, and M. \u00d8. Pedersen. Formal treatment of privacy-enhancing credential systems. IACR Cryptol. ePrint Arch., 2014:708, 2014."},{"key":"2022051409231705591_j_popets-2021-0079_ref_007","doi-asserted-by":"crossref","unstructured":"[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\u2013118. Springer, 2001.10.1007\/3-540-44987-6_7","DOI":"10.1007\/3-540-44987-6_7"},{"key":"2022051409231705591_j_popets-2021-0079_ref_008","doi-asserted-by":"crossref","unstructured":"[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\u201372. Springer, 2004.10.1007\/978-3-540-28628-8_4","DOI":"10.1007\/978-3-540-28628-8_4"},{"key":"2022051409231705591_j_popets-2021-0079_ref_009","doi-asserted-by":"crossref","unstructured":"[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\u2013122. Springer, 1999.10.1007\/3-540-48910-X_8","DOI":"10.1007\/3-540-48910-X_8"},{"key":"2022051409231705591_j_popets-2021-0079_ref_010","doi-asserted-by":"crossref","unstructured":"[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\u2013144. Springer, 2003.10.1007\/978-3-540-45146-4_8","DOI":"10.1007\/978-3-540-45146-4_8"},{"key":"2022051409231705591_j_popets-2021-0079_ref_011","doi-asserted-by":"crossref","unstructured":"[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\u2013145. IEEE Computer Society, 2001.10.1109\/SFCS.2001.959888","DOI":"10.1109\/SFCS.2001.959888"},{"key":"2022051409231705591_j_popets-2021-0079_ref_012","doi-asserted-by":"crossref","unstructured":"[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.","DOI":"10.1109\/CSF.2014.22"},{"key":"2022051409231705591_j_popets-2021-0079_ref_013","doi-asserted-by":"crossref","unstructured":"[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\u201396. Springer, 2006.10.1007\/11818175_5","DOI":"10.1007\/11818175_5"},{"key":"2022051409231705591_j_popets-2021-0079_ref_014","unstructured":"[14] D. Chaum. Showing credentials without identification: Signatures transferred between unconditionally unlinkable pseudonyms. In F. Pichler, editor, EUROCRYPT \u201985, Linz, Austria, April 1985, volume 219 of LNCS, pages 241\u2013244. Springer, 1985."},{"key":"2022051409231705591_j_popets-2021-0079_ref_015","doi-asserted-by":"crossref","unstructured":"[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\u2013555. Springer, 2019.10.1007\/978-3-030-12612-4_27","DOI":"10.1007\/978-3-030-12612-4_27"},{"key":"2022051409231705591_j_popets-2021-0079_ref_016","unstructured":"[16] I. Damg\u00e5rd. On sigma-protocols, 2002."},{"key":"2022051409231705591_j_popets-2021-0079_ref_017","doi-asserted-by":"crossref","unstructured":"[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\u2013535. Springer, 2008.10.1007\/978-3-540-85174-5_29","DOI":"10.1007\/978-3-540-85174-5_29"},{"key":"2022051409231705591_j_popets-2021-0079_ref_018","doi-asserted-by":"crossref","unstructured":"[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 \u201986, Santa Barbara, California, USA, 1986, volume 263 of LNCS, pages 186\u2013194. Springer, 1986.10.1007\/3-540-47721-7_12","DOI":"10.1007\/3-540-47721-7_12"},{"key":"2022051409231705591_j_popets-2021-0079_ref_019","doi-asserted-by":"crossref","unstructured":"[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\u2013168. Springer, 2005.10.1007\/11535218_10","DOI":"10.1007\/11535218_10"},{"key":"2022051409231705591_j_popets-2021-0079_ref_020","doi-asserted-by":"crossref","unstructured":"[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\u2013183. Springer, 2018.10.1007\/978-3-319-76581-5_6","DOI":"10.1007\/978-3-319-76581-5_6"},{"key":"2022051409231705591_j_popets-2021-0079_ref_021","doi-asserted-by":"crossref","unstructured":"[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\u2013408. Springer, 2016.10.1007\/978-3-319-44618-9_21","DOI":"10.1007\/978-3-319-44618-9_21"},{"key":"2022051409231705591_j_popets-2021-0079_ref_022","doi-asserted-by":"crossref","unstructured":"[22] G. Fuchsbauer, C. Hanser, and D. Slamanig. Structure-preserving signatures on equivalence classes and constantsize anonymous credentials. J. Cryptol., 32(2):498\u2013546, 2019.10.1007\/s00145-018-9281-4","DOI":"10.1007\/s00145-018-9281-4"},{"key":"2022051409231705591_j_popets-2021-0079_ref_023","doi-asserted-by":"crossref","unstructured":"[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\u2013432. Springer, 2008.10.1007\/978-3-540-78967-3_24","DOI":"10.1007\/978-3-540-78967-3_24"},{"key":"2022051409231705591_j_popets-2021-0079_ref_024","unstructured":"[24] A. Lysyanskaya. Signature schemes and applications to cryptographic protocol design. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA, 2002."},{"key":"2022051409231705591_j_popets-2021-0079_ref_025","doi-asserted-by":"crossref","unstructured":"[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\u2013199. Springer, 1999.10.1007\/3-540-46513-8_14","DOI":"10.1007\/3-540-46513-8_14"},{"key":"2022051409231705591_j_popets-2021-0079_ref_026","unstructured":"[26] S. Meiklejohn, C. C. Erway, A. K\u00fcp\u00e7\u00fc, 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\u2013206. USENIX Association, 2010."}],"container-title":["Proceedings on Privacy Enhancing Technologies"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.sciendo.com\/pdf\/10.2478\/popets-2021-0079","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,20]],"date-time":"2022-07-20T16:31:46Z","timestamp":1658334706000},"score":1,"resource":{"primary":{"URL":"https:\/\/petsymposium.org\/popets\/2021\/popets-2021-0079.php"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,23]]},"references-count":26,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2021,7,23]]},"published-print":{"date-parts":[[2021,10,1]]}},"alternative-id":["10.2478\/popets-2021-0079"],"URL":"https:\/\/doi.org\/10.2478\/popets-2021-0079","relation":{},"ISSN":["2299-0984"],"issn-type":[{"value":"2299-0984","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,23]]}}}