The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Masalah Isomorphism of Polynomials (masalah IP) diketahui penting untuk mengkaji keselamatan sistem kriptografi kunci awam multivariate, salah satu calon utama kriptografi pasca-kuantum, terhadap serangan pemulihan kunci. Pada tahun-tahun ini, beberapa skim berdasarkan masalah IP itu sendiri atau generalisasinya telah dicadangkan. Pada PQCrypto 2020, Santoso memperkenalkan generalisasi masalah Isomorphism of Polynomials, yang dipanggil masalah Blockwise Isomorphism of Polynomials (masalah BIP), dan mencadangkan skim penyulitan jenis Diffie-Hellman baharu berdasarkan masalah ini dengan Circulant matrices (masalah BIPC) . Baru-baru ini, Ikematsu et al. mencadangkan serangan yang dipanggil serangan tindanan linear untuk memulihkan kunci yang setara dengan skema penyulitan Santoso. Walaupun serangan ini mengurangkan keselamatan skim itu, ia tidak menyumbang kepada penyelesaian masalah BIPC itu sendiri. Dalam kertas kerja ini, kami menerangkan cara menyelesaikan masalah BIPC secara langsung dengan memudahkan masalah BIPC disebabkan oleh sifat konjugasi matriks edaran. Malah, kami secara eksperimen menyelesaikan masalah BIPC dengan parameter, yang mempunyai keselamatan 256 bit oleh analisis keselamatan Santoso dan mempunyai keselamatan 72.7bit terhadap serangan tindanan linear, kira-kira 10 minit.
Yasufumi HASHIMOTO
University of the Ryukyus
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Salinan
Yasufumi HASHIMOTO, "Solving the Problem of Blockwise Isomorphism of Polynomials with Circulant Matrices" in IEICE TRANSACTIONS on Fundamentals,
vol. E106-A, no. 3, pp. 185-192, March 2023, doi: 10.1587/transfun.2022CIP0002.
Abstract: The problem of Isomorphism of Polynomials (IP problem) is known to be important to study the security of multivariate public key cryptosystems, one of the major candidates of post-quantum cryptography, against key recovery attacks. In these years, several schemes based on the IP problem itself or its generalization have been proposed. At PQCrypto 2020, Santoso introduced a generalization of the problem of Isomorphism of Polynomials, called the problem of Blockwise Isomorphism of Polynomials (BIP problem), and proposed a new Diffie-Hellman type encryption scheme based on this problem with Circulant matrices (BIPC problem). Quite recently, Ikematsu et al. proposed an attack called the linear stack attack to recover an equivalent key of Santoso's encryption scheme. While this attack reduced the security of the scheme, it does not contribute to solving the BIPC problem itself. In the present paper, we describe how to solve the BIPC problem directly by simplifying the BIPC problem due to the conjugation property of circulant matrices. In fact, we experimentally solved the BIPC problem with the parameter, which has 256 bit security by Santoso's security analysis and has 72.7bit security against the linear stack attack, by about 10 minutes.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2022CIP0002/_p
Salinan
@ARTICLE{e106-a_3_185,
author={Yasufumi HASHIMOTO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Solving the Problem of Blockwise Isomorphism of Polynomials with Circulant Matrices},
year={2023},
volume={E106-A},
number={3},
pages={185-192},
abstract={The problem of Isomorphism of Polynomials (IP problem) is known to be important to study the security of multivariate public key cryptosystems, one of the major candidates of post-quantum cryptography, against key recovery attacks. In these years, several schemes based on the IP problem itself or its generalization have been proposed. At PQCrypto 2020, Santoso introduced a generalization of the problem of Isomorphism of Polynomials, called the problem of Blockwise Isomorphism of Polynomials (BIP problem), and proposed a new Diffie-Hellman type encryption scheme based on this problem with Circulant matrices (BIPC problem). Quite recently, Ikematsu et al. proposed an attack called the linear stack attack to recover an equivalent key of Santoso's encryption scheme. While this attack reduced the security of the scheme, it does not contribute to solving the BIPC problem itself. In the present paper, we describe how to solve the BIPC problem directly by simplifying the BIPC problem due to the conjugation property of circulant matrices. In fact, we experimentally solved the BIPC problem with the parameter, which has 256 bit security by Santoso's security analysis and has 72.7bit security against the linear stack attack, by about 10 minutes.},
keywords={},
doi={10.1587/transfun.2022CIP0002},
ISSN={1745-1337},
month={March},}
Salinan
TY - JOUR
TI - Solving the Problem of Blockwise Isomorphism of Polynomials with Circulant Matrices
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 185
EP - 192
AU - Yasufumi HASHIMOTO
PY - 2023
DO - 10.1587/transfun.2022CIP0002
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E106-A
IS - 3
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - March 2023
AB - The problem of Isomorphism of Polynomials (IP problem) is known to be important to study the security of multivariate public key cryptosystems, one of the major candidates of post-quantum cryptography, against key recovery attacks. In these years, several schemes based on the IP problem itself or its generalization have been proposed. At PQCrypto 2020, Santoso introduced a generalization of the problem of Isomorphism of Polynomials, called the problem of Blockwise Isomorphism of Polynomials (BIP problem), and proposed a new Diffie-Hellman type encryption scheme based on this problem with Circulant matrices (BIPC problem). Quite recently, Ikematsu et al. proposed an attack called the linear stack attack to recover an equivalent key of Santoso's encryption scheme. While this attack reduced the security of the scheme, it does not contribute to solving the BIPC problem itself. In the present paper, we describe how to solve the BIPC problem directly by simplifying the BIPC problem due to the conjugation property of circulant matrices. In fact, we experimentally solved the BIPC problem with the parameter, which has 256 bit security by Santoso's security analysis and has 72.7bit security against the linear stack attack, by about 10 minutes.
ER -