{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T21:42:52Z","timestamp":1772142172740,"version":"3.50.1"},"reference-count":38,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2018,10,12]],"date-time":"2018-10-12T00:00:00Z","timestamp":1539302400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Cryptography"],"abstract":"<jats:p>The design of a practical code-based signature scheme is an open problem in post-quantum cryptography. This paper is the full version of a work appeared at SIN\u201918 as a short paper, which introduced a simple and efficient one-time secure signature scheme based on quasi-cyclic codes. As such, this paper features, in a fully self-contained way, an accurate description of the scheme setting and related previous work, a detailed security analysis, and an extensive comparison and performance discussion.<\/jats:p>","DOI":"10.3390\/cryptography2040030","type":"journal-article","created":{"date-parts":[[2018,10,12]],"date-time":"2018-10-12T02:58:04Z","timestamp":1539313084000},"page":"30","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Efficient One-Time Signatures from Quasi-Cyclic Codes: A Full Treatment"],"prefix":"10.3390","volume":"2","author":[{"given":"Edoardo","family":"Persichetti","sequence":"first","affiliation":[{"name":"Department of Mathematical Sciences, Florida Atlantic University, Boca Raton, FL 33431, USA"}]}],"member":"1968","published-online":{"date-parts":[[2018,10,12]]},"reference":[{"key":"ref_1","unstructured":"Locke, G., and Gallagher, P. (2009). FIPS PUB 186-3: Digital Signature Standard (DSS)."},{"key":"ref_2","first-page":"157","article-title":"How to Achieve a McEliece-Based Digital Signature Scheme","volume":"Volume 2248","author":"Boyd","year":"2001","journal-title":"ASIACRYPT"},{"key":"ref_3","unstructured":"Darnell, M. (1997). A Digital Signature Scheme Based on Random Error-Correcting Codes, Springer."},{"key":"ref_4","first-page":"186","article-title":"How to Prove Yourself: Practical Solutions to Identification and Signature Problems","volume":"Volume 263","author":"Odlyzko","year":"1986","journal-title":"CRYPTO"},{"key":"ref_5","first-page":"57","article-title":"Improved identification schemes based on error-correcting codes","volume":"8","year":"1996","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"key":"ref_6","first-page":"171","article-title":"A Zero-Knowledge Identification Scheme Based on the q-ary Syndrome Decoding Problem","volume":"Volume 6544","author":"Biryukov","year":"2010","journal-title":"Selected Areas in Cryptography"},{"key":"ref_7","first-page":"13","article-title":"A New Identification Scheme Based on Syndrome Decoding","volume":"Volume 773","author":"Stinson","year":"1993","journal-title":"CRYPTO"},{"key":"ref_8","first-page":"164","article-title":"Designing Identification Schemes with Keys of Short Size","volume":"Volume 839","author":"Desmedt","year":"1994","journal-title":"CRYPTO"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Persichetti, E. (2018). Efficient One-Time Signatures from Quasi-Cyclic Codes, ACM.","DOI":"10.3390\/cryptography2040030"},{"key":"ref_10","first-page":"598","article-title":"Fiat\u2013Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures","volume":"Volume 5912","author":"Matsui","year":"2009","journal-title":"International Conference on the Theory and Application of Cryptology and Information Security"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Lyubashevsky, V. (2012). Lattice signatures without trapdoors. Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer.","DOI":"10.1007\/978-3-642-29011-4_43"},{"key":"ref_12","unstructured":"Persichetti, E. (2012). Improving the Efficiency of Code-Based Cryptography. [Ph.D. Thesis, University of Auckland]."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1109\/TIT.1978.1055873","article-title":"On the inherent intractability of certain coding problems","volume":"24","author":"Berlekamp","year":"1978","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Bernstein, D.J., Buchmann, J., and Dahmen, E. (2009). Code-based cryptography. Post-Quantum Cryptography, Springer.","DOI":"10.1007\/978-3-540-88702-7"},{"key":"ref_15","unstructured":"Preneel, B. (Volume 5580). Reducing Key Length of the McEliece Cryptosystem. International Conference on Cryptology in Africa, Springer."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1016\/S0019-9958(69)90497-5","article-title":"Some results on quasi-cyclic codes","volume":"15","author":"Chen","year":"1969","journal-title":"Inf. Control"},{"key":"ref_17","unstructured":"Chabot, C., and Legeay, M. (2010, January 5\u201311). Using automorphisms group for decoding. Proceedings of the 12th International workshop on Algebraic and Combinatorial Coding Theory (ACCT 2010), Novosibirsk, Russia."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1137\/0217017","article-title":"A digital signature scheme secure against adaptive chosen-message attacks","volume":"17","author":"Goldwasser","year":"1988","journal-title":"SIAM J. Comput."},{"key":"ref_19","first-page":"31","article-title":"Provably Secure and Practical Identification Schemes and Corresponding Signature Schemes","volume":"Volume 740","author":"Brickell","year":"1992","journal-title":"Annual International Cryptology Conference"},{"key":"ref_20","first-page":"162","article-title":"Lattice-Based Identification Schemes Secure Under Active Attacks","volume":"Volume 4939","author":"Cramer","year":"2008","journal-title":"Public Key Cryptography"},{"key":"ref_21","first-page":"279","article-title":"Algebraic Cryptanalysis of McEliece Variants with Compact Keys","volume":"Volume 6110","author":"Gilbert","year":"2010","journal-title":"Annual International Conference on the Theory and Applications of Cryptographic Techniques"},{"key":"ref_22","unstructured":"Aguilar, C., Blazy, O., Deneuville, J.C., Gaborit, P., and Z\u00e9mor, G. (arXiv, 2016). Efficient Encryption from Random Quasi-Cyclic Codes, arXiv."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Gaborit, P., and Girault, M. (2007, January 24\u201329). Lightweight code-based identification and signature. Proceedings of the 2007 IEEE International Symposium on Information Theory, Nice, France.","DOI":"10.1109\/ISIT.2007.4557225"},{"key":"ref_24","unstructured":"Tillich, J.P. (INRIA, Paris, France). Personal communication."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1016\/j.jss.2010.09.016","article-title":"One-time signature scheme from syndrome decoding over generic error-correcting codes","volume":"84","author":"Barreto","year":"2011","journal-title":"J. Syst. Softw."},{"key":"ref_26","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. Cryptol."},{"key":"ref_27","first-page":"20","article-title":"Combinatorial generation","volume":"Volume 11","author":"Ruskey","year":"2003","journal-title":"Preliminary Working Draft"},{"key":"ref_28","first-page":"31","article-title":"Attacking and Defending the McEliece Cryptosystem","volume":"Volume 5299","author":"Buchmann","year":"2008","journal-title":"PQCrypto"},{"key":"ref_29","first-page":"107","article-title":"Decoding Random Linear Codes in O(20.054n)","volume":"Volume 7073","author":"Lee","year":"2011","journal-title":"ASIACRYPT"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"May, A., and Ozerov, I. (2015). On computing nearest neighbors with applications to decoding of binary linear codes. Advances in Cryptology\u2014EUROCRYPT 2015, Springer.","DOI":"10.1007\/978-3-662-46800-5_9"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1109\/TIT.1962.1057777","article-title":"The use of information sets in decoding cyclic codes","volume":"8","author":"Prange","year":"1962","journal-title":"IRE Trans. Inf. Theory"},{"key":"ref_32","first-page":"106","article-title":"A method for finding codewords of small weight","volume":"Volume 388","author":"Cohen","year":"1988","journal-title":"Coding Theory and Applications"},{"key":"ref_33","unstructured":"Lai, X., Yung, M., and Lin, D. (2011). Quasi-Dyadic CFS Signatures. Information Security and Cryptology: 6th International Conference, Springer."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/978-3-540-73074-3_18","article-title":"On Kabatianskii-Krouk-Smeets Signatures","volume":"Volume 4547","author":"Carlet","year":"2007","journal-title":"International Workshop on the Arithmetic of Finite Fields"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Yang, B.Y. (2011). An Efficient Attack on All Concrete KKS Proposals. International Workshop on Post-Quantum Cryptography, Springer.","DOI":"10.1007\/978-3-642-25405-5"},{"key":"ref_36","unstructured":"Melchor, C.A., Gaborit, P., and Schrek, J. (2011, January 16\u201320). A new zero-knowledge code based identification scheme with reduced communication. Proceedings of the 2011 IEEE Information Theory Workshop, Paraty, Brazil."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Gaborit, P., and Schrek, J. (2012, January 1\u20136). Efficient code-based one-time signature from automorphism groups with syndrome compatibility. Proceedings of the 2012 IEEE International Symposium on Information Theory Proceedings, Cambridge, MA, USA.","DOI":"10.1109\/ISIT.2012.6283646"},{"key":"ref_38","first-page":"268","article-title":"On a CCA2-secure variant of McEliece in the standard model","volume":"2012","author":"Persichetti","year":"2012","journal-title":"IACR Cryptol. ePrint Arch."}],"container-title":["Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2410-387X\/2\/4\/30\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:25:10Z","timestamp":1760196310000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2410-387X\/2\/4\/30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,12]]},"references-count":38,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2018,12]]}},"alternative-id":["cryptography2040030"],"URL":"https:\/\/doi.org\/10.3390\/cryptography2040030","relation":{},"ISSN":["2410-387X"],"issn-type":[{"value":"2410-387X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,10,12]]}}}