In this paper, we show that by simultaneously considering the secrecy and authenticity requirements of an AKE, we can construct a scheme that is more secure and with smaller communication complexity than a scheme created by a generic combination of a KEM with a signature scheme. Our improvement uses particular properties of lattice-based encryption and signature schemes and consists of two parts -- the first part increases security, whereas the second reduces communication complexity. \\
We first observe that parameters for lattice-based encryption schemes are always set so as to avoid decryption errors, since many observations by the adversary of such failures usually leads to him recovering the secret key. But since one of the requirements of an AKE is that it be forward-secure, the public key must change every time. The intuition is therefore that one can set the parameters of the scheme so as to not care about decryption errors and everything should still remain secure. We show that this naive solution is not quite correct, but the intuition can be made to work by a small change in the scheme. Our new AKE, which now remains secure in case of decryption errors, fails to create a shared key with probability around $2^{-30}$, but adds enough security that we are able to instantiate a KEM based on the NTRU assumption with rings of smaller dimension. \\
Our second improvement is showing that certain hash-and-sign lattice signatures can be used in ``message-recovery'' mode. In this mode, the signature size is doubled but this longer signature is enough to recover an even longer message -- thus the signature is longer but the message does not need to be sent. This is advantageous when signing relatively long messages, such as the public keys and ciphertexts generated by a lattice-based KEM. We show how this technique reduces the communication complexity of the generic construction of our AKE by around $20\%$. Using a lattice-based signature in message-recovery mode is quite generic (i.e it does not depend on the structure of the message), and so it may be used in AKE constructions that use a different KEM, or even simply as a way to reduce the transmission length of a message and its digital signature.
Category / Keywords: public-key cryptography / Lattice cryptography, Authenticated Key Exchange Original Publication (with major differences): SCN 2016 Date: received 3 May 2016, last revised 28 Jun 2016 Contact author: vadim lyubash at gmail com Available format(s): PDF | BibTeX Citation Version: 20160628:065417 (All versions of this report) Short URL: ia.cr/2016/435 Discussion forum: Show discussion | Start new discussion