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 | |
State | Published - Oct 2018 |
All Science Journal Classification (ASJC) codes
- Control and Systems Engineering
- Electrical and Electronic Engineering
Access to Document
Other files and links
Fingerprint
Dive into the research topics of 'Privacy preserving distributed optimization using homomorphic encryption'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver
}
In: Automatica, Vol. 96, 10.2018, p. 314-325.
Research output: Contribution to journal › Article › peer-review
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 -