Lecture

Cryptanalysis: Public-Key & The Power of Interaction

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

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 covers the topics of cryptanalysis in public-key systems, focusing on ElGamal signatures and the security implications if certain checks are missed. It also delves into the power of interaction in interactive proofs, exploring concepts like CO-NP and NP classes, P vs. NP problems, Karp reduction, and NP-hardness. The instructor discusses the Goldwasser-Micali-Rackoff protocol, sequential composition in interactive proof systems, and tricky aspects of parallel composition. Through examples like the Coin Flipping Game and the DD Protocol, the lecture illustrates the practical applications and challenges of interactive systems and proofs.

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

Computer engineering

Computer security: Public-key cryptography

Theoretical computer science

Theory of computation: Computational complexity theory

Related concepts (32)

NP (complexity)

In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine, or alternatively the set of problems that can be solved in polynomial time by a nondeterministic Turing machine. NP is the set of decision problems solvable in polynomial time by a nondeterministic Turing machine.

NP-hardness

In computational complexity theory, NP-hardness (non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard problem is the subset sum problem. A more precise specification is: a problem H is NP-hard when every problem L in NP can be reduced in polynomial time to H; that is, assuming a solution for H takes 1 unit time, Hs solution can be used to solve L in polynomial time.

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.

NP-completeness

In computational complexity theory, a problem is NP-complete when: It is a decision problem, meaning that for any input to the problem, the output is either "yes" or "no". When the answer is "yes", this can be demonstrated through the existence of a short (polynomial length) solution. The correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying all possible solutions.

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 (64)

Interactive Proofs: The Power of Interaction

Explores interactive proofs, zero-knowledge, parallel composition, and cryptographic protocols.

Density Operator Formalism

Covers the density operator formalism, polynomial time, NP problems, BPP, QMA, and probabilistic algorithms.

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.

RSA Encryption: Principles and Applications

Explores RSA encryption principles, factorization challenges, and practical applications in data security.

Cryptanalysis: Public-Key