Advances in Cryptology - CRYPTO '88: Proceedings (Lecture Notes in Computer Science, 403)

✍ Scribed by Shafi Goldwasser (editor)

• Publisher: Springer
• Year: 1990
• Tongue: English
• Leaves: 587
• Edition: 1990
• Category: Library

✦ Synopsis

The papers in this volume were presented at the CRYPTO '88 conference on theory and applications of cryptography, held in Santa Barbara, California, August 21-25, 1988. The papers were chosen for their perceived originality and often represent preliminary reports on continuing reserach. The main sections deal with the following topics: Zero-Knowledge, Number Theory, Pseudorandomness, Signatures, Complexity, Protocols, Security, Cryptoanalysis. As such, they will give the committed reader a unique insight into the very latest developments in the field.

✦ Table of Contents

front-matter
Lecture Notes in Computer Science
Foreword
CRYPT0 '88
Table of Contents
fulltext
Introduction
Definitions
Standard forms of oblivious transfer
Nonstandard transfer mechanism
Making honest reductions more robust
The general scenario
The power of noise
A philosophical remark
An outline of our reduction
Acknowledgments
Refernces
fulltext_001
Introduction
Notation and deflnitions
Uniform Generation
Polynomial-time relations
What is uniform generation?
P = NP and uniform generation
An application to cryptography
Random Oracles
Random function oracles
Random oracles and uniform generation
Random Permutation Oracles
Cryptographic Lower Bounds
Introduction
A normal form for secret-key agreement
Notation and definitions
Eve’s sample space
Eve’s algorithm
Intersection queries and the secret
The efficacy of Eve’s algorithm
Related Work and Open Problems
Acknowledgements
References
fulltext_002
Introduction
Preliminaries
Generalized Secret Sharing
Generalized Secret Sharing Homomorphisms
Conclusions
Acknowledgements
References
fulltext_003
Abstract
Introduction
Overview of the construction
Preliminaxies
Interactive proof systems
Arthur-Merlin protocols
Zero-knowledge
Preliminary results
Zero-knowledge proofs for all of NP
Proof of the main theorem
Notarized Envelopes: Description and Implement ation
Introduction to notarized envelopes-
An implementation of notarized envelopes
IP in perfect zero-knowledge with envelopes
References
fulltext_004
ABSTRACT
INTRODUCTION
Known Results
Our Results
PRELIMINARIES
Promise Problems and Interactive Proofs
Perfect Zero-Knowledge Proofs for Promise Problems
The Discrete Logarithm Problem and a Related Promise Problem
Notations
THE PROTOCOL FOR DLPl IN Zp'
Protocol 1 - Perfect Zero Knowledge Proof with respect to the Honest Verifier
Protocol 2 - Perfect Zero Knowledge Proof with respect to Any Verifier
EXTENSIONS
Generalization of the Protocol to other Cyclic Groups
Generalization of the Results to Acyclic Groups
REFERENCES
fulltext_005
Abstract.
Introduction
Definitions
An Example
Zero Knowledge Interactive Proof Systems
Old and New Definitions
Languages Having No Zero Knowledge IPS
A Language With a Recognition Zero Knowledge IPS
Related Work
References
fulltext_006
Abstract.
Introduction
Problems related to factoring
Problems related to discrete logarithms
Algorithms
Practical considerations
Acknowledgements
References
fulltext_007
Abstract.
Theorem.
Remarks.
References
fulltext_008
ABSTRACT
THE PROBLEMS
HOW PROBLEMS AROSE
Problem (1) and its variants
Problems (2a) and (2b)
THE ALGORITHMS
Finding roots with small residual
Without conditions for x
With conditions for x
A Euclidean digression
Come back to our problems
2. Finding something about exact mots
Inferring some partial information about location of %
Finding x,, with some help
CONCLUSION
ACKNOWLEDGEAMENTS
REFERENCES
fulltext_009
Abstract
Introduction
McEliece’s Cryptosystem
Cryptanalysis of the McEliece Cryptosystem
Factoring the encryption matix
Recover message from cryptogram and encryption ma- trix
Main Idea
One Bit Swapping Attack
Number of Swaps
Work factor
F'urther Improvements
Search for one correctable error
Partial search for two correctable errors
General Attack
Reduced Public-Key
Acknowledgement
References
fulltext_010
Abstract
Introduction
The Database
The Search Technique
Interactive Mode
Extensions
Performance
Acknowledgement
References
fulltext_011
INTRODUCTION
Previous Results
Our Results
Subsequent Results
MAINRESULT
Preliminaries
Levin's Criterion: A Modified Version
Main Ideas
The Construction of f'
The game
Proof of Theorem 2
Extensions
Further Remarks:
APPLICATIONS : Pseudorandom Generators Based on Particular Intractabil- ity Assumptions
PRG Based on the Intractability of the General Factoring Problem
PRG Based on the Intractability of Decoding Random Linear Codes
PRG Based on the Average Difficulty of Cornbinatorial Problems
ACKNOWLEDGEMENTS
REFERENCES
fulltext_012
Introduction
Notation
Known Results On the Distribution of Squares Jlodulo a Prime
Jacobi Sequences are Harder to Predict than Legendre Sequences
Emphirical Tests
Practical Implementation
Generalizations
The Linear Congruence hlethod
Using Other Character Values
Conclusion and Open Problems
References
fulltext_013
Abstract
The Complexity Assumption for the Polynomial Random Generator
Hypothesis 2.1
Fact 2.2
Theorem 2.3
Corollary 2.4
Corollary 2.5
Theorem 2.6
Thearem 2.7
3. The Sequential and the Parallel Polynomial Generator
Theorem 3.1
Theorem 3.2
Corollary 3.3
Theorem 3.4
Theorem 3.5
4. Open Problems: Random Number Generators Based on 1 Prime Modulus
Problem 4.1.
Problem 4.2.
Corollary 4.3
fulltext_014
Abstract
INTRODUCTION
SIGNATURE SCHEMES AND THEIR SECU- RITY
Components of a Signature Scheme
Security against Adaptive Chosen Message Attacks
TRAPDOOR PERMUTATIONS
AN OVERVIEW OF THE SCHEME
Background
Untitled
The Signature Scheme
Why is this Secure?
THE SCHEME AND PROOF OF SECURITY
Preliminary Notation and Definitions
Building Blocks for Signing
Generating Keys
What is a Signature?
The Signing Algorithm and Signature Corpus
The Verification Algorithm
Extracting Information From a Forgery
Proof of Security
VARIATIONS AND IMPROVEMENTS
References
fulltext_015
ABSTRACT
Introduction
The GQ authentication scheme
Security of the GQ scheme
Protocols of cooperation between entities
Entities with same exponent and different identities
Two entities with the same identity and different expo- nents
Interactively authenticating both cards and
Swapping to signatures by removing interactiv- ity
The identity-based signature scheme
Exchange authentication: a priori versus a pos- teriori?
References
fulltext_016
Abstract
Introduction
Some Number-Theoretic Results
Sequential Version
Parallel Version
Applications
Efficiency
Conclusion
Acknowledgements
References
fulltext_017
Abstract
Introduction.
The original Fiat-Shamir Scheme
The New Improvement
Remark
fulltext_018
References
fulltext_019
Abstract
Introduction
Our Model Versus the Old One
The Robustness of Our Result
Applications of our Result
What’s Coming
Preliminaries
Notations and Conventions
Number Theory
A Complexity Assumption
Single-Theorem Non-Interactive Zero-Knowledge Proofs
The Proof System (P,V)
A Rough Idea of why (P,V) is a Single-Theorem Non-
Security Against Chosen Ciphertext Attack
References
fulltext_020
Abstract
A quick and dirty exposition of our results
Introduction
Preliminaries
Non-Interactive Zero-Knowledge Proof-Systems
The model
Our protocol
The language V
The implementation
Open Problems
References
fulltext_021
Abstract
Introduction
TheModel
Polynomial Time Verifiers
Knowledge complexity
Further Research
References
fulltext_022
Introduction
Terminology, Notation, and Conventions
Invulnerable Generators
Discussion, Related Work, and Open Problems
Acknowledgements
References
fulltext_023
Secrecy
Bounds on Pdi and b
Constructions for authentication codes "with arbi- trary source distribution
Authentication codes derived from partial geometries
Authentication codes derived from designs
References
fulltext_024
Introduction
Untraceable Coins
Proving Multiple Spending
Untraceable Checks
Blacklisting Withdrawals
Further Work
Acknowledgements
References
fulltext_025
Summary
Related Work
Basic Results
Payment Systems
Credential Mechanisms
Acknowled gemen t
References
fulltext_026
Abstract
Introduction
Preliminary
Complete Sets and Universal Problems
Local Transformation vs Distributed Transformation
Reducibility
The Distributed Sum Problem
Universality of the Distributed Sum Problem
Distributed Boolean Circuit Problem
Two Primitives for the Distributed Boolean Circuit Problem
Reducing the &Simulation Problem to the Distributed Sum
References
fulltext_027
Introduction
Basic Definitions
Types of Viruses
Detecting The Set Of Viruses
Isolation As A Protection Strategy
Further Research
Acknowledgments
References
fulltext_028
Introduction
Abuses
AN INTRODUCTION
ABUSES VERSUS COVERT CHANNELS
ABUSE-FREENESS
PRACTICAL ASPECTS OF THE WARDEN
Abuse-free systems in a general context
How TO GENERATE A PUBLIC KEY IN AN ABUSE-FREE WAY
ABUSE-FREE INTERACTIVE ZERO-KNOWLEDGE
ABUSE-FREE NON-INTERACTIVE ZERO-KNOWLEDGE
Abuse-free crypto-systems: in narrow contexts
ABUSE-FREE PRIVACY
ABUSE-FREE AUTHENTICATION AND SIGNATURES
ABUSE-FREE COIN FLIPPING OVER THE TELEPHONE
Theoretical and practical consequences: conclusion
REFERENCES
fulltext_029
Jntroduction
An Applicatioa (and two Realieationsl of Compattmented shared Secret Schemes
A piscussion of Exceptional Cases
An Application (and Realization) of Hultilevel Shared Secret Schemes
Conclusion
Bibliography
fulltext_030
Abstract
Introduction
Wals h- Spect rum of SAC- fulfilling Functions
Spectral Characterization of Functions FuIAlIing the SAC
Construction of SAC-Fulfilling Functions
Spectral Symmetries of SAC-Fulfilling Functions
Strict Avalanche Criterion of Higher Order
Definitions
Spectral Characterization for SAC of Higher Order
Construction of Functions Fulfilling the SAC of Maxi- mum Order
Conclusion
Acknowledgements
References
fulltext_031
References
fulltext_032
Extended Abstract
References
fulltext_033
Environment
Introduction
Security Requirements
System Requirements
Security Sub-system Overview
System Detail
Local Access Coritrol
Remote Access Control
issue Authority
Privacy o j Commuiiications
Key Management Protocol
Message Authenficctiort
Digital Signatures
Integration with IBM SNA Etrvirorrnieiits
Integration with non- IBM Interactive Environnients
Summary
Bibliography
fulltext_034
Introduction
Related Works and Assumptions
General Idea of Speed Up
Demonstrating the Speed Up Protocols
Speed Up via Coordinate Permutation
Matrix Multiplications
Linear Equations
Graph Isomorphisms
Modular Equations
Speeding Up the RSA Transformations
Secret Powering 1
Secret Powering 2
Conclusion
Acknowledgment
References
fulltext_035
Abstract
Overview of the System
System Architecture
Encryption Keys
Modification Detection
Initializing Controllers
Downline Loading Controllers
Associations
Encrypted Association Set-Up
Unencrypted Association Set-Up
Trust
Determining the Encryption Key
Sequence Numbers
Sequence Numbers Versus Timestamps
Sequence Number Use
Interoperability
Frame Length
Frame Header
Network Maintenance
References
fulltext_036
ABSTRACT
Introduction
Basics of Audio Conferencing
The Distributed Bridge
Distributing Conference Bridge
Key Distribution and Authentication
Conclusions
References
fulltext_037
Abstract
Introduction
Main idea
The main algorithm
Conclusion
References
fulltext_038
Abstract
Key words
Introduction
Joint Encryption and Error Correction (JEEC) Scheme
Secret Error-Correcting Codes (SECC)
SECC Scheme Using Nonlinear Codes
Preparata Nonlinear Codes [Preparata 681
Construction of New Code From Old Codes WacWilliams 771
Encryption and Decryption of SECC Scheme Using Nonlinear Codes
Security of SECC Scheme Using Preparata-Based Nonlinear Codes
SECC Scheme Using Block Chaining Technique
Encryption and Decryption of the Proposed Scheme
Security of the Proposed SECC Scheme
References
fulltext_039
Abstract
Introduction
The construction
A cut-and-choose procedure to eliminate dealer disruption
Remarks
Acknowledgements
Added in proof
References
fulltext_040
References
fulltext_041
References
fulltext_042
Abstract
Introduction
The Basic Authentication Scheme
Combining with Key-Exchange
Practical Implementation
References
back-matter
Author Index