PaperlayerView exact revision on arXiv

Source-linked AI summary

Privacy preserving distributed optimization using homomorphic encryption

Yang Lu, Minghui Zhu

arXiv:1805.00572v3cs.CR

TL;DR

The paper asks how distributed projected gradient-based algorithms can protect private states and coefficients while determining which functions are safe to compute. It uses homomorphic-encryption schemes and an IOI analysis, achieving perfect correctness with power-system case studies verifying correctness and computational efficiency. The scope excludes division operations and relies on a temporarily independent attack assumption for one scheme.

  • Problem

    Distributed gradient-based optimization must protect private participant states and coefficients while addressing both secure function computation and inference from function outputs.

  • Method

    The paper develops homomorphic-encryption schemes for secure computation and defines IOI conditions for identifying securely computable quadratic functions.

  • Results

    Perfect correctness is achieved while protecting participants’ states and coefficients, with correctness and computational efficiency verified in demand response and optimal power flow case studies.

  • Takeaways & Limitations

    The results support privacy-preserving execution of a class of distributed projected gradient-based algorithms in the studied power-system applications.

  • Takeaways & Limitations

    The approach excludes division operations and one private-key scheme relies on temporarily independent attacks, whose relaxation is left for future work.

Abstract

from arXiv · show

This paper studies how a system operator and a set of agents securely execute a distributed projected gradient-based algorithm. In particular, each participant holds a set of problem coefficients and/or states whose values are private to the data owner. The concerned problem raises two questions: how to securely compute given functions; and which functions should be computed in the first place. For the first question, by using the techniques of homomorphic encryption, we propose novel algorithms which can achieve secure multiparty computation with perfect correctness. For the second question, we identify a class of functions which can be securely computed. The correctness and computational efficiency of the proposed algorithms are verified by two case studies of power systems, one on a demand response problem and the other on an optimal power flow problem.

1 Introduction

The paper addresses privacy in distributed gradient-based optimization by separating secure multiparty computation from input-output inference. It develops homomorphic-encryption schemes with formal correctness and privacy guarantees, and studies which functions can be safely computed, with power-system case studies providing verification.

  • Motivation: Distributed optimization requires data sharing for network-wide goals, creating a risk that legitimate entities’ private information is disclosed.The paper frames privacy preservation as necessary for coordinating large-scale networked systems.
  • Problem formulation: The privacy problem has two parts: securely computing functions without revealing information beyond outputs, and selecting functions whose outputs do not expose private inputs.These are termed secure multiparty computation (SMC) and input-output inference (IOI), respectively.
  • Problem formulation: The paper decomposes the distributed gradient algorithm into collective gradient computation and local state updates, because each update depends on private data held by other participants.Agents receive their gradient values and then update their own states locally.
  • Approach: Homomorphic encryption schemes are proposed for secure computation, including private-key fully homomorphic encryption for arbitrary polynomial functions and Paillier-based public-key encryption for affine functions.The schemes are designed to achieve correct computation while limiting what participants and the system operator can infer.
  • Approach: The paper defines a control-aware IOI criterion and derives sufficient conditions for a class of quadratic functions using coefficient-matrix null vectors and constant terms.A function is secure under this criterion when outputs do not uniquely determine participants’ private inputs and input uncertainty is infinite.
  • Evaluation: Correctness and computational efficiency are verified in power-system case studies covering demand response and optimal power flow.The paper also positions its formal SMC and IOI analysis as an advance over earlier homomorphic-encryption work.

2 Problem formulation

The paper formulates privacy-preserving execution of a projected gradient-based distributed optimization algorithm, separating collective gradient computation from local state updates. It addresses both secure multiparty computation and input-output inference under specified attacker and communication assumptions.

  • 2.1 Gradient-based distributed optimization: The model assumes an undirected communication link between every agent and the system operator, who knows gradient structure but not undisclosed states or coefficients.All agents use the same step size, which is known to every participant and the system operator.
  • 2.1 Gradient-based distributed optimization: Agents use projected gradient updates with a common positive step size and gradients that may depend on the full system state.The update aims to converge to a solution while each agent locally projects its state onto its feasible set.
  • 2.1 Gradient-based distributed optimization: The formulation assumes each gradient component is polynomial, while convergence conditions are assumed from existing theory rather than analyzed here.The paper excludes division operations because existing homomorphic encryption schemes do not directly support them.
  • 2.2 Privacy issues: Participants’ private data include agent state sequences, feasible sets, and function coefficients that should remain undisclosed to unauthorized participants.The motivation includes protecting behavioral information in demand response and system parameters in optimal power flow.
  • 2.2 Privacy issues: The secure computation problem separates collective computation of gradient values from local updates because gradients depend on other participants’ private data.This decomposition motivates the block diagram for executing the distributed update without exposing protected inputs.
  • 2.2 Privacy issues: SMC requires correct function outputs without revealing anything beyond those outputs, whereas IOI asks which function sequences avoid exposing other participants’ private data.IOI considers inference from receiving repeated outputs over arbitrary finite horizons.
  • 2.3 Attacker model and privacy notions: The analysis considers semi-honest adversaries that follow the protocol but use received messages to infer other participants’ private data.Privacy for SMC is framed using parties’ views and computational indistinguishability.
  • 2.4 Transformation between integers and real numbers: The real-number transformation is correct when signed values with σ decimal digits satisfy |10^σr| ≤ (w − 1)/2.Under this bound, applying Tσ,w to the modularly transformed integer recovers r.

3 Private key secure computation algorithm

The private-key algorithm uses fully homomorphic encryption to securely compute polynomial functions over private real-valued states and coefficients. It establishes correctness and security against temporarily independent system-operator attacks, while requiring each private coefficient to be encrypted only once.

  • The algorithm applies private-key fully homomorphic encryption to securely compute arbitrary polynomial functions over distributed private inputs.Real values are transformed into integers before encryption, computation, and decryption.
  • Scaling transformed monomials by degree-specific factors aligns their magnitudes so homomorphic summation produces the intended polynomial result.The method scales lower-degree monomials to a common degree before summing them.
  • Each private coefficient is encrypted only once through a partition of the coefficient set, preventing repeated encryption from compromising coefficient privacy.Repeated encryption can allow the system operator to recover a good estimate of a shared private coefficient.
  • The private-key design requires agents to agree on a secret large integer and only addresses temporarily independent system-operator attacks.Its plaintext privacy notion is weaker than semantic security.
  • Under the stated assumptions, Algorithm 1 computes each desired function correctly and securely computes the sequence between agents.Against the system operator, solving for the current state and private coefficients is as hard as the approximate GCD problem at each step.

4 Public key secure computation algorithm

The public-key algorithm uses Paillier’s additive homomorphism for affine functions, removing the private-key design’s key-distribution and semantic-security limitations. Under its assumptions, it computes the desired functions correctly and provides semantic security against the system operator.

  • The public-key algorithm uses Paillier encryption to securely compute affine functions whose coefficients are known to the system operator.Paillier’s additive homomorphism supports weighted sums but not general multiplication of encrypted variables.
  • Affineness is required because Paillier supports additive homomorphism, while known weights allow multiplication by repeated addition during computation.The resulting problem class includes linear and quadratic programs, quadratic convex games, and affine variational inequalities.
  • Each agent generates public and private Paillier keys, encrypts its state for the other agents’ public keys, and receives encrypted function values from the system operator.Agents decrypt the results, transform them back to signed real numbers, and perform the local projected-gradient update.
  • Under Assumptions 2.1, 4.1, 4.2 and DCRA, Algorithm 2 securely computes the function sequence between agents and is semantically secure against the system operator.Correctness follows from Paillier’s homomorphic properties and the real-integer transformation.

5 Privacy analysis on input-output inference

The privacy analysis separates secure computation from input-output inference: even a secure computation can expose private inputs through its outputs. For quadratic functions, a null-space condition yields unbounded uncertainty about alternative private states, feasible sets, and coefficients.

  • Secure multiparty computation alone does not prevent private inputs from being inferred from function outputs.The analysis therefore asks whether private inputs can be uniquely determined from observed outputs.
  • For the quadratic case, the matrices are public while selected constant terms remain private to subsets of agents.This privacy structure defines the setting in which the null-space result applies.
  • Because the gradient process is iterative, successive observations can reveal dynamic private inputs, limiting methods designed for constant private inputs.The paper identifies the iterative nature of the process as requiring new input-output inference analysis.
  • The paper identifies a sufficient null-space condition on joint-function weight matrices under which affine functions resist input-output inference.The condition is expressed through a null vector whose entries are all nonzero.
  • Under Assumption 5.2, quadratic-function sequences resist input-output inference with unbounded uncertainty for any finite observation horizon K.Alternative states can be shifted by arbitrarily scaled nonzero null-space vectors while preserving the adversary’s observations.

6 Case study

The case studies apply the proposed secure computation algorithms to demand response and optimal power flow problems, evaluating correctness and computational efficiency. Both simulations report exact agreement with plaintext projected-gradient trajectories, while runtime is assessed across key lengths.

  • The case studies validate Algorithm 1 on demand response and Algorithm 2 on optimal power flow problems.
  • Demand response problem: The demand response study uses the IEEE 14-bus system with two generators and eleven loads.
  • Demand response problem: Algorithm 1 produces privacy-preserving trajectories exactly equal to the plaintext trajectories at every iteration.The comparison uses four decimal fraction digits and identical initial states; the difference trajectory remains constant at 0.
  • Demand response problem: Algorithm 1 runtime is measured per customer and iteration across private-key lengths, including encryption, encrypted computation, decryption, numeric transformation, and local updating.
  • Optimal power flow problem: Algorithm 2 also achieves perfect correctness, with privacy-preserving trajectories matching plaintext trajectories in the OPF simulation.
  • Optimal power flow problem: Algorithm 2 runtime is reported per generator and iteration across public-key lengths, covering encryption, encrypted computation, decryption, numeric transformation, and local updating.

7 Proofs

The proofs establish correctness and privacy properties for both homomorphic-encryption algorithms. They show secure computation between agents, computational difficulty for the system operator, and resistance to input-output inference for the studied function class.

  • Secure multiparty computation: The simulation-paradigm proofs show that agents securely compute the desired function outputs without learning beyond their permitted inputs and outputs.For Algorithm 1, the proof constructs simulated views from an agent’s inputs and output; analogous reasoning establishes secure computation for Algorithm 2.
  • System-operator security: Recovering states and coefficients from Algorithm 1’s masked values is as hard as solving the approximate GCD problem.The operator must recover the secret value w from masked states and coefficients to infer the private data.
  • System-operator security: Algorithm 2 remains semantically secure against the system operator even when the operator knows the update rule and launches causal attacks.The proof uses semantic security of Paillier encryption across ciphertexts, including ciphertexts corresponding to different algorithm iterations.
  • Input-output inference: The quadratic joint-function sequence resists input-output inference with unbounded uncertainty for any finite K.The construction perturbs other agents’ states and corresponding private coefficients while preserving the observed constraints and outputs.

8 Conclusion

The paper develops homomorphic-encryption schemes for securely executing distributed projected gradient-based algorithms. The schemes achieve perfect correctness and protect participants’ states and coefficients, while the paper also studies input-output inference and validates correctness and computational efficiency in two power-system case studies.

  • Contribution: The paper proposes homomorphic-encryption schemes for securely executing a class of distributed projected gradient-based algorithms.The schemes target distributed algorithms in which agents and a system operator jointly execute gradient-based updates.
  • Contribution: The schemes achieve perfect correctness while protecting each participant’s states and coefficients from other participants.The conclusion states both properties together as outcomes of the proposed schemes.
  • Contribution: The paper studies input-output inference for a class of quadratic joint functions.This extends the privacy analysis beyond secure computation of function outputs.
  • Evaluation: Correctness and computational efficiency are verified through demand-response and optimal-power-flow case studies.The two case studies are both in power systems.

9 Appendix

The appendix reviews homomorphic-encryption categories and Paillier preliminaries, then illustrates the proposed algorithms with numerical examples. These examples show exact decryption results and explain the masking and scaling operations used in computation.

  • Homomorphic-encryption background: Private-key and public-key homomorphic encryption schemes differ in whether encryption and decryption use the same key.The appendix also distinguishes partially homomorphic schemes, which support one algebraic operation, from fully homomorphic schemes, which support both addition and multiplication.
  • Homomorphic-encryption background: Private-key schemes face key-distribution problems, whereas Gentry’s fully homomorphic scheme is limited by highly time-consuming implementation.Reported benchmarks include 36 hours for AES encryption and bootstrapping times from 30 seconds to 30 minutes.
  • Paillier encryption: The Paillier scheme provides correctness, semantic security under DCRA, and homomorphic properties used by Algorithm 2.Its homomorphic operations support addition and multiplication of suitable plaintext values through ciphertext computations.
  • Numerical examples: The numerical example encrypts signed real coefficients and states by transforming real values into scaled integers before homomorphic computation.The example uses σ = 2 and applies integer scaling to the private coefficients and states.
  • Numerical examples: The encrypted state values in the Algorithm 1 example are computationally difficult for the system operator to invert because recovery requires solving the approximate GCD problem.The same security rationale is applied to encrypted coefficients.
Loading 1805.00572v3…