Paper 2022/722
Speedy Error Reconciliation
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)
- 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}, url = {https://eprint.iacr.org/2022/722} }