Systems and methods for efficient authentication

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, the verifying module being configured to:

break the message into n k-bit words b 1 , b 2 , . . . , b n ;

break a hierarchical signature into components σ 1 , σ 2 , . . . , σ n , γ 1 , γ 2 , . . . , γ n ;

determine a number of words p;

set a public key V to V p =[Z 1 , Z 2 , . . . , Z p ];

for each i in a set iε{1, p}:

generate X i ′=H 2 k −b i (σ i ) and Y i ′=H b i (γ i ); and

calculate Z i ′=H(X i ′∥Y i ′);

set a public key check V p ′ to V p ′=[Z 1 ′,Z 2 ′, . . . ,Z p ′]; and

compare the public key V p to the public key check V p ′.

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 , wherein if V p =V p ′, then the message is verified.

15. 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, the signing module being configured to generate the hierarchical signature by:

dividing the message into n words b 1 , b 2 , . . . , b n ;

generating 2n random variables s 1 , s 2 , . . . , s n and c 1 , c 2 , . . . , c n ;

setting a private key S as the 2n random variables S={s 1 , s 2 , . . . , s n , c 1 , c 2 , . . . , c n };

for each i in a set iε{1,n}:

generating X i =H 2 k (s i ) and Y i =H 2 k (c i ); and

calculating Z i =H(X i ∥Y i );

setting a public key V as V=[Z 1 , Z 2 , . . . , Z n ];

for each i in a set iε{1,n}:

generating σ i =H b i (s i ) and γ i =H 2 k −b i (c i ); and

setting the hierarchical signature σ as σ=σ 1 ∥ . . . ∥σ n ∥γ 1 ∥ . . . ∥γ n .

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

17. A non-transitory computer readable medium on which are stored executable authentication instructions for:

signing a message for use by a communication system, comprising:

dividing the message into n words b 1 , b 2 , . . . , b n ;

generating 2n random variables s 1 , s 2 , . . . , s n and c 1 , c 2 , . . . , c n ;

setting a private key S as the 2n random variables S={s 1 , s 2 , . . . , s n , c 1 , c 2 , . . . , c n };

for each i in a set iε{1,n}:

generating X i =H 2 k (s i ) and Y i =H 2 k (c i ); and

calculating Z i =H(X i ∥Y i );

setting a public key V as V=[Z 1 , Z 2 , . . . , Z n ];

for each i in a set iε{1,n}:

generating σ i =H b i (s i ) and Y i =H 2 k −b i (c i ); and

setting a hierarchical signature σ as σ=σ 1 ∥ . . . ∥σ n ∥γ 1 ∥ . . . ∥γ n .

18. The non-transitory computer readable medium of claim 17 , wherein the authentication instructions are further for verifying a message, used in a communication system, comprising:

breaking the message into n k-bit words b 1 , b 2 , . . . , b n ;

breaking the hierarchical signature into components σ 1 , σ 2 , . . . , σ n , γ 1 , γ 2 , . . . , γ n ;

determining a number of words p;

setting a public key V to V p =[Z 1 , Z 2 , . . . , Z p ];

for each i in a set iε{1,p}:

generating X i ′=H 2 k −b i (σ i ) and Y i ′=H b i (γ i ); and

calculating Z i ′=H(X i ′∥Y i ′);

setting a public key check V p ′ to V p ′=[Z 1 ′, Z 2 ′, . . . , Z p ′]; and

comparing the public key V p to the public key check V p ′.