Secure outsourced aggregation with one-way chains

• US 8,607,057 B2
• Filed: 05/15/2009
• Issued: 12/10/2013
• Est. Priority Date: 05/15/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Nath, Suman K.
• Primary Examiner(s): Kyle, Tamara T
• Assistant Examiner(s): VOSTAL, ONDREJ C
• Application Number:
  US12/466,678
• Publication Number:
  US 20100290617A1
• Time in Patent Office: 1,670 Days
• Field of Search: 713/180
• US Class Current: 713/180
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 9/008 involving homomorphic encryption
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

Secure outsourced aggregation of data using one-way chains is discussed in this application. Each input data source such as a sensor generates a Verifiable Synopsis (“VS”) which includes sensor data, an Inflation Free Proof (“IFP”) generated using a cryptographic function and a Self-Authenticating Value (“SEAL”) chain generated using a one-way function. An aggregator takes a plurality VSs from multiple data sources and aggregates them together into one. Maximum value, top-k, count, count distinct, sum, average, and other aggregate functions may be used. Folded VS provides a concise proof that no value greater than the maximum value was reported by a sensor, thus providing a check against deflation of sensor data. Similarly, the cryptographic function of the IFP provides a mechanism to prevent inflation of the sensor data. Thus it becomes possible at a portal to verify that aggregated data has not been inflated or deflated by the aggregator.

Claims

1. A computer-implemented method of securely outsourcing data aggregation, the method comprising:

using a processor of a verifying computer, receiving an aggregated verifiable synopsis (AVS) corresponding to an aggregated result of a set of data values provided by a plurality of sources;

using the processor of the verifying computer, verifying the aggregated result of the set of data values provided by the plurality of sources by using the received aggregated verifiable synopses (AVS), the AVS comprising at least one received data value of the set of data values provided by the plurality of sources, a received folded self-authentication value (SEAL) for the aggregated result of the set of data values, and a received inflation free proof (IFP) of a received maximum data value v_m of the set of data values provided by the plurality of sources, the at least one received data value of the set of data values provided by the plurality of sources including at least the received maximum data value, the verifying comprising;

computing a reference inflation free proof (IFP) for the received maximum data value using a cryptographic function known to the verifying computer and a source of the plurality of sources providing the received maximum data value using at least a value indicative of the received maximum data value;

computing individual reference self-authentication values (SEALs) for the plurality of sources providing the data using a one-way function, and

folding the individual reference SEALs together to form a reference folded SEAL;

comparing the received IFP of the received aggregated verifiable synopsis to the computed reference IFP and the received folded SEAL of the received aggregated verifiable synopsis to the reference folded SEAL; and

designating the received aggregated verifiable synopsis as valid based at least in part on the comparing determining that the received IFP equals the computed reference IFP and the received folded SEAL equals the reference folded SEAL.

2. The method of claim 1, wherein the set of data values provided by the plurality of sources changes over time.

3. The method of claim 1, wherein the folding comprises modulo multiplication.

4. The method of claim 1, wherein the received folded SEAL comprises a chain of iterations of the one-way function of a maximum length, the one-way function is a homomorphic one-way function, the reference folded SEAL computed by rolling individual reference SEALs forward by iterating with the homomorphic one-way function F until the individual reference SEALs are of length equal to the maximum length and folding the individual reference SEALS together to form the reference folded SEAL.

5. The method of claim 1, wherein the one-way function is a homomorphic one-way function F.

6. The method of claim 1, further comprising determining a top-k listing of the data values of the set of data values provided by the plurality of sources, where k is pre-defined.

7. The method of claim 1, further comprising associating each data value in the set of data values with an IFP representing that data value.

8. The method of claim 1, wherein the cryptographic function used to generate the reference IFP comprises a full domain hash with parameters including a key, a time epoch, and a data value v.

9. A method of securely aggregating data, the method comprising:

using one of more processors of one or more computing devices, for a plurality of self-authenticating values (SEAL) that have been iterated with a function F( ) at least one iteration and that corresponding to a plurality of data values, determining a particular self-authenticating value (SEAL) of the plurality of SEALs that has been iterated with the function F( ) a maximum number of iterations (m) among the plurality of SEALs corresponding to the plurality of data values;

for each of the plurality of SEALs that has been iterated with F( ) a number of iterations less than m, rolling each SEAL that has been iterated a number of iterations less than m forward by iterating the SEAL with F( ) until each of the plurality of SEALs has been iterated m number of iterations with F( ), F( ) being a one-way function applied to a seed or folded set of seeds of the corresponding SEAL; and

folding the plurality of SEALs that have been iterated m number of iterations together to form a single SEAL.

10. The method of claim 9, wherein F^v( ) comprises a homomorphic one-way function.

11. The method of claim 9, wherein each SEAL of the plurality of SEALs is a corresponding seed iterated by F^v( ) at least once.

12. The method of claim 11, wherein each seed comprises a full domain hash with parameters including a shared key and a time epoch.

13. One or more computer-readable storage devices storing instructions that when executed instruct a processor to perform acts comprising:

ordering at least a subset of a plurality of self-authenticating values (SEAL) chains by length, the length of a SEAL chain being the number of iterations of the function F^v( ) applied to the SEAL chain and wherein the ordering at least the subset of the plurality of SEAL chains by length comprises sorting the at least the subset of the plurality of SEAL chains based on the number of iterations that the function F^v( ) has been applied to each of the at least the subset of the plurality of SEAL chains, F^v( ) being a one-way function applied to a seed or folded set of seeds of the corresponding SEAL chain;

subsequent to the ordering, where adjacent SEAL chains of the subset are not of equal length, rolling a shorter SEAL chain of the adjacent SEAL chains forward to match length of the longer adjacent SEAL chain, wherein rolling the shorter SEAL chain forward to match the length of the longer adjacent SEAL chain comprises applying the function F^v( ) to the shorter SEAL chain of the adjacent SEAL chains until the number of iterations of the function F^v( ) applied to the shorter SEAL chain of the adjacent SEAL chains is equal to the number of iterations of the function F^v( ) applied to the longer SEAL chain of the adjacent SEAL chains; and

folding a plurality of pairs of SEAL chains of equal length together to form a single SEAL.

14. The one or more computer-readable storage devices of claim 13, the acts further comprising folding SEAL chains until a single SEAL remains.

15. The one or more computer-readable storage devices of claim 13, wherein each SEAL chain is a corresponding seed iterated by F^v( ) at least once and the seed comprises a full domain hash with parameters including a shared key and a time epoch.

16. The one or more computer readable storage devices of claim 13, wherein the function F^v( ) is a one-way function.

17. The one or more computer-readable storage devices of claim 16, wherein the one-way function is homomorphic.

18. The one or more computer-readable storage devices of claim 16, wherein the one-way function comprises RSA encryption.