Lecture

Weak Fiat-Shamir: Vulnerabilities in Cryptographic Protocols

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-506: Seminar on applied cryptography

This seminar introduces the participants to the current trends, problems, and methods in the area of communication security. ...

Description

This lecture discusses the vulnerabilities associated with the Fiat-Shamir heuristic and its implications for the Helios electronic voting system. The instructor introduces Sigma Protocols, which allow a prover to demonstrate knowledge of a secret without revealing it. The lecture explains how the Fiat-Shamir transformation can convert these interactive protocols into non-interactive ones, emphasizing the importance of security properties such as special soundness and zero-knowledge. The presentation highlights two significant attacks on the Helios system: a denial of service attack that invalidates elections and a more severe attack that enables an attacker to manipulate election outcomes. The discussion includes a detailed analysis of how weak Fiat-Shamir transformations can lead to security flaws, particularly in the context of Helios. The lecture concludes with recommendations for using strong Fiat-Shamir transformations to enhance security, while also considering the trade-offs between security and efficiency in cryptographic applications.

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

Related concepts (32)

Cryptography

Cryptography, or cryptology (from κρυπτός "hidden, secret"; and γράφειν graphein, "to write", or -λογία -logia, "study", respectively), is the practice and study of techniques for secure communication in the presence of adversarial behavior. More generally, cryptography is about constructing and analyzing protocols that prevent third parties or the public from reading private messages. Modern cryptography exists at the intersection of the disciplines of mathematics, computer science, information security, electrical engineering, digital signal processing, physics, and others.

Key (cryptography)

A key in cryptography is a piece of information, usually a string of numbers or letters that are stored in a file, which, when processed through a cryptographic algorithm, can encode or decode cryptographic data. Based on the used method, the key can be different sizes and varieties, but in all cases, the strength of the encryption relies on the security of the key being maintained. A key's security strength is dependent on its algorithm, the size of the key, the generation of the key, and the process of key exchange.

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.

Electoral system

An electoral system or voting system is a set of rules that determine how elections and referendums are conducted and how their results are determined. Electoral systems are used in politics to elect governments, while non-political elections may take place in business, non-profit organisations and informal organisations. These rules govern all aspects of the voting process: when elections occur, who is allowed to vote, who can stand as a candidate, how ballots are marked and cast, how the ballots are counted, how votes translate into the election outcome, limits on campaign spending, and other factors that can affect the result.

Cryptographic protocol

A cryptographic protocol is an abstract or concrete protocol that performs a security-related function and applies cryptographic methods, often as sequences of cryptographic primitives. A protocol describes how the algorithms should be used and includes details about data structures and representations, at which point it can be used to implement multiple, interoperable versions of a program. Cryptographic protocols are widely used for secure application-level data transport.

Related lectures (64)

E-Voting: Research and Challenges

Explores e-voting research, digital algorithms, privacy challenges, and cryptographic methods in ensuring legitimacy and participation.

Digital Voting Systems: Security and Verifiability

Explores the security and verifiability of digital voting systems, including in-person and remote e-voting, focusing on protection against tampering and ballot counting efficiency.

Commitment Scheme and PRNG

Explores the commitment scheme, key derivation function, and pseudorandom generator in cryptographic protocols, emphasizing their role in ensuring data integrity and authentication.

Hash Functions: Security and Applications

Explores hash functions, their security, common attacks, and applications in data verification and blockchain.

Technologies for Identity & Anonymity