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 esquema QC-MDPC McEliece foi considerado um dos esquemas de criptografia de chave pública mais promissores para criptografia segura pós-quântica eficiente. Como variante do esquema de McEliece, baseia-se no problema de decodificação da síndrome, que é um problema difícil da Teoria da Codificação. Seus tamanhos de chave são competitivos com os do sistema criptográfico RSA amplamente utilizado, e veio com uma redução de segurança aparentemente forte. Há três anos, o esquema não sofre grandes ameaças, até o final de 2016, no Asiacrypt, quando Guo, Johansson e Stankovski apresentaram um ataque de reação ao QC-MDPC que explora um aspecto que não foi considerado na redução da segurança : a probabilidade de ocorrer uma falha de decodificação é menor quando a chave secreta e o erro usado para criptografia compartilham certas propriedades. Registrando as falhas de decodificação, o invasor obtém informações sobre a chave secreta e então utiliza as informações coletadas para reconstruir a chave. Guo et al. apresentou um algoritmo para reconstrução de chaves para o qual podemos apontar dois pontos fracos. A primeira é que ele não consegue lidar com informações parciais sobre a chave secreta, fazendo com que o invasor tenha que enviar um grande número de desafios de decodificação. A segunda é que ele não se adapta bem a níveis de segurança mais elevados. Para melhorar o ataque, propomos um algoritmo de reconstrução de chave que roda mais rápido que o de Guo et al. algoritmo, mesmo utilizando cerca de 20% menos interações com o detentor da chave secreta do que o utilizado por seu algoritmo, considerando parâmetros sugeridos para 80 bits de segurança. Ele também possui uma complexidade assintótica mais baixa, o que o torna muito melhor dimensionado para parâmetros de segurança mais elevados. O algoritmo pode ser paralelizado diretamente, o que não é o caso de Guo et al.
Thales BANDIERA PAIVA
Universidade de São Paulo
Routo TERADA
Universidade de São Paulo
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
Thales BANDIERA PAIVA, Routo TERADA, "Improving the Efficiency of a Reaction Attack on the QC-MDPC McEliece" in IEICE TRANSACTIONS on Fundamentals,
vol. E101-A, no. 10, pp. 1676-1686, October 2018, doi: 10.1587/transfun.E101.A.1676.
Abstract: The QC-MDPC McEliece scheme was considered one of the most promising public key encryption schemes for efficient post-quantum secure encryption. As a variant of the McEliece scheme, it is based on the syndrome decoding problem, which is a hard problem from Coding Theory. Its key sizes are competitive with the ones of the widely used RSA cryptosystem, and it came with an apparently strong security reduction. For three years, the scheme has not suffered major threats, until the end of 2016, at the Asiacrypt, when Guo, Johansson, and Stankovski presented a reaction attack on the QC-MDPC that exploits one aspect that was not considered in the security reduction: the probability of a decoding failure to occur is lower when the secret key and the error used for encryption share certain properties. Recording the decoding failures, the attacker obtains information about the secret key and then use the information gathered to reconstruct the key. Guo et al. presented an algorithm for key reconstruction for which we can point two weaknesses. The first one is that it cannot deal with partial information about the secret key, resulting in the attacker having to send a large number of decoding challenges. The second one is that it does not scale well for higher security levels. To improve the attack, we propose a key reconstruction algorithm that runs faster than Guo's et al. algorithm, even using around 20% less interactions with the secret key holder than used by their algorithm, considering parameters suggested for 80 bits of security. It also has a lower asymptotic complexity which makes it scale much better for higher security parameters. The algorithm can be parallelized straightforwardly, which is not the case for the one by Guo et al.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E101.A.1676/_p
Copiar
@ARTICLE{e101-a_10_1676,
author={Thales BANDIERA PAIVA, Routo TERADA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Improving the Efficiency of a Reaction Attack on the QC-MDPC McEliece},
year={2018},
volume={E101-A},
number={10},
pages={1676-1686},
abstract={The QC-MDPC McEliece scheme was considered one of the most promising public key encryption schemes for efficient post-quantum secure encryption. As a variant of the McEliece scheme, it is based on the syndrome decoding problem, which is a hard problem from Coding Theory. Its key sizes are competitive with the ones of the widely used RSA cryptosystem, and it came with an apparently strong security reduction. For three years, the scheme has not suffered major threats, until the end of 2016, at the Asiacrypt, when Guo, Johansson, and Stankovski presented a reaction attack on the QC-MDPC that exploits one aspect that was not considered in the security reduction: the probability of a decoding failure to occur is lower when the secret key and the error used for encryption share certain properties. Recording the decoding failures, the attacker obtains information about the secret key and then use the information gathered to reconstruct the key. Guo et al. presented an algorithm for key reconstruction for which we can point two weaknesses. The first one is that it cannot deal with partial information about the secret key, resulting in the attacker having to send a large number of decoding challenges. The second one is that it does not scale well for higher security levels. To improve the attack, we propose a key reconstruction algorithm that runs faster than Guo's et al. algorithm, even using around 20% less interactions with the secret key holder than used by their algorithm, considering parameters suggested for 80 bits of security. It also has a lower asymptotic complexity which makes it scale much better for higher security parameters. The algorithm can be parallelized straightforwardly, which is not the case for the one by Guo et al.},
keywords={},
doi={10.1587/transfun.E101.A.1676},
ISSN={1745-1337},
month={October},}
Copiar
TY - JOUR
TI - Improving the Efficiency of a Reaction Attack on the QC-MDPC McEliece
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1676
EP - 1686
AU - Thales BANDIERA PAIVA
AU - Routo TERADA
PY - 2018
DO - 10.1587/transfun.E101.A.1676
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E101-A
IS - 10
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - October 2018
AB - The QC-MDPC McEliece scheme was considered one of the most promising public key encryption schemes for efficient post-quantum secure encryption. As a variant of the McEliece scheme, it is based on the syndrome decoding problem, which is a hard problem from Coding Theory. Its key sizes are competitive with the ones of the widely used RSA cryptosystem, and it came with an apparently strong security reduction. For three years, the scheme has not suffered major threats, until the end of 2016, at the Asiacrypt, when Guo, Johansson, and Stankovski presented a reaction attack on the QC-MDPC that exploits one aspect that was not considered in the security reduction: the probability of a decoding failure to occur is lower when the secret key and the error used for encryption share certain properties. Recording the decoding failures, the attacker obtains information about the secret key and then use the information gathered to reconstruct the key. Guo et al. presented an algorithm for key reconstruction for which we can point two weaknesses. The first one is that it cannot deal with partial information about the secret key, resulting in the attacker having to send a large number of decoding challenges. The second one is that it does not scale well for higher security levels. To improve the attack, we propose a key reconstruction algorithm that runs faster than Guo's et al. algorithm, even using around 20% less interactions with the secret key holder than used by their algorithm, considering parameters suggested for 80 bits of security. It also has a lower asymptotic complexity which makes it scale much better for higher security parameters. The algorithm can be parallelized straightforwardly, which is not the case for the one by Guo et al.
ER -