Homomorphic signatures and network coding signatures

Patent metadata

Field	Value
Publication number	US-9722776-B2
Application number	US-201213529332-A
Country	US
Kind code	B2
Filing date	Jun 21, 2012
Priority date	Jun 21, 2012
Publication date	Aug 1, 2017
Grant date	Aug 1, 2017

Abstract

The subject disclosure is directed towards a technology by which data is securely distributed using a homomorphic signature scheme and homomorphic network coding signature schemes. A homomorphic signature scheme for signing the data is based upon binary pairing with standard prime order groups. Sets of data are signed based upon dividing a larger block of data into smaller blocks, and separately signing each smaller block. The smaller blocks may be distributed to nodes of a network topology that are configured for network coding. In one alternative, the homomorphic signature scheme protects against changes to the block identifier. Proof data may be provided independent of a random oracle, may be provided by providing parameters for verification in a Groth-Sahai proof system, or may be provided by providing parameters for verification independent of a Groth-Sahai proof system.

First claim

What is claimed is:

1. In a computing environment, a method performed at least in part on at least one processor comprising:
signing a set of data using an homomorphic signature scheme, in which the homomorphic signature scheme is based upon bilinear pairing with standard prime order groups, the homomorphic signature scheme secure in a standard model that has no dependency on random oracle without requiring a special composite order pairing group; and
providing public information useable for authenticating the signed set of data.

2. The method of claim 1 wherein signing the sets of data comprises dividing a block of data into smaller blocks, and separately signing each smaller block.

3. The method of claim 2 wherein distributing the data comprises sending the smaller blocks to nodes of a network topology configured for network coding combinations of a subset of the smaller blocks.

4. The method of claim 1 , wherein the bilinear pairing with standard prime order groups comprises prime numbers and points on an elliptic curve used to sign the data.

5. The method of claim 1 , wherein using the signed set of data for further processing comprises transmitting the signed set of data to an intermediary node to use the set of data for further processing prior to transmitting the signed set of data to a final destination node.

6. The method of claim 5 , further comprising combining the signed set of data with at least one other set of data in a network coding scheme into a combined set of data, sign the combined set of data using the homomorphic signature scheme and additional public information, and transmit the combined, signed set of data using a distribution scheme and the additional public information to the final destination node.

7. A computing device comprising:
a processor; and
a memory coupled to the processor, the memory comprising computer-program instructions executable by the processor, the instructions configured to:
receive public information with a set of data from a node within a network topology, the set of data being digitally signed using a homomorphic signature scheme based upon bilinear pairing with standard prime order groups, the public information enabling authentication of the digitally signed set of data, the homomorphic signature scheme secure in a standard model that has no dependency on random oracle without requiring a special composite order pairing group; and
authenticate the digitally signed set of data using the public information and
proof data including parameters for verification in a Groth-Sahai proof system.

8. The computing device of claim 7 wherein the instructions are further configured to discard the set of data if not verified.

9. The computing device of claim 7 wherein the instructions to use the set of data for further processing comprise instructions that when executed combine the set of data with at least one other set of data in a network coding scheme into a combined set of data, sign the combined set of data using the homomorphic signature scheme, and transmit the combined, signed set of data using a distribution scheme.

10. The computing device of claim 9 , wherein the distribution scheme comprises a network coding content distribution scheme.

11. The computing device of claim 9 wherein the bilinear pairing with standard prime order groups comprises prime numbers and points on an elliptic curve used to sign the data.

12. The computing device of claim 7 wherein the instructions to use the set of data for further processing comprise instructions that when executed decode the set of data and at least one other set of data into decoded sets of data, and reassemble the decoded sets of data into an original data block.

13. The computing device of claim 7 , wherein the processor is further programmed to, upon determining that the digitally signed set of data is authentic, decode and reassemble the set of data in original data blocks.

14. A computer-readable storage memory having executable instructions which, when processed by a computer, cause the computer to perform operations comprising:
receiving public information along with a signed set of data from a node in a network topology, the set of data signed using a homomorphic signature scheme based upon bilinear pairing with standard prime order groups, the public information enabling an authentication of the digitally signed data, the homomorphic signature scheme secure in a standard model that has no dependency on random oracle without requiring a special composite order pairing group;
verifying whether the digitally signed set of data is authenticated using the public information and proof data including parameters for verification in a Groth-Sahai proof system; and
upon determining that the digitally signed set of data is authenticated:
combining the set of data with at least one other set of data in a network coding scheme into a combined set of data;
signing the combined set of data using the homomorphic signature scheme; and
transmitting the combined set of data to a second node in the network topology using a distribution scheme for further processing.

15. The computer-readable storage memory of claim 14 having further executable instructions comprising providing proof data independent of a random oracle.

16. The computer-readable storage memory of claim 14 , wherein transmitting the combined, signed set of data further comprises transmitting the combined, signed set of data to an intermediary node to use the set of data for further processing prior to transmitting the combined, signed set of data to a final destination node.

17. The computer-readable storage memory of claim 16 , wherein the instructions to use the set of data for further processing comprise instructions that when executed combine the set of data with at least one other set of data in a network coding scheme into a combined set of data, sign the combined set of data using the homomorphic signature scheme, and transmit the combined, signed set of data using a distribution scheme to the final destination node.

18. The computer-readable storage memory of claim 17 , wherein the distribution scheme comprises a network coding content distribution scheme.

19. The computer-readable storage memory of claim 14 wherein the bilinear pairing with standard prime order groups comprises prime numbers and points on an elliptic curve used to sign the data.

20. The computer-readable storage memory of claim 14 , wherein the digitally signed set of data comprises a plurality of signed blocks of data.

Assignees

• Nguyen Duy Lan
• Acar Tolga
• Mandal Avradip
• Microsoft Technology Licensing Llc

Inventors

• Nguyen Duy Lan
• Acar Tolga
• Mandal Avradip

Classifications

• H04L9/008 Primary

  involving homomorphic encryption · CPC title

• H04L9/3073

  involving pairings, e.g. identity based encryption [IBE], bilinear mappings or bilinear pairings, e.g. Weil or Tate pairing · CPC title

• H04L9/3247

  involving digital signatures · CPC title