Fwd: Rahul Ilango on Nov 18

[Alan Karp]

Not a Security Lunch talk, but one some of you might find interesting.

--------------
Alan Karp

---------- Forwarded message ---------
From: Aditi Partap <adit...@stanford.edu>
Date: Fri, Nov 14, 2025 at 11:45 AM
Subject: Rahul Ilango on Nov 18
To: security...@lists.stanford.edu <security...@lists.stanford.edu>

   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

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
security...@lists.stanford.edu
https://mailman.stanford.edu/mailman/listinfo/security-seminar