{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,20]],"date-time":"2026-06-20T03:01:56Z","timestamp":1781924516657,"version":"3.54.5"},"reference-count":41,"publisher":"Oxford University Press (OUP)","issue":"12","license":[{"start":{"date-parts":[[2020,11,27]],"date-time":"2020-11-27T00:00:00Z","timestamp":1606435200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61772514"],"award-info":[{"award-number":["61772514"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61602061"],"award-info":[{"award-number":["61602061"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61822202"],"award-info":[{"award-number":["61822202"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61872089"],"award-info":[{"award-number":["61872089"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11701089"],"award-info":[{"award-number":["11701089"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Key R D Program of China","award":["2017YFB1400700"],"award-info":[{"award-number":["2017YFB1400700"]}]},{"name":"Natural Science Foundation of Fujian Province, China","award":["2019J01428"],"award-info":[{"award-number":["2019J01428"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,12,17]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Linearly homomorphic signatures (LHSs) allow any entity to linearly combine a set of signatures and to provide authentication service for the corresponding (combined) data. The public key of the current known LHSs from lattices in the standard model requires $O(l)$ matrices and $O(k)$ vectors, where $l$ is the length of file identifier and $k$ is the maximum data set size that linear functions support. In this paper, we construct two lattice-based LHS schemes with provable security in the standard model and both schemes can authenticate vectors defined over finite field. First, we present a basic LHS scheme satisfying selective security, based on the full-rank difference hash functions. Second, we modify the chameleon hash function constructed by (Cash, D., Hofheinz, D., Kiltz, E. and Peikert, C. (2010) Bonsai Trees, or How to Delegate a Lattice Basis. In Proc. EUROCRYPT 10, Monaco\/French Riviera, May 30 to June 3, pp. 523\u2013552. Springer, Berlin) to construct a linearly homomorphic chameleon hash function (LHCHF), which can be applied to all transformations from selectively secure LHS scheme that authenticates vectors defined over finite field $\\mathbb{F}_{p}$ ($p=poly(n)$) to fully secure one, except for a new one that authenticates vectors defined over a small field. Starting from LHCFH and the basic scheme as above, we obtain a fully secure LHS scheme. Both schemes can be used to sign multiple files and have relatively short public keys consisting of $O(1)$ matrices and $O(k)$ vectors.<\/jats:p>","DOI":"10.1093\/comjnl\/bxaa034","type":"journal-article","created":{"date-parts":[[2020,3,11]],"date-time":"2020-03-11T12:31:48Z","timestamp":1583929908000},"page":"1871-1885","source":"Crossref","is-referenced-by-count":13,"title":["Linearly Homomorphic Signatures from Lattices"],"prefix":"10.1093","volume":"63","author":[{"given":"Cheng-Jun","family":"Lin","sequence":"first","affiliation":[{"name":"State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China"},{"name":"School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rui","family":"Xue","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China"},{"name":"School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shao-Jun","family":"Yang","sequence":"additional","affiliation":[{"name":"Fujian Provincial Key Laboratory of Network Security and Cryptology, School of Mathematics and Informatics, Fujian Normal University, Fuzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xinyi","family":"Huang","sequence":"additional","affiliation":[{"name":"Fujian Provincial Key Laboratory of Network Security and Cryptology, School of Mathematics and Informatics, Fujian Normal University, Fuzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shimin","family":"Li","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China"},{"name":"School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2020,11,27]]},"reference":[{"key":"2020121207433402700_ref1","doi-asserted-by":"crossref","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","article-title":"New directions in cryptography","volume":"22","author":"Diffie","year":"1976","journal-title":"IEEE Trans. Information Theory"},{"key":"2020121207433402700_ref2","doi-asserted-by":"crossref","first-page":"1204","DOI":"10.1109\/18.850663","article-title":"Network information flow","volume":"46","author":"Ahlswede","year":"2000","journal-title":"IEEE Trans. Information Theory"},{"key":"2020121207433402700_ref3","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1109\/TIT.2002.807285","article-title":"Linear network coding","volume":"49","author":"Li","year":"2003","journal-title":"IEEE Trans Information Theory"},{"key":"2020121207433402700_ref4","first-page":"68","article-title":"Signing a Linear Subspace: Signature Schemes for Network Coding","volume-title":"Proc. PKC 09","author":"Boneh","year":"2009"},{"key":"2020121207433402700_ref5","first-page":"1","article-title":"Computing on Authenticated Data","volume-title":"Proc. TCC 12","author":"Ahn","year":"2012"},{"key":"2020121207433402700_ref6","first-page":"367","article-title":"Computing on Authenticated Data: New Privacy Definitions and Constructions","volume-title":"Proc. ASIACRYPT 12","author":"Attrapadung","year":"2012"},{"key":"2020121207433402700_ref7","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1504\/IJICOT.2009.024044","article-title":"Signatures for network coding","volume":"1","author":"Charles","year":"2009","journal-title":"IJICoT"},{"key":"2020121207433402700_ref8","doi-asserted-by":"crossref","first-page":"1295","DOI":"10.1109\/TC.2010.73","article-title":"On homomorphic signatures for network coding","volume":"59","author":"Yun","year":"2010","journal-title":"IEEE Trans. Computers"},{"key":"2020121207433402700_ref9","first-page":"1409","article-title":"An Efficient Signature-Based Scheme for Securing Network Coding Against Pollution Attacks","volume-title":"Proc. INFOCOM 08","author":"Yu","year":"2008"},{"key":"2020121207433402700_ref10","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1145\/283751.283834","article-title":"Computer Security by Redefining What a Computer Is","volume-title":"Proc. 1992\u20131993 Workshop on New Security Paradigms","author":"Desmedt","year":"1993"},{"key":"2020121207433402700_ref11","first-page":"244","article-title":"Homomorphic Signature Schemes","volume-title":"Proc. CT-RSA 02","author":"Johnson","year":"2002"},{"key":"2020121207433402700_ref12","first-page":"142","article-title":"Secure Network Coding over the Integers","volume-title":"Proc. PKC 10","author":"Gennaro","year":"2010"},{"key":"2020121207433402700_ref13","first-page":"680","article-title":"Efficient Network Coding Signatures in the Standard Model","volume-title":"Proc. PKC 12","author":"Catalano","year":"2012"},{"key":"2020121207433402700_ref14","first-page":"17","article-title":"Homomorphic Network Coding Signatures in the Standard Model","volume-title":"Proc. PKC 11","author":"Attrapadung","year":"2011"},{"key":"2020121207433402700_ref15","first-page":"254","article-title":"Programmable Hash Functions Go Private: Constructions and Applications to (Homomorphic) Signatures with Shorter Public Keys","volume-title":"Proc. CRYPTO 15","author":"Catalano","year":"2015"},{"key":"2020121207433402700_ref16","first-page":"1","article-title":"Linearly Homomorphic Signatures over Binary Fields and New Tools for Lattice-Based Signatures","volume-title":"Proc. PKC 11","author":"Boneh","year":"2011"},{"key":"2020121207433402700_ref17","first-page":"149","article-title":"Homomorphic Signatures for Polynomial Functions","volume-title":"Proc. EUROCRYPT 11","author":"Boneh","year":"2011"},{"key":"2020121207433402700_ref18","first-page":"1","article-title":"Lattice-based linearly homomorphic signature scheme over binary field","volume":"56","author":"Wang","year":"2013","journal-title":"Sci. China Info. Sci."},{"key":"2020121207433402700_ref19","first-page":"239","article-title":"Network Coding Signature Schemes Against Related-Key Attacks in the Random Oracle Model","volume-title":"Proc. ICISC 16","author":"Chang","year":"2016"},{"key":"2020121207433402700_ref20","first-page":"491","article-title":"A Theoretical Treatment of Related-Key Attacks: RKA-PRPs, RKA-PRFs, and Applications","volume-title":"Proc. EUROCRYPT 03","author":"Bellare","year":"2003"},{"key":"2020121207433402700_ref21","article-title":"On the security of LWE cryptosystem against subversion attacks","author":"Yang","year":"2019","journal-title":"The Computer Journal"},{"key":"2020121207433402700_ref22","first-page":"653","article-title":"Homomorphic signature schemes\u2014A survey","volume":"2015","author":"Traverso","year":"2015","journal-title":"IACR Cryptology ePrint Archive"},{"key":"2020121207433402700_ref23","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1145\/237814.237838","article-title":"Generating Hard Instances of Lattice Problems (Extended Abstract)","volume-title":"Proc. Twenty-Eighth Annual ACM Symposium on the Theory of Computing","author":"Ajtai","year":"1996"},{"key":"2020121207433402700_ref24","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/j.tcs.2016.04.009","article-title":"Lattice-based linearly homomorphic signatures in the standard model","volume":"634","author":"Chen","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"2020121207433402700_ref25","article-title":"Chameleon Signatures","volume-title":"Proc. NDSS 00","author":"Krawczyk","year":"2000"},{"key":"2020121207433402700_ref26","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1145\/1374376.1374407","article-title":"Trapdoors for Hard Lattices and New Cryptographic Constructions","volume-title":"Proc. 40th Annual ACM Symposium on Theory of Computing","author":"Gentry","year":"2008"},{"key":"2020121207433402700_ref27","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1145\/2746539.2746576","article-title":"Leveled Fully Homomorphic Signatures from Standard Lattices","volume-title":"Proc. STOC 15","author":"Gorbunov","year":"2015"},{"key":"2020121207433402700_ref28","first-page":"499","article-title":"Lattice Mixing and Vanishing Trapdoors: A Framework for Fully Secure Short Signatures and More","volume-title":"Proc. PKC 10","author":"Boyen","year":"2010"},{"key":"2020121207433402700_ref29","first-page":"553","article-title":"Efficient Lattice (H)IBE in the Standard Model","volume-title":"Proc. EUROCRYPT 10","author":"Agrawal","year":"2010"},{"key":"2020121207433402700_ref30","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1007\/s00145-014-9183-z","article-title":"Confined guessing: New signatures from standard assumptions","volume":"28","author":"B\u00f6hl","year":"2015","journal-title":"J. Cryptol."},{"key":"2020121207433402700_ref31","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-88702-7_5","volume-title":"Lattice-Based Cryptography","author":"Micciancio","year":"2009"},{"key":"2020121207433402700_ref32","first-page":"31","article-title":"Predicting Lattice Reduction","volume-title":"Proc. EUROCRYPT 08","author":"Gama","year":"2008"},{"key":"2020121207433402700_ref33","first-page":"1","article-title":"Generating Hard Instances of the Short Basis Problem","volume-title":"Proc. ICALP 99","author":"Ajtai","year":"1999"},{"key":"2020121207433402700_ref34","first-page":"75","article-title":"Generating Shorter Bases for Hard Random Lattices","volume-title":"Proc. STACS 09","author":"Alwen","year":"2009"},{"key":"2020121207433402700_ref35","first-page":"700","article-title":"Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller","volume-title":"Proc. EUROCRYPT 12","author":"Micciancio","year":"2012"},{"key":"2020121207433402700_ref36","first-page":"372","article-title":"Worst-Case to Average-Case Reductions Based on Gaussian Measures","volume-title":"Proc. FOCS 04","author":"Micciancio","year":"2004"},{"key":"2020121207433402700_ref37","first-page":"523","article-title":"Bonsai Trees, or How to Delegate a Lattice Basis","volume-title":"Proc. EUROCRYPT 10","author":"Cash","year":"2010"},{"key":"2020121207433402700_ref38","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-0897-7","volume-title":"Complexity of Lattice Problems: A Cryptographic Perspective","author":"Micciancio","year":"2002"},{"key":"2020121207433402700_ref39","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1137\/060651380","article-title":"Fuzzy extractors: How to generate strong keys from biometrics and other noisy data","volume":"38","author":"Dodis","year":"2008","journal-title":"SIAM J. Comput."},{"key":"2020121207433402700_ref40","first-page":"236","article-title":"Signatures with Short Public Keys from Homomorphic Trapdoor Functions","volume-title":"Proc. PKC 2015","author":"Alperin-Sheriff","year":"2015"},{"key":"2020121207433402700_ref41","first-page":"152","article-title":"Chameleon-Hashes with Ephemeral Trapdoors\u2014and Applications to Invisible Sanitizable Signatures","volume-title":"Proc. PKC 17","author":"Camenisch","year":"2017"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/63\/12\/1871\/34867820\/bxaa034.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/63\/12\/1871\/34867820\/bxaa034.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,28]],"date-time":"2023-09-28T13:15:28Z","timestamp":1695906928000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/63\/12\/1871\/5824921"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,27]]},"references-count":41,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2020,11,27]]},"published-print":{"date-parts":[[2020,12,17]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxaa034","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2020,12]]},"published":{"date-parts":[[2020,11,27]]}}}