---------- Forwarded message ---------
De: Aditi Partap <[email protected]>
Date: sex., 14 de nov. de 2025 às 16:45
Subject: Rahul Ilango on Nov 18
To: [email protected] <[email protected]
>
Gödel in Cryptography: Zero-Knowledge Proofs With No
Interaction, No Setup, and Perfect Soundness
Rahul Ilango
Tuesday, November 18, 2025
Talk at 4:00pm
CoDA E401 & Zoom
<https://stanford.zoom.us/j/92732897040?pwd=Q29JOFVFSy9kWXVDR3dIVWlGektFdz09>
Abstract:
Gödel showed that there are true but unprovable statements. This was
bad news for Hilbert, who hoped that every true statement was provable.
In this talk, I’ll describe why Gödel’s result is, in fact, good news
for cryptography.
Specifically, Gödel’s result allows for the following strange scenario:
a cryptographic system S is insecure, but it is impossible to prove that
S is insecure. As I will explain, in this scenario (defined carefully),
S is secure for nearly all practical purposes.
Leveraging this idea, we effectively construct — under longstanding
assumptions — a classically-impossible cryptographic dream object:
“zero-knowledge proofs for NP with no interaction, no setup, and perfect
soundness” (I won’t assume you know what this means!). As an
application, our result lets one give an ordinary mathematical proof
that a Sudoku puzzle is solvable without revealing how to solve it.
Previously, it was not known how to do this.
Bio:
Rahul is a postdoc in theoretical computer science at the Insitute for
Advanced Study. Before this, he did his PhD at MIT advised by Ryan
Williams. Most of his research is in the field of computational
complexity theory, which quantifies the amount of resources — like time
and hardware — needed to solve computational tasks, like finding the
fastest route from point A to point B on a map.
--++**==--++**==--++**==--++**==--++**==--++**==--++**==
security-seminar mailing list
[email protected]
https://mailman.stanford.edu/mailman/listinfo/security-seminar
--
LOGICA-L
Lista acadêmica brasileira dos profissionais e estudantes da área de Lógica
<[email protected]>
---
Você está recebendo esta mensagem porque se inscreveu no grupo "LOGICA-L" dos
Grupos do Google.
Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um
e-mail para [email protected].
Para ver esta conversa, acesse
https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CANSQ7QhkmgX9Q6aJ2cmm8EG4aycFH12SQKDUbxx0Vf7SVhSN0A%40mail.gmail.com.
