Overview

Content

?Zero-knowledge: Fiat-Shamir, Feige-Fiat-Shamir

?Secret sharing: threshold scheme, perfect schemes

?Special purpose signatures: undeniable signatures

In this chapter we review other particular cryptographic protocols. Although they have a minor practical relevance when compared to encryption or signature, they beautifully illustrate how cryptography can be a fun and a highly technical science.

11.1 ?Zero-Knowledge

All access control protocols that we have seen so far leak some information (which is not necessarily useful). For instance, password access controls require to disclose the password. Challenge-response protocols aim at proving the knowledge of a password, but require to disclose responses for some given challenges. Complexity theory can however show that it is possible to make access control without disclosing any information through the puzzling notion of zero-knowledge proof of knowledge. This is made possible by the power of interaction.

This puzzling concept was first introduced by Shafi Goldwasser, Silvio Micali, and Charles Rackoff in the eighties (see Ref. [78]). The concept of power of interaction was further extended by Adi Shamir who proved that all languages which can be accepted by an interactive proof are actually all languages which can be accepted by a Turing machine limited by a polynomially bounded memory space. This result was stated by the equation IP=PSPACE (for "Interactive Proof" and "Polynomial space"; see Ref. [166]).