Paper 2017/295

Improved key-reconciliation method

Ludo Tolhuizen, Ronald Rietman, and 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.

Note: References have been added.

Available format(s)
Publication info
Preprint. MINOR revision.
Contact author(s)
ludo tolhuizen @ philips com
2017-05-02: revised
2017-04-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ludo Tolhuizen and Ronald Rietman and Oscar Garcia-Morchon},
      title = {Improved key-reconciliation method},
      howpublished = {Cryptology ePrint Archive, Paper 2017/295},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.