TOC calendar

Experimental Relativistic Zero-Knowledge Proofs

Speaker: Claude Crépeau , School of Computer Science, McGill University 

Date: Friday, July 01, 2022

Time: 1:00 PM to 2:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-370

Host: Vinod Vaikuntanathan, CSAIL MIT

Contact: Felicia Raton, fraton@csail.mit.edu

Relevant URL: https://www.nature.com/articles/s41586-021-03998-y

Abstract: Protecting secrets is a key challenge in our contemporary 
information-based era. In common situations, however, revealing 
secrets appears unavoidable, for instance, when identifying oneself in 
a bank to retrieve money. In turn, this may have highly undesirable 
consequences in the unlikely, yet not unrealistic, case where the 
bank’s security gets compromised. This naturally raises the question 
of whether disclosing secrets is fundamentally necessary for 
identifying oneself, or more generally for proving a statement to be 
correct. Developments in computer science provide an elegant solution 
via the concept of zero-knowledge proofs: a prover can convince a 
verifier of the validity of a certain statement without facilitating 
the elaboration of a proof at all. In this work, we report the 
experimental realisation of such a zero-knowledge protocol involving 
two separated verifier-prover pairs. Security is enforced via the 
physical principle of special relativity, and no computational 
assumption (such as the existence of one-way functions) is required. 
Our implementation exclusively relies on off-the-shelf equipment and 
works at both short (60m) and long distances (>400m) in about one 
second. This demonstrates the practical potential of multi-prover 
zero-knowledge protocols, promising for identification tasks.

Joint work with Pouriya Alikhani, Nicolas Brunner, Sébastien Designolle, 
Raphaël Houlmann, Weixu Shi, Nan Yang, and Hugo Zbinden 
in Nature, https://www.nature.com/articles/s41586-021-03998-y

Research Areas: 
Security & Cryptography

November 2022

Sun Mon Tue Wed Thu Fri Sat
30
31
1
2
3
4
5
 
 
 
11:00 am to 12:30 pm Distributed Algorithms Mohsen Ghaffari, Nancy Lynch
 
 
11:00 am to 12:30 pm Design and Analysis of Algorithms Piotr Indyk
 
 
11:00 am to 12:30 pm Topics in Theoretical Computer Science Dor Minzer
 
 
11:00 am to 12:30 pm Intro to Algorithms Nir Shavit, Mauricio Karchmer
 
 
 
 
1:00 pm to 2:30 pm AI, Decision-Making, and Society Aleksander Madry
 
 
2:30 pm to 4:00 pm Math for Computer Science Tom Leighton
 
 
2:30 pm to 4:00 pm Software Performance Engineering Charles Leiserson
 
 
2:30 pm to 4:00 pm Theory of Computation Mike Sipser
 
 
2:30 pm to 4:00 pm Fixed Parameter and Fine-grained Complexity Virginia Vassilevska-Williams, Ryan Williams
 
 
2:30 pm to 4:00 pm Math for Computer Science Zachary Abel
 
 
9:30 am to 11:00 pm Introduction to Quantum Systems Engineering Anand Natarajan
 
 
10:00 am to 11:00 am Probability and Random Variables Jon Kelner
 
 
11:00 am to 12:30 pm Foundations of Computer Security Yael Kalai
 
 
11:00 am to 12:30 pm Sublinear Time Algorithms Ronitt Rubinfeld
 
 
11:30 am to 1:00 pm Topics in Computational Molecular Biology Bonnie Berger
 
 
1:00 pm to 2:00 pm Linear Algebra and Optimization Ankur Moitra
 
 
1:00 pm to 2:00 pm Quantum Computation Peter Shor
 
 
1:00 pm to 2:30 pm Cryptography & Cryptanalysis Vinod Vaikuntanathan
 
 
2:30 pm to 4:00 pm Advanced Algorithms David Karger
 
 
11:00 am to 12:30 pm Distributed Algorithms Mohsen Ghaffari, Nancy Lynch
 
 
11:00 am to 12:30 pm Design and Analysis of Algorithms Piotr Indyk
 
 
11:00 am to 12:30 pm Topics in Theoretical Computer Science Dor Minzer
 
 
11:00 am to 12:30 pm Intro to Algorithms Nir Shavit, Mauricio Karchmer
 
 
 
 
1:00 pm to 2:30 pm AI, Decision-Making, and Society Aleksander Madry
 
 
2:30 pm to 4:00 pm Math for Computer Science Tom Leighton
 
 
2:30 pm to 4:00 pm Software Performance Engineering Charles Leiserson
 
 
2:30 pm to 4:00 pm Theory of Computation Mike Sipser
 
 
2:30 pm to 4:00 pm Fixed Parameter and Fine-grained Complexity Virginia Vassilevska-Williams, Ryan Williams
 
 
2:30 pm to 4:00 pm Math for Computer Science Zachary Abel
 
 
9:30 am to 12:30 pm The Sum of Squares Method Sam Hopkins
 
 
10:00 am to 11:00 am Probability and Random Variables Jon Kelner
 
 
1:00 pm to 2:00 pm Linear Algebra and Optimization Ankur Moitra
 
 
1:00 pm to 2:00 pm Quantum Computation Peter Shor
 
 
2:30 pm to 4:00 pm Advanced Algorithms David Karger
 
 
6
7
8
9
10
11
12
 
 
9:30 am to 11:00 pm Introduction to Quantum Systems Engineering Anand Natarajan
 
 
10:00 am to 11:00 am Probability and Random Variables Jon Kelner
 
 
11:00 am to 12:30 pm Foundations of Computer Security Yael Kalai
 
 
11:00 am to 12:30 pm Sublinear Time Algorithms Ronitt Rubinfeld
 
 
11:30 am to 1:00 pm Topics in Computational Molecular Biology Bonnie Berger
 
 
1:00 pm to 2:00 pm Linear Algebra and Optimization Ankur Moitra
 
 
1:00 pm to 2:00 pm Quantum Computation Peter Shor
 
 
1:00 pm to 2:30 pm Cryptography & Cryptanalysis Vinod Vaikuntanathan
 
 
2:30 pm to 4:00 pm Advanced Algorithms David Karger
 
 
11:00 am to 12:30 pm Distributed Algorithms Mohsen Ghaffari, Nancy Lynch
 
 
11:00 am to 12:30 pm Design and Analysis of Algorithms Piotr Indyk
 
 
11:00 am to 12:30 pm Topics in Theoretical Computer Science Dor Minzer
 
 
11:00 am to 12:30 pm Intro to Algorithms Nir Shavit, Mauricio Karchmer
 
 
 
 
1:00 pm to 2:30 pm AI, Decision-Making, and Society Aleksander Madry
 
 
2:30 pm to 4:00 pm Math for Computer Science Tom Leighton
 
 
2:30 pm to 4:00 pm Software Performance Engineering Charles Leiserson
 
 
2:30 pm to 4:00 pm Theory of Computation Mike Sipser
 
 
2:30 pm to 4:00 pm Fixed Parameter and Fine-grained Complexity Virginia Vassilevska-Williams, Ryan Williams
 
 
2:30 pm to 4:00 pm Math for Computer Science Zachary Abel
 
 
9:30 am to 11:00 pm Introduction to Quantum Systems Engineering Anand Natarajan
 
 
10:00 am to 11:00 am Probability and Random Variables Jon Kelner
 
 
11:00 am to 12:30 pm Foundations of Computer Security Yael Kalai
 
 
11:00 am to 12:30 pm Sublinear Time Algorithms Ronitt Rubinfeld
 
 
11:30 am to 1:00 pm Topics in Computational Molecular Biology Bonnie Berger
 
 
1:00 pm to 2:00 pm Linear Algebra and Optimization Ankur Moitra
 
 
1:00 pm to 2:00 pm Quantum Computation Peter Shor
 
 
1:00 pm to 2:30 pm Cryptography & Cryptanalysis Vinod Vaikuntanathan
 
 
2:30 pm to 4:00 pm Advanced Algorithms David Karger
 
 
11:00 am to 12:30 pm Distributed Algorithms Mohsen Ghaffari, Nancy Lynch
 
 
11:00 am to 12:30 pm Design and Analysis of Algorithms Piotr Indyk
 
 
11:00 am to 12:30 pm Topics in Theoretical Computer Science Dor Minzer
 
 
11:00 am to 12:30 pm Intro to Algorithms Nir Shavit, Mauricio Karchmer
 
 
 
 
1:00 pm to 2:30 pm AI, Decision-Making, and Society Aleksander Madry
 
 
2:30 pm to 4:00 pm Math for Computer Science Tom Leighton
 
 
2:30 pm to 4:00 pm Software Performance Engineering Charles Leiserson
 
 
2:30 pm to 4:00 pm Theory of Computation Mike Sipser
 
 
2:30 pm to 4:00 pm Fixed Parameter and Fine-grained Complexity Virginia Vassilevska-Williams, Ryan Williams
 
 
2:30 pm to 4:00 pm Math for Computer Science Zachary Abel
 
 
 
13
14
15
16
17
18
19
 
 
9:30 am to 11:00 pm Introduction to Quantum Systems Engineering Anand Natarajan
 
 
10:00 am to 11:00 am Probability and Random Variables Jon Kelner
 
 
11:00 am to 12:30 pm Foundations of Computer Security Yael Kalai
 
 
11:00 am to 12:30 pm Sublinear Time Algorithms Ronitt Rubinfeld
 
 
11:30 am to 1:00 pm Topics in Computational Molecular Biology Bonnie Berger
 
 
1:00 pm to 2:00 pm Linear Algebra and Optimization Ankur Moitra
 
 
1:00 pm to 2:00 pm Quantum Computation Peter Shor
 
 
1:00 pm to 2:30 pm Cryptography & Cryptanalysis Vinod Vaikuntanathan
 
 
2:30 pm to 4:00 pm Advanced Algorithms David Karger
 
 
11:00 am to 12:30 pm Distributed Algorithms Mohsen Ghaffari, Nancy Lynch
 
 
11:00 am to 12:30 pm Design and Analysis of Algorithms Piotr Indyk
 
 
11:00 am to 12:30 pm Topics in Theoretical Computer Science Dor Minzer
 
 
11:00 am to 12:30 pm Intro to Algorithms Nir Shavit, Mauricio Karchmer
 
 
 
 
1:00 pm to 2:30 pm AI, Decision-Making, and Society Aleksander Madry
 
 
2:30 pm to 4:00 pm Math for Computer Science Tom Leighton
 
 
2:30 pm to 4:00 pm Software Performance Engineering Charles Leiserson
 
 
2:30 pm to 4:00 pm Theory of Computation Mike Sipser
 
 
2:30 pm to 4:00 pm Fixed Parameter and Fine-grained Complexity Virginia Vassilevska-Williams, Ryan Williams
 
 
2:30 pm to 4:00 pm Math for Computer Science Zachary Abel
 
 
9:30 am to 11:00 pm Introduction to Quantum Systems Engineering Anand Natarajan
 
 
10:00 am to 11:00 am Probability and Random Variables Jon Kelner
 
 
11:00 am to 12:30 pm Foundations of Computer Security Yael Kalai
 
 
11:00 am to 12:30 pm Sublinear Time Algorithms Ronitt Rubinfeld
 
 
11:30 am to 1:00 pm Topics in Computational Molecular Biology Bonnie Berger
 
 
1:00 pm to 2:00 pm Linear Algebra and Optimization Ankur Moitra
 
 
1:00 pm to 2:00 pm Quantum Computation Peter Shor
 
 
1:00 pm to 2:30 pm Cryptography & Cryptanalysis Vinod Vaikuntanathan
 
 
2:30 pm to 4:00 pm Advanced Algorithms David Karger
 
 
11:00 am to 12:30 pm Distributed Algorithms Mohsen Ghaffari, Nancy Lynch
 
 
11:00 am to 12:30 pm Design and Analysis of Algorithms Piotr Indyk
 
 
11:00 am to 12:30 pm Topics in Theoretical Computer Science Dor Minzer
 
 
11:00 am to 12:30 pm Intro to Algorithms Nir Shavit, Mauricio Karchmer
 
 
 
 
1:00 pm to 2:30 pm AI, Decision-Making, and Society Aleksander Madry
 
 
2:30 pm to 4:00 pm Math for Computer Science Tom Leighton
 
 
2:30 pm to 4:00 pm Software Performance Engineering Charles Leiserson
 
 
2:30 pm to 4:00 pm Theory of Computation Mike Sipser
 
 
2:30 pm to 4:00 pm Fixed Parameter and Fine-grained Complexity Virginia Vassilevska-Williams, Ryan Williams
 
 
2:30 pm to 4:00 pm Math for Computer Science Zachary Abel
 
 
9:30 am to 12:30 pm The Sum of Squares Method Sam Hopkins
 
 
10:00 am to 11:00 am Probability and Random Variables Jon Kelner
 
 
1:00 pm to 2:00 pm Linear Algebra and Optimization Ankur Moitra
 
 
1:00 pm to 2:00 pm Quantum Computation Peter Shor
 
 
2:30 pm to 4:00 pm Advanced Algorithms David Karger
 
 
20
21
22
23
24
25
26
 
 
9:30 am to 11:00 pm Introduction to Quantum Systems Engineering Anand Natarajan
 
 
10:00 am to 11:00 am Probability and Random Variables Jon Kelner
 
 
11:00 am to 12:30 pm Foundations of Computer Security Yael Kalai
 
 
11:00 am to 12:30 pm Sublinear Time Algorithms Ronitt Rubinfeld
 
 
11:30 am to 1:00 pm Topics in Computational Molecular Biology Bonnie Berger
 
 
1:00 pm to 2:00 pm Linear Algebra and Optimization Ankur Moitra
 
 
1:00 pm to 2:00 pm Quantum Computation Peter Shor
 
 
1:00 pm to 2:30 pm Cryptography & Cryptanalysis Vinod Vaikuntanathan
 
 
2:30 pm to 4:00 pm Advanced Algorithms David Karger
 
 
11:00 am to 12:30 pm Distributed Algorithms Mohsen Ghaffari, Nancy Lynch
 
 
11:00 am to 12:30 pm Design and Analysis of Algorithms Piotr Indyk
 
 
11:00 am to 12:30 pm Topics in Theoretical Computer Science Dor Minzer
 
 
11:00 am to 12:30 pm Intro to Algorithms Nir Shavit, Mauricio Karchmer
 
 
 
 
1:00 pm to 2:30 pm AI, Decision-Making, and Society Aleksander Madry
 
 
2:30 pm to 4:00 pm Math for Computer Science Tom Leighton
 
 
2:30 pm to 4:00 pm Software Performance Engineering Charles Leiserson
 
 
2:30 pm to 4:00 pm Theory of Computation Mike Sipser
 
 
2:30 pm to 4:00 pm Fixed Parameter and Fine-grained Complexity Virginia Vassilevska-Williams, Ryan Williams
 
 
2:30 pm to 4:00 pm Math for Computer Science Zachary Abel
 
 
 
 
9:30 am to 11:00 pm Introduction to Quantum Systems Engineering Anand Natarajan
 
 
10:00 am to 11:00 am Probability and Random Variables Jon Kelner
 
 
11:00 am to 12:30 pm Foundations of Computer Security Yael Kalai
 
 
11:00 am to 12:30 pm Sublinear Time Algorithms Ronitt Rubinfeld
 
 
11:30 am to 1:00 pm Topics in Computational Molecular Biology Bonnie Berger
 
 
1:00 pm to 2:00 pm Linear Algebra and Optimization Ankur Moitra
 
 
1:00 pm to 2:00 pm Quantum Computation Peter Shor
 
 
1:00 pm to 2:30 pm Cryptography & Cryptanalysis Vinod Vaikuntanathan
 
 
2:30 pm to 4:00 pm Advanced Algorithms David Karger
 
 
 
 
27
28
29
30
1
2
3
 
 
9:30 am to 11:00 pm Introduction to Quantum Systems Engineering Anand Natarajan
 
 
10:00 am to 11:00 am Probability and Random Variables Jon Kelner
 
 
11:00 am to 12:30 pm Foundations of Computer Security Yael Kalai
 
 
11:00 am to 12:30 pm Sublinear Time Algorithms Ronitt Rubinfeld
 
 
11:30 am to 1:00 pm Topics in Computational Molecular Biology Bonnie Berger
 
 
1:00 pm to 2:00 pm Linear Algebra and Optimization Ankur Moitra
 
 
1:00 pm to 2:00 pm Quantum Computation Peter Shor
 
 
1:00 pm to 2:30 pm Cryptography & Cryptanalysis Vinod Vaikuntanathan
 
 
2:30 pm to 4:00 pm Advanced Algorithms David Karger
 
 
11:00 am to 12:30 pm Distributed Algorithms Mohsen Ghaffari, Nancy Lynch
 
 
11:00 am to 12:30 pm Design and Analysis of Algorithms Piotr Indyk
 
 
11:00 am to 12:30 pm Topics in Theoretical Computer Science Dor Minzer
 
 
11:00 am to 12:30 pm Intro to Algorithms Nir Shavit, Mauricio Karchmer
 
 
 
 
1:00 pm to 2:30 pm AI, Decision-Making, and Society Aleksander Madry
 
 
2:30 pm to 4:00 pm Math for Computer Science Tom Leighton
 
 
2:30 pm to 4:00 pm Software Performance Engineering Charles Leiserson
 
 
2:30 pm to 4:00 pm Theory of Computation Mike Sipser
 
 
2:30 pm to 4:00 pm Fixed Parameter and Fine-grained Complexity Virginia Vassilevska-Williams, Ryan Williams
 
 
2:30 pm to 4:00 pm Math for Computer Science Zachary Abel
 
 
4:00 pm to 5:15 pm Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
Yang P Liu (Stanford)
 
 
9:30 am to 11:00 pm Introduction to Quantum Systems Engineering Anand Natarajan
 
 
10:00 am to 11:00 am Probability and Random Variables Jon Kelner
 
 
11:00 am to 12:30 pm Foundations of Computer Security Yael Kalai
 
 
11:00 am to 12:30 pm Sublinear Time Algorithms Ronitt Rubinfeld
 
 
11:30 am to 1:00 pm Topics in Computational Molecular Biology Bonnie Berger
 
 
1:00 pm to 2:00 pm Linear Algebra and Optimization Ankur Moitra
 
 
1:00 pm to 2:00 pm Quantum Computation Peter Shor
 
 
1:00 pm to 2:30 pm Cryptography & Cryptanalysis Vinod Vaikuntanathan
 
 
2:30 pm to 4:00 pm Advanced Algorithms David Karger