{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T18:33:11Z","timestamp":1773513191076,"version":"3.50.1"},"reference-count":35,"publisher":"Oxford University Press (OUP)","issue":"9","license":[{"start":{"date-parts":[[2021,5,31]],"date-time":"2021-05-31T00:00:00Z","timestamp":1622419200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,9,16]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>With the help of a multi-signature scheme, we can reduce the cost of storage and bandwidth in case of many signers signing the same message. Therefore, multi-signature schemes can be used in bitcoin to reduce the size of a blockchain. In this paper, we propose a lattice-based multi-signature scheme with the following highlighted features. Our lattice-based multi-signature scheme supports signature compression and public key aggregation. The only existing lattice-based multi-signature scheme by Kansal and Dutta (Africacrypt, 2020) that supports both signature compression and public key aggregation has communication and storage cost $\\widetilde{\\mathcal{O}}(n^2)$, whereas our communication and storage cost is $\\mathcal{O}(n)$. Our multi-signature scheme is in the plain public key model where the special registration of the public key is not necessary and it is secure under the rogue key attack. Our multi-signature scheme is secure under the hardness of ring short integer solution problem in the random oracle model.<\/jats:p>","DOI":"10.1093\/comjnl\/bxab077","type":"journal-article","created":{"date-parts":[[2021,5,7]],"date-time":"2021-05-07T19:29:25Z","timestamp":1620415765000},"page":"2421-2429","source":"Crossref","is-referenced-by-count":14,"title":["Efficient Multi-Signature Scheme Using Lattice"],"prefix":"10.1093","volume":"65","author":[{"given":"Meenakshi","family":"Kansal","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering , Indian Institute of Technology Madras, Chennai, Tamil Nadu-600036, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amit Kumar","family":"Singh","sequence":"additional","affiliation":[{"name":"Department of Mathematics , Indian Institute of Technology Kharagpur, Kharagpur, West Bengal-721302, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ratna","family":"Dutta","sequence":"additional","affiliation":[{"name":"Department of Mathematics , Indian Institute of Technology Kharagpur, Kharagpur, West Bengal-721302, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2021,5,31]]},"reference":[{"key":"2022091610474792100_ref1","first-page":"449","volume-title":"Multisignatures Secure under the Discrete Logarithm Assumption and a Generalized Forking Lemma. In Proc. 15th ACM Conf. Computer and Communications Security","author":"Bagherzandi","year":"2008"},{"key":"2022091610474792100_ref2","first-page":"390","volume-title":"Multi-Signatures in the Plain Public-Key Model and a General Forking Lemma. In Proc. 13th ACM Conf. Computer and Communications Security","author":"Bellare","year":"2006"},{"key":"2022091610474792100_ref3","first-page":"31","volume-title":"Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap\u2013Diffie\u2013Hellman-Group Signature Scheme. In Proc. 6th Int. Workshop on Public Key Cryptography","author":"Boldyreva","year":"2003"},{"key":"2022091610474792100_ref4","first-page":"276","volume-title":"Ordered Multisignatures and Identity-Based Sequential Aggregate Signatures, With Applications to Secure Routing. In Proc. 14th ACM Conf. Computer and Communications Security","author":"Boldyreva","year":"2007"},{"key":"2022091610474792100_ref5","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1007\/978-3-030-03329-3_15","volume-title":"Compact Multi-Signatures for Smaller Blockchains. In Proc. Advances in Cryptology\u2014ASIACRYPT 2018","author":"Boneh","year":"2018"},{"key":"2022091610474792100_ref6","first-page":"416","volume-title":"Aggregate and Verifiably Encrypted Signatures from Bilinear Maps. In Proc. Advances in Cryptology\u2014EUROCRYPT 2003","author":"Boneh","year":"2003"},{"key":"2022091610474792100_ref7","volume-title":"Recommended Elliptic Curve Domain Parameters","author":"Brown","year":"2010"},{"key":"2022091610474792100_ref8","first-page":"466","volume-title":"A Structured Elgamal-Type Multisignature Scheme. In Proc. 3rd Int. Workshop on Public Key Cryptography","author":"Burmester","year":"2000"},{"key":"2022091610474792100_ref9","first-page":"154","volume-title":"A Scheme for Obtaining a Message from the Digital Multisignature. In Proc. 1st Int. Workshop on Public Key Cryptography","author":"Chang","year":"1998"},{"key":"2022091610474792100_ref10","volume-title":"Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)","author":"ANSI X9.62","year":"2005"},{"key":"2022091610474792100_ref11","first-page":"1084","article-title":"On the Security of Two-Round Multi-Signatures","volume-title":"IEEE Symposium on Security and Privacy","author":"Drijvers","year":"2019"},{"key":"2022091610474792100_ref12","first-page":"2093","article-title":"Pixel: Multi-Signatures for Consensus","volume-title":"Proc. 29th USENIX Security Symposium, USENIX Security 2020","author":"Drijvers","year":"2020"},{"key":"2022091610474792100_ref13","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1007\/978-3-319-48965-0_9","article-title":"An Efficient Lattice-Based Multisignature Scheme With Applications to Bitcoins","volume-title":"Proc. 15th Int. Conf. Cryptology and Network Security","author":"El Bansarkhani","year":"2016"},{"key":"2022091610474792100_ref14","first-page":"530","article-title":"Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems","volume-title":"Proc. 14th Int. Workshop on Cryptographic Hardware and Embedded Systems","author":"G\u00fcneysu","year":"2012"},{"key":"2022091610474792100_ref15","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/978-3-642-38616-9_5","article-title":"Software Speed Records for Lattice-Based Signatures","volume-title":"Proc. 5th Int. Workshop on Post-Quantum Cryptography","author":"G\u00fcneysu","year":"2013"},{"key":"2022091610474792100_ref16","first-page":"122","article-title":"A Practical Digital Multisignature Scheme Based on Discrete Logarithms","volume-title":"Proc. Advances in Cryptology\u2014AUSCRYPT 1992","author":"Hardjono","year":"1992"},{"key":"2022091610474792100_ref17","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1049\/ip-cdt:19941293","article-title":"Group-oriented (t,n) threshold digital signature scheme and digital multisignature","volume":"141","author":"Harn","year":"1994","journal-title":"IEE Proc. Comput. Digit. Tech."},{"key":"2022091610474792100_ref18","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1007\/978-0-387-34873-5_11","article-title":"Meta-Multisignature Schemes Based on the Discrete Logarithm Problem","volume-title":"Information Security\u2014The Next Decade","author":"Horster","year":"1995"},{"key":"2022091610474792100_ref19","first-page":"1","article-title":"A public-key cryptosystem suitable for digital multisignatures","volume":"71","author":"Ltakura","year":"1983","journal-title":"NEC Res. Dev."},{"key":"2022091610474792100_ref20","first-page":"281","article-title":"Round Optimal Secure Multisignature Schemes from Lattice With Public Key Aggregation and Signature Compression","volume-title":"Proc. 12th Int. Conf. Cryptology in Africa","author":"Kansal","year":"2020"},{"key":"2022091610474792100_ref21","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1007\/11836810_11","article-title":"Formal Security Model of Multisignatures","volume-title":"Proc. 9th Int. Conf. Information Security","author":"Komano","year":"2006"},{"key":"2022091610474792100_ref22","first-page":"194","article-title":"Threshold-Multisignature Schemes Where Suspected Forgery Implies Traceability of Adversarial Shareholders","volume-title":"Proc. Advances in Cryptology\u2014EUROCRYPT 1994","author":"Li","year":"1994"},{"key":"2022091610474792100_ref23","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1007\/11761679_28","article-title":"Sequential Aggregate Signatures and Multisignatures Without Random Oracles","volume-title":"Proc. Advances in Cryptology\u2014EUROCRYPT 2006","author":"Lu","year":"2006"},{"key":"2022091610474792100_ref24","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1007\/3-540-45708-9_38","article-title":"Unique Signatures and Verifiable Random Functions from the DH-DDH Separation","volume-title":"Proc. Advances in Cryptology\u2014CRYPTO 2002","author":"Lysyanskaya","year":"2002"},{"key":"2022091610474792100_ref25","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/s10623-009-9313-z","article-title":"Efficient discrete logarithm based multi-signature scheme in the plain public key model","volume":"54","author":"Ma","year":"2010","journal-title":"Des. Codes Cryptogr."},{"key":"2022091610474792100_ref26","doi-asserted-by":"crossref","first-page":"2139","DOI":"10.1007\/s10623-019-00608-x","article-title":"Simple Schnorr multi-signatures with applications to bitcoin","volume":"87","author":"Maxwell","year":"2019","journal-title":"Des. Codes Cryptogr."},{"key":"2022091610474792100_ref27","first-page":"245","article-title":"Accountable-Subgroup Multisignatures","volume-title":"Proc. 8th ACM Conf. Computer and Communications Security","author":"Micali","year":"2001"},{"key":"2022091610474792100_ref28","first-page":"356","article-title":"Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions from Worst-Case Complexity Assumptions","volume-title":"Proc. 43rd Symposium on Foundations of Computer Science","author":"Micciancio","year":"2002"},{"key":"2022091610474792100_ref29","volume-title":"Bitcoin: A peer-to-peer electronic cash system","author":"Nakamoto","year":"2008"},{"key":"2022091610474792100_ref30","first-page":"21","article-title":"Multi-signature schemes secure against active insider attacks","volume":"82","author":"Ohta","year":"1999","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"key":"2022091610474792100_ref31","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/BFb0028477","article-title":"Two Efficient RSA Multisignature Schemes","volume-title":"Proc. 1st Int. Conf. Information and Communications Security","author":"Park","year":"1997"},{"key":"2022091610474792100_ref32","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/s001450010003","article-title":"Security arguments for digital signatures and blind signatures","volume":"13","author":"Pointcheval","year":"2000","journal-title":"J. Cryptology"},{"key":"2022091610474792100_ref33","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1007\/978-3-540-72540-4_13","article-title":"The Power of Proofs-of-Possession: Securing Multiparty Signatures Against Rogue-Key Attacks","volume-title":"Proc. Advances in Cryptology\u2014EUROCRYPT 2007","author":"Ristenpart","year":"2007"},{"key":"2022091610474792100_ref34","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/BF00196725","article-title":"Efficient signature generation by smart cards","volume":"4","author":"Schnorr","year":"1991","journal-title":"J. Cryptology"},{"key":"2022091610474792100_ref35","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1137\/S0036144598347011","article-title":"Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer","volume":"41","author":"Shor","year":"1999","journal-title":"SIAM Rev."}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/65\/9\/2421\/45882275\/bxab077.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/65\/9\/2421\/45882275\/bxab077.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,16]],"date-time":"2022-09-16T10:49:37Z","timestamp":1663325377000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/65\/9\/2421\/6289877"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,31]]},"references-count":35,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2021,5,31]]},"published-print":{"date-parts":[[2022,9,16]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxab077","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022,9]]},"published":{"date-parts":[[2021,5,31]]}}}