Browse Prior Art Database

Protocols for Data Security Disclosure Number: IPCOM000131591D
Original Publication Date: 1983-Feb-01
Included in the Prior Art Database: 2005-Nov-11
Document File: 18 page(s) / 64K

Publishing Venue

Software Patent Institute

Related People

Richard DeMillo: AUTHOR [+4]


Georgia Institute of Technology

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 6% of the total text.

Page 1 of 18


This record contains textual material that is copyright ©; 1983 by the Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Contact the IEEE Computer Society (714-821-8380) for copies of the complete work that was the source of this textual material and for all use beyond that as a record from the SPI Database.

Protocols for Data Security

Richard DeMillo and Michael Merritt

Georgia Institute of Technology

Can two mutually suspicious participants play poker over the telephone? Certainly, if they are clever enough to institute a secure protocol.

Alice lives in Atlanta and Bob lives in Detroit. They have never met, but they wish to play poker. After some negotiation, they decide to play cards over the telephone. The first problem that arises is how to deal the cards fairly. If, for instance, Bob deals to Alice, how will Alice know that Bob has not cheated? On the other hand, if Bob manages to somehow deal a fair hand to Alice, without looking at her cards, what will stop Alice from changing her hand to a more favorable one?

The problem confronting Alice and Bob is very similar to problems confronting users of modern communications systems such as electronic funds transfer systems, military communication networks, and distributed database systems. Such systems operate by series of message exchanges, and the possibility always exists that one or more of the participants in the exchanges will cheat to gain some advantage, or that some external agent will interfere with normal communications. Security in this context refers to the ability of such a system to withstand attacks by determined cheaters or enemies. Although other methods have been proposed for withstanding such attacker the methods we will describe in this article require the participants to execute communications algorithms, called protocols.

What are the properties that Alice and Bob's protocol must maintain in order to guard against cheating by either side? The card game they play should have rules just like the ordinary game of poker, except that no cards are actually exchanged. Alice and Bob must know the cards in their own hand, but neither can have any information about the other's hand. The deal must distribute all possible hands with equal probability and should not allow the same card to appear in two hands simultaneously. A player should be able to discard from his own hand and reveal individual cards without compromising the rest of the hand. Alice and Bob should both be able to verify that a preceding game has been fairly played. Finally, both Alice and Bob must be viewed as potential cheaters who cannot be relied upon to follow the rules of the protocol.

The first question to ask is whether Alice and Bob can play poker at all under these constraints. In 1949, Claude Shannon applied information theoretic methods to the study of secure communication sy...