Search
Now showing items 1-10 of 12
Time-lock Puzzles and Timed-release Crypto
(1996-02)
Our motivation is the notion of ``timed-release crypto,'' where the goal is to encrypt a message so that it can not be decrypted by anyone, not even the sender, until a pre-determined amount of time has passed. The goal ...
A Fast Signature Scheme
(1978-05)
In this paper we propose a new scheme for generating and verifying "electronic signatures" in public-key communications. The scheme is based on the difficulty of solving the knapsack problem, and its two main advantages ...
The Cryptographic Security of Compact Knapsacks (Preliminary Report)
(1980-04)
In 1978, Merkle and Hellman introduced a knapsack-based public-key cryptosystem, which received widespread attention. The two major open problems concerning this cryptosystem are: (i) Security: How difficult are the ...
Finding Minimum Cutsets in Reducible Graphs
(1977-06)
The analysis of many processes modelled by directed graphs requires the selection of a subset of vertices which cut all the cycles in the graph. Reducing the size of such a cutset usually leads to a simpler and more efficient ...
Factoring Numbers in 0(log n) Arithmetic Steps
(1977-11)
In this paper we show that a non-trivial factor of a composite number n can be found by performing arithmetic steps in a number proportional to the number of bits in n, and thus there are extremely short straight-line ...
On the Security of the Merkle-Hellman Cryptographic Scheme
(1978-12)
In this paper we show that a simplified version of the Merkel-Hellman public-key cryptographic system is breakable. While their full-fledged system seems to be resistant to the cryptanalytic attack we propose, this result ...
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 & ...
How to Share a Secret
(1979-05)
In this paper we show how to divide data D into n pieces in such a way that D is easily reconstructable from any k pieces, but even complete knowledge of k-1 pieces reveals absolutely no information about D. This technique ...
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 ...
Embedding Cryptographic Trapdoors in Arbirtrary Knapsack Systems
(1982-09)
In this paper we show that after sufficiently many modular multiplications, any knapsack system becomes a trapdoor system that can be used in pubic-key cryptography.