Secure outsourced aggregation with one-way chains
First Claim
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 vm 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, andfolding 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 Assignments
0 Petitions
Accused Products
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.
-
Citations
18 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 vm 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
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. - View Dependent Claims (10, 11, 12)
-
-
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 Fv( ) 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 Fv( ) has been applied to each of the at least the subset of the plurality of SEAL chains, Fv( ) 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 Fv( ) to the shorter SEAL chain of the adjacent SEAL chains until the number of iterations of the function Fv( ) applied to the shorter SEAL chain of the adjacent SEAL chains is equal to the number of iterations of the function Fv( ) 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. - View Dependent Claims (14, 15, 16, 17, 18)
-
Specification