Speedy Error Reconciliation

Kaibo Liu; Xiaozhuo Gu; Peixin Ren; Xuwen Nie

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

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 eﬀiciently 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 eﬀiciency 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: 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},
      note = {\url{https://eprint.iacr.org/2022/722}},
      url = {https://eprint.iacr.org/2022/722}
}