Paper 2020/585

Improving Key Mismatch Attack on NewHope with Fewer Queries

Satoshi Okada, Yuntao Wang, and Tsuyoshi Takagi

Abstract

NewHope is a lattice cryptoscheme based on the Ring Learning With Errors (Ring-LWE) problem, and it has received much attention among the candidates of the NIST post-quantum cryptography standardization project. Recently, there have been key mismatch attacks on NewHope, where the adversary tries to recover the server’s secret key by observing the mismatch of the shared key from chosen queries. At CT-RSA 2019, Bauer et al. first proposed a key mismatch attack on NewHope, and then at ESORICS 2019, Qin et al. proposed an improved version with a success probability of 96.9% using about 880,000 queries. In this paper, we further improve their key mismatch attack on NewHope. First, we reduce the number of queries by adapting the terminating condition to the response from the server using an early abort technique. Next, the success rate of recovering the secret key polynomial is raised by considering the deterministic condition judging its coefficients. Furthermore, the search range of the secret key in Qin et al.’s attack is extended without increasing the number of queries. With the above improvements, to achieve an almost success rate of 97%, about 73% of queries can be reduced compared with Qin et al.’s method. Additionally, the success rate can be improved to 100.0%. In particular, we analyze the trade-off between the cost of queries and the success rate. We show that a lower success rate of 20.9% is available by further reduced queries of 135,000 simultaneously.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. 25th Australasian Conference on Information Security and Privacy (ACISP 2020)
Keywords
PQCRing-LWEKey Mismatch AttackNewHope
Contact author(s)
okada-satoshi323 @ g ecc u-tokyo ac jp
y-wang @ jaist ac jp
takagi @ mist i u-tokyo ac jp
History
2020-05-22: received
Short URL
https://ia.cr/2020/585
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/585,
      author = {Satoshi Okada and Yuntao Wang and Tsuyoshi Takagi},
      title = {Improving Key Mismatch Attack on NewHope with Fewer Queries},
      howpublished = {Cryptology ePrint Archive, Paper 2020/585},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/585}},
      url = {https://eprint.iacr.org/2020/585}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.