PaperlayerView exact revision on arXiv

Source-linked AI summary

Data Aggregation without Secure Channel: How to Evaluate a Multivariate Polynomial Securely

Taeho Jung, XuFei Mao, Xiang-Yang Li, Shaojie Tang, Wei Gong, Lan Zhang

arXiv:1206.2660v4cs.CR

TL;DR

The paper addresses private aggregation when prior approaches require secure channels or incur high complexity. It proposes sum and product protocols for multivariate polynomial evaluation over insecure channels, reporting linear communication and computation complexity. The conclusion also identifies disclosure of product parts as an information-leakage issue.

  • Problem

    Privacy-preserving aggregation seeks to compute sums, products, or other functions over participants’ sensitive data without revealing individual inputs, while prior approaches may require secure channels or have high complexity.

    Source: §I · pp. 1–2

  • Method

    The paper introduces secure sum and product protocols and generalizes them to multivariate polynomial evaluation without requiring secure communication channels.

    Source: §I · p. 2, §IX · p. 9

  • Results

    Communication and computation complexity are proportional to n, and the paper reports achieving privacy-preserving multivariate polynomial evaluation without secure communication channels.

    Source: §I · p. 2, §IX · p. 9

  • Takeaways & Limitations

    The polynomial framework can express statistical values including mean, variance, skewness, and regression.

    Source: §I · p. 2

    The scheme discloses each product part in the polynomial, which the authors identify as unnecessary information leakage to attackers.

    Source: §IX · p. 9

Abstract

from arXiv · show

Much research has been conducted to securely outsource multiple parties' data aggregation to an untrusted aggregator without disclosing each individual's data, or to enable multiple parties to jointly aggregate their data while preserving privacy. However, those works either assume to have a secure channel or suffer from high complexity. Here we consider how an external aggregator or multiple parties learn some algebraic statistics (e.g., summation, product) over participants' data while any individual's input data is kept secret to others (the aggregator and other participants). We assume channels in our construction are insecure. That is, all channels are subject to eavesdropping attacks, and all the communications throughout the aggregation are open to others. We successfully guarantee data confidentiality under this weak assumption while limiting both the communication and computation complexity to at most linear.

I. INTRODUCTION

The paper targets privacy-preserving aggregation in settings with an external aggregator or participant collaboration, without relying on secure pairwise channels. It proposes linear-complexity protocols and generalizes aggregation to multivariate polynomial evaluation and statistical outputs.

  • Synchronous SMC can require interactive invocation, increasing communication and computation complexity; asynchronous SMC is also described as too computationally costly for practical applications.SMC can return one uniform aggregation result to participants, but the paper says this does not fully solve the problem.Source: §I · p. 1
  • Homomorphic encryption can support ciphertext addition and multiplication, but its shared decryption key creates a conflict between aggregator access to the aggregate and protection of individual ciphertexts.The paper also cites high computation time for general homomorphic encryption and notes that both SMC and HE require secure-channel key initialization.Source: §I · p. 1
  • The proposed model does not require a secure communication channel throughout the protocol.The paper’s goal is to design efficient protocols without a trusted authority or secure pair-wise channels.Source: §I · p. 2
  • The paper’s communication and computation costs are proportional to n, versus n^2 for many similar works.The authors also attribute faster operation to avoiding complicated encryption protocols.Source: §I · p. 2
  • The scheme generalizes privacy-preserving aggregation to secure multivariate polynomial evaluation and can express statistics including variance, skewness, and regression.The authors also state that vector inputs, such as for dot products, can be supported.Source: §I · p. 2

II. RELATED WORK

Prior aggregation schemes trade privacy, communication, or trust assumptions in different ways. The paper’s system model formalizes private multivariate polynomial evaluation and considers both an external aggregator and participant-only computation.

II. RELATED WORK

  • Castelluccia et al. extend with additively homomorphic encryption for aggregation, but their trusted aggregator can decrypt each sensor’s data.Source: §II · p. 2
  • Sheikh et al. [19], building on, distribute data segments to reduce leakage, but require pair-wise secure channels; without them, individual data can be recovered in O(k) computations.Source: §II · p. 2
  • The CPDA and SMART schemes of He et al. support additions only, and SMART’s per-node communication overhead is linear in the number of slices.Source: §II · p. 2
  • Shi et al. use periodic encrypted uploads and an aggregator, but assume a trusted key dealer.Source: §II · p. 2
  • Unlike schemes in [6] and [19], the proposed scheme removes the trusted aggregator, assumes insecure channels, and avoids data segmentation and its per-participant communication overhead.It also uses efficient sum and product protocols rather than brute-force decryption.Source: §II · p. 3

A. System Model and Problem Definition

  • The system model defines the objective as computing a multivariate polynomial over participants’ private data without revealing any individual input; its powers and coefficients are public.The final result is assumed positive and bounded above by a large prime P.Source: A. System Model and Problem Definition · p. 3
  • The paper considers an aggregator model and a participants-only model; participants are assumed not to collude, a restriction left for future work.In the aggregator model, no individual participant may compute the final result.Source: A. System Model and Problem Definition · p. 3

B. Additional Assumptions

The protocols assume insecure channels, a computationally hard discrete logarithm problem, and a secure PRF; they also assume user authentication when needed. The preliminary secure-channel sum scheme reduces communication while preserving computation privacy, but still requires secure channels.

B. Additional Assumptions

  • The scheme assumes eavesdroppable channels, a computationally hard discrete logarithm problem for large groups and numbers, and a secure PRF that samples elements indistinguishable from uniform.User authentication is assumed to be in place when needed.Source: B. Additional Assumptions · p. 3

C. Discrete Logarithm Problem

  • The discrete logarithm problem is to find k from h = g^k in a cyclic group; the protocol assumes solving it is computationally expensive.The paper relates this assumption to DDH and cites its use in cryptographic protocols.Source: C. Discrete Logarithm Problem · p. 3

IV. ACHIEVING SUM UNDER SECURED COMMUNICATION CHANNEL

  • Choosing k around (1 + ǫ) ln n + 1 participants ensures, with high probability, that everyone receives a segment from another participant.The bound follows from a balls-into-bins argument; the scheme adds a redistribution round because participants exclude themselves.Source: §IV · p. 4
  • With k of order ln n, the secure-channel scheme preserves computation privacy and reduces communication complexity compared with traditional secure sum, but requires secure channels.It redistributes data blocks as random segments among participants in a ring before aggregation.Source: §IV · p. 4

V. EFFICIENT PROTOCOLS FOR SUM AND PRODUCT

The paper presents four privacy-preserving calculation protocols across two participant models. In the participants-only product protocol, ring-shared public parameters produce secret random masks whose product is 1 modulo p, allowing participants to encrypt and aggregate their inputs.

V. EFFICIENT PROTOCOLS FOR SUM AND PRODUCT

  • The paper presents two calculation protocols for each of its two models to preserve individual data privacy.The protocols are intended as bases for privacy-preserving data aggregation.Source: §V · p. 4

A. Product Protocol - Participants Only Model

  • In the participants-only product protocol, participants use secret random values whose product is 1 mod p, each easy for its owner to compute but computationally expensive for others.The protocol specifies setup, encryption, and product steps in a cyclic group of prime order.Source: A. Product Protocol - Participants… · p. 4
  • Participants arranged in a ring use a PRF to choose secret integers, share public parameters with their two neighbors, and compute their secret masks from neighboring parameters.Each participant keeps its resulting random value secret.Source: A. Product Protocol - Participants… · pp. 4–5
  • Each participant encrypts its private input into a ciphertext and broadcasts it for participants to aggregate; choosing p ≥ M^n allows recovery of the product without modular reduction.A participant that does not wish to join the multiplication can set its input to 1.Source: A. Product Protocol - Participants… · p. 5

B. Product Protocol - One Aggregator Model

In the one-aggregator product model, the aggregator acts as an additional participant and receives participant ciphertexts directly. It uses its own random number in calculating the final product.

B. Product Protocol - One Aggregator Model

C. Sum Protocol - Participants Only Model

The participants-only sum protocol converts summation into a product-based computation using a modular property. It uses ring-based setup and ciphertext aggregation to recover the sum, avoiding the costly discrete-log approach described for an earlier solution.

C. Sum Protocol - Participants Only Model

D. Sum Protocol - One Aggregator Model

The section builds on the sum and product protocols to evaluate a general multivariate polynomial. In the One Aggregator Model, participants send ciphertexts to the aggregator, with a basic scheme whose privacy condition is stated for each product.

VI. EFFICIENT PROTOCOLS FOR GENERAL MULTIVARIATE POLYNOMIAL

A. One Aggregator Model

  • In the One Aggregator Model, ciphertexts are sent to the aggregator rather than broadcast, reducing communication complexity while remaining equivalent to broadcasting for security over insecure channels.The change is described as a communication-complexity reduction only.Source: A. One Aggregator Model · p. 6

1) Basic Scheme:

  • For each k, participants calculate x_i^d_i,k using powers specified by the aggregator, then run the product protocol for k in [1, m].The excerpt identifies these steps as the Basic Scheme.Source: 1) Basic Scheme · p. 6
  • The Basic Scheme preserves data privacy only if each product includes at least two x_i^d_i,k values not equal to 1.The passage states this as a condition for privacy.Source: 2) Advanced Scheme · p. 6

2) Advanced Scheme:

The Advanced Scheme addresses product terms that could reveal an individual input by omitting those terms and using the sum protocol. The section also presents a Participants Only Model combination and introduces correctness, complexity, and security analyses.

2) Advanced Scheme:

  • When a product term would expose an individual input, the Advanced Scheme omits it and applies the sum protocol to the affected data.A term is identified for omission when its input is the only one not equal to 1; the affected owners form the sum-participant set.Source: 2) Advanced Scheme · p. 6

B. Participants Only Model

  • The Participants Only Model combines the product protocol with the second sum protocol, and the section presents that scheme alone as the best combination from the One Aggregator Model.In this model, sum participants share their sum with each other before participants calculate the polynomial result.Source: B. Participants Only Model · p. 6

VII. CORRECTNESS, COMPLEXITY AND SECURITY ANALYSIS

  • The analysis section covers correctness, complexity, and security, including conditions under which private inputs could leak and possible remedies.The excerpt frames these as the subjects of the section’s analysis.Source: §VII · p. 6

A. Correctness

  • Correctness is shown for the product protocol in the Participants Only Model, with the One Aggregator Model proof described as easily derivable.The proof discussion begins from participants receiving the ciphertexts and conducting a calculation.Source: 1) Product Protocol · p. 6, A. Correctness · p. 6

1) Product Protocol:

The section gives correctness and security analyses for the protocols, including an input-indistinguishability result and a special-case disclosure risk. It prescribes an additional secure-sum calculation for that special case.

1) Product Protocol:

2) Sum Protocol:

  • The supplied passage displays only the fragment “i=1 xi mod p.”, so it supports a modulo-p expression involving xi at i=1, but not a complete sum over participants.Source: 2) Sum Protocol · p. 7

1) Special Case of Products Calculation:

  • If a product has only one ciphertext term not equal to 1, the corresponding individual input can be disclosed.The passage recommends an additional secure-sum calculation before sending ciphertexts in this case.Source: 1) Special Case of Products Calculation · p. 7

2) Randomness and Group Selection:

  • The proof discussion says any x_i is a possible valid input for a given ciphertext C_i.The passage presents this as a consequence of the preceding algebraic argument.Source: 2) Randomness and Group Selection · p. 7
  • Theorem VII.2 states that input x_i is computationally indistinguishable from a random element chosen from G1.The passage also describes the indistinguishability claim from the perspective of other participants or attackers.Source: 2) Randomness and Group Selection · p. 7

3) Closure and Group Selection:

The section specifies the group choice used to keep the sum-protocol multiplication closed, and states minimum participant counts for privacy in each model.

3) Closure and Group Selection:

  • G2 is chosen as a cyclic multiplicative subgroup of Z_p² so that 1 + x_i·p belongs to G2 and the sum-protocol multiplication remains closed.The passage specifies G2 as generated by h, the generator of Z_p.Source: 3) Closure and Group Selection · p. 7
  • Privacy requires at least three participants in the Participants Only Model and at least two in the One Aggregator Model.With two participants in the Participants Only Model, the passage says privacy is not preservable; in the One Aggregator Model, the aggregator alone knows the final result.Source: 4) Restriction of the Product and Sum… · p. 7

4) Restriction of the Product and Sum Protocol:

The section bounds computation and communication for the protocols, then contrasts communication overhead in the One Aggregator and Participants Only models.

C. Complexity

  • Setup, Encrypt, and Product have computation complexities O(1), O(1), and O(n); in the Advanced Scheme, Encrypt and Product each run m times.For the sum protocol, Setup, Encrypt, and Sum have complexities O(1), O(1), and O(m), and each is executed once.Source: 1) One Aggregator Model · pp. 7–8

1) One Aggregator Model:

  • In the One Aggregator Model, product encryption costs the aggregator O(mn|p|) bits; sum-protocol Setup, Encrypt, and Sum cost O(|p2|), O(|p2|), and O(m|p2|) bits.The section defines |p2| as twice |p|.Source: 1) One Aggregator Model · p. 8

2) Participants Only Model:

VIII. PERFORMANCE EVALUATION BY IMPLEMENTATION

Implementation measurements report faster addition and multiplication than the compared HE and FairplayMP systems, while protocol computation scales proportionally with participant count. The conclusion also identifies product-part leakage and further privacy-preserving data release as open work.

VIII. PERFORMANCE EVALUATION BY IMPLEMENTATION

  • Timing averages 100,000 executions of computation including participant encryption and aggregator decryption, using 20-bit inputs, 256-bit q, and roughly 270-bit p.The implementation used GMP on an Intel i7-2620M @ 2.70GHz computer with 2GB RAM.Source: §VIII · p. 8
  • Each protocol’s computation grows proportionally with participant count; sum calculation takes longer because its Zp2 parameters are twice the product protocol’s Zp parameter length.The paper describes multivariate polynomial evaluation as m products followed by one sum, with computation overhead combining the product and sum protocols.Source: §VIII · p. 8
  • 72.2 microseconds for 26 additions (1,066 gates) is 2 × 10^4 times faster than FairplayMP’s 1.394 seconds for 1,024 gates.The authors note that the FairplayMP runtime includes communication delay for the aggregator, unlike a pure computation-time measure.Source: Table IV · p. 8, §VIII · p. 9
  • 16.2 microseconds per addition versus 1 millisecond, and 0.7 microseconds per multiplication versus 41 milliseconds, are about 100 times and 6×10^4 times faster than HE.The comparison uses a 1024-bit modulus q and a setting allowing one multiplication.Source: Table V · p. 9, §VIII · p. 9
  • The authors state that FairplayMP and HE serve different purposes and provide a higher security level through differential privacy, so these comparisons are speed evidence rather than matched-purpose comparisons.The paper describes its own security level as acceptable in real-life applications.Source: §VIII · p. 9

IX. CONCLUSION

  • The scheme discloses each polynomial product part; future work targets minimizing computation leakage and designing privacy-preserving releases that protect functional privacy.The paper presents privacy-preserving multivariate polynomial evaluation without secure communication channels as its achieved result.Source: §IX · p. 9
Loading 1206.2660v4…