top of page
###### Seminar

Our seminar is held each Friday at 4 PM.  If you want to participate in the seminar or you need instructions on getting access to the building, please contact Stefan Dziembowski.

The detailed schedule of meetings is available below. You can add it to your own calendar by using the following link (note that once you use this link, it will save only a template of our schedule in your calendar, thus any changes to the schedule will not be visible in your private copy).

###### Recent talks

31/03/2023 Marcin Mielniczuk - PLONK (Continued)

17/03/2023 Marcin Mielniczuk - PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge

(...) We present a universal SNARK construction with fully succinct verification, and significantly lower prover running time (roughly 7.5-20 less group exponentiations than [MBKM] in the fully succinct verifier mode depending on circuit structure).  (...)

10/03/2023 Mikołaj Leonarski - Intrusion-Resilient Secret Sharing

We introduce a new primitive called intrusion-resilient secret sharing (IRSS), whose security proof exploits the fact that there exist functions which can be efficiently computed interactively using low communication complexity in k, but not in k-1 rounds. IRSS is a means of sharing a secret message amongst a set of players which comes with a very strong security guarantee. The shares in an IRSS are made artificially large so that it is hard to retrieve them completely, and the reconstruction procedure is interactive requiring the players to exchange k short messages. The adversaries considered can attack the scheme in rounds, where in each round the adversary chooses some player to corrupt and some function, and retrieves the output of that function applied to the share of the corrupted player. This model captures for example computers connected to a network which can occasionally he infected by malicious software like viruses, which can compute any function on the infected machine, but cannot sent out a huge amount of data. (...)

17/02/2023 Tomasz Lizurej - Efficiently Testable Circuits

We put forward the notion of efficiently testable circuits'' and provide circuit compilers that transform any circuit into an efficiently testable one. Informally, a circuit is testable if one can detect tampering with the circuit by evaluating it on a small number of inputs from some test set.

Our technical contribution is a compiler that transforms any circuit into a testable circuit for which we can detect arbitrary tampering with all wires by traversing a small testing set. The notion of a testable circuit is weaker or incomparable to existing notions of tamper-resilience, which aim to detect or even correct for errors introduced by tampering during every query, but our new notion is interesting in several settings, and we achieve security against much more general tampering classes -- like tampering with all wires -- with very modest overhead.

3/02/2023 Stefan Dziembowski - Lower Bounds for Off-Chain Protocols: Exploring the Limits of Plasma

(...) In this work we initiate the study of the inherent limitations of Plasma protocols. More concretely, we show that in every Plasma system the adversary can either (a)  force the honest parties to communicate a lot with the blockchain, even though they did not intend to (this is traditionally called \emph{mass exit}); or (b) an honest party that wants to leave the system needs to quickly communicate large amounts of data to the blockchain. What makes these attacks particularly hard to handle in real life is that these attacks do not have so-called \emph{uniquely attributable faults}, i.e.~the smart contract cannot determine which party is malicious, and hence cannot force it to pay the fees for the blockchain interaction. An important implication of our result is that the benefits of two of the most prominent Plasma types, called \emph{Plasma Cash} and \emph{Fungible Plasma}, cannot be achieved simultaneously.

27/01/2023 Michał Zając - On Subversion-Resistant SNARKs

While NIZK arguments in the CRS model are widely studied, the question of what happens when the CRS was subverted has received little attention.  In ASIACRYPT 2016, Bellare, Fuchsbauer, and Scafuro showed the first negative and positive results in the case of NIZK, proving also that it is impossible to achieve subversion soundness and (even non-subversion) zero-knowledge at the same time. On the positive side, they constructed an involved sound and subversion-zero-knowledge (Sub-ZK) non-succinct NIZK argument for NP. We consider the practically very relevant case of zk-SNARKs. We make Groth's zk-SNARK for \textsc{Circuit-SAT} from EUROCRYPT 2016 computationally knowledge-sound and perfectly composable Sub-ZK with minimal changes. We only require the CRS trapdoor to be extractable and the CRS to be publicly verifiable. To achieve the latter, we add some new elements to the CRS and construct an efficient CRS verification algorithm. We also provide a definitional framework for knowledge-sound and Sub-ZK SNARKs.

20/01/2023 Vincenzo Botta - On Redaction in Blockchain

A major issue for many applications of blockchain technology is the tension between immutability and compliance to regulations. For instance, the GDPR in the EU requires to guarantee, under some circumstances, the right to be forgotten. This could imply that at some point one might be forced to delete some data from a locally stored blockchain, therefore irreparably hurting the security and transparency of such decentralized platforms. Motivated by such data protection and consistency issues, in this work we design and implement a mechanism for securely deleting data from Bitcoin blockchain. We use zero-knowledge proofs to allow any node to delete some data from Bitcoin transactions, still preserving the public verifiability of the correctness of the spent and spendable coins. Moreover, we specifically use STARK proofs to exploit the transparency that they provide. Our solution, unlike previous approaches, avoids the complications of asking nodes to reach consensus on the content to delete. In particular, our design allows every node to delete some specific data without coordinating this decision with others. In our implementation, data removal can be performed (resp., verified) in minutes (resp., seconds) on a standard laptop rather than in days as required in previous designs based on consensus.

bottom of page