Search
Now showing items 11-18 of 18
Metal Poker
(1979-02)
Can two potentially dishonest players play a fair game of poker without using any cards (e.g. over the phone)? This paper provides the following answers: 1. No. (Rigorous mathematical proof supplied. 2. Yes. (Correct & ...
K+1 Heads are Better Than K
(1976-09)
There are languages which can be recognized by a deterministic (k+1)-headed one-way finite automaton but which cannot be recognized by a k-headed one-way (deterministic or non-deterministic) finite automaton. Furthermore, ...
A Method for Obtaining Digital Signatures and Public-key Cryptosystems
(1977-04)
We present an encryption method with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key. This has two important consequences. 1. Couriers or other secure ...
The Mutual Exclusion Problem for Unreliable Processes
(1977-04)
Consider n processes operating asynchronously in parallel, each of which maintains a single "public" variable which can be read (but not written) by the other processes. We show that the processes can synchronize their ...
Randomized Encryption Techniques
(1983-01)
A randomized encryption procedure enciphers a message by randomly choosing a ciphertext from a set of ciphertexts corresponding to the message under the current encryption key. At the cost of increasing the required ...
The Markov Chain Tree Theorem
(1983-11)
Let M be a finite first-order stationary Markov chain. We define an arborescence to be a set of edges in the directed graph for M having at most one edge out of every vertex, no cyles, and maximum cardinality. The weight ...