Advances in Cryptology - CRYPTO '87

Zero-knowledge interactive proofsystems are a new technique which can be used as a cryptographic tool for designing provably secure protocols. Goldwasser, Micali, and Rackoff originally suggested this technique for controlling the knowledge released in an interactive proof of membership in a language, and for classification of languages [19]. In this approach, knowledge is defined in terms of complexity to convey knowledge if it gives a computational advantage to the receiver, theory, and a message is said for example by giving him the result of an intractable computation. The formal model of interacting machines is described in [19, 15, 171. A proof-system (for a language L) is an interactive protocol by which one user, the prover, attempts to convince another user, the verifier, that a given input x is in L. We assume that the verifier is a probabilistic machine which is limited to expected polynomial-time computation, while the prover is an unlimited probabilistic machine. (In cryptographic applications the prover has some trapdoor information, or knows the cleartext of a publicly known ciphertext) A correct proof-system must have the following properties: If XE L, the prover will convince the verifier to accept the pmf with very high probability. If XP L no prover, no matter what program it follows, is able to convince the verifier to accept the proof, except with vanishingly small probability.

Inhalt

Communication Networks and Standards.- Standards for Data Security - a Change of Direction.- Integrating Cryptography in ISDN.- Protocols.- Special Uses and Abuses of the Fiat-Shamir Passport Protocol (extended abstract).- Direct Minimum-Knowledge Computations (Extended Abstract).- Non-Interactive Zero-Knowledge Proof Systems.- How to Solve any Protocol Problem - An Efficiency Improvement (Extended Abstract).- Multiparty Computations Ensuring Privacy of Each Party's Input and Correctness of the Result.- Society and Group Oriented Cryptography: a New Concept.- A Simple and Secure Way to Show the Validity of Your Public Key.- Cryptographic Computation: Secure Fault-Tolerant Protocols and the Public-Key Model (Extended Abstract).- Gradual and Verifiable Release of a Secret (Extended Abstract).- Strong Practical Protocols.- Key Distribution Systems.- Identity-based conference key distribution systems.- On the KEY PREDISTRIBUTION SYSTEM: A Practical Solution to the Key Distribution Problem.- Key Distribution Systems Based on Identification Information.- Secret Distribution of Keys for Public-Key Systems.- Public Key Systems.- An Impersonation-Proof Identity Verification Scheme.- Arbitration in Tamper Proof Systems.- Efficient Digital Public-Key Signatures with Shadow.- Security-Related Comments Regarding McEliece's Public-Key Cryptosystem.- Design and Analysis of Cryptographic Systems.- Components and Cycles of a Random Function.- Fast Spectral Tests for Measuring Nonrandomness and the DES.- Other Cycling Tests for DES.- A Crypto-Engine.- A Natural Taxonomy for Digital Information Authentication Schemes.- Analyzing Encryption Protocols Using Formal Verification Techniques (Extended Abstract).- Cryptosystems based on an analog of heat flow.- A Combinatorial Approach to Threshold Schemes.- A Realization Scheme for the Identity-Based Cryptosystem.- Equivalence Between Two Flavours of Oblivious Transfers.- A construction for authentication / secrecy codes from certain combinatorial designs.- Applications.- A Digital Signature Based on a Conventional Encryption Function.- How to Make Replicated Data Secure.- A Study of Password Security.- A Video Scrambling Technique Based On Space Filling Curves (Extended Abstract).- Secure Audio Teleconference.- Informal Contributions.- Attack on the Koyama-Ohta Identity Based Key Distribution Scheme.- On the F-function of FEAL.- Patterns of Entropy Drop of the Key in an S-Box of the DES (Extended Abtract).- The Rao-Nam Scheme is Insecure Against a Chosen-Plaintext Attack.- On Struik-Tilburg Cryptanalysis of Rao-Nam Scheme.- A Generalization of Hellman's Extension of Shannon's Approach to Cryptography (Abstract).- Multiparty Unconditionally Secure Protocols (Abstract).