{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T01:04:26Z","timestamp":1772240666066,"version":"3.50.1"},"reference-count":27,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,2,14]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>From the work by Laguillaumie and Vergnaud in ICICS\u201904, it has been widely believed that multi-designated verifiers signature scheme (MDVS) can be constructed from ring signature schemes in general. However, in this article, somewhat surprisingly, we prove that it is impossible to construct an MDVS scheme from a ring signature scheme in a black-box sense (in the standard model). The impossibility stems from the difference between the definitions of unforgeability of the two schemes. To the best of our knowledge, existing works demonstrating the constructions do not provide formal reductions from an MDVS scheme to a ring signature scheme, and thus, the impossibility has been overlooked for a long time.<\/jats:p>","DOI":"10.1515\/jmc-2023-0028","type":"journal-article","created":{"date-parts":[[2024,2,14]],"date-time":"2024-02-14T15:32:22Z","timestamp":1707924742000},"source":"Crossref","is-referenced-by-count":5,"title":["On the Black-Box impossibility of multi-designated verifiers signature schemes from ring signature schemes"],"prefix":"10.1515","volume":"18","author":[{"given":"Kyosuke","family":"Yamashita","sequence":"first","affiliation":[{"name":"The Graduate School of Information Science and Technology, Osaka University , Osaka , Japan"},{"name":"Cyber Physical Security Research Center, National Institute of Advanced Industrial Science and Technology , Tokyo , Japan"}]},{"given":"Keisuke","family":"Hara","sequence":"additional","affiliation":[{"name":"Cyber Physical Security Research Center, National Institute of Advanced Industrial Science and Technology , Tokyo , Japan"},{"name":"Graduate School of Environment and Information Sciences, Yokohama National University , Yokohama , Japan"}]}],"member":"374","published-online":{"date-parts":[[2024,2,14]]},"reference":[{"key":"2025120600251216872_j_jmc-2023-0028_ref_001","doi-asserted-by":"crossref","unstructured":"Laguillaumie F, Vergnaud D. Multi-designated verifiers signatures. In: Lopez J, Qing S, Okamoto E, editors. Information and communications security. Berlin, Heidelberg: Springer Berlin Heidelberg; 2004. p. 495\u2013507.","DOI":"10.1007\/978-3-540-30191-2_38"},{"key":"2025120600251216872_j_jmc-2023-0028_ref_002","doi-asserted-by":"crossref","unstructured":"Borisov N, Goldberg I, Brewer E. Off-the-record communication, or, why not to use PGP. In: Proceedings of the 2004 ACM Workshop on Privacy in the Electronic Society. WPES \u201904. New York, NY, USA: Association for Computing Machinery; 2004. p. 77\u201384.","DOI":"10.1145\/1029179.1029200"},{"key":"2025120600251216872_j_jmc-2023-0028_ref_003","doi-asserted-by":"crossref","unstructured":"Damg\u00e5rd I, Haagh H, Mercer R, Nitulescu A, Orlandi C, Yakoubov S. Stronger security and constructions of multi-designated verifier signatures. In: Pass R, Pietrzak K, editors. Theory of Cryptography. Cham: Springer International Publishing; 2020. p. 229\u201360.","DOI":"10.1007\/978-3-030-64378-2_9"},{"key":"2025120600251216872_j_jmc-2023-0028_ref_004","doi-asserted-by":"crossref","unstructured":"Lee B, Choo KKR, Yang J, Yoo S. Secret signatures: how to achieve business privacy efficiently? In: Kim S, Yung M, Lee HW, editors. Information security applications. Berlin, Heidelberg: Springer; 2007. p. 30\u201347.","DOI":"10.1007\/978-3-540-77535-5_3"},{"key":"2025120600251216872_j_jmc-2023-0028_ref_005","doi-asserted-by":"crossref","unstructured":"Jakobsson M, Sako K, Impagliazzo R. Designated verifier proofs and their applications. In: Maurer U, editor. Advances in cryptology \u2013 EUROCRYPT \u201996. Berlin Heidelberg: Springer; 1996. p. 143\u201354.","DOI":"10.1007\/3-540-68339-9_13"},{"key":"2025120600251216872_j_jmc-2023-0028_ref_006","doi-asserted-by":"crossref","unstructured":"Laguillaumie F, Vergnaud D. Multi-designated verifiers signatures: anonymity without encryption. Inform Process Lett. 2007;102(2):127\u201332.","DOI":"10.1016\/j.ipl.2006.08.015"},{"key":"2025120600251216872_j_jmc-2023-0028_ref_007","doi-asserted-by":"crossref","unstructured":"Vergnaud D. New extensions of pairing-based signatures into universal designated verifier signatures. In: Bugliesi M, Preneel B, Sassone V, Wegener I, editors. Automata, Languages and Programming. Berlin Heidelberg: Springer; 2006. p. 58\u201369.","DOI":"10.1007\/11787006_6"},{"key":"2025120600251216872_j_jmc-2023-0028_ref_008","doi-asserted-by":"crossref","unstructured":"Zhang Y, Au MH, Yang G, Susilo W. (Strong) Multi-designated verifiers signatures secure against Rogue key attack. In: Xu L, Bertino E, Mu Y, editors. Network and System Security Berlin Heidelberg: Springer; 2012. p. 334\u201347.","DOI":"10.1007\/978-3-642-34601-9_25"},{"key":"2025120600251216872_j_jmc-2023-0028_ref_009","doi-asserted-by":"crossref","unstructured":"Gennaro R, Trevisan L. Lower bounds on the efficiency of generic cryptographic constructions. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science. FOCS \u201900. USA: IEEE Computer Society; 2000. p. 305.","DOI":"10.1109\/SFCS.2000.892119"},{"key":"2025120600251216872_j_jmc-2023-0028_ref_010","doi-asserted-by":"crossref","unstructured":"Impagliazzo R, Rudich S. Limits on the provable consequences of one-way permutations. In: Goldwasser S, editor. Advances in Cryptology \u2013 CRYPTO\u2019 88. New York, NY: Springer; 1990. p. 8\u201326.","DOI":"10.1007\/0-387-34799-2_2"},{"key":"2025120600251216872_j_jmc-2023-0028_ref_011","doi-asserted-by":"crossref","unstructured":"Gertner Y, Kannan S, Malkin T, Reingold O, Viswanathan M. The relationship between public key encryption and oblivious transfer. In: Proceedings 41st Annual Symposium on Foundations of Computer Science; 2000. p. 325\u201335.","DOI":"10.1109\/SFCS.2000.892121"},{"key":"2025120600251216872_j_jmc-2023-0028_ref_012","doi-asserted-by":"crossref","unstructured":"Mahmoody M, Mohammed A, Nematihaji S. On the impossibility of virtual black-box obfuscation in idealized models. In: Kushilevitz E, Malkin T, editors. Theory of cryptography. Berlin, Heidelberg: Springer; 2016. p. 18\u201348.","DOI":"10.1007\/978-3-662-49096-9_2"},{"key":"2025120600251216872_j_jmc-2023-0028_ref_013","doi-asserted-by":"crossref","unstructured":"Pass R. Unprovable security of perfect NIZK and non-interactive non-malleable commitments. In: Sahai A, editor. Theory of cryptography. Berlin, Heidelberg: Springer; 2013. p. 334\u201354.","DOI":"10.1007\/978-3-642-36594-2_19"},{"key":"2025120600251216872_j_jmc-2023-0028_ref_014","doi-asserted-by":"crossref","unstructured":"Simon DR. Finding collisions on a one-way street: Can secure hash functions be based on general assumptions? In: Nyberg K, editor. Advances in Cryptology \u2013 EUROCRYPT\u201998. Berlin, Heidelberg: Springer; 1998. p. 334\u201345.","DOI":"10.1007\/BFb0054137"},{"key":"2025120600251216872_j_jmc-2023-0028_ref_015","doi-asserted-by":"crossref","unstructured":"Brendel J, Fiedler R, G\u00fcnther F, Janson C, Stebila D. Post-quantum asynchronous deniable key exchange and the signal Handshake. In: Hanaoka G, Shikata J, Watanabe Y, editors. Public-Key Cryptography - PKC 2022. Cham: Springer International Publishing; 2022. p. 3\u201334.","DOI":"10.1007\/978-3-030-97131-1_1"},{"key":"2025120600251216872_j_jmc-2023-0028_ref_016","doi-asserted-by":"crossref","unstructured":"Hashimoto K, Katsumata S, Kwiatkowski K, Prest T. An efficient and generic construction for signal\u2019s handshake (X3DH): post-quantum, state leakage secure, and deniable. In: Garay JA, editor. Public-Key Cryptography - PKC 2021. Cham: Springer International Publishing; 2021. p. 410\u201340.","DOI":"10.1007\/978-3-030-75248-4_15"},{"key":"2025120600251216872_j_jmc-2023-0028_ref_017","unstructured":"Chow S. Multi-designated verifiers signatures revisited. Int J Network Security. 2008;01:7."},{"key":"2025120600251216872_j_jmc-2023-0028_ref_018","doi-asserted-by":"crossref","unstructured":"Chakraborty S, Hofheinz D, Maurer U, Rito G. Deniable authentication when signing keys leak. In: Hazay C, Stam M, editors. Advances in cryptology - EUROCRYPT 2023. Cham: Springer Nature Switzerland; 2023. p. 69\u2013100.","DOI":"10.1007\/978-3-031-30620-4_3"},{"key":"2025120600251216872_j_jmc-2023-0028_ref_019","doi-asserted-by":"crossref","unstructured":"Maurer U, Portmann C, Rito G. Multi-designated receiver signed public key encryption. In: Dunkelman O, Dziembowski S, editors. Advances in cryptology - EUROCRYPT 2022. Cham: Springer International Publishing; 2022. p. 644\u201373.","DOI":"10.1007\/978-3-031-07085-3_22"},{"key":"2025120600251216872_j_jmc-2023-0028_ref_020","doi-asserted-by":"crossref","unstructured":"Behrouz P, Grontas P, Konstantakatos V, Pagourtzis A, Spyrakou M. Designated-verifier linkable ring signatures. In: Park JH, Seo SH, editors. Information security and cryptology - ICISC 2021. Cham: Springer International Publishing; 2022. p. 51\u201370.","DOI":"10.1007\/978-3-031-08896-4_3"},{"key":"2025120600251216872_j_jmc-2023-0028_ref_021","doi-asserted-by":"crossref","unstructured":"Yamashita K, Hara K, Watanabe Y, Yanai N, Shikata J. Designated verifier signature with claimability. In: Proceedings of the 10th ACM Asia Public-Key Cryptography Workshop. APKC \u201923. New York, NY, USA: Association for Computing Machinery; 2023. p. 21\u201332.","DOI":"10.1145\/3591866.3593071"},{"key":"2025120600251216872_j_jmc-2023-0028_ref_022","doi-asserted-by":"crossref","unstructured":"Xu S, Yung M. Accountable ring signatures: a smart card approach. In: Smart card research and advanced applications VI; 2004. p. 271\u201386.","DOI":"10.1007\/1-4020-8147-2_18"},{"key":"2025120600251216872_j_jmc-2023-0028_ref_023","doi-asserted-by":"crossref","unstructured":"Liu JK, Wei VK, Wong DS. Linkable spontaneous anonymous group signature for Ad Hoc groups. In: Wang H, Pieprzyk J, Varadharajan V, editors. Information security and privacy. Berlin, Heidelberg: Springer; 2004. p. 325\u201335.","DOI":"10.1007\/978-3-540-27800-9_28"},{"key":"2025120600251216872_j_jmc-2023-0028_ref_024","doi-asserted-by":"crossref","unstructured":"Fujisaki E, Suzuki K. Traceable ring signature. In: Public Key Cryptography - PKC 2007; 2007. p. 181\u2013200.","DOI":"10.1007\/978-3-540-71677-8_13"},{"key":"2025120600251216872_j_jmc-2023-0028_ref_025","doi-asserted-by":"crossref","unstructured":"Komano Y, Ohta K, Shimbo A, Kawamura S. Toward the fair anonymous signatures: deniable ring signatures. In: Pointcheval D, editor. Topics in cryptology - CT-RSA 2006. Berlin Heidelberg: Springer; 2006. p. 174\u201391.","DOI":"10.1007\/11605805_12"},{"key":"2025120600251216872_j_jmc-2023-0028_ref_026","doi-asserted-by":"crossref","unstructured":"Park S, Sealfon A. It wasn\u2019t me! repudiability and unclaimability of ring signatures. In: Annual International Cryptology Conference. Springer; 2019. p. 159\u201390.","DOI":"10.1007\/978-3-030-26954-8_6"},{"key":"2025120600251216872_j_jmc-2023-0028_ref_027","doi-asserted-by":"crossref","unstructured":"Bender A, Katz J, Morselli R. Ring signatures: stronger definitions, and constructions without random oracles. In: Halevi S, Rabin T, editors. Theory of Cryptography. Berlin, Heidelberg: Springer; 2006. p. 60\u201379.","DOI":"10.1007\/11681878_4"}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2023-0028\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2023-0028\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:25:45Z","timestamp":1764980745000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2023-0028\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,1]]},"references-count":27,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2024,2,14]]},"published-print":{"date-parts":[[2024,2,14]]}},"alternative-id":["10.1515\/jmc-2023-0028"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2023-0028","relation":{},"ISSN":["1862-2984"],"issn-type":[{"value":"1862-2984","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,1]]},"article-number":"20230028"}}