MAK Crypto Seminar: Ramiro Martínez and Carla Ràfols

TALK #1:

By: Ramiro Martínez, MAK-UPC

Title: RLWE-based Zero-Knowledge Proofs for linear and multiplicative relations

Abstract: Ring Learning With Errors (RLWE) samples are pairs of polynomials in $\\mathbb{Z}_q\[x\]/(x^{n}+1)$, obtained from a distribution that depends on a secret polynomial. RLWE samples are computationally indistinguishable from uniformly random pairs of polynomials. We present efficient Zero-Knowledge Proofs of Knowledge (ZKPoK) for linear and multiplicative relations among secret messages hidden as RLWE samples. Our proposed protocols for a ZKPoK are based on the celebrated paper by Stern on identification schemes using coding problems (Crypto'93). Our 5-move protocol achieves a soundness error slightly above 1/2 and perfect Zero-Knowledge.

As an application we present ZKPoK of relations between committed messages. The resulting commitment scheme is perfectly binding with overwhelming probability over the choice of the public key, and computationally hiding under the RLWE assumption. Compared with previous Stern-based commitment scheme proofs we decrease computational complexity, improve the size of the parameters and reduce the soundness error of each round.

TALK #2:

By: Carla Ràfols, UPF

Title: A survey on SNARKs

Abstract: Zero-Knowledge proofs are among the oldest and most useful cryptographic primitives. Efficient proofs for "simple" languages (non NP complete) have been known for a long time, in different security models and based on various different computational assumptions. SNARKs or Succint Non-Interactive Arguments of Knowledge, proposed by Groth in 2010, allow to prove circuit satisfiability in zero-knowledge. The most efficient constructions are not only succinct (independent of the witness size) but also very efficient concretely. SNARKs have had a major impact in cryptographic research and practice, partly due to their application to anonymous financial transactions in cryptocurrencies. In this talk, I will survey some of the main results, techniques and applications in the area.