=Paper=
{{Paper
|id=Vol-2301/paper13
|storemode=property
|title=AutoMPC: Efficient Multi-Party Computation for Secure and Privacy-Preserving Cooperative Control of Connected Autonomous Vehicles
|pdfUrl=https://ceur-ws.org/Vol-2301/paper_13.pdf
|volume=Vol-2301
|authors=Tao Li,Lei Lin,Siyuan Gong
|dblpUrl=https://dblp.org/rec/conf/aaai/LiLG19
}}
==AutoMPC: Efficient Multi-Party Computation for Secure and Privacy-Preserving Cooperative Control of Connected Autonomous Vehicles==
https://ceur-ws.org/Vol-2301/paper_13.pdf
AutoMPC: Efficient Multi-Party Computation for Secure and Privacy-Preserving
Cooperative Control of Connected Autonomous Vehicles
Tao Li Lei Lin Siyuan Gong
Department of Computer Science Goergen Institute of Data Science Department of Computer Science
Purdue University Rochester University Chang’an University
taoli@purdue.edu lei.lin@rochester.edu sgong@chd.edu.cn
Abstract on (Shladover 2018), These applications require low latency
and high reliability networking. Hence, efficient, secure, and
The advent of connected autonomous vehicles provides trustworthy data transmitting is of paramount importance.
opportunities for safer, smoother, and smarter trans-
portation. However, broadcasting information to sur- More recently, interesting opportunities appear through
rounding vehicles and infrastructures risks security and the utilization of techniques from connected vehicles to au-
privacy. Moreover, control decisions relying on such in- tonomous vehicles. The connectivity allows an autonomous
formation are vulnerable to malicious attacks. In this pa- to have more detailed knowledge of the environment. The
per, we propose a cooperative control strategy incorpo- sensing capability of the autonomous vehicle is hence fur-
rating with efficient multi-party computation (MPC). In ther expanded. A platoon formed by connected and au-
an effort to perform secure MPC without third-party au- tonomous (CAVs) on the road can increase the capacity, re-
thentication while reducing latency, we integrate a func- duce energy consumption and improve safety. It was pre-
tion secret sharing scheme with a distributed oblivious
dicted that the transition from the current human-driven
random access memory. We further design an adaptive
proportional-derivative controller to increase resilience vehicles to a fully CAV traffic environment require a few
toward latency and adversaries. Theoretical foundations decades (GSMA 2013), during which the road traffic consist
and limitations are also discussed. of a mixed traffic flow (see Figure 1). Equipped with mul-
tiple sensors and V2V communications, a CAV can track
the trajectories of other CAVs in its vicinity, and ideally, all
1 Introduction CAVs in communication range. Such CAV trajectory data
Since the first competition of autonomous vehicles hosted by can be leveraged with advances in computing and machine
the Defense Advanced Research Projects Agency (DARPA) learning algorithms to potentially predict trajectories of sur-
Grand Challenge in 2005 (Seetharaman, Lakhotia, and rounding vehicles, such as acceleration and speed. Based on
Blasch 2006), self-driving vehicle or autonomous vehicle these predictions, CAVs can react accordingly to avoid or
techniques have attracted tremendous attentions from both mitigate traffic flow oscillations and accidents.
academia and industry. An autonomous vehicle is equipped In reality, V2V communications are unreliable due to fac-
with various powerful sensors like camera, radar, LiDAR, tors such as interference, network congestion, and malicious
GPS, ultrasonic and so on to detect and perceive its sur- attacks; in the worst case, V2V networks undergo Byzan-
rounding environment. Autonomous vehicles have the po- tine failures (Lamport, Shostak, and Pease 1982; Li and Lin
tential to change driving behavior and the travel envi- 2018), which is the most general and severe failure model,
ronment, providing opportunities for safer, smoother, and since attackers are fully aware of any information of the
smarter road transportation. However, the development of entire system. Moreover, current architecutre of vehicular
autonomous vehicles has also raised disputations and skep- ad-hoc networks (VANETs) communicate in an open-access
ticism in terms of liability, ethics, cybersecurity, privacy and environment and thereby experience serious issues in secu-
so on. Especially, the fatal accident in March, 2018 involv- rity and privacy (Qu et al. 2015). To tackle these, we propose
ing an Ubers self-driving car where a pedestrian was killed a novel cooperative control strategy, AutoMPC, by leverag-
implies a large room to enhance autonomous vehicle tech- ing advances in modern cryptography such as multi-party
niques and safety should always be considered with the computation (MPC). As V2V communication requires low
highest priority in this process (Li et al. 2018a). latency, we further adopt an efficient MPC scheme incor-
On the other hand, connected vehicle techniques are also porating with an adaptive proportional-derivative controller
being deployed to improve the safety and mobility of our and prove its effectiveness through numerical experiments.
transportation system by enhancing situational awareness The rest of this paper is organized as follows: in Section 2
and traffic state estimation through vehicle-to-vehicle (V2V) we introduce necessary background; Section 3 presents the
and vehicle-to-infrastructure communications, which can AutoMPC model; future works are discussed in Section 4;
enable applications like cooperative collision warning, pro- we leave the experimental section and more theoretical re-
viding traffic signal status information in real time and so sults in the full paper.
Figure 1: Scenario of a mixed platoon of connected autonomous vehicles (CAVs) and human-driven vehicles (HDVs).
2 Background secrets. (Parakh and Kak 2011) proposed a k-threshold com-
We first introduce necessary background in security. putational secret sharing scheme that divide a secret S into
|S|
shares of size K−1 for optimal space efficiency.
2.1 Secure Multi-Party Computation
To formalize the problem, we suppose a multi-agent sys-
3 The AutoMPC Model
tem in which each party i has a secret input xi and a func- Inspired by existing works (Gordon et al. 2012; Wang et al.
tion f (x1 , x2 , . . . ) can be jointly evaluated. Secure multi- 2014; Doerner and Shelat 2017) and aforementioned tech-
party computation (MPC) is a mechanism to ensure that each niques, we propose the AutoMPC model, which adopts a
party known the output of the function f while being un- function secret sharing (FSS) scheme following the defini-
aware of others’ inputs. Two-party computation (2PC) is a tion in (Boyle, Gilboa, and Ishai 2016) that:
special case of MPC, which was first introduced by (Yao Definition 1. An m-party function secret sharing scheme is
1982) as a problem that two millionaires (Alice and Bob) a pair of algorithms (Gen, Eval) with the following syntax:
wish to know who is richer but don’t want to disclose their • Gen(1λ , f¯) is a PPT key generation algorithm, which
own wealth. The famous solution is Yao’s Garbled Circuits on input 1λ (security parameter) and f¯ ∈ {0, 1}∗ (de-
(Yao 1986), which is based on honest-but-curious model or scription of a function f ) outputs an m-tuple of keys
semi-honest security model that curious adversaries and out- (k1 , . . . , km ). f¯ is assumed to explicitly contains an in-
side observers may learn the secrets by analyzing protocol put length 1n , group description G, and size parameter
transcripts. S.
• Eval(i, ki , x) is a polynomial-time evaluation algorithm,
2.2 Oblivious Random Access Memory
which on input i ∈ [m] (party index), ki (key defining
Oblivious random access memory (ORAM) (Goldreich fi : {0, 1}n → G), and x ∈ {0, 1}n (intput for fi ) outputs
and Ostrovsky 1996) is similar to random access memory a group element yi ∈ G (the value of fi (x), the i-th share
(RAM) but translates the sequence of logical access instruc- of f (x)).
tions in certain ways so that preserves the observing of phys- The setting of FSS ensures correctness and security that
ical access patterns from adversaries. An ORAM supports each party’s key cannot individually reveal any information
READ(i) and W RIT E(i) functions that are able to per- of f (Boyle, Gilboa, and Ishai 2015). We further adopt a
form “read” and “write” operations with a private index i. distributed oblivious RAM (Doerner and Shelat 2017) to
For the case of MPC, we consider a variant of ORAM, optimize the computational complexity to O(n) which out-
distributed oblivious RAM (DORAM) (Lu and Ostrovsky performs current state-of-the-arts such as circuit oblivious
2013), which generalize ORAM to a scenario that the mem- RAM (Wang, Chan, and Shi 2015) and square-root oblivi-
ory is splited among m parties and has a security property ous RAM (Zahur et al. 2016).
that no party can learn anything of the RAM by observing To mitigate the latency trade-offs given by MPCs and in-
their own share of the physical memory. crease resilience towards adversaries, we propose an adap-
tive proportional-derivative (PD) controller based on a two-
2.3 Secret Sharing predecessor-following scheme as shown in Figure 2, in
Secret sharing (Shamir 1979) is a method in cryptography which we assume all CAVs in the platoon to be identical,
that distributes a secret among a group of m parties by di- forming a homogeneous vehicle string. Below is the control
viding the secret into m shares, one for each of m parties, command
so that none of the individual party has any insight of the se-
Ui (s) = Ub,i (s) + Uf,i−1 (s) + Uf,i−2 (s) (1)
cret while all m shares as a group contain full information of
the secret. (Franklin and Yung 1992) designed a multi-secret which consists of control feedback Ub,i from the error Ei
sharing system where multiple points of the polynomial host and two extra feedforward terms Uf,i−1 and Uf,i−2 from
Boyle, E.; Gilboa, N.; and Ishai, Y. 2016. Function secret
sharing: Improvements and extensions. In Proceedings of
the 2016 ACM SIGSAC Conference on Computer and Com-
munications Security, 1292–1303. ACM.
Doerner, J., and Shelat, A. 2017. Scaling oram for secure
computation. In Proceedings of the 2017 ACM SIGSAC
Conference on Computer and Communications Security,
523–535. ACM.
Du, W., and Atallah, M. J. 2001. Secure multi-party com-
putation problems and their applications: a review and open
problems. In Proceedings of the 2001 workshop on New se-
Figure 2: Diagram of the control schematic.
curity paradigms, 13–22. ACM.
Franklin, M., and Yung, M. 1992. Communication complex-
the acceleration rates Ẍi−1 and Ẍi−2 , respectively. Xi is the ity of secure computation. In Proceedings of the twenty-
position output, Xi−1 is the feedback position information fourth annual ACM symposium on Theory of computing,
from the immediate predecessor. Ki is the feedback con- 699–710. ACM.
troller which generates a control command to rectify the er- Goldreich, O., and Ostrovsky, R. 1996. Software protec-
ror. Gi represents the ideal longitudinal vehicle dynamics. tion and simulation on oblivious rams. Journal of the ACM
Hi denotes spacing policy (e.g., CD and CTH), and F1,i and (JACM) 43(3):431–473.
F2,i are feedforward filters to process the acceleration infor- Gong, S.; Zhou, A.; Wang, J.; Li, T.; and Peeta, S. 2018. Co-
mation from the corresponding predecessor vehicles. α and operative adaptive cruise control for a platoon of connected
β are indicators for the success of V2V communications (α and autonomous vehicles considering dynamic information
and β are equal to 1 for a successful communication between flow topology. In the 21st IEEE International Conference
the CAV and the corresponding predecessor vehicles, and 0 on Intelligent Transportation Systems.
otherwise). These terms will be explained in detail later.
Gordon, S. D.; Katz, J.; Kolesnikov, V.; Krell, F.; Malkin,
T.; Raykova, M.; and Vahlis, Y. 2012. Secure two-party
4 Discussion and Future Works computation in sublinear (amortized) time. In Proceedings
The AutoMPC model leverages advances in cryptography of the 2012 ACM conference on Computer and communica-
to control theory for safer, smoother, and smarter trans- tions security, 513–524. ACM.
portation. The contributions lie in several ways: (i) security GSMA. 2013. Gsma: Every new car connected by 2025
and privacy are guaranteed via a MPC scheme, without the as embedded mobile technology drives growth of connected
presence of third-party authentication; (ii) the efficiency of car market.
the MPC is achieved by a distributed oblivious RAM and
IEEE. 2012. News releases.
a function secret sharing scheme, and thereby avoids the
homomorphic encryption approach which is computation- International, S. 2014. Automated driving: levels of driv-
ally expensive; and (iii) an adaptive proportional-derivative ing automation are defined in new sae international standard
controller is proposed to increase the resilience toward la- j3016.
tency and adversarial attacks. Preliminary experimental re- Lamport, L.; Shostak, R.; and Pease, M. 1982. The byzan-
sults also validate above findings by comparing control per- tine generals problem. ACM Transactions on Programming
formances in speed, spacing, and acceleration rate. Theoret- Languages and Systems (TOPLAS) 4(3):382–401.
ical properties in security and control as well as more exper- Li, T., and Lin, L. 2018. Byzantine-tolerant v2x communi-
imental results will be discussed in the full paper. cation system. In 2018 INFORMS Annual Meeting Phoenix.
Li, T.; Choi, M.; Guo, Y.; and Lin, L. 2018a. Opinion mining
Acknowledgments at scale: A case study of the first self-driving car fatality. In
The authors thank Jian Wang, Yuntao Guo, Chaojie Wang, 2018 IEEE International Conference on Big Data.
and Anye Zhou for insightful discussions and anonymous Li, T.; Kaewtip, K.; Feng, J.; and Lin, L. 2018b. IVAS: Facil-
reviewers for their helpful comments. itating safe and comfortable driving with intelligent vehicle
audio systems. In 2018 IEEE International Conference on
References Big Data.
Angraal, S.; Krumholz, H. M.; and Schulz, W. L. 2017. Li, T. 2018. Modeling uncertainty in vehicle trajectory pre-
Blockchain technology: applications in health care. Circula- diction in a mixed connected and autonomous vehicle envi-
tion: Cardiovascular Quality and Outcomes 10(9):e003800. ronment using deep learning and kernel density estimation.
Boyle, E.; Gilboa, N.; and Ishai, Y. 2015. Function se- In the Fourth Annual Symposium on Transportation Infor-
cret sharing. In Annual International Conference on the matics.
Theory and Applications of Cryptographic Techniques, 337– Lin, L., and Li, W. 2018. A compressive sensing ap-
367. Springer. proach for connected vehicle data capture and recovery
and its impact on travel time estimation. arXiv preprint Tapscott, D., and Tapscott, A. 2016. The impact of the
arXiv:1806.10046. blockchain goes beyond financial services. Harvard Busi-
Lin, L.; Wang, Q.; Huang, S.; and Sadek, A. W. 2014. On- ness Review 10.
line prediction of border crossing traffic using an enhanced
spinning network method. Transportation Research Part C: Wang, X. S.; Huang, Y.; Chan, T. H.; Shelat, A.; and Shi,
Emerging Technologies 43:158–173. E. 2014. Scoram: oblivious ram for secure computation.
In Proceedings of the 2014 ACM SIGSAC Conference on
Lin, L.; Wang, Q.; and Sadek, A. W. 2015. A novel variable Computer and Communications Security, 191–202. ACM.
selection method based on frequent pattern tree for real-time
traffic accident risk prediction. Transportation Research Wang, C.; Gong, S.; Zhou, A.; Li, T.; and Peeta, S.
Part C: Emerging Technologies 55:444–459. 2019a. Cooperative adaptive cruise control for connected
Lin, L.; Wang, Q.; and Sadek, A. W. 2016. A combined autonomous vehicles by factoring communication-related
m5p tree and hazard-based duration model for predicting ur- constraints. In the 23rd International Symposium on Trans-
ban freeway traffic accident durations. Accident Analysis & portation and Traffic Theory.
Prevention 91:114–126.
Lin, L. 2018. Efficient collection of connected vehi- Wang, J.; Peeta, S.; Lu, L.; and Li, T. 2019b. Multi-
cle data based on compressive sensing. arXiv preprint class information flow propagation control under vehicle-to-
arXiv:1806.02388. vehicle communication environments. Transportation Re-
Lu, S., and Ostrovsky, R. 2013. Distributed oblivious ram search Part B: Methodological.
for secure two-party computation. In Theory of Cryptogra-
Wang, X.; Chan, H.; and Shi, E. 2015. Circuit oram: On
phy. Springer. 377–396.
tightness of the goldreich-ostrovsky lower bound. In Pro-
Parakh, A., and Kak, S. 2011. Space efficient secret sharing ceedings of the 22nd ACM SIGSAC Conference on Com-
for implicit data security. Information Sciences 181(2):335– puter and Communications Security, 850–861. ACM.
341. Yao, A. C. 1982. Protocols for secure computations. In
Qu, F.; Wu, Z.; Wang, F.-Y.; and Cho, W. 2015. A security Foundations of Computer Science, 1982. SFCS’08. 23rd An-
and privacy review of vanets. IEEE Transactions on Intelli- nual Symposium on, 160–164. IEEE.
gent Transportation Systems 16(6):2985–2996.
Seetharaman, G.; Lakhotia, A.; and Blasch, E. P. 2006. Un- Yao, A. C.-C. 1986. How to generate and exchange se-
manned vehicles come of age: The darpa grand challenge. crets. In Foundations of Computer Science, 1986., 27th An-
Computer 39(12). nual Symposium on, 162–167. IEEE.
Shamir, A. 1979. How to share a secret. Communications Zahur, S.; Wang, X.; Raykova, M.; Gascón, A.; Doerner, J.;
of the ACM 22(11):612–613. Evans, D.; and Katz, J. 2016. Revisiting square-root oram:
Shladover, S. E. 2018. Connected and automated vehicle efficient random access in multi-party computation. In Secu-
systems: Introduction and overview. Journal of Intelligent rity and Privacy (SP), 2016 IEEE Symposium on, 218–234.
Transportation Systems 22(3):190–200. IEEE.