A Multi-Signature Scheme based on Coding Theory

<!DOCTYPE html> <html lang="en" dir="ltr"> <head>  <script async src="https://www.googletagmanager.com/gtag/js?id=G-P63WKM1TM1"></script> <script> window.dataLayer = window.dataLayer || []; function gtag(){dataLayer.push(arguments);} gtag('js', new Date()); gtag('config', 'G-P63WKM1TM1'); </script>  <script type="text/javascript" > (function(m,e,t,r,i,k,a){m[i]=m[i]||function(){(m[i].a=m[i].a||[]).push(arguments)}; m[i].l=1*new Date(); for (var j = 0; j < document.scripts.length; j++) {if (document.scripts[j].src === r) { return; }} k=e.createElement(t),a=e.getElementsByTagName(t)[0],k.async=1,k.src=r,a.parentNode.insertBefore(k,a)}) (window, document, "script", "https://mc.yandex.ru/metrika/tag.js", "ym"); ym(55165297, "init", { clickmap:false, trackLinks:true, accurateTrackBounce:true, webvisor:false }); </script> <noscript><div><img src="https://mc.yandex.ru/watch/55165297" style="position:absolute; left:-9999px;" alt="" /></div></noscript>   <script> var _paq = window._paq = window._paq || []; /* tracker methods like "setCustomDimension" should be called before "trackPageView" */ _paq.push(['trackPageView']); _paq.push(['enableLinkTracking']); (function() { var u="//matomo.waset.org/"; _paq.push(['setTrackerUrl', u+'matomo.php']); _paq.push(['setSiteId', '2']); var d=document, g=d.createElement('script'), s=d.getElementsByTagName('script')[0]; g.async=true; g.src=u+'matomo.js'; s.parentNode.insertBefore(g,s); })(); </script>  <title>A Multi-Signature Scheme based on Coding Theory</title> <meta name="description" content="A Multi-Signature Scheme based on Coding Theory"> <meta name="keywords" content="Post-quantum cryptography, Coding-based cryptography,Digital signature, Multisignature scheme."> <meta name="viewport" content="width=device-width, initial-scale=1, minimum-scale=1, maximum-scale=1, user-scalable=no"> <meta charset="utf-8"> <meta name="citation_title" content="A Multi-Signature Scheme based on Coding Theory"> <meta name="citation_author" content="Mohammed Meziani"> <meta name="citation_author" content="Pierre-Louis Cayrel"> <meta name="citation_publication_date" content="2010/03/23"> <meta name="citation_journal_title" content="International Journal of Computer and Information Engineering"> <meta name="citation_volume" content="4"> <meta name="citation_issue" content="3"> <meta name="citation_firstpage" content="405"> <meta name="citation_lastpage" content="411"> <meta name="citation_pdf_url" content="https://publications.waset.org/5409/pdf"> <link href="https://cdn.waset.org/favicon.ico" type="image/x-icon" rel="shortcut icon"> <link href="https://cdn.waset.org/static/plugins/bootstrap-4.2.1/css/bootstrap.min.css" rel="stylesheet"> <link href="https://cdn.waset.org/static/plugins/fontawesome/css/all.min.css" rel="stylesheet"> <link href="https://cdn.waset.org/static/css/site.css?v=150220211555" rel="stylesheet"> </head> <body> <header> <div class="container"> <nav class="navbar navbar-expand-lg navbar-light"> <a class="navbar-brand" href="https://waset.org"> <img src="https://cdn.waset.org/static/images/wasetc.png" alt="Open Science Research Excellence" title="Open Science Research Excellence" /> </a> <button class="d-block d-lg-none navbar-toggler ml-auto" type="button" data-toggle="collapse" data-target="#navbarMenu" aria-controls="navbarMenu" aria-expanded="false" aria-label="Toggle navigation"> <span class="navbar-toggler-icon"></span> </button> <div class="w-100"> <div class="d-none d-lg-flex flex-row-reverse"> <form method="get" action="https://waset.org/search" class="form-inline my-2 my-lg-0"> <input class="form-control mr-sm-2" type="search" placeholder="Search Conferences" value="" name="q" aria-label="Search"> <button class="btn btn-light my-2 my-sm-0" type="submit"><i class="fas fa-search"></i></button> </form> </div> <div class="collapse navbar-collapse mt-1" id="navbarMenu"> <ul class="navbar-nav ml-auto align-items-center" id="mainNavMenu"> <li class="nav-item"> <a class="nav-link" href="https://waset.org/conferences" title="Conferences in 2025/2026/2027">Conferences</a> </li> <li class="nav-item"> <a class="nav-link" href="https://waset.org/disciplines" title="Disciplines">Disciplines</a> </li> <li class="nav-item"> <a class="nav-link" href="https://waset.org/committees" rel="nofollow">Committees</a> </li> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdownPublications" role="button" data-toggle="dropdown" aria-haspopup="true" aria-expanded="false"> Publications </a> <div class="dropdown-menu" aria-labelledby="navbarDropdownPublications"> <a class="dropdown-item" href="https://publications.waset.org/abstracts">Abstracts</a> <a class="dropdown-item" href="https://publications.waset.org">Periodicals</a> <a class="dropdown-item" href="https://publications.waset.org/archive">Archive</a> </div> </li> <li class="nav-item"> <a class="nav-link" href="https://waset.org/page/support" title="Support">Support</a> </li> </ul> </div> </div> </nav> </div> </header> <main> <div class="container mt-4"> <div class="row"> <div class="col-md-9 mx-auto"> <form method="get" action="https://publications.waset.org/search"> <div id="custom-search-input"> <div class="input-group"> <i class="fas fa-search"></i> <input type="text" class="search-query" name="q" placeholder="Author, Title, Abstract, Keywords" value=""> <input type="submit" class="btn_search" value="Search"> </div> </div> </form> </div> </div> <div class="row mt-3"> <div class="col-sm-3"> <div class="card"> <div class="card-body"><strong>Commenced</strong> in January 2007</div> </div> </div> <div class="col-sm-3"> <div class="card"> <div class="card-body"><strong>Frequency:</strong> Monthly</div> </div> </div> <div class="col-sm-3"> <div class="card"> <div class="card-body"><strong>Edition:</strong> International</div> </div> </div> <div class="col-sm-3"> <div class="card"> <div class="card-body"><strong>Paper Count:</strong> 33176</div> </div> </div> </div> <div class="card publication-listing mt-3 mb-3"> <h5 class="card-header" style="font-size:.9rem">A Multi-Signature Scheme based on Coding Theory</h5> <div class="card-body"> <p class="card-text"><strong>Authors:</strong> <a href="https://publications.waset.org/search?q=Mohammed%20Meziani">Mohammed Meziani</a>, <a href="https://publications.waset.org/search?q=Pierre-Louis%20Cayrel"> Pierre-Louis Cayrel</a> </p> <p class="card-text"><strong>Abstract:</strong></p> In this paper we propose two first non-generic constructions of multisignature scheme based on coding theory. The first system make use of the CFS signature scheme and is secure in random oracle while the second scheme is based on the KKS construction and is a few times. The security of our construction relies on a difficult problems in coding theory: The Syndrome Decoding problem which has been proved NP-complete [4]. <iframe src="https://publications.waset.org/5409.pdf" style="width:100%; height:400px;" frameborder="0"></iframe> <p class="card-text"><strong>Keywords:</strong> <a href="https://publications.waset.org/search?q=Post-quantum%20cryptography" title="Post-quantum cryptography">Post-quantum cryptography</a>, <a href="https://publications.waset.org/search?q=Coding-based%20cryptography" title=" Coding-based cryptography"> Coding-based cryptography</a>, <a href="https://publications.waset.org/search?q=Digital%20signature" title="Digital signature">Digital signature</a>, <a href="https://publications.waset.org/search?q=Multisignature%20scheme." title=" Multisignature scheme."> Multisignature scheme.</a> </p> <p class="card-text"><strong>Digital Object Identifier (DOI):</strong> <a href="https://doi.org/10.5281/zenodo.1060998" target="_blank">doi.org/10.5281/zenodo.1060998</a> </p> <a href="https://publications.waset.org/5409/a-multi-signature-scheme-based-on-coding-theory" class="btn btn-primary btn-sm">Procedia</a> <a href="https://publications.waset.org/5409/apa" target="_blank" rel="nofollow" class="btn btn-primary btn-sm">APA</a> <a href="https://publications.waset.org/5409/bibtex" target="_blank" rel="nofollow" class="btn btn-primary btn-sm">BibTeX</a> <a href="https://publications.waset.org/5409/chicago" target="_blank" rel="nofollow" class="btn btn-primary btn-sm">Chicago</a> <a href="https://publications.waset.org/5409/endnote" target="_blank" rel="nofollow" class="btn btn-primary btn-sm">EndNote</a> <a href="https://publications.waset.org/5409/harvard" target="_blank" rel="nofollow" class="btn btn-primary btn-sm">Harvard</a> <a href="https://publications.waset.org/5409/json" target="_blank" rel="nofollow" class="btn btn-primary btn-sm">JSON</a> <a href="https://publications.waset.org/5409/mla" target="_blank" rel="nofollow" class="btn btn-primary btn-sm">MLA</a> <a href="https://publications.waset.org/5409/ris" target="_blank" rel="nofollow" class="btn btn-primary btn-sm">RIS</a> <a href="https://publications.waset.org/5409/xml" target="_blank" rel="nofollow" class="btn btn-primary btn-sm">XML</a> <a href="https://publications.waset.org/5409/iso690" target="_blank" rel="nofollow" class="btn btn-primary btn-sm">ISO 690</a> <a href="https://publications.waset.org/5409.pdf" target="_blank" class="btn btn-primary btn-sm">PDF</a> <span class="bg-info text-light px-1 py-1 float-right rounded"> Downloads <span class="badge badge-light">1894</span> </span> <p class="card-text"><strong>References:</strong></p> <br>[1] S. Barg. Some New NP-Complete Coding Problems. Probl. Peredachi Inf., 30:23-28, 1994. <br>[2] M. Bellare and G. Neven. Multi-signatures in the plain public-key model and a general forking lemma. In CCS -06: Proc. of the 13th ACM conference on Computer and communications security, pages 390-399. ACM, 2006. <br>[3] T. P. Berger, P.-L. Cayrel, P. Gaborit, and A. Otmani. Reducing key length of the McEliece cryptosystem. In Progress in Cryptology - Africacrypt-2009, LNCS, pages 77-97. Springer, 2009. <br>[4] E. Berlekamp, R. McEliece, and H. van Tilborg. On the inherent intractability of certain coding problems. IEEE Transactions on Information Theory, 24(3):384-386, 1978. <br>[5] D. J. Bernstein, T. Lange, and C. Peters. Attacking and defending the McEliece cryptosystem. Cryptology ePrint Archive, Report 2008/318, 2008. http://eprint.iacr.org/. <br>[6] D. Boneh and M. Franklin. Identity-based encryption from the weil pairing. In CRYPTO -01: Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, pages 213-229. Springer, 2001. <br>[7] D. Boneh, C. Gentry, B. Lynn, and H. Shacham. Aggregate and verifiably encrypted signatures from bilinear maps. In EUROCRYPT, pages 416-432. Springer, 2003. <br>[8] P.L. Cayrel, A. Otmani, and D. Vergnaud. On Kabatianskii-Krouk- Smeets Signatures. In Proceedings of the first International Workshop on the Arithmetic of Finite Fields (WAIFI 2007), Springer, pages 237-251, Madrid, Spain, June 21-22 2007. <br>[9] N. Courtois, M. Finiasz, and N. Sendrier. How to achieve a McEliecebased digital signature scheme. In Advances in Cryptology - Asiacrypt- 2001, volume 2248 of LNCS, pages 157-174, Gold Coast, Australia, 2001. Springer. <br>[10] L. Dallot. Towards a concrete security proof of courtois, finiasz and sendrier signature scheme. Proceedings of WEWoRC 2007, Bochum, GermanyÔÇ× 2007. http://users.info.unicaen.fr/~ldallot/download/articles/ CFSProof-dallot.pdf. <br>[11] M. Finiasz. Nouvelles constructions utilisant des codes correcteurs d-erreurs en cryptographie ├á clef publique. PhD thesis, INRIA-Ecole polytechnique, October 2004. <br>[12] M. Finiasz and N. Sendrier. Security bounds for the design of codebased cryptosystems. In to appear in Advances in Cryptology - Asiacrypt-2009, 2009. http://eprint.iacr.org/2009/414.pdf. <br>[13] T. Hardjono and Y. Zheng. A practical digital multisignature scheme based on discrete logarithms (extended abstract). In in AUSCRYPT-92, pages 122-132. Springer, 1993. <br>[14] L. Harn and T. Kiesler. Rsa blocking and multisignature schemes with no bit expansion. Electron Letters, 26(18):1490.1491, August 1990. <br>[15] L. Harn and T. Kiesler. New scheme for digital multisignature. Electron Letters, 25(15):1002.1003, July 1989. <br>[16] K. Itakura and K. Nakamura. New scheme for digital multisignature. NEC Research and Development, 71:1-8, October 1983. <br>[17] G. Kabatianskii, E.Krouk, and B. J. M. Smeets. A digital signature scheme based on random error-correcting codes. IMA Int. Conf., Springer LNCS 1355:161-167, 1997. <br>[18] K. Kawauchi and M. Tada. On the exact security of multi-signature schemes based on rsa. In ACISP 2003, volume 2727. <br>[19] K. Kawauchi and M. Tada. On the security and the efficiency of multisignature schemes based on a trapdoor one-way permutation. IEICE Trans. Fundam. Electron. Commun. Comput. Sci., E88-A(5):1274-1282, 2005. <br>[20] Y. Komano, K. Ohta, A. Shimbo, and S. Kawamura. Formal security model of multisignatures. In ISC, pages 146-160, 2006. <br>[21] E. Liberty and S. W. Zucker. The mailman algorithm: A note on matrixvector multiplication. Inf. Process. Lett., 109(3):179-182, 2009. <br>[22] R.J. McEliece. A public-key cryptosystem based on algebraic coding theory. Jpl dsn progress report 42-44 , pages 114-116, 1978. <br>[23] S. Micali, K. Ohta, and L. Reyzin. Accountable-subgroup multisignatures: extended abstract. In ACM Conference on Computer and Communications Security, pages 245-254, 2001. <br>[24] R. Misoczki and P. S. L. M. Barreto. Compact mceliece keys from goppa codes. Preprint, 2009. http://eprint.iacr.org/2009/187.pdf. <br>[25] S. Mitomi and A. Miyaji. A general model of multisignature schemes with message flexibility, order flexibility, and order verifiability. IEICE Trans. Fundam., E-84-A(5):2488-2499, 2001. <br>[26] T. Okamoto. A digital multisignature scheme using bijective public-key cryptosystems. ACM Trans. Comput. Syst., 6(4):432-441, 1988. <br>[27] O.Kazuo and O. Tatsuaki. A digital multisignature scheme based on the fiat-shamir scheme. In ASIACRYPT -91: Proc. of the International Conference on the Theory and Applications of Cryptology, pages 139- 148. Springer, 1993. <br>[28] A. Shamir. Identity-based cryptosystems and signature schemes. In Proceedings of CRYPTO 84 on Advances in cryptology, pages 47-53. Springer-Verlag., 1984. <br>[29] P. W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26:1484-1509, 1997. <br>[30] L. Wang, E. Okamoto, Y. Miao, T. Okamoto, and H. Doi. Id-based series-parallel multisignature schemes for multi-messages from bilinear maps. In WCC, pages 291-303, 2005. </div> </div> </div> </main> <footer> <div id="infolinks" class="pt-3 pb-2"> <div class="container"> <div style="background-color:#f5f5f5;" class="p-3"> <div class="row"> <div class="col-md-2"> <ul class="list-unstyled"> About <li><a href="https://waset.org/page/support">About Us</a></li> <li><a href="https://waset.org/page/support#legal-information">Legal</a></li> <li><a target="_blank" rel="nofollow" href="https://publications.waset.org/static/files/WASET-16th-foundational-anniversary.pdf">WASET celebrates its 16th foundational anniversary</a></li> </ul> </div> <div class="col-md-2"> <ul class="list-unstyled"> Account <li><a href="https://waset.org/profile">My Account</a></li> </ul> </div> <div class="col-md-2"> <ul class="list-unstyled"> Explore <li><a href="https://waset.org/disciplines">Disciplines</a></li> <li><a href="https://waset.org/conferences">Conferences</a></li> <li><a href="https://waset.org/conference-programs">Conference Program</a></li> <li><a href="https://waset.org/committees">Committees</a></li> <li><a href="https://publications.waset.org">Publications</a></li> </ul> </div> <div class="col-md-2"> <ul class="list-unstyled"> Research <li><a href="https://publications.waset.org/abstracts">Abstracts</a></li> <li><a href="https://publications.waset.org">Periodicals</a></li> <li><a href="https://publications.waset.org/archive">Archive</a></li> </ul> </div> <div class="col-md-2"> <ul class="list-unstyled"> Open Science <li><a target="_blank" rel="nofollow" href="https://publications.waset.org/static/files/Open-Science-Philosophy.pdf">Open Science Philosophy</a></li> <li><a target="_blank" rel="nofollow" href="https://publications.waset.org/static/files/Open-Science-Award.pdf">Open Science Award</a></li> <li><a target="_blank" rel="nofollow" href="https://publications.waset.org/static/files/Open-Society-Open-Science-and-Open-Innovation.pdf">Open Innovation</a></li> <li><a target="_blank" rel="nofollow" href="https://publications.waset.org/static/files/Postdoctoral-Fellowship-Award.pdf">Postdoctoral Fellowship Award</a></li> <li><a target="_blank" rel="nofollow" href="https://publications.waset.org/static/files/Scholarly-Research-Review.pdf">Scholarly Research Review</a></li> </ul> </div> <div class="col-md-2"> <ul class="list-unstyled"> Support <li><a href="https://waset.org/page/support">Support</a></li> <li><a href="https://waset.org/profile/messages/create">Contact Us</a></li> <li><a href="https://waset.org/profile/messages/create">Report Abuse</a></li> </ul> </div> </div> </div> </div> </div> <div class="container text-center"> <hr style="margin-top:0;margin-bottom:.3rem;"> <a href="https://creativecommons.org/licenses/by/4.0/" target="_blank" class="text-muted small">Creative Commons Attribution 4.0 International License</a> <div id="copy" class="mt-2">© 2025 World Academy of Science, Engineering and Technology</div> </div> </footer> <a href="javascript:" id="return-to-top"><i class="fas fa-arrow-up"></i></a> <div class="modal" id="modal-template"> <div class="modal-dialog"> <div class="modal-content"> <div class="row m-0 mt-1"> <div class="col-md-12"> <button type="button" class="close" data-dismiss="modal" aria-label="Close"><span aria-hidden="true">×</span></button> </div> </div> <div class="modal-body"></div> </div> </div> </div> <script src="https://cdn.waset.org/static/plugins/jquery-3.3.1.min.js"></script> <script src="https://cdn.waset.org/static/plugins/bootstrap-4.2.1/js/bootstrap.bundle.min.js"></script> <script src="https://cdn.waset.org/static/js/site.js?v=150220211556"></script> <script> jQuery(document).ready(function() { /*jQuery.get("https://publications.waset.org/xhr/user-menu", function (response) { jQuery('#mainNavMenu').append(response); });*/ jQuery.get({ url: "https://publications.waset.org/xhr/user-menu", cache: false }).then(function(response){ jQuery('#mainNavMenu').append(response); }); }); </script> </body> </html>

CINXE.COM

A Multi-Signature Scheme based on Coding Theory