System and method for message verification in broadcast and multicast networks

• US 8,667,288 B2
• Filed: 05/29/2012
• Issued: 03/04/2014
• Est. Priority Date: 05/29/2012
• Status: Active Grant

• Current Assignee: Robert Bosch GmbH
• Original Assignee: Robert Bosch GmbH
• Inventors: Yavuz, Attila Altay
• Primary Examiner(s): Chai, Longbit
• Application Number:
  US13/482,037
• Publication Number:
  US 20130326224A1
• Time in Patent Office: 644 Days
• Field of Search: 713/176
• US Class Current: 713/176
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

In a network device, a method for verified communication includes generating a network communication message using a selection of predetermined message elements having digital signatures generated with a private key. The network device generates a signature for the message by applying a homomorphic operation to the digital signatures of the selected predetermined message elements and to a one-time signature corresponding to a random number. The network device transmits the message in association with the signature for the message and the random number to at least one other network device.

Claims

1. A method for verified communication comprising:

generating an individual digital signature of a hash for each one of a plurality of predetermined message elements with a private key in a first network device;

generating a random number in the first network device;

generating a one-time digital signature for the random number with the private key in the first network device;

generating a network communication message including a subset of the plurality of predetermined message elements in the first network device;

applying a first homomorphic operation to the one-time digital signature and each of the individual digital signatures corresponding to each the subset of predetermined message elements included in the network communication message to generate a homomorphic signature for the network communication message, wherein the momomorphic operation preserves a homomorphic property of a list of the individual signatures by the first network device; and

transmitting the network communication message, the homomorphic signature and the random number to at least one other network device so as to verify an integrity of said communication message at said other network device by using a second homomorphic operation.

2. The method of claim 1 further comprising:

receiving the network communication message in association with the homomorphic signature for the network communication message and the random number with the at least one other network device;

generating a hash for the random number with the at least one other network device;

generating a hash for each one of the message elements in the network communication message with the at least one other network device;

applying the second homomorphic operation to the hash of the random number and to the hash of each one of the message elements with the at least one other network device to generate a message digest of the network communication message; and

verifying, with the at least one other network device, that the network communication message was generated by the first network device with reference to the message digest, the homomorphic signature for the network communication message, and a public key associated with the private key in the first network device.

3. The method of claim 2 further comprising:

generating a random identification number to identify the first network device with a random number generator;

distributing the public key corresponding to the private key of the first network device in association with the random identification number to the at least one other network device.

4. The method of claim 3, the generation of the one-time digital signature further comprising:

concatenating the random number and the random identification number to produce a concatenated random number; and

signing a hash of the concatenated random number with the private key to generate the one-time signature in the first network device.

5. The method of claim 4 further comprising:

transmitting the network communication message with the first network device in association with the random identification number; and

generating the hash for the random number with the at least one other network device as a hash of the random number concatenated with the random identification number.

6. The method of claim 2, the first homomorphic operation and the second homomorphic operation being the same operation.

7. The method of claim 6, both the first homomorphic operation and second homomorphic operation being a multiplication operation.

8. The method of claim 2, the first homomorphic operation being a multiplication operation and the second homomorphic operation being a pairing and multiplication operation.

9. The method of claim 2, the first homomorphic operation being a modular addition operation, and the second homomorphic operation being a modular exponentiation and multiplication operation.

10. The method of claim 1 further comprising:

storing the random number in association with the one-time digital signature in a memory in the first network device prior to generation of the network communication message.

11. The method of claim 2 further comprising:

generating an individual digital signature of a hash for each one of a plurality of message elements corresponding to timestamps with the private key in the first network device;

generating the network communication message including at least one message element selected from the plurality of message elements corresponding to timestamps, the at least one message element being selected to indicate a time at which the network communication message is generated; and

generating the homomorphic signature for the network communication message including the first homomorphic operation applied to each of the individual digital signatures for the plurality of message elements corresponding to timestamps.

12. The method of claim 11 further comprising:

identifying a time when the network communication message is received in the at least one other network device; and

verifying, with the at least one other network device, that the network communication message is valid in response to the timestamp in the network communication message being within a predetermined threshold of the identified time.

13. The method of claim 1 further comprising:

identifying an index number corresponding to each one of the plurality of message elements with reference to a predetermined format of the communication message;

generating the individual digital signature for each one of the plurality of predetermined message elements including the identified index number in the first network device with the private key; and

generating the communication message with the subset of predetermined message elements arranged in an order corresponding to the index number for each message element.

14. A network communication system comprising:

a plurality of network devices, each network device including;

a network interface device;

a memory configured to store;

a plurality of predetermined message elements;

a private key corresponding to the network device;

a random device identifier corresponding to the network device; and

a random device identifier and an associated public key corresponding to each of the other network devices in the plurality of network devices; and

a processor operatively connected to the network interface device and the memory, the processor in a first network device in the plurality of network devices being configured to execute programmed instructions stored in the memory to;

generate an individual digital signature of a hash for each one of the plurality of predetermined message elements with the private key stored in the memory of the first network device;

generate a random number;

generate a one-time digital signature for the random number with the private key;

generate a network communication message including a subset of the plurality of predetermined message elements;

apply a first homomorphic operation to the one-time digital signature and each of the individual digital signatures for each hash of the predetermined message elements corresponding to each predetermined message element in the subset of predetermined message elements included in the generated network communication message to generate a homomorphic signature for the network communication message, wherein the first homomorphic operation preserves a homomorphic property of a list of the individual signatures by the first network device; and

transmitting the network communication message, the homomorphic signature and the random number with the network interface device to at least one other network device in the plurality of network devices so as to verify an integrity of said communication message at said one other network device by using a second homomorphic operation.

15. The system of claim 14, the processor in the at least one other network device in the plurality of network devices being configured to:

receive the network communication message with the network interface device in association with the homomorphic signature for the network communication message and the random number with the at least one other network device;

generate a hash for the random number;

generate a hash for each one of the predetermined message elements in the network communication message;

apply the second homomorphic operation to the hash of the random number and to the hash of each predetermined message element with the at least one other network device to generate a message digest of the network communication message; and

verify, with the at least one other network device, that the network communication message was generated by the first network device with reference to the message digest, the homomorphic signature for the network communication message, and a public key associated with the private key in the first network device.

16. The system of claim 15, the first network device being further configured to:

generate a random identification number with a random number generator to identify the first network device;

distribute the public key corresponding to the private key of the first network device in association with the identification number to the at least one other network device with the network interface device.

17. The system of claim 16, the processor in the first network device being further configured to:

concatenate the random number and the random identification number to produce a concatenated random number; and

sign a hash of the concatenated random number with the private key to generate the one-time signature.

18. The system of claim 16, the first network device being configured to:

transmit the network communication message in association with the random identification number; and

the processor in the at least one other network device being further configured to generate the hash for the random number as a hash of the random number concatenated with the random identification number.

19. The system of claim 15, the first homomorphic operation and the second homomorphic operation being the same operation.

20. The system of claim 19, both the first homomorphic operation and second homomorphic operation being a multiplication operation.

21. The system of claim 15, the first homomorphic operation being a multiplication operation and the second homomorphic operation being a pairing and multiplication operation.

22. The system of claim 15, the first homomorphic operation being a modular addition operation, and the second homomorphic operation being a modular exponentiation and multiplication operation.

23. The system of claim 14, the processor in the first network device being further configured to:

store the random number in association with the one-time digital signature in the memory prior to generation of the network communication message.

24. The system of claim 14, the processor in the first network device being further configured to:

generate an individual digital signature of a hash for each one of a plurality of message elements corresponding to timestamps with the private key;

generate the network communication message including at least one message element selected from the plurality of message elements corresponding to timestamps, the at least one message element being selected to indicate a time at which the network communication message is generated; and

generate the homomorphic signature for the network communication message including the first homomorphic operation applied to each of the individual digital signatures for the plurality of message elements corresponding to timestamps.

25. The system of claim 24, the processor in the at least one other network device being configured to:

identify a time when the network communication message is received; and

verify that the network communication message is valid in response to the timestamp in the network communication message being within a predetermined threshold of the identified time.

26. The system of claim 14, the processor in the first network device being further configured to:

identify an index number corresponding to each one of the plurality of message elements with reference to a predetermined format of the communication message;

generate the individual digital signature for each one of the plurality of predetermined message elements including the identified index number in the first network device with the private key; and

generate the communication message with the subset of predetermined message elements arranged in an order corresponding to the index number for each message element.