Paper 2018/081

How to validate the secret of a Ring Learning with Errors (RLWE) key

Jintai Ding, Saraswathy RV, Saed Alsayigh, and Crystal Clough

Abstract

We use the signal function from RLWE key exchange to derive an efficient zero knowledge authentication protocol to validate an RLWE key $p=as+e$ with secret $s$ and error $e$ in the Random Oracle Model (ROM). With this protocol, a verifier can validate that a key $p$ presented to him by a prover $P$ is of the form $p=as+e$ with $s,e$ small and that the prover knows $s$. We accompany the description of the protocol with proof to show that it has negligible soundness and completeness error. The soundness of our protocol relies directly on the hardness of the RLWE problem. The protocol is applicable for both LWE and RLWE but we focus on the RLWE based protocol for efficiency and practicality. We also present a variant of the main protocol with a commitment scheme to avoid using the ROM.

Metadata
Available format(s)
PDF
Publication info
Preprint.
Keywords
RLWEkey exchangepost-quantumkey reusekey validationactive attackszero knowledge
Contact author(s)
jintai ding @ gmail com
rvsaras86 @ gmail com
History
2018-01-24: received
Short URL
https://ia.cr/2018/081
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/081,
      author = {Jintai Ding and Saraswathy RV and Saed Alsayigh and Crystal Clough},
      title = {How to validate the secret of a Ring Learning with Errors (RLWE) key},
      howpublished = {Cryptology ePrint Archive, Paper 2018/081},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/081}},
      url = {https://eprint.iacr.org/2018/081}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.