SECURE OUTSOURCED AGGREGATION WITH ONE-WAY CHAINS

• US 20100290617A1
• Filed: 05/15/2009
• Published: 11/18/2010
• 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.
• Granted Patent: US 8,607,057 B2
• Time in Patent Office: Days
• US Class Current: 380/29
• 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:

verifying an aggregated result of data provided by a plurality of sources by using an aggregated verifiable synopses (AVS) comprising one or more verifiable synopsis (VS), the verifying comprising;

determining an inflation free proof (IFP) for a maximum data value v_m;

determining individual self-authentication values (SEALs) and folding those SEALs together to form a single SEAL;

generating a reference synopsis (RS) from v_m and sensor metadata; and

designating the VS as valid when the RS equals the VS.

2. The method of claim 1, wherein the data 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 AVS comprises a maximum value SEAL, the maximum value SEAL comprising all non-maximum data value SEALs rolled forward by iterating with a homomorphic one-way function F until all chains are of equal length and folding SEALS together to form a single SEAL.

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

6. The method of claim 1, further comprising determining a top-k listing of the data values returned from the sensors, where k is pre-defined.

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

8. The method of claim 1, wherein the 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:

determining a self-authenticating value (SEAL) with maximum value v_m from a set of data comprising one or more values v_i;

rolling each SEAL with value v_i<

v_m in the set of data forward by iterating each SEAL with F^v( ) until each SEAL equals v_m; and

folding SEALs with length equal to v_m 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 the SEAL comprises a seed and data as parameters for a one-way function.

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

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

ordering SEAL chains by length;

where adjacent SEAL chains are not of equal length, rolling a shortest first SEAL chain forward to match length of a next second SEAL chain having an equal or next shortest length; and

folding SEAL chains of equal length together.

14. The computer-readable storage media of claim 13, wherein ordering SEAL chains by length further comprises sorting by a count of iterations of a one-way function on a seed.

15. The computer-readable storage media of claim 13, further comprising folding SEAL chains until a single SEAL remains.

16. The computer-readable storage media of claim 13, further comprising representing SEALs as a tree, wherein the leaves of the tree are s⁻

_i,j'"'"'s ordered by i, and each internal node of the tree is the modulo multiplication of subordinate leaves.

17. The computer-readable storage media of claim 19, wherein the one-way function is homomorphic.

18. The computer-readable storage media of claim 19, wherein the one-way function comprises RSA encryption.

19. The computer-readable storage media of claim 13, wherein the SEAL comprises a seed iterated with a one-way function.

20. The computer-readable storage media of claim 19, wherein the seed comprises a full domain hash with parameters including a shared key and a time epoch.