Systems and Methods for Efficient Authentication

• US 20110304425A1
• Filed: 06/09/2010
• Published: 12/15/2011
• Est. Priority Date: 06/09/2010
• Status: Active Grant

• Current Assignee: GM Global Technology Operations LLC (General Motors Company)
• Original Assignee: GM Global Technology Operations Incorporated (Motors Liquidation Co. GUC Trust)
• Inventors: Iyer, Aravind V., Bellur, Bhargav R.
• Granted Patent: US 8,593,253 B2
• Time in Patent Office: Days
• US Class Current: 340/5.8
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 2209/84 Vehicles
• CPC Class Codes: H04L 63/123 received data contents, e.g. message integrity
• CPC Class Codes: H04L 67/12 specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: H04W 4/38 for collecting sensor information
• CPC Class Codes: H04W 4/40 for vehicles, e.g. vehicle-to-pedestrians [V2P]

Abstract

A communication system is configured to operate in an ad hoc wireless network. The communication system includes a transmission device configured to send and receive a message, a signing module configured to generate a hierarchical signature using the message, and a verifying module configured to hierarchically verify a predetermined portion of a hierarchically signed message.

Claims

1. A communication system configured to operate in an ad hoc network, comprising:

a transmission device configured to receive a message; and

a verifying module configured to hierarchically verify a predetermined portion of the message.

2. The communication system of claim 1, wherein the communication system is a vehicle communication system operating in a mobile ad hoc network.

3. The communication system of claim 1, wherein the communication system is configured to operate in a sensor network.

4. The communication system of claim 1, wherein the predetermined portion of the message is a number of words of the message.

5. The communication system of claim 1, further comprising a processor configured to execute instructions of the verifying module.

6. The communication system of claim 1, wherein the predetermined portion is more significant than the remainder of the message.

7. The communication system of claim 1, wherein the predetermined portion of the message corresponds at least one piece of imprecise information.

8. The communication system of claim 7, further comprising an evaluation module configured to identify an event based on the information.

9. The communication system of claim 8, the evaluation module being configured to instruct the verifying module to verify a portion of the message that is greater than the predetermined portion.

10. The communication system of claim 8, the evaluation module comprising instructions for ignoring the message.

11. The communication system of claim 8, further comprising a response module configured to generate a response to an identified event.

12. The communication system of claim 1, further comprising a signing module that is configured to generate a hierarchical signature.

13. The communication system of claim 1, wherein the message is hierarchically encoded as a number of bits that are grouped into words and the verifying module is configured to verify any number of words.

14. The communication system of claim 1, the verifying module being configured to:

break the message into n k-bit words b₁, b₂, . . . , b_n;

break a hierarchical signature into components σ

₁, σ

₂, . . . , σ

_n, γ

₁, γ

₂, . . . , γ

_n;

determine a number of words p;

set a public key V to V_p=[Z₁, Z₂, . . . , Z_p];

for each i in a set iε

{1,p};

generate X_i′

=H<sup>2k−

bi</sup>(σ

_i) and Y_i′

=H^bi(γ

_i); and

calculate Z_i′

=H(X_i′

∥

Y_i′

);

set a public key check V_p′

to V_p′

=[Z₁′

, Z₂′

, . . . , Z_p′

]; and

compare the public key V_p to the public key check V_p′

.

15. The communication system of claim 14, wherein if V_p=V_p′

, then the message is verified.

16. A communication system configured to operate in an ad hoc network, comprising:

a transmission device configured to transmit a message; and

a signing module configured to generate a hierarchical signature using the message.

17. The communication system of claim 16, wherein the communication system is a vehicle communication system operating in a mobile ad hoc network.

18. The communication system of claim 16, the signing module being configured to generate the hierarchical signature by:

dividing the message into n words b₁, b₂, . . . , b_n;

generating 2n random variables s₁, s₂, . . . , s_n and c₁, c₂, . . . , c_n;

setting a private key S as the 2n random variables S={s₁, s₂, . . . , s_n, c₁, c₂, . . . , c_n};

for each i in a set iε

{1,n};

generating X_i=H^2k(s_i) and Y_i=H^2k(c_i); and

calculating Z_i=H(X_i∥

Y_i);

setting a public key V as V=[Z₁, Z₂, . . . , Z_n];

for each i in a set iε

{1,n};

generating σ

_i=H^bi(s_i) and γ

_i=H<sup>2k−

bi</sup>(c_i); and

setting the hierarchical signature σ

as σ

=σ

₁∥

. . . ∥

σ

_n∥

γ

₁∥

. . . ∥

γ

_n.

19. A computer readable medium on which are stored executable authentication instructions for:

signing a message, comprising;

dividing the message into n words b₁, b₂, . . . , b_n;

generating 2n random variables s₁, s₂, . . . , s_n and c₁, c₂, . . . , c_n;

setting a private key S as the 2n random variables S={s₁, s₂, . . . , s_n, c₁, c₂, . . . , c_n};

for each i in a set iε

{1,n};

generating X_i=H^2k(s_i) and Y_i=H^2k(c_i); and

calculating Z_i=H(X_i∥

Y_i);

setting a public key V as V=[Z₁, Z₂, . . . , Z_n];

for each i in a set iε

{1,n};

generating σ

_i=H^bi(s_i) and Y_i=H<sup>2k−

bi</sup>(c_i); and

setting a hierarchical signature σ

as σ

=σ

₁∥

. . . ∥

σ

_n∥

γ

₁∥

. . . ∥

γ

_n.

20. The computer readable medium of claim 19, wherein the authentication instructions are further for verifying the message, comprising:

breaking the message into n k-bit words b₁, b₂, . . . , b_n;

breaking the hierarchical signature into components σ

₁, σ

₂, . . . , σ

_n, γ

₁, γ

₂, . . . , γ

_n;

determining a number of words p;

setting a public key V to V_p=[Z₁, Z₂, . . . , Z_p];

for each i in a set iε

{1,p};

generating X_i′

=H<sup>2k−

bi</sup>(σ

_i) and Y_i′

=H^bi(γ

_i); and

calculating Z_i′

=H(X_i′

∥

Y_i′

);

setting a public key check V_p′

to V_p′

=[Z₁′

, Z₂′

, . . . , Z_p′

]; and

comparing the public key V_p to the public key check V_p′

.