Combination of values from a pseudo-random source

• US 8,468,186 B2
• Filed: 08/05/2010
• Issued: 06/18/2013
• Est. Priority Date: 08/05/2009
• Status: Expired due to Fees

• Current Assignee: Verayo, Inc.
• Original Assignee: Verayo, Inc.
• Inventors: Yu, Meng-Day
• Primary Examiner(s): Malzahn, David H
• Application Number:
  US12/850,849
• Publication Number:
  US 20110066670A1
• Time in Patent Office: 1,048 Days
• Field of Search: None
• US Class Current: 708/250
• CPC Class Codes: G06F 7/582 Pseudo-random number generators
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 9/3278 using physically unclonable functions [PUF]

Abstract

Values generated by at least one pseudo-random source (PRS) are recombined to form one or more recombined values. The method involves using analog, digital, or hybrid manipulation techniques to transform characteristics of PRS, including but not limited to statistical characteristics, and input/output characteristics. In some examples, the recombination method provides a way to de-bias output bits from PRS without appreciable increase in self noise. In some examples, the recombined result passes NIST'"'"'s Statistical Tests for Randomness even if underlying PRS natively does not. In some examples, the recombination method provides a way to make a PRS challengeable, even if the underlying PRS is not natively challengeable. In some examples, recombination is used to allow single PRS to have multiple outputs, and in some cases multi-dimensional (orthogonal) outputs. In some examples, a multi-modal system is created via recombination using multiple PRS. In some examples, post recombined result exhibit super error characteristics (prior to application of any error correction codes) compared to native PRS output. In some examples, the recombined values are applied to security applications, for instance authentication and/or cryptographic functions, which may provide improved characteristics (e.g., cryptographic strength) in view of a de-biased output which in some examples also passes NIST'"'"'s Statistical Tests.

Claims

1. A device comprising:

an input for accepting a challenge value;

a pseudo-random source, comprising circuitry for generating one or more device-specific quantities, each quantity depending on device-specific characteristics that vary among like devices formed according to a common design, each of the device-specific quantities representing a degree of comparison of devices-specific characteristics, wherein the circuitry for generating the device-specific quantities includes an output for passing each device-specific quantity as a digital value having a multiple bit representation;

circuitry configured to combine the generated device-specific quantities according to a challenge input;

a recombination module coupled to the input for accepting the challenge and coupled to the pseudo-random source, the recombination module being configurable according to the challenge value to combine values received from the pseudo-random source according to a combination function dependent on the challenge value to form a combined pseudo-random value; and

an output for providing the combined pseudo-random value.

2. The device of claim 1 further comprising at least one of:

(1) an authentication component responsive to the combined value, (2)a cryptographic component responsive to the combined value for generating a secret value, and (3) an error correction module for determining and/or using error correction data for the combined value.

3. The device of claim 1 wherein the challenge value comprises an N-bit value, where N≧

32, and the recombination module is configurable in at least 2^N configurations.

4. The device of claim 1 further comprising the pseudo-random source, said source being coupled to the recombination module.

5. The device of claim 4 wherein the pseudo-random source is configured to provide a plurality of values, each value comprising a multiple-bit representation of a measurable physical characteristics.

6. The device of claim 4 wherein the pseudo random source provides values according to a seed value.

7. The device of claim 6 wherein the seed value comprises a fixed seed value.

8. The device of claim 1 further comprising an input for accepting values determined from the pseudo-random source, said input being coupled to the recombination module.

9. The device of claim 8 wherein the input for accepting values determined from the pseudo-random source comprises a sensor for determining measurements of physical characteristics associated with the source.

10. The device of claim 9 wherein the physical characteristics comprise at least one of manufacturing characteristics and biometric characteristics.

11. The device of claim 1 wherein the pseudo-random source comprises multiple separate pseudo-random sources, at least one of the separate sources being external to the device.

12. The device of claim 1 wherein the recombination module is configured to form successive recombined values, each recombined value being formed from a recombination function and a different instantaneous challenge determined from the challenge input.

13. The device of claim 12 further comprising a sequence generator for accepting the challenge input and deterministically generating a sequence of instantaneous challenge values.

14. The device of claim 13 wherein the sequence generator comprises a linear feedback shift register.

15. The device of claim 1 wherein the degree of comparison includes a polarity and magnitude.

16. The device of claim 1 wherein the challenge input selects different combination functions.

17. The device of claim 1 wherein the challenge input selects a region of the device-specific characteristics.

18. The device of claim 1 wherein the challenge input is used to affect weighting of the device specific values.

19. The device of claim 18 wherein the weighting of values comprise weights by values in a set of +1, −

1 and 0.

20. The device of claim 1 wherein the circuitry to combine the challenge input and the device-specific values forms a non-linear combination of the challenge and device specific values.

21. The device of claim 1 wherein the circuitry to combine the challenge and the device-specific values includes circuitry to form a linear function of the device-specific values, the linear function being configured according to the challenge input.