Accés ràpid intranet

Més informació...

a a a

Deim Seminar


Zero Knowledge Proofs with lattices


Ramiro Martnez

Professor/a organitzador/a

Oriol Farrs Ventura




08-06-2018 15:30


Lattice-based cryptography seems one of the most promising post-quantum alternatives. The hardness of the Learning With Errors problem (LWE) and its ring version (RLWE), stating that it is difficult to recover a lattice point when a small error is added (and that it is also difficult even to distinguish it from a random point) is widely used as security assumption. The main challenge constructing lattice-based ZKPs is to prove that those errors are indeed small, without revealing any other information. Two main techniques exist, Fiat-Shamir with aborts requires a noticeable probability of aborting the protocol in order to guarantee that the published elements do not reveal information about the errors. On the other hand, Stern proposed [CRYPTO 1993] how to prove knowledge of a codeword of small Hamming weight. His original code-based identification scheme has been extended to lattice-based identification schemes, signatures and commitments, replacing low Hamming weight codewords with small norm integer vectors. We present in this talk a further extension of this latter family of applications by proposing a new efficient ZKPK of linear and multiplicative relations between secrets hidden as RLWE samples.


Aula 213