Limits on the Efficiency of Ring LWE-based Key Exchange
This study explores the limitations of Ring LWE-based key exchange protocols and their impact on non-interactive key exchange mechanisms. It discusses the LWE assumption, noise distribution, and the practical implications of small moduli q and noise-to-modulus ratio r. Additionally, it delves into Post-Quantum Cryptography standardization efforts, including quantum-resistant cryptosystems like lattice-based, code-based, multivariate, and hash-based signatures.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Limits on the Efficiency of (Ring) LWE based Non-Interactive Key Exchange Siyao Guo NUY Shanghai Pritish Kamath TTIC Alon Rosen IDC Herzliya Katerina Sotiraki MIT
POST-QUANTUM KEY EXCHANGE NIST Post-Quantum Cryptography standardization includes proposals for key-encapsulation mechanism.
POST-QUANTUM KEY EXCHANGE NIST Post-Quantum Cryptography standardization includes proposals for key-encapsulation mechanism. Many quantum-resistant cryptosystems: lattice-based, code-based, multivariate, hash-based signatures, etc.
POST-QUANTUM KEY EXCHANGE NIST Post-Quantum Cryptography standardization includes proposals for key-encapsulation mechanism. Many quantum-resistant cryptosystems: lattice-based, code-based, multivariate, hash-based signatures, etc.
LWE ASSUMPTION noise distribution e.g. discrete Gaussian or bounded uniform
LWE ASSUMPTION LWE assumption:
LWE ASSUMPTION LWE assumption: Modulus q: Small q improves practical performance. Fewer constructions known from small q.
LWE ASSUMPTION LWE assumption: Noise-to-modulus ratio r: Intuitively, how large the noise is compared to the modulus q. Large r gives better theoretical guarantees. Fewer constructions known from large r.
LWE-BASED KEY EXCHANGE Key-exchange through public-key encryption Inherently interactive One party completely controls the common secret key Key-exchange through reconciliation
LWE-BASED KEY EXCHANGE Key-exchange through public-key encryption Inherently interactive One party completely controls the common secret key Key-exchange through reconciliation
LWE-BASED KEY EXCHANGE Key-exchange through public-key encryption Inherently interactive One party completely controls the common secret key Key-exchange through reconciliation Introduced by Ding, Xie and Lin [DXL 12], and Peikert [P 14]
LWE-BASED KEY EXCHANGE Key-exchange through public-key encryption Inherently interactive One party completely controls the common secret key Key-exchange through reconciliation Introduced by Ding, Xie and Lin [DXL 12], and Peikert [P 14] Our main focus
LWE-BASED KEY EXCHANGE Approximate Common Key: x1TAx2
EXISTING PROPOSALS extra information Existing proposals [DingXieLui 12], [Peikert 14] add extra communication.
EXISTING PROPOSALS extra information Is this interaction inherent?
LWE-BASED KEY EXCHANGE If noise1 and noise2 are very small compared to q, interaction is not necessary.
LWE-BASED KEY EXCHANGE If noise1 and noise2 are very small compared to q, interaction is not necessary.
LWE-BASED KEY EXCHANGE If we have small noise-to-modulus ratio, interaction is not necessary.
LWE-BASED KEY EXCHANGE In practice, q needs to be small. The typical size of q is 213 and there are proposals that even use q = 257 [LLJ + 17]. Small noise-to-modulus ratio results in worse theoretical security guarantees.
LWE-BASED KEY EXCHANGE In practice, q needs to be small. The typical size of q is 213 and there are proposals that even use q = 257 [LLJ + 17]. Small noise-to-modulus ratio results in worse theoretical security guarantees. Is it possible to have non-interactive LWE-based key exchange when q is small?
OUR RESULTS Natural ideas for achieving non-interactive key agreement do not work.
OUR RESULTS Parties exchange LWE-samples and then run locally a reconciliation function.
OUR RESULTS Natural choices of reconciliation functions cannot achieve agreement.
IMPOSSIBILITY 1 Approximate Common Key: x1TAx2 If noise-to-modulus ratio r is large, then rounding gives agreement with probability < 1 1/q.
IMPOSSIBILITY 1 Can we amplify the agreement probability by repetition?
IMPOSSIBILITY 1 Can we amplify the agreement probability by repetition?
IMPOSSIBILITY 1 Can we amplify the agreement probability by repetition?
IMPOSSIBILITY 1 Can we amplify the agreement probability by repetition?
IMPOSSIBILITY 1 Can we amplify the agreement probability by repetition?
IMPOSSIBILITY 1 Can we amplify the agreement probability by repetition?
IMPOSSIBILITY 1 Can we amplify the agreement probability by repetition? Impossible to amplify the agreement probability by repetition
IMPOSSIBILITY 1 Impossible to amplify the agreement probability by repetition Captured by the problem of Non-interactive Agreement Distillation in Information Theory.
MAXIMAL CORRELATION Maximal correlation almostcaptures the best agreement probability that the players can get even with an infinite number of samples!
MAXIMAL CORRELATION Maximal correlation almostcaptures the best agreement probability that the players can get even with an infinite number of samples! If maximal correlation is bounded away from 1, then repetition does not help!
IMPOSSIBILITY 1 Has very special form: Cayley distribution Known how to compute maximal correlation for Cayley distribution [Lov sz 75]
