-
Previous Article
Infinite families of 2-designs from two classes of binary cyclic codes with three nonzeros
- AMC Home
- This Issue
-
Next Article
${\sf {FAST}}$: Disk encryption and beyond
Polynomial-time plaintext recovery attacks on the IKKR code-based cryptosystems
Temasek Laboratories, National University of Singapore, 5A Engineering Drive 1, #09-02, Singapore 117411, Singapore |
Recently, Ivanov et al. proposed a new approach to construct code-based cryptosystems, namely the $ {\sf IKKR} $ public-key encryptions (PKE) in the International Workshop on Code-Based Cryptography (CBCrypto 2020) [
References:
[1] |
M. Baldi and F. Chiaraluce, Cryptanalysis of a new instance of McEliece cryptosystem based on QC-LDPC codes, in IEEE International Symposium on Information Theory (ISIT 2007), 2007, 2591–2595. Google Scholar |
[2] |
S. Barg,
Some New NP-Complete Coding Problems, Problems Inform. Transmission, 30 (1994), 209-214.
|
[3] |
A. Becker, A. Joux, A. May and A. Meurer, Decoding random binary linear codes in 2n/20: How 1 + 1 = 0 improves Information Set Decoding, in Advances in Cryptology—EUROCRYPT 2012, Lecture Notes in Comput. Sci., vol. 7237, Springer, Heidelberg, 2012,520–536.
doi: 10.1007/978-3-642-29011-4_31. |
[4] |
E. Berlekamp, R. McEliece and H. C. A. van Tilborg,
On the inherent intractability of certain coding problems, IEEE Trans. Inform. Theory, 24 (1978), 384-386.
doi: 10.1109/tit.1978.1055873. |
[5] |
D. J. Bernstein, T. Lange and C. Peters, Smaller decoding exponents: Ball-collision decoding, in Advances in Cryptology (CRYPTO 2011), Lecture Notes in Comput. Sci., vol. 6841, Springer, Heidelberg, 2011,743–760.
doi: 10.1007/978-3-642-22792-9_42. |
[6] |
C. T. Gueye, J. B. Klamti and S. Hirose, Generalization of BJMM-ISD using May-Ozerov nearest neighbor algorithm over an arbitrary finite field $\mathbb{F}_q$, in Codes, Cryptology and Information Security, Lecture Notes in Comput. Sci., vol. 10194, Springer, Cham, 2017, 96–109.
doi: 10.1007/978-3-319-55589-8. |
[7] |
S. Hirose, May-Ozerov algorithm for nearest-neighbor problem over $\mathbb{F}_q$ and its application to information set decoding, in International Conference for Information Technology and Communications, 2016,115–126. Google Scholar |
[8] |
C. Interlando, K. Khathuria, N. Rohrer, J. Rosenthal and V. Weger,
Generalization of the ball-collision algorithm, Journal of Algebra Combinatorics Discrete Structures and Applications, 7 (2020), 195-207.
doi: 10.13069/jacodesmath.729477. |
[9] |
F. Ivanov, G. Kabatiansky, E. Krouk and N. Rumenko, A new code-based cryptosystem, in International Workshop on Code-Based Cryptography (CBCrypto 2020), 2020, 41–49.
doi: 10.1007/978-3-030-54074-6_3. |
[10] |
F. Ivanov, G. Kabatiansky, E. Krouk and N. Rumenko, A new code-based cryptosystem, International Workshop on Code-Based Cryptography (CBCrypto 2020), 2020, https://drive.google.com/open?id=1NvEShYAu_6RkL2nmooydvP1yWxaPTiXt. Google Scholar |
[11] |
P. J. Lee and E. F. Brickell, An observation on the security of McEliece's public-key cryptosystem, in Advances in cryptology—EUROCRYPT '88 (Davos, 1988), Lecture Notes in Comput. Sci., vol. 330, Springer, Berlin, 1988,275–280.
doi: 10.1007/3-540-45961-8_25. |
[12] |
Y. Lee, J. Cho, Y. S. Kim and J. S. No,
Cryptanalysis of the Ivanov-Kabatiansky-Krouk-Rumenko Cryptosystems, IEEE Communications Letters, 24 (2020), 2678-2681.
doi: 10.1109/LCOMM.2020.3019054. |
[13] |
J. S. Leon,
A probabilistic algorithm for computing minimum weights of large error-correcting codes, IEEE Transactions on Information Theory, 34 (1988), 1354-1359.
doi: 10.1109/18.21270. |
[14] |
A. May and I. Ozerov, On computing nearest neighbors with applications to decoding of binary linear codes, in Advances in Cryptology—EUROCRYPT 2015, Part I, Lecture Notes in Comput. Sci., vol. 9056, Springer, Heidelberg, 2015,203–228.
doi: 10.1007/978-3-662-46800-5_9. |
[15] |
R. J. McEliece, A Public-Key Cryptosystem Based on Algebraic Coding Theory, DSN Progress Report, Jet Propulsion Laboratory, Pasadena, Technical report, 1978. Google Scholar |
[16] |
R. Niebuhr, E. Persichetti, P.-L. Cayrel, S. Bulygin and J. Buchmann,
On lower bounds for information set decoding over $\mathbb{F}_q$ and on the effect of partial knowledge, Int. J. Inf. Coding Theory, 4 (2017), 47-78.
doi: 10.1504/IJICOT.2017.081458. |
[17] |
C. Peters, Information-set decoding for linear codes over |
[18] |
E. Prange,
The use of information sets in decoding cyclic codes, IRE Transactions on Information Theory, 8 (1962), 5-9.
doi: 10.1109/tit.1962.1057777. |
[19] |
V. M. Sidelnikov and S. O. Shestakov,
On an encoding system constructed on the basis of generalized Reed-Solomon codes, Diskret. Mat., 4 (1992), 57-63.
|
[20] |
J. Stern, A method for finding codewords of small weight, in Coding Theory and Applications, Lecture Notes in Comput. Sci., vol. 388, Springer, New York, 1989,106–113.
doi: 10.1007/BFb0019850. |
show all references
References:
[1] |
M. Baldi and F. Chiaraluce, Cryptanalysis of a new instance of McEliece cryptosystem based on QC-LDPC codes, in IEEE International Symposium on Information Theory (ISIT 2007), 2007, 2591–2595. Google Scholar |
[2] |
S. Barg,
Some New NP-Complete Coding Problems, Problems Inform. Transmission, 30 (1994), 209-214.
|
[3] |
A. Becker, A. Joux, A. May and A. Meurer, Decoding random binary linear codes in 2n/20: How 1 + 1 = 0 improves Information Set Decoding, in Advances in Cryptology—EUROCRYPT 2012, Lecture Notes in Comput. Sci., vol. 7237, Springer, Heidelberg, 2012,520–536.
doi: 10.1007/978-3-642-29011-4_31. |
[4] |
E. Berlekamp, R. McEliece and H. C. A. van Tilborg,
On the inherent intractability of certain coding problems, IEEE Trans. Inform. Theory, 24 (1978), 384-386.
doi: 10.1109/tit.1978.1055873. |
[5] |
D. J. Bernstein, T. Lange and C. Peters, Smaller decoding exponents: Ball-collision decoding, in Advances in Cryptology (CRYPTO 2011), Lecture Notes in Comput. Sci., vol. 6841, Springer, Heidelberg, 2011,743–760.
doi: 10.1007/978-3-642-22792-9_42. |
[6] |
C. T. Gueye, J. B. Klamti and S. Hirose, Generalization of BJMM-ISD using May-Ozerov nearest neighbor algorithm over an arbitrary finite field $\mathbb{F}_q$, in Codes, Cryptology and Information Security, Lecture Notes in Comput. Sci., vol. 10194, Springer, Cham, 2017, 96–109.
doi: 10.1007/978-3-319-55589-8. |
[7] |
S. Hirose, May-Ozerov algorithm for nearest-neighbor problem over $\mathbb{F}_q$ and its application to information set decoding, in International Conference for Information Technology and Communications, 2016,115–126. Google Scholar |
[8] |
C. Interlando, K. Khathuria, N. Rohrer, J. Rosenthal and V. Weger,
Generalization of the ball-collision algorithm, Journal of Algebra Combinatorics Discrete Structures and Applications, 7 (2020), 195-207.
doi: 10.13069/jacodesmath.729477. |
[9] |
F. Ivanov, G. Kabatiansky, E. Krouk and N. Rumenko, A new code-based cryptosystem, in International Workshop on Code-Based Cryptography (CBCrypto 2020), 2020, 41–49.
doi: 10.1007/978-3-030-54074-6_3. |
[10] |
F. Ivanov, G. Kabatiansky, E. Krouk and N. Rumenko, A new code-based cryptosystem, International Workshop on Code-Based Cryptography (CBCrypto 2020), 2020, https://drive.google.com/open?id=1NvEShYAu_6RkL2nmooydvP1yWxaPTiXt. Google Scholar |
[11] |
P. J. Lee and E. F. Brickell, An observation on the security of McEliece's public-key cryptosystem, in Advances in cryptology—EUROCRYPT '88 (Davos, 1988), Lecture Notes in Comput. Sci., vol. 330, Springer, Berlin, 1988,275–280.
doi: 10.1007/3-540-45961-8_25. |
[12] |
Y. Lee, J. Cho, Y. S. Kim and J. S. No,
Cryptanalysis of the Ivanov-Kabatiansky-Krouk-Rumenko Cryptosystems, IEEE Communications Letters, 24 (2020), 2678-2681.
doi: 10.1109/LCOMM.2020.3019054. |
[13] |
J. S. Leon,
A probabilistic algorithm for computing minimum weights of large error-correcting codes, IEEE Transactions on Information Theory, 34 (1988), 1354-1359.
doi: 10.1109/18.21270. |
[14] |
A. May and I. Ozerov, On computing nearest neighbors with applications to decoding of binary linear codes, in Advances in Cryptology—EUROCRYPT 2015, Part I, Lecture Notes in Comput. Sci., vol. 9056, Springer, Heidelberg, 2015,203–228.
doi: 10.1007/978-3-662-46800-5_9. |
[15] |
R. J. McEliece, A Public-Key Cryptosystem Based on Algebraic Coding Theory, DSN Progress Report, Jet Propulsion Laboratory, Pasadena, Technical report, 1978. Google Scholar |
[16] |
R. Niebuhr, E. Persichetti, P.-L. Cayrel, S. Bulygin and J. Buchmann,
On lower bounds for information set decoding over $\mathbb{F}_q$ and on the effect of partial knowledge, Int. J. Inf. Coding Theory, 4 (2017), 47-78.
doi: 10.1504/IJICOT.2017.081458. |
[17] |
C. Peters, Information-set decoding for linear codes over |
[18] |
E. Prange,
The use of information sets in decoding cyclic codes, IRE Transactions on Information Theory, 8 (1962), 5-9.
doi: 10.1109/tit.1962.1057777. |
[19] |
V. M. Sidelnikov and S. O. Shestakov,
On an encoding system constructed on the basis of generalized Reed-Solomon codes, Diskret. Mat., 4 (1992), 57-63.
|
[20] |
J. Stern, A method for finding codewords of small weight, in Coding Theory and Applications, Lecture Notes in Comput. Sci., vol. 388, Springer, New York, 1989,106–113.
doi: 10.1007/BFb0019850. |
PKE | ||
must be decodable | any random code | |
requires decoding | does not require decoding |
PKE | ||
must be decodable | any random code | |
requires decoding | does not require decoding |
Instance | Code | Security | ||
Goppa | 12,288 KB | 80-bit | ||
BCH | 2,513 KB | 56-bit |
Instance | Code | Security | ||
Goppa | 12,288 KB | 80-bit | ||
BCH | 2,513 KB | 56-bit |
Instance | Security | Plaintext Recovery Attack | |
80-bit | Algorithm 2 | 176 ms | |
Algorithm 3 | 103 ms | ||
56-bit | Algorithm 2 | 120 ms | |
Algorithm 3 | 77 ms |
Instance | Security | Plaintext Recovery Attack | |
80-bit | Algorithm 2 | 176 ms | |
Algorithm 3 | 103 ms | ||
56-bit | Algorithm 2 | 120 ms | |
Algorithm 3 | 77 ms |
[1] |
Z. Reichstein and B. Youssin. Parusinski's "Key Lemma" via algebraic geometry. Electronic Research Announcements, 1999, 5: 136-145. |
[2] |
Jia Cai, Guanglong Xu, Zhensheng Hu. Sketch-based image retrieval via CAT loss with elastic net regularization. Mathematical Foundations of Computing, 2020, 3 (4) : 219-227. doi: 10.3934/mfc.2020013 |
[3] |
Teddy Pichard. A moment closure based on a projection on the boundary of the realizability domain: 1D case. Kinetic & Related Models, 2020, 13 (6) : 1243-1280. doi: 10.3934/krm.2020045 |
[4] |
Peter Benner, Jens Saak, M. Monir Uddin. Balancing based model reduction for structured index-2 unstable descriptor systems with application to flow control. Numerical Algebra, Control & Optimization, 2016, 6 (1) : 1-20. doi: 10.3934/naco.2016.6.1 |
2019 Impact Factor: 0.734
Tools
Article outline
Figures and Tables
[Back to Top]