TY - GEN
T1 - A Complete and Optimized Key Mismatch Attack on NIST Candidate NewHope
AU - Qin, Yue
AU - Cheng, Chi
AU - Ding, Jintai
N1 - Publisher Copyright:
© 2019, Springer Nature Switzerland AG.
PY - 2019
Y1 - 2019
N2 - In CT-RSA 2019, Bauer et al. have analyzed the case when the public key is reused for the NewHope key encapsulation mechanism (KEM), a second-round candidate in the NIST Post-quantum Standard process. They proposed an elegant method to recover coefficients ranging from -6 to 4 in the secret key. We repeat their experiments but there are two fundamental problems. First, even for coefficients in [−6, 4] we cannot recover at least 262 of them in each secret key with 1024 coefficients. Second, for the coefficient outside [−6, 4], they suggested an exhaustive search. But for each secret key on average there are 10 coefficients that need to be exhaustively searched, and each of them has 6 possibilities. This makes Bauer et al.’s method highly inefficient. We propose an improved method, which with 99.22% probability recovers all the coefficients ranging from -6 to 4 in the secret key. Then, inspired by Ding et al.’s key mismatch attack, we propose an efficient strategy which with a probability of 96.88% succeeds in recovering all the coefficients in the secret key. Experiments show that our proposed method is very efficient, which completes the attack in about 137.56 ms using the NewHope parameters.
AB - In CT-RSA 2019, Bauer et al. have analyzed the case when the public key is reused for the NewHope key encapsulation mechanism (KEM), a second-round candidate in the NIST Post-quantum Standard process. They proposed an elegant method to recover coefficients ranging from -6 to 4 in the secret key. We repeat their experiments but there are two fundamental problems. First, even for coefficients in [−6, 4] we cannot recover at least 262 of them in each secret key with 1024 coefficients. Second, for the coefficient outside [−6, 4], they suggested an exhaustive search. But for each secret key on average there are 10 coefficients that need to be exhaustively searched, and each of them has 6 possibilities. This makes Bauer et al.’s method highly inefficient. We propose an improved method, which with 99.22% probability recovers all the coefficients ranging from -6 to 4 in the secret key. Then, inspired by Ding et al.’s key mismatch attack, we propose an efficient strategy which with a probability of 96.88% succeeds in recovering all the coefficients in the secret key. Experiments show that our proposed method is very efficient, which completes the attack in about 137.56 ms using the NewHope parameters.
KW - Key exchange
KW - Key mismatch attack
KW - Post-quantum cryptography
KW - Ring learning with errors
UR - http://www.scopus.com/inward/record.url?scp=85075608903&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-29962-0_24
DO - 10.1007/978-3-030-29962-0_24
M3 - Conference Proceeding
AN - SCOPUS:85075608903
SN - 9783030299613
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 504
EP - 520
BT - Computer Security – ESORICS 2019 - 24th European Symposium on Research in Computer Security, Proceedings
A2 - Sako, Kazue
A2 - Schneider, Steve
A2 - Ryan, Peter Y.A.
PB - Springer
T2 - 24th European Symposium on Research in Computer Security, ESORICS 2019
Y2 - 23 September 2019 through 27 September 2019
ER -