Paper 2022/722

Speedy Error Reconciliation

Kaibo Liu, Institute of Information Engineering, Chinese Academy of Sciences, China, University of Chinese Academy of Sciences, China
Xiaozhuo Gu, Institute of Information Engineering, Chinese Academy of Sciences, China, University of Chinese Academy of Sciences, China
Peixin Ren, Institute of Information Engineering, Chinese Academy of Sciences, China, University of Chinese Academy of Sciences, China
Xuwen Nie, Institute of Information Engineering, Chinese Academy of Sciences, China, University of Chinese Academy of Sciences, China
Abstract

Introducing small errors in the lattice-based key exchange protocols, although it is resistant to quantum computing attacks, will cause both parties to only get roughly equal secret values, which brings uncertainty to the negotiation of the key agreement. The role of the error reconciliation mechanism is to eliminate this uncertainty and ensure that both parties can reach a consensus. This paper designs a new error reconciliation mechanism: Speedy Error Reconciliation (SER), which can efficiently complete key negotiation while ensuring key correctness and security. SER exploits the properties of the approximate secret values σ1 and σ2 shared by the two parties, and simultaneously reconciles the most and least significant bits of the secret value, and a two-bit key can be obtained by one coordination. By sharing g-bit auxiliary information between two entities, SER expands the fault tolerance interval during reconciliation and improves the success rate of consensus. To test the actual performance of SER, we integrate it into key ex- change protocols based on LWE, RLWE, and MLWE, such as Frodo and NewHope. By comparing parameters such as failure rate, security strength, and the number of CPU rounds, we find that SER performs well in various modes, especially in RLWE-based protocol. Since SER doubles the error to reconcile the least significant bit, which in turn leads to a relatively large error in SER; while the RLWE-based key ex- change scheme adopts a polynomial ring and selects a large parameter q, which is very suitable for SER. Compared with Frodo and NewHope, SER improves the reconciliation efficiency of the per-bit key by 61.6% and 797.6%, respectively.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Preprint.
Keywords
Post Quantum Key exchange Error reconciliation
Contact author(s)
liukaibo @ iie ac cn
guxiaozhuo @ iie ac cn
renpeixin @ iie ac cn
niexuwen @ iie ac cn
History
2022-06-06: approved
2022-06-06: received
See all versions
Short URL
https://ia.cr/2022/722
License
Creative Commons Attribution-NonCommercial-NoDerivs
CC BY-NC-ND

BibTeX

@misc{cryptoeprint:2022/722,
      author = {Kaibo Liu and Xiaozhuo Gu and Peixin Ren and Xuwen Nie},
      title = {Speedy Error Reconciliation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/722},
      year = {2022},
      url = {https://eprint.iacr.org/2022/722}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.