research-article

A New LRPC-Kronecker Product Codes Based Public-Key Cryptography

Authors:

Nari LeeAuthors Info & Claims

APKC '18: Proceedings of the 5th ACM on ASIA Public-Key Cryptography Workshop

Pages 25 - 33

https://doi.org/10.1145/3197507.3197513

Published: 23 May 2018 Publication History

Abstract

In this paper, we propose a variant of the McEliece cryptosystem, called LRPC-Kronecker cryptosystem. LRPC-Kronecker product codes are LRPC codes with higher rank and better error-correction capability. For this, we introduce a new decoding algorithm using blocks which has lower decoding complexity and higher error-correction capability compared to those of the LRPC decoding algorithm. Furthermore, it is shown that this scheme is secure against existing attacks.

References

[1]

N. Aragon, P. Gaborit, A. Hauteville, and J. P. Tillich. 2017. Improvement of Generic Attacks on the Rank Syndrome Decoding Problem. (2017). https://hal. archives-ouvertes.fr/hal-01618464 working paper or preprint. A New LRPC-Kronecker Product Codes Based Public-Key Cryptography APKC'18, June 4, 2018, Incheon, Republic of Korea

[2]

M. Baldi and F. Chiaraluce. 2007. Cryptanalysis of a new instance of McEliece cryptosystem based on QC-LDPC Codes. In 2007 IEEE International Symposium on Information Theory. 2591--2595.

[3]

M. Baldi, F. Chiaraluce, R. Garello, and F. Mininni. 2007. Quasi-Cyclic Low-Density Parity-Check Codes in the McEliece Cryptosystem. In 2007 IEEE International Conference on Communications. 951--956.

[4]

A. Becker, A. Joux, A. May, and A. Meurer. 2012. Decoding random binary linear codes in 2n/20: How 1 + 1 = 0 improves information set decoding. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 520--536.

Digital Library

[5]

T. Berger and P. Loidreau. 2005. Designing an Efficient and Secure Public-Key Cryptosystem Based on Reducible Rank Codes. In Progress in Cryptology - INDOCRYPT 2004, A. Canteaut and K. Viswanathan (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 218--229.

Digital Library

[6]

T. P. Berger and P. Loidreau. 2005. How to Mask the Structure of Codes for a Cryptographic Use. Designs, Codes and Cryptography 35, 1 (01 Apr 2005), 63--79.

Digital Library

[7]

E. Berlekamp, R. McEliece, and H. van Tilborg. 1978. On the inherent intractability of certain coding problems (Corresp.). IEEE Transactions on Information Theory 24, 3 (May 1978), 384--386.

Digital Library

[8]

D. Bernstein, T. Lange, and C. Peters. 2008. Attacking and Defending the McEliece Cryptosystem. In Proceedings of the 2Nd International Workshop on Post-Quantum Cryptography (PQCrypto '08). Springer-Verlag, Berlin, Heidelberg, 31--46.

Digital Library

[9]

J. Buss, G. Frandsen, and J. Shallit. 1999. The Computational Complexity of Some Problems of Linear Algebra. J. Comput. System Sci. 58, 3 (1999), 572 -- 596.

Digital Library

[10]

A. Canteaut and F. Chabaud. 1998. A new algorithm for finding minimum-weight words in a linear code: application to McEliece's cryptosystem and to narrowsense BCH codes of length 511. IEEE Transactions on Information Theory 44, 1 (Jan 1998), 367--378.

Digital Library

[11]

F. Chabaud and J. Stern. 1996. The cryptographic security of the syndrome decoding problem for rank distance codes. In Advances in Cryptology -- ASIACRYPT '96, K. Kim and T. Matsumoto (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 368--381.

Digital Library

[12]

I. V. Chizhov and M. A. Borodin. 2013. The failure of McEliece PKC based on Reed-Muller codes. Prikl. Diskr. Mat. Suppl. 6 (2013), 48--49.

[13]

A. Couvreur, I. Márquez-Corbella, and R. Pellikaan. 2014. A polynomial time attack against algebraic geometry code based public key cryptosystems. In 2014 IEEE International Symposium on Information Theory. 1446--1450.

[14]

P. H. Delsarte. 1978. Bilinear Forms over a finite field, with applications to coding theory. Journal of Combinatorial Theory, Series A 25, 3 (1978), 226--241.

[15]

J. C. Faugère, M. S. El Din, and P. J. Spaenlehauer. 2010. Computing Loci of Rank Defects of Linear Matrices Using Gröbner Bases and Applications to Cryptology. In Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation (ISSAC '10). ACM, New York, NY, USA, 257--264.

Digital Library

[16]

J. C. Faugère, F. Levy-dit Vehel, and L. Perret. 2008. Cryptanalysis of MinRank. In Advances in Cryptology -- CRYPTO 2008, David Wagner (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 280--296.

Digital Library

[17]

J. C. Faugère, A. Otmani, L. Perret, F. de Portzamparc, and J. P. Tillich. 2014. Structural weakness of compact variants of the McEliece cryptosystem. In 2014 IEEE International Symposium on Information Theory. 1717--1721.

[18]

J. C. Faugère, A. Otmani, L. Perret, F. de Portzamparc, and J. P. Tillich. 2016. Structural cryptanalysis of McEliece schemes with compact keys. Designs, Codes and Cryptography 79, 1 (01 Apr 2016), 87--112.

Digital Library

[19]

C. Faure and L. Minder. 2008. Cryptanalysis of the McEliece cryptosystem over hyperelliptic codes. In Proceedings of the eleventh International Workshop on Algebraic and Combinatorial Coding Theory. 99--107.

Digital Library

[20]

E. Fujisaki and T. Okamoto. 2013. Secure Integration of Asymmetric and Symmetric Encryption Schemes. Journal of Cryptology 26, 1 (2013), 80--101.

Digital Library

[21]

E. M. Gabidulin. 1985. Theory of codes with maximum rank distance. Problemy Peredachi Informatsii 21 (1985), 1--12.

[22]

E. M. Gabidulin, A. V. Ourivski, B. Honary, and B. Ammar. 2003. Reducible rank codes and their applications to cryptography. IEEE Transactions on Information Theory 49, 12 (2003), 3289--3293.

Digital Library

[23]

E. M. Gabidulin, A. V. Paramonov, and O. V. Tretjakov. 1991. Ideals over a Noncommutative Ring and Their Application in Cryptology. In Proceedings of the 10th Annual International Conference on Theory and Application of Cryptographic Techniques (EUROCRYPT'91). Springer-Verlag, Berlin, Heidelberg, 482--489.

Digital Library

[24]

P. Gaborit, G. Murat, O. Ruatta, and G. Zémor. 2013. Low Rank Parity Check codes and their application to cryptography. In The Proceedings of Workshop on Coding and Cryptography (WCC) 2013. 168--180.

[25]

P. Gaborit, O. Ruatta, and J. Schrek. 2016. On the Complexity of the Rank Syndrome Decoding Problem. IEEE Transactions on Information Theory 62, 2 (Feb 2016), 1006--1019.

[26]

P. Gaborit, O. Ruatta, J. Schrek, and G. Zémor. 2014. New Results for Rank-Based Cryptography. In Progress in Cryptology -- AFRICACRYPT 2014, D. Pointcheval and D. Vergnaud (Eds.). Springer International Publishing, Cham, 1--12.

[27]

P. Gaborit and G. Zémor. 2016. On the Hardness of the Decoding and the Minimum Distance Problems for Rank Codes. IEEE Transactions on Information Theory 62, 12 (Dec 2016), 7245--7252.

Digital Library

[28]

A. Hauteville and J. P. Tillich. 2015. New algorithms for decoding in the rank metric and an attack on the LRPC cryptosystem. In 2015 IEEE International Symposium on Information Theory (ISIT). 2747--2751.

[29]

J. Hoffstein, J. Pipher, and J. H. Silverman. 1998. NTRU: A ring-based public key cryptosystem. In Algorithmic Number Theory, J. P. Buhler (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 267--288.

Digital Library

[30]

H. Janwa and O. Moreno. 1996. McEliece public key cryptosystems using algebraic-geometric codes. Designs, Codes and Cryptography 8, 3 (Jun 1996), 293--307.

Digital Library

[31]

K. Kobara and H. Imai. 2001. Semantically Secure McEliece Public-Key Cryptosystems -Conversions for McEliece PKC -. In Public Key Cryptography, K. Kim (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 19--35.

Digital Library

[32]

G. Landais and J. P. Tillich. 2013. An Efficient Attack of a McEliece Cryptosystem Variant Based on Convolutional Codes. In Post-Quantum Cryptography, P. Gaborit (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 102--117.

[33]

F. Levy-dit Vehel and L. Perret. 2006. Algebraic decoding of rank metric codes. Proceedings of YACC (2006).

[34]

P. Loidreau. 2017. A New Rank Metric Codes Based Encryption Scheme. In PostQuantum Cryptography, T. Lange and T. Takagi (Eds.). Springer International Publishing, Cham, 3--17.

[35]

C. Löndahl and T. Johansson. 2012. A New Version of McEliece PKC Based on Convolutional Codes. In Information and Communications Security, T.W. Chim and T. H. Yuen (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 461--470.

Digital Library

[36]

R. J. McEliece. 1978. A Public-Key Cryptosystem Based on Algebraic Coding Theory. DSN Progress Report 42, 44 (1978), 114--116.

[37]

L. Minder and A. Shokrollahi. 2007. Cryptanalysis of the Sidelnikov Cryptosystem. In Advances in Cryptology - EUROCRYPT 2007, M. Naor (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 347--360.

Digital Library

[38]

R. Misoczki and P. S. L. M. Barreto. 2009. Compact McEliece Keys from Goppa Codes. In Selected Areas in Cryptography, M.J. Jacobson, V. Rijmen, and R. SafaviNaini (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 376--392.

Digital Library

[39]

R. Misoczki, J. P. Tillich, N. Sendrier, and P. S. L. M. Barreto. 2013. MDPCMcEliece: New McEliece variants from Moderate Density Parity-Check codes. In 2013 IEEE International Symposium on Information Theory. 2069--2073.

[40]

C. Monico, J. Rosenthal, and A. Shokrollahi. 2000. Using low density parity check codes in the McEliece cryptosystem. In 2000 IEEE International Symposium on Information Theory. 215--.

[41]

H. Niederreiter. 1986. Knapsack Type Cryptosystems and Algebraic Coding Theory. Problems of Control and Information Theory 15 (1986), 159--166.

[42]

A. V. Ourivski and T. Johansson. 2002. New Technique for Decoding Codes in the Rank Metric and Its Cryptography Applications. Problems of Information Transmission 38, 3 (Jul 2002), 237--246.

Digital Library

[43]

R. Overbeck. 2005. A New Structural Attack for GPT and Variants. In Progress in Cryptology -- Mycrypt 2005, E. Dawson and S. Vaudenay (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 50--63.

Digital Library

[44]

N. Sendrier. 1998. On the Concatenated Structure of a Linear Code. Applicable Algebra in Engineering, Communication and Computing 9, 3 (Nov 1998), 221--242.

[45]

P. W. Shor. 1997. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comput. 26, 5 (Oct 1997), 1484--1509.

Digital Library

[46]

V. M. Sidelnikov. 1994. Public-key cryptosystem based on binary Reed-Muller codes. Discrete Mathematics and Applications 4, 3 (1994), 191--208.

[47]

V. M. Sidelnikov and S. O. Shestakov. 1992. On insecurity of cryptosystems based on generalized Reed-Solomon codes. Discrete Mathematics and Applications 2, 4 (1992), 439--444.

[48]

C. Wieschebrink. 2010. Cryptanalysis of the Niederreiter Public Key Scheme Based on GRS Subcodes. In Proceedings of the Third International Conference on Post-Quantum Cryptography (PQCrypto'10). Springer-Verlag, Berlin, Heidelberg, 61--72.

Digital Library

Cited By

Sun ZZhuang JZhou ZFu F(2024)A new McEliece-type cryptosystem using Gabidulin-Kronecker product codesTheoretical Computer Science10.1016/j.tcs.2024.114480994:COnline publication date: 1-May-2024
https://dl.acm.org/doi/10.1016/j.tcs.2024.114480
Lau TTan C(2019)Cryptanalysis on CCA2-Secured LRPC-Kronecker CryptosystemInformation Security and Privacy10.1007/978-3-030-21548-4_12(211-228)Online publication date: 30-May-2019
https://doi.org/10.1007/978-3-030-21548-4_12
Lau TTan C(2019)A New Gabidulin-Like Code and Its Application in CryptographyCodes, Cryptology and Information Security10.1007/978-3-030-16458-4_16(269-287)Online publication date: 28-Mar-2019
https://doi.org/10.1007/978-3-030-16458-4_16

Index Terms

A New LRPC-Kronecker Product Codes Based Public-Key Cryptography
1. Security and privacy
  1. Cryptography
    1. Public key (asymmetric) techniques
      1. Public key encryption

Recommendations

Cryptanalysis on CCA2-Secured LRPC-Kronecker Cryptosystem
Information Security and Privacy
Abstract
Recently, a new rank metric code, namely LRPC-Kronecker Product codes was proposed in APKC 2018 Workshop, and adapted into a construction of a new cryptosystem, namely the LRPC-Kronecker cryptosystem. The LRPC-Kronecker cryptosystem has compact ...
Proof of plaintext knowledge for code-based public-key encryption revisited
ASIA CCS '13: Proceedings of the 8th ACM SIGSAC symposium on Information, computer and communications security

In a recent paper at Asiacrypt'2012, Jain et al point out that Veron code-based identification scheme is not perfect zero-knowledge. In particular, this creates a gap in security arguments of proof of plaintext knowledge (PPK) and verifiable encryption ...
A Code-based Group Signature Scheme with Shorter Public Key Length
ICETE 2016: Proceedings of the 13th International Joint Conference on e-Business and Telecommunications

Group signatures allow members to sign on behalf of a group while maintaining signerâ s identity anonymous.

In this paper, we show that it is possible to reduce the public key length of the first provably secure group

signature scheme from code-based ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

APKC '18: Proceedings of the 5th ACM on ASIA Public-Key Cryptography Workshop

May 2018

66 pages

ISBN:9781450357562

DOI:10.1145/3197507

Program Chairs:
Keita Emura
National Institute of Information & Communications Technology, Japan
,
Jae Hong Seo
Hanyang University, Korea
,
Yohei Watanabe
The University of Electro-Communications, Japan

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 May 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Samsung Science and Technology Foundation

Conference

ASIA CCS '18

Sponsor:

SIGSAC

ASIA CCS '18: ACM Asia Conference on Computer and Communications Security

June 4, 2018

Incheon, Republic of Korea

Acceptance Rates

APKC '18 Paper Acceptance Rate 7 of 20 submissions, 35%;

Overall Acceptance Rate 36 of 103 submissions, 35%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
153
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)2

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Sun ZZhuang JZhou ZFu F(2024)A new McEliece-type cryptosystem using Gabidulin-Kronecker product codesTheoretical Computer Science10.1016/j.tcs.2024.114480994:COnline publication date: 1-May-2024
https://dl.acm.org/doi/10.1016/j.tcs.2024.114480
Lau TTan C(2019)Cryptanalysis on CCA2-Secured LRPC-Kronecker CryptosystemInformation Security and Privacy10.1007/978-3-030-21548-4_12(211-228)Online publication date: 30-May-2019
https://doi.org/10.1007/978-3-030-21548-4_12
Lau TTan C(2019)A New Gabidulin-Like Code and Its Application in CryptographyCodes, Cryptology and Information Security10.1007/978-3-030-16458-4_16(269-287)Online publication date: 28-Mar-2019
https://doi.org/10.1007/978-3-030-16458-4_16

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten