Index-based coding with a pseudo-random source

• US 8,811,615 B2
• Filed: 08/05/2010
• Issued: 08/19/2014
• Est. Priority Date: 08/05/2009
• Status: Active Grant

• Current Assignee: Verayo, Inc.
• Original Assignee: Verayo, Inc.
• Inventors: Yu, Meng-Day, Devadas, Srinivas
• Primary Examiner(s): Pwu, Jeffrey
• Assistant Examiner(s): JHAVERI, JAYESH M
• Application Number:
  US12/850,693
• Publication Number:
  US 20110033041A1
• Time in Patent Office: 1,475 Days
• Field of Search: 713/193, 380 28- 29, 380/42, 380/44, 380/46, 380/47, 380/268
• US Class Current: 380/268
• 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 series of one or more indices formed based on a first series of quantities generated by a first pseudo-random source, the data representing the indices being insufficient to reproduce the first data;

using circuitry implementing a second pseudo-random source, generating a second series of quantities with the second pseudo-random source, the second series of quantities differing from the first series of quantities, the series of one or more indices identifying quantities in the second series; and

combining the series of one or more indices and the second series of quantities to reproduce the 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 series 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 wherein the subset of the indices and the subset of the second series of quantities used to reproduce different of the elements are disjoint subsets.

5. The method of claim 1 wherein one or both of the first pseudo-random source and the second 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. An apparatus comprising:

an encoder including;

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

an input circuit for receiving first data for encoding;

circuitry implementing an encoding module for determining a first series of indices into the generated first series of quantities according to a mapping function from the generated values to functions of index positions in the series; and

an output circuit for providing an encoding of the first data comprising the first series of indices;

a decoder including;

an input circuit for receiving the encoding of the first data comprising the first series of indices

circuitry implementing a second pseudo-random source for generating a second series of quantities different from the first series of quantities; and

circuitry implementing a combination module for combining the first series of indices and the second series of quantities to reproduce the first data wherein the first data include a plurality of elements, and wherein the combination module is configured to reproduce each element of the first data by processing a subset of the second series of quantities corresponding to the element according to a subset of the first series of indices identifying one or more quantities in said subset of the second series of quantities.

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

9. The apparatus 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 apparatus of claim 7 wherein the second pseudo-random source is integrated in a device that implements the combination module.

11. The apparatus of claim 7 wherein the second 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. The apparatus of claim 7 wherein generating the first series of quantities includes accepting a challenge value and generating said quantities according to the accepted value.

13. The apparatus of claim 7 further configured to:

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

14. The apparatus of claim 13 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.

15. The apparatus of claim 7 wherein the first pseudo-random source circuit depends on device-specific characteristics that vary among like devices formed according to a common design.

16. The apparatus of claim 7 wherein each of the series of quantities represents a degree of comparison of device-specific values.

17. The apparatus of claim 16 wherein each quantity includes a polarity and a magnitude of the comparison.

18. The apparatus of claim 7 wherein the first pseudo-random source and the second pseudo-random source are the same pseudo-random source.

19. The apparatus of claim 7 wherein at least one of the first pseudo-random source and the second pseudo-random source is implemented using processor circuitry as a model of the other pseudo-random source.