Systems and methods for encoding randomly distributed features in an object

• US 7,577,844 B2
• Filed: 03/17/2004
• Issued: 08/18/2009
• Est. Priority Date: 03/17/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kirovski, Darko
• Primary Examiner(s): Dada; Beemnet W
• Assistant Examiner(s): Debnath; Suman
• Application Number:
  US10/802,981
• Publication Number:
  US 20050210255A1
• Time in Patent Office: 1,980 Days
• Field of Search: 713/176, 713/180, 380/201
• US Class Current: 713/180
• CPC Class Codes: G06K 19/086 with markings consisting of randomly placed or oriented elements, the randomness of the elements being useable for generating a unique identifying signature of the record carrier, e.g. randomly placed magnetic fibers or magnetic particles in the body of a credit card
• CPC Class Codes: G06T 1/0021 Image watermarking
• CPC Class Codes: G06T 2201/0051 Embedding of the watermark in the spatial domain
• CPC Class Codes: G06V 10/48 by mapping characteristic values of the pattern into a parameter space, e.g. Hough transformation
• CPC Class Codes: G06V 20/80 Recognising image objects characterised by unique random patterns
• CPC Class Codes: G07D 7/2033 Matching unique patterns, i.e. patterns that are unique to each individual paper
• CPC Class Codes: G09C 1/00 Apparatus or methods whereby a given sequence of signs, e.g. an intelligible text, is transformed into an unintelligible sequence of signs by transposing the signs or groups of signs or by replacing them by others according to a predetermined system cryptographic typewriters G09C3/00
• CPC Class Codes: H04L 2209/30 Compression, e.g. Merkle-Damgard construction
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 9/3249 using RSA or related signature schemes, e.g. Rabin scheme
• CPC Class Codes: H04L 9/3263 involving certificates, e.g. public key certificate [PKC] or attribute certificate [AC]; Public key infrastructure [PKI] arrangements network architectures or network communication protocols for supporting authentication of entities using certificates in a packet data network H04L63/0823
• CPC Class Codes: H04L 9/3278 using physically unclonable functions [PUF]

Abstract

The described systems and methods described are directed at encoding randomly distributed features in an object. Randomly distributed features in an authentication object are determined. Data representing the randomly distributed features is compressed and encoded with a signature. A label is created and includes the authentication object and the encoded data. The data may be compressed by determining a probability density function associated with the authentication object. Vectors associated with the randomly distributed attributes are determined based, at least in part, on the probability density function. The vectors are encoded using an arithmetic coding algorithm.

Claims

1. A method comprising:

determining randomly distributed features in an object;

determining a probability density function associated with the object;

compressing data representing the randomly distributed features, wherein the compressing is based in part on the probability density function;

encoding the compressed data with a signature; and

creating a label comprising the object and the encoded data;

determining vectors associated with the randomly distributed features based, at least in part, on the probability density function; and

encoding the vectors using an arithmetic coding algorithm, wherein the algorithm comprises;

set U as a list of all unit areas in S−

S_i−

u

list of all marked units, M(u), is set to M(u)=Ø

do

find all unit areas V=argmin<sub>ν

⊂

U</sub>∥

Q_ν

−

Q_u∥

do

find unit area w=argmax<sub>ν

ε

V</sub>ζ

(1, ν

)

set AC range for w to γ

(w,u)

set of nodes ordered before w is M_w(u)=M(u)

M(u)=M(u)∪

w, V=V−

w, U=U−

w

while V≠

Ø

while U≠

Ø

.

2. The method as recited in claim 1, wherein encoding the vectors using the arithmetic coding algorithm includes determining a path for connecting a portion of the vectors within a fixed amount of data.

3. The method as recited in claim 1, wherein the randomly distributed features are fibers that are randomly positioned in the object.

4. The method as recited in claim 3, wherein the probability density function represents a probability that fibers in the particular region are illuminated by a light source.

5. The method as recited in claim 3, wherein the probability density function is derived based, at least in part, on the length of the fibers.

6. The method as recited in claim 3, wherein each vector represents the end points of two fibers.

7. The method as recited in claim 1, wherein the data is encoded with a private key.

8. The method as recited in claim 1, wherein the label is a certificate of authenticity configured to be self-authenticated and wherein the object is an authentication object included in the certificate of authenticity.

9. The method as recited in claim 1, wherein the encoded data is included in the label as a barcode.

10. The method as recited in claim 1, further comprising:

determining textual data that includes a string of characters;

hashing the textual data with an algorithm;

encrypting the compressed data using the hashed textual data; and

including the textual data in the label.

11. The method as recited in claim 10, wherein the algorithm is a cryptographically secure hash algorithm.

12. The method as recited in claim 10, wherein the algorithm is an SHA1 cryptographical algorithm.

13. One or more computer-readable memories containing instructions that are executable by a processor to perform the method recited in claim 1.

14. A system comprising

an issuer configured to determine randomly distributed features in an authentication object and to compress data representing the randomly distributed features comprising fibers, the issuer being further configured to encode the compressed data with a signature and to create a label that includes the authentication object and the encoded data;

wherein the issuer is further configured to determine a probability density function associated with the authentication object, wherein the probability density function is defined as the likelihood of finding a second end of a fiber at a given location within a non-illuminated area when a first end of the fiber is located within an illuminated area of the authentication object, to determine vectors associated with the randomly distributed attributes based, at least in part, on the probability density function, and to encode a portion of the vectors as a path by applying an arithmetic coding algorithm, wherein the algorithm comprises;

set U as a list of all unit areas in S−

S_i−

u

list of all marked units, M(u), is set to M(u)=Ø

do

find all unit areas V=argmin<sub>ν

⊂

U</sub>∥

Q_ν

−

Q_u∥

do

find unit area w=argmax<sub>ν

ε

V</sub>ζ

(1, ν

)

set AC range for w to γ

(w,u)

set of nodes ordered before w is M_w(u)=M(u)

M(u)=M(u)∪

w, V=V−

w, U=U−

w

while V≠

Ø

while U≠

Ø

.

15. The system as recited in claim 14, wherein the probability density function utilizes a perimeter containment function.

16. The system as recited in claim 15, wherein the perimeter containment function assumes that the first end of the fiber can be located anywhere within the authentication object and that the second end of the fiber will be in a location dependent on a location of the first end of the fiber.

17. The system as recited in claim 15, wherein the perimeter containment function comprises different instances, depending on intersection of a perimeter with edges of the authentication object.

18. The system as recited in claim 14, wherein the determined vectors are encoded using a near-minimal number of bits type algorithm.

19. The system as recited in claim 14, further comprising:

a verifier configured to decode the data representing the randomly distributed features in the label and to authenticate the label by comparing the decoded data with the data of the actual randomly distributed features determined from the authentication object.

20. A label comprising:

an authentication object including randomly distributed features; and

encoded information associated with the authentication object, the information being encoded with a signature and including compressed data representing the randomly distributed features in the authentication object, wherein the data in the encoded information is compressed by;

determining a probability density function associated with the authentication object;

determining vectors associated with the randomly distributed attributes based, at least in part, on the probability density function; and

encoding the vectors using an arithmetic coding algorithm;

wherein the label is self-authenticated by comparing the compressed data in the encoded information and the data representing the randomly distributed features obtained by analyzing the authentication object; and

wherein the compressed data was compressed by;

determining vectors associated with the randomly distributed features based, at least in part, on the probability density function; and

encoding the vectors using an arithmetic coding algorithm, wherein the algorithm comprises;

set U as a list of all unit areas in S−

S_i−

u,

list of all marked units, M(u), is set to M(u)=Ø

,

do

find all unit areas V=argmin<sub>ν

⊂

U</sub>∥

Q_ν

−

Q_u∥

, do

find unit area w=argmax<sub>ν

ε

V</sub>ζ

(1, ν

),

set AC range for w to γ

(w,u) (see Eqns. 17,

     18),

set of nodes ordered before w is M_w(u)=M(u),

M(u)=M(u)∪

w, V=V−

w, U=U−

w,

while V≠

Ø

while U≠

Ø

.

21. The label as recited in claim 20, wherein encoded information is included in the label as a barcode.

22. The label as recited in claim 20, wherein encoded information is encoded using a private key.

23. The label as recited in claim 20, further comprising:

textual data that includes a string of characters, wherein the compressed data is encrypted using the textual data.

24. The label as recited in claim 23, wherein compressed data is encrypted by:

hashing the textual data with an algorithm; and

encrypting the compressed data using the hashed textual data.

25. An apparatus comprising:

means for determining randomly distributed features in an authentication object;

means for determining a probability density function associated with the authentication object, wherein the probability density function defines a likelihood a point will contain an illuminated second end of a fiber and is conditioned on location of a first end of the fiber in an illuminated region;

means for compressing data representing the randomly distributed features, wherein the compressing is based in part on the probability density function;

means for encoding the data with a signature; and

means for creating a label that includes the authentication object and the encoded data,

means for determining vectors associated with the randomly distributed features based, at least in part, on the probability density function; and

means for encoding the vectors using an arithmetic coding algorithm, wherein the algorithm comprises;

set U as a list of all unit areas in S−

S_i−

u,

list of all marked units, M(u), is set to M(u)=Ø

,

do

find all unit areas V=argmin<sub>ν

⊂

U</sub>∥

Q_ν

−

Q_u∥

,

do

find unit area w=argmax<sub>ν

ε

V</sub>ζ

(1, ν

),

set AC range for w to γ

(w,u) (see Eqns. 17,

     18),

set of nodes ordered before w is M_w(u)=M(u),

M(u)=M(u)∪

w, V=V−

w, U=U−

w,

while V≠

Ø

while U≠

Ø

.

26. The apparatus as recited in claim 25, further comprising

means for incorporating fibers in the authentication object as the randomly distributed features.

27. The apparatus as recited in claim 25, further comprising:

means for determining vectors associated with the randomly distributed features based, at least in part, on the probability density function; and

means for encoding the vectors using an arithmetic coding algorithm.

28. The method as recited in claim 25, further comprising:

means for determining textual data that includes a string of characters;

means for hashing the textual data with an algorithm;

means for encrypting the compressed data using the hashed textual data; and

means for including the textual data in the label.

29. The apparatus as recited in claim 25, further comprising:

means for authenticating the label by comparing encoded data with the data associated with the randomly distributed features in the authentication object.