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
QC-MDPC McEliece 체계는 효율적인 양자 후 보안 암호화를 위한 가장 유망한 공개 키 암호화 체계 중 하나로 간주되었습니다. McEliece 방식의 변형으로 코딩 이론에서 어려운 문제인 신드롬 디코딩 문제를 기반으로 합니다. 키 크기는 널리 사용되는 RSA 암호화 시스템과 경쟁적이며 분명히 강력한 보안 감소를 제공합니다. 2016년 동안 이 계획은 큰 위협을 받지 않았으며 20년 말 Asiacrypt에서 Guo, Johansson 및 Stankovski가 보안 감소에서 고려되지 않은 한 가지 측면을 이용하는 QC-MDPC에 대한 대응 공격을 발표했습니다. : 비밀키와 암호화에 사용된 오류가 특정 속성을 공유하는 경우 디코딩 실패 확률이 낮아집니다. 공격자는 디코딩 실패를 기록하여 비밀 키에 대한 정보를 얻은 다음 수집된 정보를 사용하여 키를 재구성합니다. Guo et al. 두 가지 약점을 지적할 수 있는 키 재구성 알고리즘을 제시했습니다. 첫 번째는 비밀 키에 대한 부분적인 정보를 처리할 수 없기 때문에 공격자가 많은 수의 디코딩 문제를 보내야 한다는 것입니다. 두 번째는 더 높은 보안 수준에 맞게 확장되지 않는다는 것입니다. 공격을 개선하기 위해 Guo et al.보다 빠르게 실행되는 키 재구성 알고리즘을 제안합니다. 알고리즘은 80비트 보안을 위해 제안된 매개변수를 고려하여 알고리즘에서 사용하는 것보다 비밀 키 보유자와의 상호 작용을 약 XNUMX% 적게 사용합니다. 또한 점근적 복잡성이 낮아서 더 높은 보안 매개변수에 대해 훨씬 더 나은 확장성을 제공합니다. 알고리즘은 간단하게 병렬화될 수 있지만 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.
부
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
부
@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},}
부
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 -