Cryptology ePrint Archive: Report 2017/295

Improved key-reconciliation method

Ludo Tolhuizen and Ronald Rietman and Oscar Garcia-Morchon

Abstract: At PQ Crypto 2014, Peikert proposed efficient and practical lattice-based protocols for key transport, encryption and authenticated key exchange. One of the main technical innovations of this work is a reconciliation technique that allows two parties who "approximately agree" on a secret value to reach exact agreement, a setting common to essentially all lattice-based encryption schemes. Peikert's reconciliation technique has been extended in the Frodo key exchange scheme, allowing for agreement on more than one bit. In both cases, only one reconciliation bit is required to reach exact agreement. As symmetric keys typically require many bits, say 128 or more, the parties compute multiple secret values, and reach exact agreement on each of those values individually. In this paper, we propose a reconciliation method that sends more than one reconciliation bit. In this way, the parties can agree on the same number of bits as with Peikert's method with less stringent conditions on "how approximate" the approximate agreement must be. An instance of our method allows the two parties on a secret value that is one bit longer than with the previous methods, with virtually the same approximation requirements (i.e., with virtually the same security guarantees) as before. We numerically illustrate the advantages of our method with the impact to the instantiations of the Frodo scheme.

Category / Keywords:

Date: received 29 Mar 2017, last revised 2 May 2017

Contact author: ludo tolhuizen at philips com

Available format(s): PDF | BibTeX Citation

Note: References have been added.

Version: 20170502:075310 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]