Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Interactive Proofs: The Power of Interaction

In course

COM-501: Advanced cryptography

This course reviews some failure cases in public-key cryptography. It introduces some cryptanalysis techniques. It also presents fundamentals in cryptography such as interactive proofs. Finally, it presents some techniques to validate the security of crypt ...

Description

This lecture explores the concept of interactive proofs, focusing on topics such as zero-knowledge proofs, parallel composition, sequential composition, and the Goldreich-Micali-Wigderson protocol. It delves into the complexities of cryptographic protocols, soundness, zero-knowledge levels, and the relationship between complexity classes. The instructor discusses the Goldwasser-Micali-Rackoff protocol, graph coloring, and the Graph Isomorphism problem. The lecture also covers the Sigma Protocol, ZK Trick, and the notion of a malicious prover. Additionally, it examines the properties of E-protocols, proof of knowledge, and the implications of protocols as proof of knowledge.

Instructor

Serge Vaudenay

Serge Vaudenay entered at the Ecole Normale Supérieure in 1989 with a major in mathematics. He earned his agrégation (secondary teaching degree) in mathematics in 1992, then a PhD in Computer Science at the University of Paris 7 - Denis Diderot in 1995. He subsequently became a senior research fellow at the CNRS, prior to being granted his habilitation à diriger des recherches (a postdoctoral degree authorizing the recipient to supervise doctoral students). In 1999, he was appointed as a Professor at the EPFL, where he created the Security and Cryptography Laboratory.

Official source

Ontological neighbourhood

Theoretical computer science

Theory of computation: Computational complexity theory

Related concepts (32)

Zero-knowledge proof

In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true, while avoiding conveying to the verifier any information beyond the mere fact of the statement's truth. The intuition underlying zero-knowledge proofs is that it is trivial to prove the possession of certain information by simply revealing it; the challenge is to prove this possession without revealing the information, or any aspect of it whatsoever.

Interactive proof system

In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties: a prover and a verifier. The parties interact by exchanging messages in order to ascertain whether a given string belongs to a language or not. The prover possesses unlimited computational resources but cannot be trusted, while the verifier has bounded computation power but is assumed to be always honest.

Complexity class

In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of a type of computational problem, a model of computation, and a bounded resource like time or memory. In particular, most complexity classes consist of decision problems that are solvable with a Turing machine, and are differentiated by their time or space (memory) requirements.

Interaction design

Interaction design, often abbreviated as IxD, is "the practice of designing interactive digital products, environments, systems, and services." While interaction design has an interest in form (similar to other design fields), its main area of focus rests on behavior. Rather than analyzing how things are, interaction design synthesizes and imagines things as they could be. This element of interaction design is what characterizes IxD as a design field, as opposed to a science or engineering field.

AC power

In an electric circuit, instantaneous power is the time rate of flow of energy past a given point of the circuit. In alternating current circuits, energy storage elements such as inductors and capacitors may result in periodic reversals of the direction of energy flow. Its SI unit is the watt. The portion of instantaneous power that, averaged over a complete cycle of the AC waveform, results in net transfer of energy in one direction is known as instantaneous active power, and its time average is known as active power or real power.

Related lectures (34)

The Power of Interaction: Zero-Knowledge Construction

Explores zero-knowledge construction, setup models, and the power of interaction in cryptographic protocols, including Sigma Protocol and NP Zero-Knowledge Proofs.

Cryptanalysis: Public-Key & The Power of Interaction

Explores cryptanalysis in public-key systems and the power of interaction in interactive proofs, covering CO-NP, NP classes, P vs. NP, and more.

Graphical Models: Representing Probabilistic Distributions

Covers graphical models for probabilistic distributions using graphs, nodes, and edges.

Complex Systems: Critical Phenomena

Explores critical phenomena in complex systems, including stochastic objects, percolation, and combinatorial optimization.

Complexity & Induction: Algorithms & Proofs