Privacy preserving distributed optimization using homomorphic encryption

Yang Lu; Minghui Zhu

doi:10.1016/j.automatica.2018.07.005

Privacy preserving distributed optimization using homomorphic encryption

Yang Lu, Minghui Zhu

Electrical Engineering

Research output: Contribution to journal › Article › peer-review

98 Scopus citations

Abstract

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.

Original language	English (US)
Pages (from-to)	314-325
Number of pages	12
Journal	Automatica
Volume	96
DOIs	https://doi.org/10.1016/j.automatica.2018.07.005
State	Published - Oct 2018

All Science Journal Classification (ASJC) codes

Control and Systems Engineering
Electrical and Electronic Engineering

Access to Document

10.1016/j.automatica.2018.07.005

Cite this

@article{fae9bab0b2f44f11a3dd5c0d9c24acd0,

title = "Privacy preserving distributed optimization using homomorphic encryption",

abstract = "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.",

author = "Yang Lu and Minghui Zhu",

note = "Funding Information: In this subsection, we provide some preliminaries for the Paillier encryption scheme. The results of this subsection can be found in Paillier (1999) and Yi et al. (2014) . Consider a scenario consisting of a message sender, a message receiver and an adversary. The message sender aims to send a private message to the message receiver via an open communication link which is insecure and can be eavesdropped by the adversary. To achieve secure message delivery, the message sender and receiver can adopt some public key encryption scheme. In this paper, we choose the Paillier encryption scheme as our implementing scheme. The standard Paillier encryption scheme consists of key generation, encryption and decryption operations as follows. • Key generation: The message receiver randomly chooses two large prime numbers p and q such that gcd ( p q , ( p − 1 ) ( q − 1 ) ) = 1 ; computes α = p q , ν = lcm ( p − 1 , q − 1 ) ; selects random integer β ∈ Z α 2 ∗ such that the modular multiplicative inverse π = ( ( β ν m o d α 2 ) − 1 α ) − 1 m o d α exists, i.e., π ( β ν m o d α 2 ) − 1 α ≡ 1 m o d α . The public keys are ( α , β ) and the private keys are ( ν , π ) . The message receiver publicizes ( α , β ) while keeps ( ν , π , p , q ) private to itself. • Encryption: To encrypt a plaintext p t ∈ Z α , the message sender selects a random number r ∈ Z α ∗ and computes the ciphertext by the encryption operation E ( ⋅ ) as c t = E ( p t , α , β , r ) = β p t ⋅ r α m o d α 2 . The message sender then sends c t to the message receiver. • Decryption: To decrypt the ciphertext c t ∈ Z α 2 , the message receiver performs the decryption operation D ( ⋅ ) as p t ¯ = D ( c t , α , ν , π ) = ( c t ν m o d α 2 ) − 1 α ⋅ π m o d α . In cryptography, the security of most public-key encryption schemes are established under certain mathematical assumptions which state that certain mathematical problems are difficult to solve. Specifically, the semantic security of the Paillier encryption scheme is proved under the decisional composite residuosity assumption (DCRA), stated as follows: Given a composite C and an integer z , it is computationally intractable to decide whether z is a C -residue modulo C 2 or not, i.e., whether there exists y such that z = y C m o d C 2 . The correctness, security and homomorphic properties of the Paillier encryption scheme are provided by the following theorem, whose proof is given in Paillier (1999) . Theorem A.1 By the Paillier encryption scheme, the following claims hold: (1) Correctness: p t ¯ = p t . (2) Semantic security: If the DCRA holds, then the Paillier encryption scheme is semantically secure. (3) Homomorphic properties: (3-i) Given any p t 1 , … , p t m ∈ N . If ∑ ℓ = 1 m p t ℓ ∈ Z α , then D ( ∏ ℓ = 1 m E ( p t ℓ , α , β , r ℓ ) , α , ν , π ) = ∑ ℓ = 1 m p t ℓ . (3-ii) Given any p t 1 , p t 2 ∈ N . If p t 1 p t 2 ∈ Z α , then D ( E ( p t 1 , α , β , r ) p t 2 , α , ν , π ) = p t 1 p t 2 . ■ Yang Lu is a Ph.D. student in the School of Electrical Engineering and Computer Science at the Pennsylvania State University. Prior to that, he worked as a visiting scholar in the School of Electrical and Computer Engineering at the Georgia Institute of Technology. He received the B.E. and M.E. degrees in electrical engineering from Shanghai Jiao Tong University, Shanghai, China, in 2010 and 2013, respectively, and the M.S. degree in electrical engineering from the Georgia Institute of Technology in 2013. His research interests mainly focus on distributed control and optimization and cyber–physical security. Minghui Zhu is the Dorothy Quiggle Assistant Professor in the School of Electrical Engineering and Computer Science at the Pennsylvania State University. Prior to that, he was a postdoctoral associate in the Laboratory for Information and Decision Systems at the Massachusetts Institute of Technology. He received Ph.D. in Engineering Science (Mechanical Engineering) from the University of California, San Diego in 2011. His research interests lie in the design, analysis and control of multi-agent networks with applications in multi-vehicle networks, security and the smart grid. He is the co-author of the book ”Distributed optimization-based control of multi-agent networks in complex environments” (Springer, 2015). He was the recipient of the Powell fellowship and the Back fellowship at the University of California, San Diego in 2007. For his Ph.D. research, he received the award of Outstanding Graduate Student of Mechanical and Aerospace Engineering at the University of California, San Diego in 2011. He is an associate editor of the Conference Editorial Board of the IEEE Control Systems Society. He was selected as an outstanding reviewer of Automatica in 2013 and 2014. Funding Information: This work was partially supported by NSA grant H98230-15-1-0289 and NSF grant CNS-1505664. The material in this paper was partially presented at the 5th IFAC Workshop on Distributed Estimation and Control in Networked Systems, September 10–11, 2015, Philadelphia, PA, USA. This paper was recommended for publication in revised form by Associate Editor Shreyas Sundaram under the direction of Editor Christos G. Cassandras. Publisher Copyright: {\textcopyright} 2018 Elsevier Ltd",

year = "2018",

month = oct,

doi = "10.1016/j.automatica.2018.07.005",

language = "English (US)",

volume = "96",

pages = "314--325",

journal = "Automatica",

issn = "0005-1098",

publisher = "Elsevier Limited",

}

TY - JOUR

T1 - Privacy preserving distributed optimization using homomorphic encryption

AU - Lu, Yang

AU - Zhu, Minghui

N1 - Funding Information: In this subsection, we provide some preliminaries for the Paillier encryption scheme. The results of this subsection can be found in Paillier (1999) and Yi et al. (2014) . Consider a scenario consisting of a message sender, a message receiver and an adversary. The message sender aims to send a private message to the message receiver via an open communication link which is insecure and can be eavesdropped by the adversary. To achieve secure message delivery, the message sender and receiver can adopt some public key encryption scheme. In this paper, we choose the Paillier encryption scheme as our implementing scheme. The standard Paillier encryption scheme consists of key generation, encryption and decryption operations as follows. • Key generation: The message receiver randomly chooses two large prime numbers p and q such that gcd ( p q , ( p − 1 ) ( q − 1 ) ) = 1 ; computes α = p q , ν = lcm ( p − 1 , q − 1 ) ; selects random integer β ∈ Z α 2 ∗ such that the modular multiplicative inverse π = ( ( β ν m o d α 2 ) − 1 α ) − 1 m o d α exists, i.e., π ( β ν m o d α 2 ) − 1 α ≡ 1 m o d α . The public keys are ( α , β ) and the private keys are ( ν , π ) . The message receiver publicizes ( α , β ) while keeps ( ν , π , p , q ) private to itself. • Encryption: To encrypt a plaintext p t ∈ Z α , the message sender selects a random number r ∈ Z α ∗ and computes the ciphertext by the encryption operation E ( ⋅ ) as c t = E ( p t , α , β , r ) = β p t ⋅ r α m o d α 2 . The message sender then sends c t to the message receiver. • Decryption: To decrypt the ciphertext c t ∈ Z α 2 , the message receiver performs the decryption operation D ( ⋅ ) as p t ¯ = D ( c t , α , ν , π ) = ( c t ν m o d α 2 ) − 1 α ⋅ π m o d α . In cryptography, the security of most public-key encryption schemes are established under certain mathematical assumptions which state that certain mathematical problems are difficult to solve. Specifically, the semantic security of the Paillier encryption scheme is proved under the decisional composite residuosity assumption (DCRA), stated as follows: Given a composite C and an integer z , it is computationally intractable to decide whether z is a C -residue modulo C 2 or not, i.e., whether there exists y such that z = y C m o d C 2 . The correctness, security and homomorphic properties of the Paillier encryption scheme are provided by the following theorem, whose proof is given in Paillier (1999) . Theorem A.1 By the Paillier encryption scheme, the following claims hold: (1) Correctness: p t ¯ = p t . (2) Semantic security: If the DCRA holds, then the Paillier encryption scheme is semantically secure. (3) Homomorphic properties: (3-i) Given any p t 1 , … , p t m ∈ N . If ∑ ℓ = 1 m p t ℓ ∈ Z α , then D ( ∏ ℓ = 1 m E ( p t ℓ , α , β , r ℓ ) , α , ν , π ) = ∑ ℓ = 1 m p t ℓ . (3-ii) Given any p t 1 , p t 2 ∈ N . If p t 1 p t 2 ∈ Z α , then D ( E ( p t 1 , α , β , r ) p t 2 , α , ν , π ) = p t 1 p t 2 . ■ Yang Lu is a Ph.D. student in the School of Electrical Engineering and Computer Science at the Pennsylvania State University. Prior to that, he worked as a visiting scholar in the School of Electrical and Computer Engineering at the Georgia Institute of Technology. He received the B.E. and M.E. degrees in electrical engineering from Shanghai Jiao Tong University, Shanghai, China, in 2010 and 2013, respectively, and the M.S. degree in electrical engineering from the Georgia Institute of Technology in 2013. His research interests mainly focus on distributed control and optimization and cyber–physical security. Minghui Zhu is the Dorothy Quiggle Assistant Professor in the School of Electrical Engineering and Computer Science at the Pennsylvania State University. Prior to that, he was a postdoctoral associate in the Laboratory for Information and Decision Systems at the Massachusetts Institute of Technology. He received Ph.D. in Engineering Science (Mechanical Engineering) from the University of California, San Diego in 2011. His research interests lie in the design, analysis and control of multi-agent networks with applications in multi-vehicle networks, security and the smart grid. He is the co-author of the book ”Distributed optimization-based control of multi-agent networks in complex environments” (Springer, 2015). He was the recipient of the Powell fellowship and the Back fellowship at the University of California, San Diego in 2007. For his Ph.D. research, he received the award of Outstanding Graduate Student of Mechanical and Aerospace Engineering at the University of California, San Diego in 2011. He is an associate editor of the Conference Editorial Board of the IEEE Control Systems Society. He was selected as an outstanding reviewer of Automatica in 2013 and 2014. Funding Information: This work was partially supported by NSA grant H98230-15-1-0289 and NSF grant CNS-1505664. The material in this paper was partially presented at the 5th IFAC Workshop on Distributed Estimation and Control in Networked Systems, September 10–11, 2015, Philadelphia, PA, USA. This paper was recommended for publication in revised form by Associate Editor Shreyas Sundaram under the direction of Editor Christos G. Cassandras. Publisher Copyright: © 2018 Elsevier Ltd

PY - 2018/10

Y1 - 2018/10

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85050098876&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85050098876&partnerID=8YFLogxK

U2 - 10.1016/j.automatica.2018.07.005

DO - 10.1016/j.automatica.2018.07.005

M3 - Article

AN - SCOPUS:85050098876

SN - 0005-1098

VL - 96

SP - 314

EP - 325

JO - Automatica

JF - Automatica

ER -

Privacy preserving distributed optimization using homomorphic encryption

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this