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
O problema do Isomorfismo de Polinômios (problema IP) é conhecido por ser importante para estudar a segurança de criptossistemas multivariados de chave pública, um dos principais candidatos da criptografia pós-quântica, contra ataques de recuperação de chave. Nestes anos, vários esquemas baseados no próprio problema da PI ou na sua generalização foram propostos. No PQCrypto 2020, Santoso introduziu uma generalização do problema de Isomorfismo de Polinômios, chamado de problema de Isomorfismo Blockwise de Polinômios (problema BIP), e propôs um novo esquema de criptografia do tipo Diffie-Hellman baseado neste problema com matrizes circulantes (problema BIPC) . Muito recentemente, Ikematsu et al. propôs um ataque denominado ataque de pilha linear para recuperar uma chave equivalente do esquema de criptografia de Santoso. Embora este ataque tenha reduzido a segurança do esquema, não contribui para resolver o problema do BIPC em si. No presente artigo, descrevemos como resolver o problema BIPC diretamente, simplificando o problema BIPC devido à propriedade de conjugação de matrizes circulantes. Na verdade, resolvemos experimentalmente o problema do BIPC com o parâmetro, que possui segurança de 256 bits pela análise de segurança de Santoso e possui segurança de 72.7 bits contra o ataque de pilha linear, em cerca de 10 minutos.
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.
Copiar
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
Copiar
@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},}
Copiar
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 -