RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Probl. Peredachi Inf.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Probl. Peredachi Inf., 2002, Volume 38, Issue 3, Pages 83–93 (Mi ppi1319)  

This article is cited in 25 scientific papers (total in 25 papers)

Information Protection

New Technique for Decoding Codes in the Rank Metric and Its Cryptography Applications

A. V. Urivskii, T. Johansson


Abstract: We present two new algorithms for decoding an arbitrary $(n,k)$ linear rank distance code over $GF(q^N)$. These algorithms correct errors of rank $r$ in $O((Nr)^3q^{(r-1)(k+1)})$ and $O((k+r)^3r^3q^{(r-1)(N-r)})$ operations in $GF(q)$ respectively. The algorithms give one of the most efficient attacks on public-key cryptosystems based on rank codes, as well as on the authentication scheme suggested by Chen.

Full text: PDF file (2440 kB)
References: PDF file   HTML file

English version:
Problems of Information Transmission, 2002, 38:3, 237–246

Bibliographic databases:

UDC: 621.391.15
Received: 20.11.2001

Citation: A. V. Urivskii, T. Johansson, “New Technique for Decoding Codes in the Rank Metric and Its Cryptography Applications”, Probl. Peredachi Inf., 38:3 (2002), 83–93; Problems Inform. Transmission, 38:3 (2002), 237–246

Citation in format AMSBIB
\Bibitem{OurJoh02}
\by A.~V.~Urivskii, T.~Johansson
\paper New Technique for Decoding Codes in the Rank Metric and Its Cryptography Applications
\jour Probl. Peredachi Inf.
\yr 2002
\vol 38
\issue 3
\pages 83--93
\mathnet{http://mi.mathnet.ru/ppi1319}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2101270}
\zmath{https://zbmath.org/?q=an:1026.94023}
\transl
\jour Problems Inform. Transmission
\yr 2002
\vol 38
\issue 3
\pages 237--246
\crossref{https://doi.org/10.1023/A:1020369320078}


Linking options:
  • http://mi.mathnet.ru/eng/ppi1319
  • http://mi.mathnet.ru/eng/ppi/v38/i3/p83

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. Gabidulin E.M., Ourivski A.V., Honary B., Ammar B., “Reducible rank codes and their applications to cryptography”, IEEE Trans. Inform. Theory, 49:12 (2003), 3289–3293  crossref  mathscinet  zmath  isi
    2. Berger T., Loidreau P., “Designing an efficient and secure public-key cryptosystem based on reducible rank codes”, Progress in cryptology—INDOCRYPT 2004, Lecture Notes in Comput. Sci., 3348, Springer, Berlin, 2004, 218–229  crossref  mathscinet  zmath  isi
    3. Overbeck R., “A new structural attack for GPT and variant”, Progress in cryptology—Mycrypt 2005, Lecture Notes in Comput. Sci., 3715, Springer, Berlin, 2005, 50–63  crossref  zmath  isi
    4. Loidreau P., “A Welch-Berlekamp like algorithm for decoding Gabidulin codes”, Coding and cryptography, Lecture Notes in Comput. Sci., 3969, Springer, Berlin, 2006, 36–45  crossref  mathscinet  zmath  isi
    5. Overbeck R., “Extending Gibson's attacks on the GPT cryptosystem”, Coding and cryptography, Lecture Notes in Comput. Sci., 3969, Springer, Berlin, 2006, 178–188  crossref  mathscinet  zmath  isi
    6. Faure C., Loidreau P., “A new public-key cryptosystem based on the problem of reconstructing $p$-polynomials”, Coding and cryptography, Lecture Notes in Comput. Sci., 3969, Springer, Berlin, 2006, 304–315  crossref  mathscinet  zmath  isi
    7. Gadouleau M., Yan Zh., “Security of the GPT-type cryptosystems”, 2006 IEEE International Symposium on Information Theory, 2006, 724–728  crossref  isi
    8. Gabidulin E.M., Loidreau P., “Properties of subspace subcodes of Gabidulin codes”, Adv. Math. Commun., 2:2 (2008), 147–157  crossref  mathscinet  zmath  isi  elib
    9. Overbeck R., “Structural attacks for public key cryptosystems based on Gabidulin codes”, J. Cryptology, 21:2 (2008), 280–301  crossref  mathscinet  zmath  isi  elib
    10. Gabidulin E.M., Rashwan H., Honary B., “On improving security of GPT cryptosystems”, 2009 IEEE International Symposium on Information Theory, 2009, 1110–1114  crossref  isi
    11. Rashwan H., Gabidulin E.M., Honary B., “A Smart Approach for GPT Cryptosystem Based on Rank Codes”, 2010 IEEE International Symposium on Information Theory, IEEE International Symposium on Information Theory, 2010, 2463–2467  isi
    12. Loidreau P., “Designing a Rank Metric Based McEliece Cryptosystem”, Post-Quantum Cryptography, Proceedings, Lecture Notes in Computer Science, 6061, 2010, 142–152  crossref  mathscinet  zmath  isi
    13. Faugere J.-Ch., El Din M.S., Spaenlehauer P.-J., “Grobner bases of bihomogeneous ideals generated by polynomials of bidegree (1,1): Algorithms and complexity”, J Symbolic Comput, 46:4 (2011), 406–437  crossref  mathscinet  zmath  isi
    14. Rashwan H., Gabidulin E.M., Honary B., “Security of the GPT cryptosystem and its applications to cryptography”, Security and Communication Networks, 4:8 (2011), 937–946  crossref  isi
    15. Gaborit Ph. Schrek J. Zemor G., “Full Cryptanalysis of the Chen Identification Protocol”, Post-Quantum Cryptography, Lecture Notes in Computer Science, 7071, ed. Yang B., Springer-Verlag Berlin, 2011, 35–50  crossref  mathscinet  zmath  isi
    16. Tan V.Y.F. Balzano L. Draper S.C., “Rank Minimization Over Finite Fields: Fundamental Limits and Coding-Theoretic Interpretations”, IEEE Trans. Inf. Theory, 58:4 (2012), 2018–2039  crossref  mathscinet  isi  elib
    17. E. M. Gabidulin, N. I. Pilipchuk, B. Honary, H. Rashwan, “Information security in a random network coding network”, Problems Inform. Transmission, 49:2 (2013), 179–191  mathnet  crossref  isi
    18. Loidreau P., “Asymptotic Behaviour of Codes in Rank Metric Over Finite Fields”, Des. Codes Cryptogr., 71:1 (2014), 105–118  crossref  mathscinet  zmath  isi  elib
    19. Gaborit Ph. Ruatta O. Schrek J. Zemor G., “Ranksign: An Efficient Signature Algorithm Based on the Rank Metric”, Post-Quantum Cryptography, Pqcrypto 2014, Lecture Notes in Computer Science, 8772, ed. Mosca M., Springer-Verlag Berlin, 2014, 88–107  crossref  mathscinet  zmath  isi
    20. Gaborit Ph. Ruatta O. Schrek J. Zemor G., “New Results For Rank-Based Cryptography”, Progress in Cryptology - Africacrypt 2014, Lecture Notes in Computer Science, 8469, ed. Pointcheval D. Vergnaud D., Springer-Verlag Berlin, 2014, 1–12  crossref  mathscinet  zmath  isi
    21. Gaborit Ph., Ruatta O., Schrek J., “on the Complexity of the Rank Syndrome Decoding Problem”, IEEE Trans. Inf. Theory, 62:2 (2016), 1006–1019  crossref  mathscinet  isi  elib
    22. Horlemann-Trautmann A.-L. Marshall K. Rosenthal J., “Extension of Overbeck'S Attack For Gabidulin-Based Cryptosystems”, Designs Codes Cryptogr., 86:2, SI (2018), 319–340  crossref  mathscinet  zmath  isi  scopus
    23. Lau Terry Shue Chien Tan Ch.H., “Key Recovery Attack on Mcnie Based on Low Rank Parity Check Codes and Its Reparation”, Advances in Information and Computer Security, Iwsec 2018, Lecture Notes in Computer Science, 11049, ed. Inomata A. Yasuda K., Springer International Publishing Ag, 2018, 19–34  crossref  zmath  isi  scopus
    24. Kim J.-L. Galvez L. Kim Y.-S. Lee N., “A New Lrpc-Kronecker Product Codes Based Public-Key Cryptography”, Apkc'18: Proceedings of the 5Th Acm Asia Public-Key Cryptography Workshop, Assoc Computing Machinery, 2018, 25–33  crossref  isi  scopus
    25. Aragon N. Gaborit Ph. Hauteville A. Tillich J.-P., “A New Algorithm For Solving the Rank Syndrome Decoding Problem”, 2018 IEEE International Symposium on Information Theory (Isit), IEEE International Symposium on Information Theory, IEEE, 2018, 2421–2425  isi
  • Проблемы передачи информации Problems of Information Transmission
    Number of views:
    This page:552
    Full text:155
    References:46

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019