US5515307A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Pseudo-random generator
Assignee: Nytell Software LLC
•
Filing: 1994-08-04
•
Granted: 1996-05-07
•
Expires: 2014-08-04
Abstract
Abstract A method for generating random bits which is as fast as popular generators and which has provable strong properties. The method makes use of the unpredictability properties of a relatively slow cryptographically strong generator and the rapid mixing properties of random walks on expander graphs. Use of the cryptographically strong generator is typically restricted to a small off-line or a preprocessing step. Subsequent bits are produced with a few register operations per bit. The method and concomitant generator are useful in at least two different types of applications: for faster reliable simulations (or randomizing algorithms), and cryptographic/encryption schemes.
Inventors
- 👤 William A. Aiello
- 👤 Sivaramakrishnan Rajagopalan
- 👤 Ramarathnam Venkatesan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 22:56
CPC Classifications
H; H04; H04L; H04L9/00; H04L9/06; H04L9/065; H04L9/0656; H04L9/0662; H04L2209/00; H04L2209/12
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
154 words
A method for generating an output stream of cryptographically strong pseudo-random bits from an input stream of either cryptographically strong pseudo-random bits or weakly random bits, the method comprising the steps of (a) forming a matrix of bits from the input stream, (b) forming a seed from the input stream, (c) selecting a first set of bits from the input stream, using the first set to select rows from the matrix and bitwise exclusive-OR'ing the selected rows to generate a matrix bit stream, (d) selecting a second set of bits from the input stream, using the second set to generate a graph bit stream, the initial graph bit stream being obtained from a neighbor of the seed, with each subsequent graph bit stream being obtained from a neighbor of each previous graph bit stream, and (e) generating the output stream as the bitwise exclusive-OR of the matrix bit stream and the graph bit stream.
Claim 2
Independent Claim
154 words
A method for generating an output stream of cryptographically strong pseudo-random bits from an input stream of either cryptographically strong pseudo-random bits or weakly random bits, the method comprising the steps of (a) forming a matrix of bits from the input stream, (b) forming a seed from the input stream, (c) selecting a first set of bits from the input stream, using the first set to select rows from the matrix and bitwise exclusive-OR'ing the selected rows to generate a matrix bit stream, (d) selecting a second set of bits from the input stream, using the second set to generate a graph bit stream, the initial graph bit stream being obtained from a neighbor of the seed, with each subsequent graph bit stream being obtained from a neighbor of each previous graph bit stream, and (e) generating the output stream as the bitwise exclusive-OR of the matrix bit stream and the graph bit stream.
Claim 3
Independent Claim
212 words
A method for generating an output stream of cryptographically strong pseudo-random bits from an input stream of either cryptographically strong pseudo-random bits or weakly random bits, the method comprising the steps of (a) forming a matrix of bits from the input stream, (b) forming a seed from the input stream, (c) selecting a first set of bits from the input stream for processing by a matrix processor, the matrix processor having the matrix of bits and the first set of bits as inputs, and causing the matrix processor to use the first set to select rows from the matrix and to generate a matrix bit stream as the bitwise exclusive-OR of the selected rows, (d) selecting a second set of bits from the input stream for processing by a graph processor, the graph processor having the seed and the first set of bits as inputs, and causing the graph processor to use the first set of bits to generate a graph bit stream, the initial graph bit stream being determined from a neighbor of the seed, with each subsequent graph bit stream being determined from a neighbor of each previous graph bit stream, and (e) generating the output stream as the bitwise exclusive-OR of the matrix bit stream and the graph stream.
Claim 4
Independent Claim
212 words
A method for generating an output stream of cryptographically strong pseudo-random bits from an input stream of either cryptographically strong pseudo-random bits or weakly random bits, the method comprising the steps of (a) forming a matrix of bits from the input stream, (b) forming a seed from the input stream, (c) selecting a first set of bits from the input stream for processing by a matrix processor, the matrix processor having the matrix of bits and the first set of bits as inputs, and causing the matrix processor to use the first set to select rows from the matrix and to generate a matrix bit stream as the bitwise exclusive-OR of the selected rows, (d) selecting a second set of bits from the input stream for processing by a graph processor, the graph processor having the seed and the first set of bits as inputs, and causing the graph processor to use the first set of bits to generate a graph bit stream, the initial graph bit stream being determined from a neighbor of the seed, with each subsequent graph bit stream being determined from a neighbor of each previous graph bit stream, and (e) generating the output stream as the bitwise exclusive-OR of the matrix bit stream and the graph stream.
Claim 5
Dependent Claim
63 words
The method as recited in claim 2 wherein the graph processor is based on an expander graph having a number of nodes corresponding to the number of rows of the matrix, and the second set of bits is used as an index to select the neighbor of each previous graph bit stream on the expander graph to produce each subsequent graph bit stream.
Claim 6
Dependent Claim
29 words
The method as recited in claim 3 wherein the expander graph is a 5-regular graph with neighborhood rule such that node (a,b) is connected to (a,b), (a,a+b+0.5±0.5), and (a+b+0.5±0.5,b).
Claim 7
Dependent Claim
31 words
The method as recited in claim 3 wherein the expander graph is a 7-regular graph with neighborhood rule such that node (a,b) is connected to (a,b), (a+2b,b), (2a+b,b), (a,2a+b+0.5±0.5), and (a+2b+0.5±0.5,b).
Claim 8
Dependent Claim
16 words
The method as recited in claim 3 wherein the expander graph is a L-dimensional hypercube G'.
Claim 9
Dependent Claim
85 words
The method as recited in claim 2 wherein the matrix is designated by R with R having n rows and L columns, wherein the first set of bits has k elements each log n bits in length, the k elements being designated i 1 , i 2 , . . . , i k and wherein the matrix bit stream is computed as R i 1 !⊕R i 2 !⊕ . . . ⊕R i k ! where R i! represents the entire i-th row.
Claim 10
Dependent Claim
208 words
Circuitry for generating an output stream of cryptographically strong pseudo-random bits from an input stream of either cryptographically strong pseudo-random bits or weakly random bits, the circuitry comprising means, responsive to the input stream, for forming a matrix of bits from the input stream, means, responsive to the input stream, for forming a seed from the input stream, means, responsive to the input stream, for selecting a first set of bits from the input stream, means, responsive to the first set of bits, for selecting rows from the matrix and for bitwise exclusive-OR'ing the selected rows to produce a matrix bit stream, means, responsive to the input stream, for selecting a second set of bits from the input stream, means, responsive to the second set of bits and the first seed, for determining a graph bit stream, said means for determining the graph bit stream including means for evaluating a neighbor of each previous graph bit stream to produce each subsequent graph bit stream, with the initial graph bit stream being determined from said seed, and means, responsive to said matrix bit stream and said graph bit stream, for generating the output stream as the the bitwise exclusive-OR of the matrix bit stream and the graph bit stream.
Claim 11
Dependent Claim
208 words
Circuitry for generating an output stream of cryptographically strong pseudo-random bits from an input stream of either cryptographically strong pseudo-random bits or weakly random bits, the circuitry comprising means, responsive to the input stream, for forming a matrix of bits from the input stream, means, responsive to the input stream, for forming a seed from the input stream, means, responsive to the input stream, for selecting a first set of bits from the input stream, means, responsive to the first set of bits, for selecting rows from the matrix and for bitwise exclusive-OR'ing the selected rows to produce a matrix bit stream, means, responsive to the input stream, for selecting a second set of bits from the input stream, means, responsive to the second set of bits and the first seed, for determining a graph bit stream, said means for determining the graph bit stream including means for evaluating a neighbor of each previous graph bit stream to produce each subsequent graph bit stream, with the initial graph bit stream being determined from said seed, and means, responsive to said matrix bit stream and said graph bit stream, for generating the output stream as the the bitwise exclusive-OR of the matrix bit stream and the graph bit stream.
Claim 12
Independent Claim
167 words
A method for generating successive output streams of cryptographically strong pseudo-bits from an input stream of either cryptographically strong pseudo-random bits or weakly random bits, the method comprising the steps of (a) forming a matrix of bits from the input stream, (b) forming a seed from the input stream, (c) selecting a first set of bits from the input stream, using the first set to select rows from the matrix and bits wise exclusive-OR'ing the selected rows to generate a matrix bit stream, (d) selecting a second set of bits from the input stream, using the second set to generate a graph bit stream, the initial graph bit stream being obtained from a neighbor of the seed, with each subsequent graph bit stream being obtained from a neighbor of each previous graph bit stream, (e) generating the output stream as the bitwise exclusive-0R of the matrix bit stream and the graph bit stream, and (f) returning to steps (c), (d), and (e) to generate successive output streams.
Claim 13
Independent Claim
167 words
A method for generating successive output streams of cryptographically strong pseudo-bits from an input stream of either cryptographically strong pseudo-random bits or weakly random bits, the method comprising the steps of (a) forming a matrix of bits from the input stream, (b) forming a seed from the input stream, (c) selecting a first set of bits from the input stream, using the first set to select rows from the matrix and bits wise exclusive-OR'ing the selected rows to generate a matrix bit stream, (d) selecting a second set of bits from the input stream, using the second set to generate a graph bit stream, the initial graph bit stream being obtained from a neighbor of the seed, with each subsequent graph bit stream being obtained from a neighbor of each previous graph bit stream, (e) generating the output stream as the bitwise exclusive-0R of the matrix bit stream and the graph bit stream, and (f) returning to steps (c), (d), and (e) to generate successive output streams.
Claim 14
Independent Claim
217 words
A method for generating successive output streams of cryptographically strong pseudo-random bits or weakly random bits, the method comprising the steps of (a) forming a matrix of bits from the input stream, (b) forming a seed from the input stream, (c) selecting a first set of bits from the input stream for processing by a matrix processor, the matrix processor having the matrix of bits and the first set of bits as input, and causing the matrix processor to use the first set to select rows from the matrix and to generate a matrix bit stream as the bitwise exclusive OR of the selected rows, (d) selecting a second set of bits from the input stream for processing by a graph processor, the graph processor having the seed and the second set of bits as inputs and causing the graph processor to use the first set of bits to generate a graph bit stream, the initial graph bit stream being determined from a neighbor of the seed, with each subsequent graph bit stream being determined from a neighbor of each previous graph bit stream, (e) generating the output stream as the bitwise exclusive-0R of the matrix bit stream and the graph bit stream, and (f) returning to steps (G), (d), and (e) to generate successive output streams.
Claim 15
Independent Claim
217 words
A method for generating successive output streams of cryptographically strong pseudo-random bits or weakly random bits, the method comprising the steps of (a) forming a matrix of bits from the input stream, (b) forming a seed from the input stream, (c) selecting a first set of bits from the input stream for processing by a matrix processor, the matrix processor having the matrix of bits and the first set of bits as input, and causing the matrix processor to use the first set to select rows from the matrix and to generate a matrix bit stream as the bitwise exclusive OR of the selected rows, (d) selecting a second set of bits from the input stream for processing by a graph processor, the graph processor having the seed and the second set of bits as inputs and causing the graph processor to use the first set of bits to generate a graph bit stream, the initial graph bit stream being determined from a neighbor of the seed, with each subsequent graph bit stream being determined from a neighbor of each previous graph bit stream, (e) generating the output stream as the bitwise exclusive-0R of the matrix bit stream and the graph bit stream, and (f) returning to steps (G), (d), and (e) to generate successive output streams.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-05-07 | 1999-11-06 | 2000-05-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-05-07 | 2003-11-06 | 2004-05-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-05-07 | 2007-11-06 | 2008-05-07 | $7700.00 | Window Closed / Lapsed |