[Resource Topic] 2017/295: Improved key-reconciliation method

Welcome to the resource topic for 2017/295

Improved key-reconciliation method

Authors: Ludo Tolhuizen, Ronald Rietman, Oscar Garcia-Morchon


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.

ePrint: https://eprint.iacr.org/2017/295

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .