DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

EDITORS: Joan Feigenbaum and Michael Merritt
Published by the American Mathematical Society

Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.

You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.


On October 4,5, and 6, 1989, seventy-four people from twenty-three institutions in five countries met at the Nassau Inn in Princeton, New Jersey, to take a critical look at current research and development efforts in the fields of distributed computing and cryptography. Much of the material covered at this highly successful workshop is contained in this volume.

The first item in these proceedings is a technical report containing a summary of the open questions raised during informal discussions, short abstracts of the formal presentations, names and addresses of the participants, and a bibliograpy. The rest of the proceedings consists of fifteen papers based on talks presented at the workshop and two additional contributed papers on related topics. (The two papers that were not presented at the workshop are "Formal Definitions for Secure Distributed Protocols," by Donald Beaver, and "On expected polynomial time simulation of zero knowledge protocols," by Uriel Feige and Adi Shamir.) These are unrefereed papers, many of which describe ongoing research; we expect authors to write longer, more formal papers on some of these projects for refereed journals.

We would like to thank the DIMACS executive committee for sponsoring the Workshop and all of the participants for making it so successful and enjoyable.


Preface                                                        vii
Foreword                                                       ix

Open Questions, Talk Abstracts, and Summary of Discussions
	Joan Feigenbaum and Michael Merritt		     	1

Formal Definitions for Secure Distributed Protocols
	Donald Beaver					       47

Perfect Privacy For Two-Party Protocols
	Donald Beaver 					       65

On the Structure of Secret Key Exchange Protocols
	Mihir Bellare, Lenore Cowen, and Shafi Goldwasser      79

Privacy-Enhanced Electronic Mail
	Matt Bishop					       93

Program Result Checking against Adaptive Programs and in
      Cryptographic Settings
	Manuel Blum, Michael Luby, and Ronitt Rubinfeld       107

The Scope of a Logic of Authentication
	Michael Burrows, Martin Abadi, and Roger Needham      119

Secure Policy Enforcement in Internetworks
	Deborah Estrin and Gene Tsudik 			      127

On Expected Polynomial Time Simulation of Zero Knowledge 
	Uriel Feige and Adi Shamir			      155
Cryptographic Protection of Databases and Software
	Joan Feigenbaum, Mark Y. Liberman, 
          and Rebecca N. Wright                               161

Secret Bit Transmission Using a Random Deal of Cards
 	Michael J. Fischer, Michael S. Paterson, 
          and Charles Rackoff                                 173

Security against Replay Chosen-Ciphertext Attack
	Zvi Galil, Stuart Haber, and Moti Yung                183

New Directions In Testing
	Richard J. Lipton                                     191

Towards a Theory of Cryptographic Systems: A Critique of
	Michael Merritt	                                      203

Feeback in Discrete Communication
	Alon Orlitsky			                      213

On Necessary Conditions for Secure Distributed Computation
	Rafail Ostrovsky and Moti Yung	                      229

Secure IX Network
 	Jim Reeds                                             235

Reasoning about Cryptographic Protocols
	Marie-Jeanne Toussaint and Pierre Wolper              245

Index Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on June 4, 2013.