Vortrag von Thomas Attema: „Compressed Σ-Protocol Theory“

Symbolbild zum Artikel. Der Link öffnet das Bild in einer großen Anzeige.

Am 17. September 2021 um 16 Uhr hält Thomas Attema einen Vortrag zum Thema „Compressed Σ-Protocol Theory“.

Zur Teilnahme via Zoom verwenden Sie die folgenden Daten:


Meeting ID: 934 0936 1471 Passcode: 942451

Unten stehend finden Sie die Kurzfassung des Vortrags in englischer Sprache sowie eine Kurzbiografie des Autors.


Σ-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.


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.