INDEX-BASED CODING WITH A PSEUDO-RANDOM SOURCE

• US 20110033041A1
• Filed: 08/05/2010
• Published: 02/10/2011
• Est. Priority Date: 08/05/2009
• Status: Active Grant

• Current Assignee: Verayo, Inc.
• Original Assignee: Verayo, Inc.
• Inventors: Devadas, Srinivas, Yu, Meng-Day
• Granted Patent: US 8,811,615 B2
• Time in Patent Office: Days
• US Class Current: 380/28
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• CPC Class Codes: H04L 9/0662 with particular pseudorandom sequence generator
• CPC Class Codes: H04L 9/3278 using physically unclonable functions [PUF]

Abstract

Outputs from at least one pseudo-random source are used to encode hidden value. The hidden value is encoded using index based quantities, for example, based on numerically ordering a sequence of outputs from pseudo-random source(s). In some examples, the numerical ordering of re-generated device-specific quantities is used to re-generate the hidden value, without necessarily requiring additional error correction mechanisms. Information leak may be reduced by constructing system whose “syndrome” helper bits are random, as measured, for example, by NIST'"'"'s Statistical Tests for Randomness In some examples, index based coding provides coding gain that exponentially reduces total error correction code complexity, resulting in efficiently realizable PRS-based key generation systems. In some examples, index based coding allows noisy PRS to be robust across conditions where conventional error correction code cannot error correct.

Claims

1. A method comprising:

accepting an encoding of first data as data representing a set of one or more indices formed based on a first series of quantities generated by a pseudo-random source, the data representing the indices being insufficient to reproduce the first data;

generating a second series of quantities with the pseudo-random source, the set of one or more indices identifying quantities in the second series; and

combining the set of one or more indices and the second series of quantities to reproduce first data.

2. The method of claim 1 wherein generating the second series of quantities includes accepting a challenge value and generating said quantities according to the accepted value, wherein the set of one or more indices were formed according to said challenge value.

3. The method of claim 1 wherein the first data include a plurality of elements, wherein reproducing each element of the first data includes combining a subset of the indices and a subset of the second series of quantities based on the pseudo-random source to reproduce the element.

4. The method of claim 3 the subsets of quantities used to reproduce different of the elements are disjoint subsets.

5. The method of claim 1 wherein the pseudo-random source includes a plurality of separate pseudo-random sources.

6. The method of claim 5 wherein at least one of the separate pseudo-random sources is integrated in a device that performs the combining of the indices and the second series of quantities, and at least another is separate from the device.

7. A decoder comprising:

an input for receiving an encoding of first data as data representing a set of one or more indices;

a pseudo-random source for generating a series of quantities; and

a combination module for combining the set of one or more indices and the series of quantities to reproduce first data.

8. The decoder of claim 7 wherein the pseudo random source is configurable to generate the series of quantities according to a challenge value.

9. The decoder of claim 7 wherein the encoding of the first data includes error correction data, and the decoder further includes an error corrector for application to the encoding after processing by the combination module.

10. The decoder of claim 7 wherein the pseudo-random source is integrated in a device that implements the combination module.

11. The decoder of claim 7 wherein the pseudo-random source comprises a plurality of separate pseudo-random sources, at least one of which is integrated in a device that implements the combination module, and at least one of which that is separate from the device.

12. A method comprising:

generating a first series of quantities based on a pseudo-random source, each quantity being represented as a multiple bit representation;

accepting first data for encoding; and

encoding the first data as a first set of one or more indices into the series of generated values according to a mapping function from the generated values to functions of index positions in the series.

13. The method of claim 12 wherein generating the first series of quantities includes accepting a challenge value and generating said quantities according to the accepted value.

14. The method of claim 12 wherein the mapping function depends on a numerical ordering of the quantities in the first series.

15. The method of claim 12 further comprising:

generating a second series of quantities based on the pseudo-random source, the quantities in the first series corresponding to the quantities in the second series; and

combining the first set of one or more indices and the second series of quantities to reproduce the first data.

16. The method of claim 15 wherein generating the first series of quantities includes generating said quantities according to a challenge value, and where generating the second series of quantities includes generating said quantities according to the challenge value.

17. The method of claim 12 wherein the pseudo-random source depends on device-specific characteristics that vary among like devices formed according to a common design.

18. The method of claim 12 wherein each of the series of quantities represents a degree of comparison of device-specific values.

19. The method of claim 18 wherein each quantity includes a polarity and a magnitude of the comparison.

20. An encoder comprising:

a pseudo-random source for generating a first series of quantities, each quantity being represented as a multiple bit representation;

an input for receiving first data for encoding;

a encoding module for determining a first set of one or more indices into the series of generated values according to a mapping function from the generated values to functions of index positions in the series; and

an output for providing the determined indices.

21. The encoder of claim 20 wherein the pseudo random source is configurable to generate the series of quantities according to a challenge value.