Talk by Thomas Attema: “Compressed Σ-Protocol Theory”
On 17 September 2021 at 16:00 CEST, Thomas Attema will give a talk titled “Compressed Σ-Protocol Theory”.
You can join the Zoom meeting using the following details:
https://fau.zoom.us/j/93409361471?pwd=YUZ2NFZYcGRBME5zUys4aTd4VmdtQT09
Meeting ID: 934 0936 1471 Passcode: 942451
Abstract:
Σ-Protocols provide a well-understood basis for secure algorithmics. Compressed Σ-protocol theory (CRYPTO 2020) was introduced as a strengthening yielding protocols with low communication complexity. It is built around basic Σ-protocols for proving that a compactly committed (long) vector satisfies a linear constraint. The communication complexity of these protocols is first compressed, from linear down to logarithmic, using a recursive “folding-technique” adapted from Bulletproofs (Bootle et al., EUROCRYPT 2016, and Bünz et al., S&P 2018), at the expense of logarithmic rounds. Proving in ZK that the secret vector satisfies a given constraint – captured by a (non-linear) circuit – is then by (blackbox) reduction to the linear case, via arithmetic secret-sharing techniques adapted from MPC.
This abstract modular theory has been instantiated from a variety of cryptographic hardness assumptions, i.e., the discrete-logarithm, strong-RSA, knowledge-of-exponent assumption. In two separate works, it has also been generalized to a bilinear circuit model and instantiated from the ring-SIS assumption. Thus for all these platforms compressed Σ-protocol theory yields circuit zero-knowledge protocols with (poly)-logarithmic communication.
All in all, our theory should more generally be useful for modular (“plug-&-play”) design of practical cryptographic protocols; this is further evidenced by our separate work on proofs of partial knowledge.
Biography:
Thomas Attema is a researcher at the applied research institute TNO in The Netherlands, where he works on (applied) multi-party computation, zero-knowledge proof systems and post-quantum cryptography. Moreover, he is pursuing a part-time PhD in the Cryptology group of CWI.