Applying Multiparty Computation to Car Access Provision · Sharing economy is a cutting-edge concept used by many successful companies such as Airbnb and Uber. These companies allow

Applying Multiparty Computation to CarAccess Provision

Siemen Dhooghe

Thesis voorgedragen tot het behalenvan de graad van Master of Science

in de ingenieurswetenschappen:wiskundige ingenieurstechnieken

Promotor:Prof. dr. ir. Bart Preneel

Assessor:Prof. dr. ir. Vincent Rijmen

Prof. dr. Raf Vandebril

Begeleider:Iraklis Symeonidis

Dr. Abdelrahaman AlyDr. Mustafa A. Mustafa

Academiejaar 2017 – 2018

© Copyright KU Leuven

Without written permission of the thesis supervisor and the author it is forbiddento reproduce or adapt in any form or by any means any part of this publication.Requests for obtaining the right to reproduce or utilize parts of this publicationshould be addressed to the Departement Computerwetenschappen, Celestijnenlaan200A bus 2402, B-3001 Heverlee, +32-16-327700 or by email [email protected].

A written permission of the thesis supervisor is also required to use the meth-ods, products, schematics and programs described in this work for industrial orcommercial use, and for submitting this publication in scientific contests.

Zonder voorafgaande schriftelijke toestemming van zowel de promotor als de auteuris overnemen, kopiëren, gebruiken of realiseren van deze uitgave of gedeelten ervanverboden. Voor aanvragen tot of informatie i.v.m. het overnemen en/of gebruiken/of realisatie van gedeelten uit deze publicatie, wend u tot het DepartementComputerwetenschappen, Celestijnenlaan 200A bus 2402, B-3001 Heverlee, +32-16-327700 of via e-mail [email protected].

Voorafgaande schriftelijke toestemming van de promotor is eveneens vereist voorhet aanwenden van de in deze masterproef beschreven (originele) methoden, pro-ducten, schakelingen en programma’s voor industrieel of commercieel nut en voorde inzending van deze publicatie ter deelname aan wetenschappelijke prijzen ofwedstrijden.

Contents

Acknowledgements ii

Abstract iii

List of Figures iv

List of Tables v

1 Introduction 1

2 Literature Review 32.1 Car Sharing Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.2 Multiparty Computation (MPC) . . . . . . . . . . . . . . . . . . . . . . 62.3 MPC Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3 SePCAR in Practice 253.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.2 SePCAR in Detail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263.3 Evaluation of SePCAR . . . . . . . . . . . . . . . . . . . . . . . . . . . 303.4 Evaluation of the MPC Protocol . . . . . . . . . . . . . . . . . . . . . . 343.5 Performance Tweaks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433.6 Complexity and Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . 453.7 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

4 Optimised MPC Operations 494.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494.2 Improved S-Box Calls over MPC . . . . . . . . . . . . . . . . . . . . . 494.3 Improved Multiplication over MPC . . . . . . . . . . . . . . . . . . . 554.4 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

5 Conclusions and Future Work 615.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 615.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

Bibliography 65

Appendix 71Breaking Privacy while Retaining Correctness . . . . . . . . . . . . . . . . . 71Paper: SePCAR: A Secure and Privacy-enhancing Protocol for Car Access

Provision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76Poster . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

i

Acknowledgements

First of all, I want to thank my supervisors Abdelrahaman Aly, Mustafa A. Mustafaand Iraklis Symeonidis and promotor Bart Preneel for their continuous support andthe opportunity to pursue my interests in the domain of cryptography. Thank youto my assessors Vincent Rijmen and Raf Vandebril for the time to read my thesis.Thank you to Milan who supported me in everything software related and for beinga best friend for all these years. Thank you to Gabriele who helped me understandthe wonder world of hardware. I want to thank everyone in COSIC for creatingsuch a nice environment where I was able to work on the thesis. Finally, I want tothank my parents who gave me the freedom to pursue my own dreams and whoshowed me the beauty of science and mathematics.

ii

Abstract

Car sharing systems such as car2go or Zipcar are becoming more and more popular.Physical key-less car sharing systems allow users to share their cars convenientlywithout the need of physical keys. Such systems introduce several security andprivacy challenges and a solution is currently missing by the state-of-the-art litera-ture. The protocol proposed by Symeonidis et al. [1] provides a protocol designedto protect the system’s security and the users’ privacy for car access provision. Assuch a protocol needs strong security and privacy properties, it relies on multipartycomputation techniques to ensure the privacy of the data given by the differententities in the protocol and a forensics system to retrace this data when an incidentoccurs.

Several contributions to the work proposed by Symeonidis et al. [1] are madeduring this work. To support the decentralised architecture, a suitable candidate forthe multiparty protocol is selected by a comparison of the studied protocols withrespect to their performance and their characteristics, e.g., threshold secret sharing,Boolean circuits. Moreover, a proof of concept of the car access provision protocolis implemented. The proof of concept achieves to deliver an access token in 1.55seconds which proves the practicality of the protocol. Several tweaks are made tothe protocol to enhance the operational speed and improve the communication costof the multiparty computation part of the protocol. To this end, different operationsusing multiparty computation are researched, implemented and improved. Morespecifically, novel techniques are proposed for the S-Box call and the multiplicationover Boolean circuits.

iii

List of Figures

2.1 System model of a physical keyless car sharing system [1]. . . . . . . . . 42.2 Garbled AND gate. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.1 First step of the SePCAR protocol. . . . . . . . . . . . . . . . . . . . . . . 283.2 Second step of the SePCAR protocol. . . . . . . . . . . . . . . . . . . . . . 293.3 Third step of the SePCAR protocol. . . . . . . . . . . . . . . . . . . . . . . 293.4 Fourth step of the SePCAR protocol. . . . . . . . . . . . . . . . . . . . . . 303.5 A simulation of network latency. . . . . . . . . . . . . . . . . . . . . . . . 313.6 Circuits to compute a secure equality test over MPC. . . . . . . . . . . . . 40

4.1 Second method to create a masked S-Box. . . . . . . . . . . . . . . . . . . 54

5.1 An improved implementation. . . . . . . . . . . . . . . . . . . . . . . . . 62

iv

List of Tables

2.1 1-out-of-4 oblivious transfer. . . . . . . . . . . . . . . . . . . . . . . . . . . 112.2 Encryption table of a garbled AND gate. . . . . . . . . . . . . . . . . . . . 152.3 Encryption table of a garbled AND gate with signal bits. . . . . . . . . . 16

3.1 The different entities in SePCAR. . . . . . . . . . . . . . . . . . . . . . . . 253.2 Notations used in SePCAR. . . . . . . . . . . . . . . . . . . . . . . . . . . 263.3 Classification of two-party MPC protocols . . . . . . . . . . . . . . . . . . 353.4 Classification of three-party MPC protocols . . . . . . . . . . . . . . . . . 363.5 Classification of MPC protocols . . . . . . . . . . . . . . . . . . . . . . . . 363.6 A comparison between MPC protocols for SePCAR. . . . . . . . . . . . . 373.7 A comparison on invertion methods. . . . . . . . . . . . . . . . . . . . . . 413.8 A comparison with Araki et al.’s implementation. . . . . . . . . . . . . . 433.9 Efficiency of the simulation with multiple parallel AES calls. . . . . . . . 433.10 Efficiency of SePCAR when hashing the consumer’s certificate. . . . . . 433.11 Performance of SePCAR. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463.12 Performance of MPC operations. . . . . . . . . . . . . . . . . . . . . . . . 47

4.1 Novel invertion methods. . . . . . . . . . . . . . . . . . . . . . . . . . . . 494.2 S-Box lookup table. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514.3 Masked S-Box lookup table. . . . . . . . . . . . . . . . . . . . . . . . . . . 534.4 First method to create a masked S-Box lookup table. . . . . . . . . . . . . 534.5 A comparison on multiplication methods. . . . . . . . . . . . . . . . . . . 554.6 Multiplication lookup table. . . . . . . . . . . . . . . . . . . . . . . . . . . 564.7 Masked multiplication lookup table. . . . . . . . . . . . . . . . . . . . . . 564.8 A method to create a masked multiplication lookup table. . . . . . . . . . 56

v

Chapter 1

Introduction

The success of Uber, Airbnb andTaskRabbit isn’t a fad - it’s a newway of doing business.

PwC

Sharing economy is a cutting-edge concept used by many successful companiessuch as Airbnb and Uber. These companies allow users to share their properties, tocreate an online marketplace for freelance labor or to let users share their cars withother people. These car sharing systems are becoming more popular, its users havegrown in number over the past years [2] [3] [4] [5]. They can positively affect theenvironment as the use of car sharing effectively reduces the number of cars in theworld [6]. To encourage users to embrace the concept, such systems should allowusers to share their cars via the use of a mobile application, without the need of aphysical key exchange. However, to gain users’ confidence, security of such keylesscar sharing systems is essential. Also users’ privacy is important as private data mayalways be misused by the system or any other party. An example of such misuseis the case of Uber using a tool called “Hell” to spy on rival company drivers [7].Uber’s mobile app also violates the privacy of their own users as it always trackstheir location [8]. In addition, protecting users’ location by default will also berequired by the new European data protection regulation [9] as the location data ofthe car may involve sensitive information, e.g., identifying users who use cars fordisabled passengers.

There are already car sharing applications for cars that belong to a certaincompany, for example car2go, Zipcar, Getaround, DriveNow, Enterprise CarShareor Cambio CarSharing. However, car sharing applications that allow users to builda community where everyone can rent their own car are rare, let alone applicationsthat are both secure and privacy friendly. To fill this gap Symeonidis et al. [1]proposed a car sharing protocol that guarantees security of the car key, privacy ofthe person booking the car, protection against a user’s denial of ever accessing thecar and, in case of a car incident, the protocol provides forensic evidence to revealthe identity of the owner, consumer and car involved. Additionally, the protocol has

1

1. INTRODUCTION

been designed to support an access procision while the car is not able to connectto a network. It also allows for car key revocation, for example in the case theuser’s personal device is stolen. It achieves this by making use of state-of-the-artcryptographic methods. One of these methods is multiparty computation, whichallows different parties to work together and compute the result of a function whilekeeping their respective inputs private.

While Symeonidis et al. [1] propose a car sharing protocol with strong securityand privacy properties, the authors provide only a rough estimation of the feasibilityof the system. This work completes their car sharing protocol by tweaking it toimprove its performance and to make its multiparty computation part feasible. Italso provides a proof of concept of the car sharing protocol with an approximationof its run-time showing that the protocol is practically applicable. We also proposenovel methods to perform certain operations using multiparty computation whichimprove the current state-of-the-art. Our work has led to a paper submission toESORICS 2017 [1].

The remainder of this thesis is organised as follows. Chapter 2 consists of abackground on multiparty computation along with a description of the car sharingprotocol proposed by Symeonidis et al. [1]. Chapter 3 describes the implemen-tation of the car sharing protocol and the multiparty computation protocol, thelink between both protocols, the different operations in the multiparty computa-tion setting and the different tweaks that were made to car sharing protocol. Thischapter concludes with a discussion over the complexity and efficiency of the carsharing protocol. Chapter 4 discusses novel methods to calculate S-Box calls andmultiplications over multiparty computation using Boolean circuits. These methodsare discussed in detail as they are useful to make multiparty computation feasible.Finally, Chapter 5 concludes the thesis and gives directions for further research infast performing multiparty computation.

2

Chapter 2

Literature Review

2.1 Car Sharing Protocols

This section reviews the existing work on car sharing systems and describes the carsharing protocol proposed by Symeonidis et al. [1] in more detail.

2.1.1 Existing Work

This subsection reviews the existing work on car sharing systems. Troncoso et al. [10]has designed a protocol which uses location data to calculate fees which the driverneeds to pay where privacy is kept in mind. Balasch et al. [11] proposes a similar sys-tem which calculates an annual toll. Floriat et al. [12] proposes a privacy-preservingspot checking for observation in public spaces and Mustafa et al. [13] proposes ananonymous electric vehicle charging protocol.

Not many systems exist that allow users to, both securely and privately, sharetheir car by using their mobile device. Dmitrienko and Plappert [5] propose a sys-tem which offers security via second factor authentication, e.g., a smartwatch ora smartcard. However, their protocol does not consider the user’s privacy. Syme-onidis et al. [1] proposes a system, SePCAR, that fulfils the privacy requirements.The difference between the two protocols lies in the creation of the access token.Dmitrienko and Plappert’s protocol mainly consists of a secure way to open thecar where the user already has an access token. SePCAR consists of a secure andprivacy-friendly protocol to make the booking and give the resulting access tokento the person who is booking the car. As the SePCAR protocol satisfies the desiredsecurity and privacy properties of a car sharing system it is chosen as the protocolwhich is analysed further in the work.

2.1.2 SePCAR

In this subsection the system model, the security and privacy requirements and ahigh level description of the SePCAR protocol is explained.

3

2. LITERATURE REVIEW

Information flow

Authorities

OBU

Owner PDs

Consumer PDs

DatabasePersonal DeviceKey-less Sharing Management SystemOn-Board Unit

DBPDKSMSOBUPublic Ledger

KSMS

Car ManufacturerDB

Figure 2.1: System model of a physical keyless car sharing system [1].

System Model

The system model, as shown in Figure 2.1, consists of a few entities such as “Owners”which are users who own a car and are willing to share this car and “Consumers”which are users in need of a car. Users use an application on a Portable Device (PD) tocommunicate with each other and the Keyless Sharing Management System (KSMS).The KSMS consists of independent parties which, via multiparty computation, areable to create an access token to the car such that the car key and the bookingdetails are kept secret from them. The KSMS communicates regularly with the CarManufacturer (CM), which has a database with the different car keys. Using theinformation provided by the owner and the car manufacturer, the KSMS is able topost a temporary access token on a Public Ledger (PL), which enables the consumerto privately access this token. The consumer communicates with the car’s On-BoardUnit (OBU), an embedded component of the car, using Bluetooth or NFC. Via achallenge-response protocol the consumer can have access to the car. In case anincident occurs, the authorities can break the consumer’s privacy by forcing thedifferent parties in the KSMS to work together.

For the threat model we assume the KSMS, the CM and the PL to be honest butcurious. Meaning that they follow the protocol and do not maliciously alter theprotocol but are interested in extracting private information about users. The OBU isseen as trusted and secure, however the user’s portable devices are seen as insecureand untrusted.

Security and Privacy Properties

SePCAR aims to satisfy the following security properties [1].

• Confidentiality of the booking details: only the owner and the consumer knowthe contents of the booking details.

• Authenticity of the booking details: the car checks the integrity and origin ofthe booking details. It makes sure the booking details are agreed upon by the

4

2.1. Car Sharing Protocols

owner.

• Confidentiality of the access token: only the shared car and the consumerknow the contents of the access token.

• Confidentiality of the car key: only the shared car and the car manufacturerknow the car key.

• Backward and forward secrecy of the access token: comprise of a key used toencrypt any access token should not compromise other access tokens (futureor past) published on the PL of any honest consumer.

• Non repudiation of the origin of the access token: the owner is able to proveto the consumer and the shared car that the access token delivered to the carwas originated by the owner.

• Non repudiation of delivery of the access token: the consumer is able to proveto the owner that the agreed access token was delivered to the shared car.

Apart from security properties SePCAR also aims to satisfy the following privacyproperties [1].

• Unlinkability of the consumer and the shared car: no one but the shared car,the consumer and the owner should be able to link two booking requests ofthe same consumer and the car.

• Anonymity of the consumer and the car: no one but the shared car, theconsumer and the owner should learn the identity of the consumer and thecar.

• Undetectability of the access token operations: no one but the shared car, theowner and if necessary the consumer should be able to distinguish betweenaccess token generation, update and revocation.

• Forensic evidence provision: the car sharing system should be able to provideauthorities with forensic evidence for an access provision to a car in case of anincident. This can be done without violating other users’ privacy.

SePCAR also works in case the shared car is offline, meaning the car has limited orno network connection.

High Level Description

The car sharing protocol described by Symeonidis et al. [1] starts by the owner andthe consumer who agree on the booking details. These booking details consist of theidentity of the owner, the consumer and the car and the information on when andwhere the car can be used. The booking details are sent to the KSMS that encryptthem and create an access token for the consumer to access the car. The wholeprocess is done in such a way that the privacy of the consumer is protected. If an

5


incident happens this privacy may be lifted and the information revealed can beused by authorities. This last property is called the forensics property and is ensuredby using MPC with threshold security. The lifting of the privacy is done by makingthe independent parties in the MPC protocol work together to release the data, asexplained later in Section 2.2. MPC is also used to guarantee data confidentiality ofthe car key and the booking details. To ensure this, SePCAR makes use of two MPCphases, a car key retrieval phase and an access token generation phase. We givean in depth view, explaining the different steps in the SePCAR protocol in Section 3.2.

Car Key Retrieval Phase: The KSMS servers, using the information sent by theowner of the car, extract the correct car key shares to create the access token for thecar. Every server extracts all car identity and key shares related to the owner fromits database. To retrieve the correct car key shares, the servers perform a securecomparison between the car ID shares from their database and the car ID shares inthe booking details given by the car owner. Using the results of the comparisons,the car key shares are constructed in a privacy friendly way.

Access Token Generation Phase: The consumer generates two symmetric secretkeys for the KSMS servers to encrypt the access token. As these keys are only knownto the consumer, only that user can use the access token for the car. Via the shares ofthe previously extracted car key and the shares of the booking details, the serversgenerate shares of an encryption and a MAC of these booking details using theshares of the car key and the symmetric keys of the consumer. This is done via amultiparty symmetric encryption protocol. These shares are then sent to the PLwhich the consumer can access in a privacy friendly way.

2.2 Multiparty Computation (MPC)

Secure multiparty computation has the goal to compute the outcome of a functionwhere the inputs are given by multiple parties while keeping those inputs privatefrom the other parties. Multiparty computation is often applied if a trusted thirdparty cannot be found and the user’s input needs to be kept private. An examplewhere MPC is used in practice, which is found in the book "Secure MultipartyComputation and Secret Sharing" [14], is on contracts of sugar beets in Denmark.The farmers are given contracts to produce a certain amount of beets each year.These contracts may be traded between farmers, which is frequently done since thesupport for sugar beet production drastically decreased over the last years. Thetrading of these contracts is done via a double auction. This means the buyers andsellers of these contracts simultaneously submit the price on which they want tobuy or sell beets. An independent auctioneer then selects a market-clearing pricefor the beets. However, the farmers and the buyers of the sugar beets do not wish toreveal their buying or selling price since this would reveal their economic position.A natural solution to this is to choose a trusted third party which checks all buyingand selling prices and would not reveal any private information. There are two

6

2.2. Multiparty Computation (MPC)

parties which are in a position to fulfil this role, namely Danisco or PKD, but theyare not accepted by the community. A solution was instead found in a three partycomputation between Danisco, PKD and the research project implementing theauction. The solution guaranties the privacy of the buyers and sellers and bothDanisco and PKD cooperate in the calculation of the market-clearing price, meaningthat neither of them have the full power to change this price to their advantage.

2.2.1 The Foundation of MPC

In practice only general MPC protocols are considered, meaning MPC protocols thatcalculate any polynomial time function. MPC protocols for a specific function alsoexist, for example, calculating the sum of all inputs [15]. However, general MPCprotocols are typically favored due to their high level of efficiency. If the functionis of polynomial time then this function can be written as a Boolean circuit or anarithmetic circuit (with a method to decompose numbers in bits). Thus, it is sufficientfor an MPC protocol to securely calculate an addition and a multiplication gate overFpq , with p prime. Optionally, to improve the performance, we can implement away to check an equality, an inequality or a more efficient way to exponentiate ashare with a constant. The protocols for each of these operations satisfy certainproperties that need to be upheld. To be more precise, given parties P1, ...,Pn thatwish to compute the result y of the function f(x1, ..., xn) = y, where Pi gives theinput xi, the following two definitions need to be fulfilled.

Definition 2.2.1. Privacy: Given the function f(x1, .., xn) = y, each party Pi mayonly learn xi and the output y.

Notice that it is possible that a party learns the other inputs from the output ofthe function even if the protocol fulfils the privacy condition. For example, whencalculating the bitwise AND function between two parties, if one party selects 1 asinput that party always learns the input of the other party.

Definition 2.2.2. Correctness: The output of the function is computed correctly.

This definition is dependent on the adversarial model. For example, achievingcorrectness in the presence of malicious adversaries is more difficult than in thepresence of semi-honest adversaries. We define these adversaries later on.

We distinguish two kinds of security: information theoretic security and com-putational security. The former means the adversary cannot break the security ofthe protocol given unlimited time and computational power, for example, Shamir’ssecret sharing which uses Lagrange interpolation to make shares [16]. The lat-ter means that using realistic computational power, the time needed to break theprotocol would be large, for example, brute force attacks on the key. Regardingadversaries, we define two types: semi-honest and malicious. The semi-honestadversary follows the protocol and tries to deduce secret information. It is alsopossible for semi-honest adversaries to collude with each other, bundling their infor-mation together to learn the inputs of the other parties. The malicious adversary

7


tries to find out the inputs of the honest parties by deviating from the protocol. Thismeans, for example, that the adversary gives the wrong output. These adversariesmay again collude with each other. The adversary may also give the wrong outputin order to affect the correctness of the protocol. Another type of adversary is thestatic adversary or the adaptive adversary. The static adversary can choose whichparties to corrupt before the computation has started and the adaptive adversary canchoose which parties to corrupt at any time during the protocol. The MPC protocolmay be resistant to multiple adversaries working together. We speak of “thresholdsecurity” when the protocol runs securely against a certain number of adversaries.As an example, the multiplication algorithm of the BGW protocol [17], in the case ofsemi-honest adversaries, is secure for a threshold t < n/2, where t is the number ofdishonest parties and n the total number of parties. For this case we have an honestmajority. In the case an MPC protocol is resistant up to n− 1 dishonest adversarieswe have security against a dishonest majority, for example, this is achieved by theSPDZ protocol [18].

MPC protocols implement a secure way of adding and multiplying shared inputs.However, it is also possible to implement a secure XOR and AND gate where theinputs are shared between parties. Thus, we need to distinguish MPC protocolson Boolean circuits and on arithmetic circuits. Note that a gate in an arithmeticcircuit is seen as unitary in delay and size independent of the bitsize of the input.Thus, the multiplication and addition gate are seen as the most elementary gatesin the circuit. The input for an arithmetic gate is an element of a finite field, in thecase this field is different from F2 arithmetic circuits cannot work with separate bits.Thus, operations such as a shift operation cannot be implemented without a wayto decompose a number into bits, however this protocol tends to cost a lot. At firstit may seem Boolean circuits are performing better than arithmetic circuits as theydo not need extra work to do bit decomposition. Arithmetic circuits however mayincrease performance, for example, summing two 1024 bit numbers requires oneround of communication in an arithmetic circuit working over F210 or 11 rounds overa Boolean circuit [19]. However, it is very expensive to compare bits over arithmeticcircuits while this is cheap over Boolean circuits. Depending on the function theparties compute either Boolean or arithmetic circuits are optimal.

Throughout this work, we denote a shared value by using square brackets, e.g.,[x], meaning the value x is divided in shares which are held by the different parties.We also use the notation [x]i, which denotes the share of the value x held by partyPi.

2.2.2 Complexity of MPC

In multiparty computation we have an arithmetic complexity similar to normalcircuits which is proportional to the number of gates in the circuit we are computing.However, the different parties are also exchanging data with each other and thiscommunication is typically very expensive. In most cases the time to compute gateslocally is insignificant in comparison with the time needed to exchange data. Thus,we focus mainly on communication complexity. This is calculated in the number of

8

2.3. MPC Protocols

communication rounds between the parties. As the multiplication gates, sharinga number and opening shares, require a communication round we need to countthe nonlinear gates in the circuit to get the communication complexity. However,note that we can calculate gates which are independent of each other in one round.This means that we need to look at the depth of the circuit where each layer ofthis circuit requires a communication round. As the most frequent nonlinear gateis the multiplication gate, we often also call this the multiplicative depth of thecircuit. An in-depth analysis on the complexity of MPC is found in the book ofCramer et al. [14].

Latency and Throughput

To measure the performance of MPC implementations we use the same quantitiesas in hardware, namely latency and throughput. Note that we assume the differentparties in the multiparty computational setting are working on general purposeCPU’s. We define latency as the time it takes to perform one operation. For example,we define the latency of an AES call as the time it takes all the parties to computethis single AES call. The throughput of an operation is measured as the number ofoperations that can be performed in one second. This has to do on how well wecan parallelise the operation. For example, the number of AES calls we can make inone second. As performance is important, the necessary balance needs to be foundbetween latency and throughput. Latency needs to be minimised when the networkdelay is high and throughput can be optimised if the network delay is low. It alsodepends on the application as throughput becomes important when we need tocalculate a function which needs to perform several parallel operations, for example,when calculating statistics on a large database.

2.3 MPC Protocols

In this section we review the different existing MPC protocols. These protocols havedifferent properties, which can affect the performance and security of the protocol.When choosing an optimal MPC protocol for the car access provision protocol weneed to have a good understanding of the different MPC protocols.

2.3.1 The GMW Protocol

The first proposed protocol for multiparty computation is from 1987 titled “How toplay any mental game” or “A completeness theorem for protocols with honest ma-jority” from Goldreich, Micali and Widgerson [20] which is commonly abbreviatedas GMW. The protocol covers security against both semi-honest as malicious adver-saries and in particular the protocol is secure against any number of adversaries.The protocol implements a secure way of computing the XOR and AND functionsbetween multiple parties by making use of “oblivious transfers”.

9


The Operations for Semi-Honest Adversaries

Similar to other MPC protocols, the GMW protocol scans in the MPC circuit gateby gate. Thus, in order to examine the GMW protocol it suffices to examine themethods to securely share the input, to securely publish the output and to securelycalculate XOR and AND between multiple parties. We only look at the opera-tions when dealing with semi-honest adversaries. When dealing with maliciousadversaries zero-knowledge proofs need to be added on the validity of the execution.

Input Sharing: First we take a look at securely sharing an input of a party.

• Party Pi randomly generates the bit rj ∈ F2 and sends this to Pj.

• Party Pi keeps the value ri = x+∑j6=i rj mod 2.

Now every party holds a share of the input x.

Secure XOR: Here we describe the protocol to XOR two shared values. In otherwords we wish to add the values a and b such that at the end of the protocol eachparty holds shares of a⊕ b and none of the parties get to know a or b. In the case ofthe GMW protocol, this is done locally by each party XORing their shares [a]i and[b]i.

• Party Pi XORs the shares [a]i and [b]i and saves it as [c]i.

It is evident to see that if all parties combine their shares [c]i they get a⊕ b. Becausethis protocol does not require any communication between parties the additionmodulo 2 is very cheap.

Secure AND: The protocol to securely calculate an AND gate between multipleparties requires communication between parties. For this calculation the protocolmakes use of an “oblivious transfer” (OT). An OT is a protocol by which a sendersends some information to the receiver without the sender knowing what the re-ceiver learned. To understand the protocol for the AND gate note the followingequality.

c ≡ a · b mod 2≡ ([a]1 + ... + [a]n) · ([b]1 + ... + [b]n) mod 2

≡∑i=1...n

aibi +∑

16i<j6n

aibj + ajbi mod 2(2.1)

Each party Pi needs to hold the share [c]i = [a]i[b]i +∑i<j6n[a]i[b]j + [a]j[b]i at

the end of the protocol. Each party Pi calculates [a]i[b]i locally, however to calculate[a]i[b]j and [a]j[b]i, the parties Pi and Pj need to run a specific protocol betweenthemselves. Intuitively, this is calculated by party Pj choosing a random bit si,j.At the end of the protocol, Pi outputs [a]i[b]j + [a]j[b]i + si,j and Pj outputs si,jsumming them both gives the desired value. Party Pj knows the values [a]j,[b]j and

10

2.3. MPC Protocols

Table 2.1: 1-out-of-4 oblivious transfer.

What Pi requests What Pj gives[a]i, [b]i [a]i[b]j + [a]j[b]i + si,j

0, 0 0 · [b]j + 0 · [a]j + si,j0, 1 0 · [b]j + 1 · [a]j + si,j1, 0 1 · [b]j + 0 · [a]j + si,j1, 1 1 · [b]j + 1 · [a]j + si,j

si,j. In total there are four possible combinations for the values of ai and bj, thusPj sets up a 1-out-of-4 OT where Pi chooses one of the four combinations linkedto their values ai,bi. Pi receives [a]i[b]j + [a]j[b]i + si,j, where Pj does not knowwhich of the four combinations Pi has chosen. Pi outputs the result of this OT andPj outputs si,j, the sum of these values results in the required [a]i[b]j + [a]j[b]i. TheOT is depicted in Table 2.1. To make the operations secure, the protocol makes useof public key cryptography. This makes the OT a costly operation, though there areways of making it to perform better. Formally, the detailed description of an ANDgate can be demonstrated as follows.

• For each other party Pj.

– Party Pj chooses a random bit si,j.

– Parties Pi and Pj set up a 1-out-of-4 OT such that party Pi receives[a]i[b]j + [a]j[b]i + si,j.

– Party Pj sends si,j to Pi and Pi sends [a]i[b]j + [a]j[b]i + si,j to Pj.

• Party Pi locally ANDs their shares [a]i and [b]i.

• Party Pi adds [a]i[b]i with [a]i[b]j + [a]j[b]i for i < j <6 n saving this as [c]i.

The calculation of an AND gate requires communication between parties Pi andPj for every i, j. More specifically, each two different parties need to run a 1-out-of-4 OT, which means the protocol needs to perform n(n−1)

2 OT’s. This may beexpensive as this is usually done with the use of public key cryptography. However,there exist optimisations that implement OT’s by symmetric key encryption [21].Such a 1-out-of-4 OT can be made via two 1-out-of-2 OT’s. Thus, it is sufficient toimplement a 1-out-of-2 OT.

Secure Output Opening: Finally we need a protocol to open the output of thefunction to a specific party Pi. This is simply done by each party Pj sending theirshare to Pi.

• Each other party Pj sends their share [c]j to Pi.

11


• Party Pi adds all the shares [c]j for j = 1...n to obtain c.

Recall that for this protocol the adversaries are semi-honest meaning they do not givewrong shares. In case of malicious adversaries the shares need to be authenticatedand its integrity needs to be checked which is not discussed in this work.

Complexity

It is evident that the complexity of the GMW protocol is dependent on the numberof AND gates in the Boolean circuit. Thus, the number of rounds is proportionalto O(|C|) with |C| the multiplicative depth of the circuit. In each round the protocolneeds to run an OT between every pair of parties. That means the number of timesthe two parties need to communicate with each other is proportional to O(|C|n2)with n the number of parties. This complexity is also equal to the number of OT’sthat need to run during the whole computation.

2.3.2 Possible extensions

The bottleneck of the GMW protocol lies with the OT’s that need to be calculatedbetween each party when computing an AND gate. As an OT needs public keycryptography and communication between parties the operation is rather slow.Nevertheless, there are ways of making the OT faster by implementing more efficientOT’s. We give two examples.

• Firstly there are “pre-computed OT’s”, this involves sharing randomness atthe setup of the protocol to then use this randomness to perform a transfer viaa one-time pad [22]. The sharing of these random bits may be done via a 1-out-of-4 OT or via multiplication triples where the latter has better communicationefficiency [23].

• Secondly there are “OT extensions”, meaning that few expensive OT’s need torun, in order to generate multiple cheaper OT’s. While it has been proven thatOT’s cannot be computed via hash functions [24], it is still possible to use afew OT’s using public key encryption to compute more OT’s using symmetriccryptography which is cheaper. The article “More Efficient Oblivious Transferand Extensions for Faster Secure Computation” [21] explains the possibility ofextending several base OT’s by the use of hash functions.

2.3.3 The BGW Protocol

The BGW protocol is a well known MPC protocol which works on arithmetic circuits.It is named after Ben-Or, Goldwasser and Widgerson who presented it in 1988 [17].The protocol achieves perfect security, meaning that the protocol remains secureagainst adversaries that have unlimited computational resources. A similar perfectlysecure multiparty protocol was proposed at the same year, the CCD protocol [25],though we only explain the BGW protocol. Unlike the GMW protocol, the BGWprotocol is not resistant against any number of malicious parties. Instead, it offers

12

2.3. MPC Protocols

threshold security. In particular the BGW protocol is secure if there are n/2 or lesssemi-honest adversaries or n/3 or less malicious adversaries. Notice that becausethe BGW protocol has threshold security it cannot work with only 2 parties. Finallythe protocol assume private channels to be available between parties. These privatechannels can be set up via encryption, though this removes the security againstinfinitely powerful adversaries.


Just like the GMW protocol, we explain BGW by describing a secure way to share,publish, multiply by a constant, and add and multiply shares. We only describe theprotocol in the case of semi-honest adversaries. In the case of malicious adversariesa verifiable secret sharing protocol is used instead.

Secure Input Sharing: Securely sharing the input of each party can be achievedusing Shamir’s secret sharing scheme. Shamir’s secret sharing shares points on apolynomial where the constant term is the secret. To recover the secret it is neces-sary to interpolate using Langrange functions at t points, where t is the degree ofthe polynomial. More information on Shamir’s secret sharing can be found in thebook of Cramer et al. [14]. This secret sharing method has the property that for apolynomial of degree t, no t shares give information on the secret. Only when aparty has t+ 1 or more shares he can reconstruct the secret which gives a protocolwith perfect secrecy. The sharing method goes as follows.

• Choose a threshold t where t < n/2.

• Party Pi randomly generates t coefficients in Fpk to construct a polynomial ofdegree t.

• Party Pi samples n points on the polynomial, keeps one and sends the rest tothe other parties.

When t+ 1 parties work together they can open the secret of party Pi. The conditiont < n/2 is necessary for computing a secure multiplication. We again denote sharesby square brackets [a]i, where the index denotes which party holds the share.

Secure Addition: The addition is done locally where each party simply adds theirown shares.

• Party Pi adds their shares [a]i and [b]i and saves it as [c]i.

Notice that the following equality holds: c =∑nk=0[c]k =

∑nk=0[a]k +

∑nk=0[b]k =

a+ b.

Secure Multiplication: Securely evaluating a multiplication gate between mul-tiple parties requires communication between parties. Each party simply multipliestheir own shares, this results in shares for a polynomial with constant term a · b.

13


However, the degree of the polynomial is 2t and in addition the polynomial is notrandom as it is the product of two other polynomials. Instead the protocol needsto run an interactive protocol to calculate the multiplication. Each party sharestheir [a]i · [b]i share via a new polynomial gi of degree t, thus gi(0) = [a]i · [b]i.Interpolation is done using the points gi(0), thus this results in g(x) =

∑ni=1 rigi(x),

where g has the property g(0) = a · b. Notice that because each gi is of degree t,g is also of degree t. This is the polynomial the protocol needed to make, thus theprotocol needs a way for each party Pi to get a share of g. The protocol looks asfollows.

• Party Pi generates a random polynomial gi of degree t with gi(0) = [a]i · [b]i.

• For each other party Pj.

– Party Pi sends gi(j) to Pj.

– Party Pj holds n shares and computes the interpolation g(j) =∑ni=1 ri ·

gi(j).

Notice that the protocol to multiply shares is essentially reducing the degree of theresulting polynomial from 2t back to t. In order for this protocol to work it needs2t < n otherwise the parties are not able to interpolate the polynomial of degree 2tsince there wont be enough shares.

Secure Output Publishing: In order to publish results each party simply sendstheir share to every other party.

• Party Pi sends their share [a]i to each other party Pj.

• Party Pi interpolates their shares.

Note that publishing results needs the computational cost for every party to interpo-late the shares.

Complexity

Just like the GMW protocol, secure multiplications require a lot of communica-tion between parties. In terms of communication the protocol has a complexityof O(n2|C|), where |C| is the depth of the circuit counted only in multiplicationgates and n is the number of parties. The computational complexity of Lagrangeinterpolation for a certain point on the resulting polynomial costs O(t2) where twaschosen as the threshold value. Thus, the computational complexity is estimated asO(t2|C|), where the computational cost of generating random coefficients for eachpolynomial is neglected.

14

2.3. MPC Protocols

Table 2.2: Encryption table of a garbled AND gate.

a b c

k0a k0

b Ek0a(Ek0

b(k0c))

k0a k1

b Ek0a(Ek1

b(k0c))

k1a k0

b Ek1a(Ek0

b(k0c))

k1a k1

b Ek1a(Ek1

b(k1c))

Possible extensions

The BGW protocol is implementable to be secure against malicious parties by using averifiable secret sharing protocol. However, this makes each message length increaseby O(n) which decreases the performance of the overal computation. We also needa secure broadcasting channel for the protocol to be secure. The BGW protocol incase of malicious adversaries is only secure when t < n/3. More information on thisprotocol when dealing with malicious adversaries is found in the article of Asharovand Lindell [26].

2.3.4 Yao’s Protocol

The first protocol for secure two party computation was created by Andrew Yaoand solved what is called “The Millionaires Problem” [27] which was a problemproposed by Yao himself in 1982. The two important tools for the two party protocolare “garbled circuits” and “oblivious transfers”. While the method only worksfor two parties, there are extensions for the multiparty case creating the BMRprotocol [28]. Yao’s original solution to secure two party computation was given in1986 in the article “How to Generate and Exchange Secrets” [29]. Originally, Yao’sprotocol works on Boolean circuits and is secure against a semi-honest adversary,but there are extensions against malicious adversaries. The interesting part on Yao’sprotocol is that it works in a constant number of rounds, which means it may be fasteven when using bad networks.

Operations via Garbled Circuits

We start by explaining the definition of a garbled circuit. This is an encrypted binarycircuit with a pair of keys k0,k1 for every input wire, where given one key forevery input wire one can compute the key of the output of the gate and where it isimpossible to learn anything else besides that key. For example take an AND gatethat takes the wires a and b as input and gives c as output. Recall that each wirehas two keys, one for the value 0 and one for the value 1. The AND gate is depictedin Table 2.2.

15


Table 2.3: Encryption table of a garbled AND gate with signal bits σa = 1,σb =0,σc = 1.

(0, 0)→ Ek1a(Ek0

b(k0c||1))

(0, 1)→ Ek1a(Ek1

b(k1c||0))

(1, 0)→ Ek0a(Ek0

b(k0c||1))

(1, 1)→ Ek0a(Ek1

b(k0c||1))

AND

a

b

c

Signal bit: 𝜎𝑎

Signal bit: 𝜎𝑏

Signal bit: 𝜎𝑐

Keys: 𝑘𝑎0, 𝑘𝑎

1

Keys: 𝑘𝑏0, 𝑘𝑏

1

Keys: 𝑘𝑐0, 𝑘𝑐

1

Figure 2.2: Garbled AND gate.

For example for the keys k0a and k1

b, it is possible to recover the key k0c. However,

the person decrypting the output key knows that this output key corresponds to theinput (0, 1) because the second row in the table was decrypted. Thus, the protocolneeds to permute the order of this table such that the inputs to remain private.However, if a party has the necessary keys, the party needs to know which entry todecrypt. This is solved by assigning a “signal bit” (σi) for every wire in the binarycircuit. The protocol distinguishes three values in a wire, an external value, aninternal value and a signal bit where there is the equation: “internal value = exter-nal value ⊕ signal bit”. Both the internal value and the signal bit are secret for theevaluator, the external value is known to the evaluator. Instead of permuting thetable randomly it is ordered based on the external values, an example is shown inTable 2.3. Thus, the evaluator knows which entry to decrypt and the protocol onlyneeds to add one bit to each wire.

We have seen a way to encrypt logic tables and, more specifically, a way tosecurely evaluate a XOR and AND gate. To initiate the protocol the first party makesthe tables encoding each gate and initiates the circuit with its inputs. That partythen sends the garbled circuit and the garbled values corresponding to their inputsto the second party. However, the first party P1 still needs the garbled values fromthe second party P2 and P2 needs the keys for his input wires. For this operation tobe performed in a secure way without giving away private information to any of the

16

2.3. MPC Protocols

two parties oblivious transfers (OT) are needed. An OT needs to be made for everyinput wire for P2. Thus, P2 is the receiver in the OT and chooses their input bit, thesender P1 sends the keys corresponding to that wire. Thus, P2 learns the neededkeys and P2’s own input remains private to P1. Note that these OT’s can be run inparallel. Party P2 securely evaluates the circuit and sends the result to party P2.

Complexity

As mentioned before, the interesting part of this protocol is that the number ofrounds is constant. Depending on which variant of an OT protocol is used and if P1needs to learn to output or not, the protocol requires between two to four rounds ofcommunication. The number of OT’s that need to be performed is the number ofinputs of the second party. The protocol also needs to perform eight encryptions forevery gate and to evaluate a gate the protocol needs to compute two decryptions.There is a lot of research in improving the performance of this protocol, for example,the number of encryptions that are needed [30]. In the protocol’s original form,transferring the complete garbled Boolean circuit to compute AES costs 528kB.

Possible extensions

The first possible extension is to secure the protocol against a malicious adversary.Considering a malicious second party an OT can be used which is secure againstmalicious parties. However, we cannot do much when the first party is malicioussince this party can make a circuit that detects if the first bit of P2 is zero or not. It isalso possible to extend Yao’s protocol to the multiparty case. This was proposed byBeaver, Micali and Rogaway and the protocol is known as the BMR protocol [28]. Itruns in a constant number of communication rounds. FairplayMP is an implementa-tion of this protocol which can be freely used [31]. As mentioned before, there are alot of possible improvements on the performance. One of these is called “half gates”and is proposed by Zahur et al. [30]. This improvement calculates XOR gates forfree and requires four encryptions, two decryptions and 256 bits of communicationfor an AND gate. In a recent article it has been shown how to compute arithmeticgates more efficiently via a protocol similar to Yao’s protocol using gates with highfan-in [32].

2.3.5 The SPDZ Protocol

This subsection reviews the SPDZ protocol which is named after Nigel Smart, ValerioPastro, Ivan Damgård and Sarah Zakarias [18]. The protocol works on arithmeticcircuits and grants security against a dishonest majority, meaning that any numberof parties may be corrupted. An interesting note that needs to be made here is that,for a protocol secure against a dishonest majority, successful termination cannot beguaranteed since the protocol simply aborts when cheating is detected. The protocoldoes not check exactly which party has cheated. This can be done against a cost incomlplexity for the protocol. The adversaries can be semi-honest or, when using averifiable secret sharing protool, malicious. Unlike the BGW protocol, SPDZ can

17


only offer computational security. However, the protocol gives the possibility ofusing a large offline phase creating a faster online phase. Research has been done tomake the offline phase more efficient, for example, by using oblivious transfers [33].The protocol assumes private point-to-point channels, synchronous communicationand a trusted dealer for the offline phase.

The Operations for Malicious Adversaries

The original protocol introduced by Damgård et al. [18] assumes malicious adver-saries. Thus, we explain the operations for this adversarial model. Just like theexplanation with the other protocols, we explain all the operations. However, herewe also need to explain the preprocessing phase. The preprocessing phase shownhere is only statistically secure against semi-honest adversaries. However, thisstill allows the overall protocol to be secure against malicious adversaries. This isbecause the adversaries can only add a known error term to the future computationsmeaning that some secret shares later on will be incorrect. However, this can bechecked while verifying the MAC values since the online phase is secure againstadaptive adversaries. Throughout this chapter we use two different notations forshares.

First we represent a share along with their MAC values as

〈a〉 = (δ, (a1, ...,an), (γ(a)1, ...,γ(a)n)).

Where a =∑ni=1 ai and γ(a) =

∑ni=1 γ(a)i = α · (a+ δ). Thus, a party Pi holds ai,

γ(a)i and δ, which is public. These gamma values are shares of a MAC which iscalculating by multiplying the message and the secret key MACα(a) = α · a. Weuse this representation to perform computations, for example, for a,b private valuesand e public:

〈a〉+ 〈b〉 = 〈a+ b〉, e · 〈a〉 = 〈e · a〉 and e+ 〈a〉 = 〈e+ a〉.

Where the public modifier of e + 〈a〉 needs to be changed, meaning e + 〈a〉 =(δ− e, (a1 + e, ...,an), (γ(a)1, ...,γ(a)n)), using a public modifier δ allows us to addpublic values. Notice that for these operation the authentication shares do not needto be recomputed because the MAC is linear.

A second representation of a share uses an authentication with a private key

[[a]] = ((a1, ...,an), (βi,γ(a)i1, ...,γ(a)in)i=1,...,n).

Where a =∑ni=1 ai and

∑nj=1 γ(a)

ji = a ·βi. The parties Pi hold ai, γ(a)i1, ...,γ(a)in

and βi which is their secret key. This is used to share the secret key α which isused to authenticate every other share throughout the protocol. The idea is thateach party authenticates the secret value αwith their secret key, in order to checkthe authentication for the key βi the shares γ(α)ji from Pj for j = 1, ...,n need to becombined. In order to open this value with authentication, each party Pj sends αjand γ(α)ji to Pi then Pi checks

∑nj=1 γ(α)

ji = α ·βi.

18

2.3. MPC Protocols

Both representations are used to represent the random values r that are dis-tributed during the preprocessing phase. In order to be able to calculate multiplica-tions in a secure and efficient way the protocol makes use of multiplication triples.These are shared random numbers 〈a〉, 〈b〉, 〈c〉 that comply to the equality c = ab.These triples are generated in a secure way when dealing with malicious parties itcosts two triples to generate one secure triple.

Initialisation Phase: The protocol is initiated with all the parties sharing the secretvalue [[α]]. They generate random triples 〈a〉, 〈b〉, 〈c〉 which are random values thatare shared in two ways 〈r〉 and [[r]] and single random numbers [[e]], [[t]]. Generat-ing the secret key [[α]] and the random values, pairs, triples in a secure way is noteasy. In the SPDZ paper [18] this is done via somewhat homomorphic encryption.For example, for the generation of [[α]] each player generates their share of α andshares this via homomorphic encryption in order to not reveal this share to the otherparties. To use homomorphic encryption between parties, keys need to be generatedin a secure way as well. The details of the initialisation phase are found in theoriginal SPDZ paper [18], other ways of doing the preprocessing phase have beensuggested and are worth looking at as well. For example, the MASCOT protocolwhich uses OT’s instead of homomorphic encryption [33].

Secure Broadcasting: If party Pi wants to broadcast a value x then Pi sends thisvalue to each other party Pj. Then each party sends this value to each other party.If any of these values do not match the parties abort the protocol. Note that thistechnique has a quadratic complexity in function of the number of parties for com-munication. The protocol can also broadcast a batch of values, in this case each partyverifies the broadcasted values by combining them and sending the hash value ofthe combination to each other party. The protocol is again aborted if these hashvalues do not match.

Input Sharing: In order to share an input, a random value represented as a pair〈r〉 and [[r]] is used. The parties Pi open the value [[r]] checking with their ownprivate key if this value is correct, the other parties do not learn the value r. PartyPi broadcasts εi = xi − r. Each party computes εi + 〈r〉. Recall that ε is public thusthe addition is defined as changing the public modifier δ and one party adding thispublic constant to the share. This method does indeed create correct shares because〈r〉 is a correct sharing of r and εi is a public constant. In other words, εi + 〈r〉 is anew correct sharing for εi + r = xi − r+ r = xi.

Partial Opening: At the end of the protocol, it does a full opening where theresult is revealed and the MAC of the output is checked using the shared secret key.However, during the protocol partial openings can be done where just the valueinside the box is revealed and the MAC is not checked. If a malicious adversary haschanged some shared values this is discovered at the end of the protocol where thefull opening with MAC checking is executed. Thus, with a partial opening for 〈a〉,each party Pi sends the share ai to a certain party P1 which calculates the sum of

19


the shares to obtain a and then broadcasts this a.

Secure Addition: To compute a secure addition between parties, each party sim-ply adds their own shares. This follows from the way the shares are represented,meaning the equality 〈a〉+ 〈b〉 = 〈a+ b〉 holds. The addition does not require anycommunication or random numbers.

Secure Multiplication: In order to perform a more efficient multiplication, theprotocol needs multiplication triples invented by Beaver and is used in multiple pro-tocols [34]. Because the multiplication triple may be false, the parties need to checkthe validity meaning that the parties need to check that for (〈a〉, 〈b〉, 〈c〉), ab = c.They do this by sacrificing another triple. Thus, the parties take two available triples(〈a〉, 〈b〉, 〈c〉) and (〈f〉, 〈g〉, 〈h〉). The parties open a representation of a random value[[t]] meaning each party gets the value t and this value is checked by every party.The parties then do a partial opening of t · 〈a〉− 〈f〉 , ρ and 〈b〉− 〈g〉 , σ. Usingthese new values the parties partially open t · 〈c〉− 〈h〉− σ · 〈f〉− ρ · 〈g〉− ρ · σ. Theparties check if this results to zero. If it does not, the parties abort and need togenerate new triples otherwise, they can conclude that the triple (〈a〉, 〈b〉, 〈c〉) iscorrect. To see that this indeed proves the validity of the triple, plug in the valuesof σ and ρ in t · 〈c〉− 〈h〉− σ · 〈f〉− ρ · 〈g〉− ρ · σ and see that this only equals ifab = c. If ab 6= c the value of t is uniquely determined and thus the chance that anadversary gets away with changing this triple is 1/pk. The other triple is discarded,if the other was used another time the adversary would gain 1 bit of informationsince it reveals the XOR of the two random numbers. This verification can be donein the preprocessing phase and for all triples in parallel, meaning that the protocolonly needs to open one random value [[t]]. Having checked the multiplicationtriple (〈a〉, 〈b〉, 〈c〉), the protocol can use this triple for an efficient multiplication.The parties partially open 〈x〉− 〈a〉 , ε and 〈y〉− 〈b〉 , δ. Via these new publicvalues each party computes 〈z〉 , 〈c〉+ ε · 〈b〉+ δ · 〈a〉+ ε · δ. Notice that this oper-ation indeed gives valid shares of xy because xy = (a+ε)(b+ δ) = c+εb+ δa+εδ.

Secure Commitment: To securely publish a value the protocol needs a way tosecurely commit values, which can be done via a shared random value. Party Piopens a random value [[r]], Pi commits the value x by broadcasting c , x+ r. Tocheck and open the commitment the value [[r]] is opened since each party whichcan compute x = c− r. The integrity of the commitment can again be checked viathe MACs in [[r]].

Secure Output Publishing: This opening protocol reveals the value y in the box〈y〉 where the parties can check the integrity of the value by opening the sharedsecret value α. Let a1, ...,aT be values that have been publicly opened during theprotocol. In order to check their validity the protocol checks the validity of a randomlinear combination. This check has an error probability of T/p, where p is usuallylarge. If there are a lot of values that were publicly opened the protocol mightneed to do a batch check before the actual output of the protocol. Thus, the parties

20

2.3. MPC Protocols

open a random value [[e]] and the players set ej = ej for j = 1..T . The playersthen compute the linear combination a =

∑j ejaj. The parties Pi securely commits

γi ,∑j ejγ(aj)i along with their share of the output yi and the corresponding

MAC γ(y)i. Then [[α]] is opened for all parties. The commitments γi are openedto all parties, where each party checks if α(a+

∑j ejδj) =

∑i γi, where δj was the

public modifier of 〈aj〉 and where α is public. If this equality does not hold theparties abort. The commitments yi and γ(y)i are opened. Where the output of theprotocol is y =

∑i yi and each party checks if α(y+ δ) =

∑i γ(y)i if this check is

correct the protocol finishes and y is the correct output otherwise the party does notaccept the output.

Complexity

We only mention the communication complexity. For the SPDZ protocol eachmultiplication costs O(n) field elements, with n the number of parties. The additionprotocol requires no communication and input sharing requires opening a randomvalue thus O(n) communication calls and one broadcast. However, publishing anoutput requires O(n3) calls because The protocol makes O(n) commitments whereeach commitment has a complexity cost of O(n2). Thus, this protocol has an onlinecomplexity of O(n · |C|+n3). The communication cost of the online phase is linearin the multiplicative depth of the circuit, which is asymptotically faster than otherMPC protocols, e.g., the BGW protocol which has a quadratic cost. Thus, SPDZcan prove to be very efficient for large circuits. However, there is still the cubicexponent in the complexity which means that for small circuits the BGW protocolis more efficient. We should not forget that this protocol also has an offline phasewhich may be costly as well. Research has been done to improve this preprocessingphase [35] [36] [37] [38]. Recently a new protocol with the same adversarial model asSPDZ has been proposed. The protocol known as MASCOT has shown significantimprovements in terms of throughput and communication complexity [33] for theoffline phase.

2.3.6 Araki et al.’s Protocol

In the multiparty setting there is the subcategory of performing multiparty com-putation between three parties, these protocols typically have higher performancecompared to MPC protocols which are able to work with multiple parties. Recently anew protocol has been proposed by Araki et al. [39]. The protocol works on Booleancircuits given that the network between the three parties is fast, the protocol isable to achieve high throughputs [39]. The protocol is proven to be secure againstone semi-honest adversary, however another version of the protocol exists whichhandles the case of a malicious adversary [40].


The protocol is optimised to work for three parties. Just like the other multipartyprotocols we explain this protocol by explaining the input sharing, addition, mul-

21


tiplication and publishing protocol. Before we start, we assume that the partiesare able to generate random bits x1, x2, x3 with x1 ⊕ x2 ⊕ x3 = 0 and we call this arandom triple. This triple can be made in an information theoretic way which costsone bit of communication for each party or via a computational way which requiresk bits sent by each party, with k a security parameter. With these k bits the partiescan compute multiple triplets without the need of a communication round.

Secure Input Sharing: The protocol has the following two-out-of-three input shar-ing protocol.Given a random triple x1, x2, x3, sharing of the bit v is done by the following shares.

• Party P1 holds the share (x1,a1), where a1 = x3 ⊕ v.



It is clear that when two parties collude they reveal the secret bit v. However, a singledishonest party cannot reveal anything about v since it is secured in a one-time padway.

Secure XOR: Additions are done locally. Say (x1,a1), (x2,a2), (x3,a3) is a sharing ofv1 and (y1,b1), (y2,b2), (y3,b3) is a sharing of v2. Thus, to obtain a secret sharing ofv1 ⊕ v2 the parties locally add their shares (x1 ⊕ y1,a1 ⊕ b1), (x2 ⊕ y2,a2 ⊕ b2), (x3 ⊕y3,a3⊕ b3) , (z1, c1), (z2, c2), (z3, c3). This is indeed a valid sharing for the additionsince z1 ⊕ z2 ⊕ z3 = 0 and for every i ∈ {1, 2, 3} the equality ci = zi−1 ⊕ (v1 ⊕ v2)holds.

Secure AND: The calculation of an AND gate needs communication between par-ties. Let (x1,a1), (x2,a2), (x3,a3) be a sharing of v1 and (y1,b1), (y2,b2), (y3,b3) asharing of v2. Each party holds a share of a random triple (α1,α2,α3). The protocolworks in two steps.

• Step 1: Party Pi computes ri = xiyi ⊕ aibi ⊕αi and sends ri to Pi+1.

• Step 2: Party Pi stores (zi, ci), where zi = ri ⊕ ri−1 and ci = ri.

To show that this is indeed correct, notice that (r1, r2, r3) is a 3-out-of-3 sharingof v1v2 because r1 ⊕ r2 ⊕ r3 = v1v2 this is seen by plugging in ai = xi−1 ⊕ v1 andbi = yi−1 ⊕ v2. Keeping this in mind we see that (z1, c1), (z2, c2), (z3, c3) is a valid 2-out-of-3 sharing of v1v2. First of all z1⊕ z2⊕ z3 = (r1⊕ r3)⊕ (r2⊕ r1)⊕ (r3⊕ r2) = 0.Secondly observe that c1 ⊕ c2 ⊕ c3 = r1 ⊕ r2 ⊕ r3 = v1v2. If we combine two shareswe find out the secret v1v2, for example, c1 = r1 = v1v2 ⊕ r2 ⊕ r3 = v1v2 ⊕ z3. Thus,with party P3’s share we find v1v2 = c1 ⊕ z3, the same can be shown for the othershares.

Secure Output Publishing: Secure output publishing is done by each party sending

22

2.3. MPC Protocols

their share to the next party. The random triples can be made via the use of a pseudorandom function, the method just requires a short initial setup phase where everyparty sends k bits, with k a security parameter, to the next party.

Complexity

For each AND gate a party needs to send only one bit to one other party, making thisprotocol optimal for Boolean circuits. The complexity still depends on the multiplica-tive depth of the circuit which is equal to the number of rounds of communicationof the computation. The number of bits sent in one round is equal to the number ofAND gates in that layer of the circuit.

2.3.7 Bogdanov et al.’s Protocol

The protocol by Bogdanov et al. is a framework made to easily and efficientlydevelop MPC circuits [41]. It is mainly focused on three party computation, howeverit also allows to work with two parties or even more than three parties but these set-ups are much less efficient. Bogdanov et al.’s protocol works on arithmetic circuitson the field F232 . It uses additive sharing and has its own multiplication protocol,it also supports bit decomposition. The choice for working over the field F232 wasmade to counter overflow problems. For the three party case, the protocol is secureagainst one semi-honest adversary, where the security is information theoretic.The protocol assumes private communication channels that provide asynchronouscommunication.

The Operation for Semi-Honest Adversaries

Secure Input Sharing: This is done in the same way as GMW but instead over F232 .

• Party Pi randomly generates the bit ri,j ∈ F232 and sends this to Pj.

• Party Pi keeps the value ri,i = xi +∑j6=i ri,j mod 232.

Secure Addition: As usual secure addition over multiple parties is possible withoutcommunication where the parties simply add their shares locally.

Secure Multiplication: Getting a valid sharing of the multiplication of two pri-vate numbers requires communication. Note that for two shared private numbers[u], [v] the multiplication is written as follows:

uv ≡n∑i=1

ui

n∑i=1

vi ≡n∑i=1

uivi +

n∑j=1

∑i 6=j

uivj mod 232.

The parties calculate uivi locally, they need to communicate for the uivj termswhere i 6= j. Thus, they need a protocol in which only two parties multiply their

23


inputs to create uivj. A third party can help them with this. Say two parties wish tomultiply x1 and x2. Observe the following equality:

x1x2 = −(x1 +α1)(x2 +α2) + x1(x2 +α2) + x2(x1 +α1) +α1α2. (2.2)

This can be used as a masking tool. The protocol is executed as follows.

• The third party P3 generates α1,α2 ∈ F232 , α1 is given to the first party and α2is given to the second party.

• The first party calculates their masked share x1 + α1 and shares it with thesecond party. The second party does the same and shares x2 +α2 with the firstparty.

• Each party calculates their new shares:

– the first party calculates (x1 +α1)(x2 +α2) + x1(x2 +α2),

– the second party calculates x2(x1 +α1),

– the third party calculates α1α2.

Note that this is indeed a valid sharing since the sum equals x1x2 as was shownbefore 2.2. This sub-protocol is used six times in the case of three parties, the totalmultiplication takes 3 rounds of communication. Via this sub-protocol we makeshares of uv by summing the shares of uivj for i, j ∈ {1, ...,n}. Until now the protocolwas secure against a dishonest majority, however this sub-protocol is secure onlyagainst one semi-honest adversary, if two parties collide they are able to determinethe other party’s input. For example, if the second and third party work together,combining the second party’s (x1 +α1) and the third party’s α1 they find the firstparty’s input x1. The other cases are similar. Note that the third party does notreceive (x1 +α1) or (x2 +α2), thus the protocol is secure against one adversary.

Secure Bit Extraction: Bogdanov et al.’s protocol also has methods to securelycalculate comparisons and perform bit extraction. We start off with the explanationof the bit extraction protocol. First, the three parties each choose 32 random bitsr(1)i , ..., r(32)

i . The parties use share conversion to transform their random bits fromF2 to F232 . Each party locally computes ri =

∑nj=1 2j−1r

(j)i . Given this shared ran-

domness bit extraction of u is done as follows. Each party shares ai = ui − ri. Theparties need to calculate the bitwise sum of a+ r to gain knowledge on the bits ofu, note that a is public. However, each carry bit requires communication betweenparties, thus extracting the kth bit requires O(k) rounds. However, by performingcarry computations in parallel they reduce this to O(log(k)). Via the bitwise sumthey get to know the kth bit of u.

24

Chapter 3

SePCAR in Practice

3.1 Introduction

In this chapter we provide a detailed analysis of the SePCAR proof of concept. Wedescribe the SePCAR protocol in detail and give a high level overview of the work,before we finish by giving an approximation of the run-time of SePCAR. As thechapter continues, we further investigate the details of the implementation as welink the possible MPC protocols with the performance of SePCAR. Moreover, wedescribe the different MPC operations in detail and provide a complete descriptionof the tweaks we make to the protocol, the complexity and practical efficiency of theresult.

Table 3.1 demonstrates the different entities used in SePCAR and Table 3.2 showsthe notations used for the protocol.

Table 3.1: The different entities in SePCAR.

Entity Description

Owner The owner of the shared carConsumer The user who wants to use the shared carPublic Ledger A public ledger used to store the encrypted access tokens

for the shared cars. This public ledger is available foranyone to see

Car Manufacturer The original manufacturer of the car which is in possessionof the car key

OBU The car’s on board unit used to securely interact with userswho want to open the car

KSMS Key-less Sharing Management System. Consists of multi-ple servers used to handle car booking

25

3. SEPCAR IN PRACTICE

Table 3.2: Notations, as found in the paper from Symeonidis et al. [1].

Symbol Description

Si, PL, CM, uo, uc Set of KSMS servers, the ith server for i ∈ {1 . . . l},Public Ledger, Car Manufacturer, owner, consumer

IDB, IDuo , IDuc , IDcar ID of booking, uo, uc, carCDuc/ACuc , Lcar Set of conditions/access rights under which uc is al-

lowed to access a car, car’s locationDBCM / DBSi Database that CM holds with (IDuo , IDcaruo , Kcaruo )

/ that Si holds with (IDuo , [IDcaruo ], [Kcaruo ]) for allowners (uo’s) and their registered cars

~Duo Car records (IDuox , [IDcaruoy ], [Kcaruoy ]) of the xth uofor the yth car extracted (query) from DBSi , where|~Duo | = n

Pkx / Skx, Certuc Public/private key pair of the KSS entity x, certificateof uc

MB Booking details, i.e, {hash(Certuc), IDcar, Lcar, CDuc ,ACuc , IDB}

σuo , σcarAccess Signature (sign output) of MB with Skuo , and{MB, TScarAccess} with Skcar

Kcar, Kuc , Kuc1 /Kuc2 Symmetric key of the car, uc’s master key, uc’ssession keys generated be (prf output) Kuc andcounter/counter+ 1

Muc , ATuc Concatenation ofMB with σuo , a secure access tokenas the encryption (E output) ofMuc with Kcar

CSi Ciphertext (enc output) of session keys {[Kuc1 ], [Kuc2 ]}with PkSi

[Cuc ] Ciphertext (E output) of {[ATuc ], [IDcar]} with [Kuc1 ]CB, [CB] Message digest (mac output) of MB with Kuc2 , and

[MB] with [Kuc2 ]TSPubi , TScarAccess Time-stamp of uc accessing the shared car, a record

published (publish) on the PL submitted by Si

3.2 SePCAR in Detail

In this section we give an in depth explanation of the SePCAR protocol with thegoal to implement the protocol.

3.2.1 Building Blocks

The SePCAR protocol assumes to have access to certain functions such as sym-metric cryptography, public key cryptography and MPC. We also assume accessto non-cryptographic functionalities for the databases in SePCAR. The followingcryptographic building blocks were proposed by Symeonidis et al. [1].

26

3.2. SePCAR in Detail

• σ← sign(Sk,m) and true/false← verify(Pk,m,σ) are public key operations forsigning and verification respectively. These can be implemented using RSA.

• z← prf(K, counter) is a pseudorandom function using as input a key and acounter. This function can be implemented using CTR mode with AES.

• c← enc(Pk,m) andm← dec(Sk, c) are public key encryption and decryptionfunctions. These can be implemented using RSA.

• c← E(K,m) andm← D(K, c) are symmetric key encryption and decryptionfunctions. These can be implemented using CTR mode with AES.

• v ← mac(K,m) is a symmetric key MAC function. This function can beimplemented using CBC-MAC with AES.1

• z ← hash(m) is a cryptographic hash function. This function can be imple-mented using SHA-2.

Next to these, we also make use of z← query(x,y) which is used to query the xthvalue from the yth database, a similar function z ← queryan(x,y) is used for ananonymous query, which we assume is done via an anonymous communicationchannel such as Tor.

MPC Building Blocks: The paper of Symeonidis et al. [1] also assumes the useof the following MPC functions.

• [x]← share(x) is used to secretly share an input. This function can be instanti-ated using Araki et al.’s sharing functionality.

• x← open([x]) reconstructs the private input based on the secret shares.

• [z]← XOR([x], [y]) outputs a secret shared bit, representing the XOR of secretshared inputs [x] and [y]. Note that for both the arithmetic or Boolean circuits,such functionality could be implemented without requiring any communica-tion cost.

• [z] ← AND([x], [y]) outputs a secret shared bit, representing the AND oftwo secret shared inputs [x] and [y]. This function can be instantiated us-ing Araki et al.’s AND operation.

• [z] ← eqz([x], [y]) outputs a secret shared bit, corresponding to an equalitytest of two secret shared inputs [x] and [y]. This is equivalent to computing

[z]← [x]?= [y] where z ∈ {0, 1}.

• [C] ← E([K], [M]) secretly computes a symmetric encryption from a secretshared key [K] and a secret shared message [M].

1CBC-MAC is proven to be secure as it is only evaluated on equal-size messages [42], which is thecase for SePCAR.

27


• [V] ← mac([K], [M]) secretly computes a MAC from a secret shared key [K]and a secret shared message [M].

The implementation of these functions are discussed further in Subsection 3.4.3.

3.2.2 The Steps

SePCAR is divided into 4 steps.

• Step 1: The booking details are agreed upon by the owner and the consumer.The owner signs the booking details, sign, using the secret key Skowner. Theconsumer generates the keys K1 and K2 via the prf function, which uses thesecret key of the consumer Kuc . Afterwards the consumer makes shares ofthese two keys, share, encrypts these shares, enc, using the public keys of theKSMS servers, and sends the results to the different KSMS servers.

Owner (uo) Consumer (uo) S1 . . . Si . . . Slmsg{SES K GEN REQ, IDB}

Kuc1 ← prf(Kuc , counter)

Kuc2 ← prf(Kuc , counter + 1)

counter ← counter + 2[Kuc

1 ]← share(Kuc1 )

[Kuc2 ]← share(Kuc

2 )for i = 1 . . . l doCSi ← enc(PkSi , {[Kuc

1 ], [Kuc2 ]})

end for

σuo ← sign(Skuo ,MB)Muc ← {MB , σuo}[Muc ]← share(Muc)

msg{SES K GEN ACK, IDB , {CS1 , . . . , CSl}}msgi{AT GEN REQ, IDuo , CSi , [Muc ]}

Figure 3.1: Step 1: session keys generation and data distribution [1].

• Step 2: The KSMS servers create the access token ATcar. From step 1, theKSMS servers have the shared booking details [Muc ] and the shared keysfrom the consumer [K1], [K2]. To get access to the shared car key, the KSMSservers perform equality tests, eqz, between [IDcar] in the booking detailsand the different [IDcaruoi ] in ~Duo for i ∈ [1, l], with l the number of cars theowner has. These equality tests make it possible to extract the correct [Kcar]in a private way. With the shares of the booking details and all the keys, theKSMS servers can perform the needed encryption and MAC procedures. Thesigned booking details [Muo ] are encrypted twice using the E function, oncewith [Kcar] and a second time with [K1]. A MAC is generated for the unsignedbooking details [MB] using the mac function with [K2]. The result creates theencrypted access token with the MAC, [CB] || [Cuc ], these are sent to the PL.

28

3.2. SePCAR in Detail

Public Ledger (PL) S1 . . . Si . . . Sl

~Duo ← query(IDuo , DBSi)for y = 1 . . . n do

~Dcary ← eqz([IDcar], [ID

caruoy ])

end for[Kcar]← ~Dcar × ~Duo

[AT car]← E([Kcar], [Muc ]){[Kuc

1 ], [Kuc2 ]} ← dec(SkSi , CSi)

[Cuc ]← E([Kuc1 ], {[AT car], [IDcar]})

[CB ]← mac([Kuc2 ], [MB ])

msgi{AT PUB REQ, [CB ], [Cuc ]}

Figure 3.2: Step 2: access token generation [1].

• Step 3: The consumer, via an anonymous channel, requests the shares of theaccess token, queryan, and opens the value, open. The consumer proceeds toverify the access token, more specifically CB, and locally generates a MAC ofthe pre-agreed booking details, mac, with K2 and checks if the two MACs areequal. If they are equal, the consumer decrypts Cuc via the function D to getthe access token ATcar.

Owner (uo) Consumer (uo) Public Ledger (PL) S1 . . . Si . . . Sl

publish(TSPubi , [CB ], [Cuc ])

msg{AT PUB ACK,TSPubi }



query an(TSPubi )

TSPubi [CB ] [Cuc ]

1477409 ersdf3tx fwefw23. . . . . . . . .

msg{[CB ], [Cuc ]}CB ← open([CB ])

if CB ?= mac(Kuc

2 ,MB) thenCuc ← open([Cuc ]){AT car, IDcar} ← D(Kuc

1 , Cuc)else

Breakend if

Figure 3.3: Step 3: access token distribution and verification [1].

• Step 4: The consumer provides the access token ATcar to the car. The carverifies, verify, if the access token originates from its owner via the signature inthe decrypted access token. If the signature is correct the car starts a challenge-response protocol with the consumer where the identity of the consumer isverified via a certificate in the booking details. In case the verification holds,the car signs the booking details with the time stamp. When the car has anetwork connection, this signature is sent to the owner of the car which verifiesthat the consumer has access to the car.

29


Owner (uo) Car Consumer (uo)msg{AT car, IDcar,Certuc}

{MB , σuo} ← D(Kcar, AT car)verify(Pkuo ,MB , σuo)

Challenge / Response

σcarAccess ← sign(Skcar, {MB , TScar

Access})msg{σcar

Access, TScarAccess}

verify(Pkcar, {MB , TScarAccess}, σcar

Access)

Figure 3.4: Step 4: car access. Dashed lines represent close range communication [1].

3.3 Evaluation of SePCAR

This section discusses the implementation of the SePCAR protocol. Further in thesection, more details on the MPC protocol and the implementation of the differentoperations over MPC are given.

3.3.1 Implementation of the Framework

In this subsection we provide a proof of concept along with an approximation ofthe run-time of SePCAR. We simulate the SePCAR protocol as the different entities,e.g., the users, the KSMS, the CM and the PL, work on the same device. Settingup communication between multiple machines can be arduous, thus we save onimplementation time and instead implement the different parties as different objectswhich communicate through functions to alter their private variables. This allowsus to simulate the SePCAR protocol and make a proof of concept, and with the rightadjustments, to make a good approximation of its run-time. However, the networkused between the different entities is simulated. This means the implementationcannot be extended to a demo, however the simulation allows for more control onthe specifications of the network.

Simulation of Network Latency

As the different SePCAR entities are on the same device a delay needs to be cal-culated to simulate the time to send data over a network and in turn, to create anapproximation of the run-time of SePCAR. Note that for the SePCAR protocol, weassume a secure connection between the parties, more specifically, we assume aTLS connection. Thus, we need to symmetrically encrypt and generate a MAC ofthe data before and after sending packets. To simulate the time it takes to send orreceive data we use the structure shown in Figure 3.5. It consist of the following.

• Encrypt and generate a MAC of the data, in the simulation this is done byusing AES in CBC mode with a random key.

• We repeat the following:

30

3.3. Evaluation of SePCAR

– Send the data to a dummy server which echoes it back using sockets witha TCP connection. Check if the echoed data is correct.

– Let the process sleep for a “delay”. This delay is chosen as the ping timeof the network. For communication between servers, this is set to 0.13msas described by Araki et al. [39]. For communication through Wi-Fi this isset to 50ms as is described in Ramamurthy et al.[43]. For communicationover a Tor network the delay is set to 1s as is found on the Tor metricsdata [44].

– Given the probability p, which simulates the chance of package loss, wehave a 1-p% probability of breaking out of the loop. Otherwise we repeatthese steps again. Here we have taken a 1% probability of package loss.

• Decrypt the data and verify the MAC.

On average this communication call takes around 294µs for a ping time of 130µs.Thus, we find that the most important bottleneck in this simulation comes from thedelay and the socket calls as the MAC or the encryption only takes around 2µs. Wefind that the simulation gives an accurate approximation. For example, a latency of300µs is found in the article by Launchbury et al. [45]. A similar result is also foundin a text provided by Cavium [46] and in the article of Keller et al. [47]. This methodallows us to simulate the network latency when sending data. However, note thatthis method only gives an approximation of the latency, thus an extra delay mightbe overlooked.

Encrypt, MAC Socket Calls Ping Time Delay Decrypt, Verify

Package Loss

Figure 3.5: A simulation of network latency.

3.3.2 Implementation of the Steps

We explain the implementation of each step in SePCAR in detail. Before step 1 weneed to initiate the KSMS servers, the PL and the CM, creating for each of them adatabase implemented via SQLite. We also assign public and private key pairs toeach party. We initiate users by giving them a unique ID, a symmetric key with acounter to produce unique random numbers, a secret and public key for public keyencryption and separate keys to generate signatures. We also initiate some sharedcars, adding the corresponding car keys to the database of the CM which in turn

31


makes shares of it and sends them to the KSMS servers. For the MPC protocol wemake use of Araki et al.’s protocol for the MPC parts of SePCAR. This choice isjustified further in Subsection 3.4.1.

3.3.3 Step 1: Preparation and Sharing of the Booking Details andGeneration of Keys

We start off with the agreement on the booking details between the consumer and theowner. This is implemented as a text file consisting of the booking details which isparsed in, extracting the needed values. The consumer generates the keys K1 and K2by making use of the prf function with the consumer’s secret key and an incrementedcounter. We implement the prf function by using AES in CTR modes, where the AEScall is made using the OpenSSL library [48]. The consumer sends the keys to theservers by creating shares of K1 and K2 using the MPC share function. For the MPCpart we make use of the protocol described by Araki et al. [39], more information onthis is found in Subsection 2.3.6. The consumer then concatenates the shares of K1and K2 and encrypts the results using the enc function with the public keys of theKSMS servers. For public key encryption we make use of RSA encryption using theOpenSSL [48] library, where we used 2048 bit keys. To simulate the network andthe time the consumer needs to send the keys to the servers, we make use of thefunction to simulate the network latency as we explained in Subsection 3.3.1. Wechoose 50ms as the delay parameter to simulate the ping time over WiFi [43]. Nextthe owner signs the booking details using the sign function and sends the shares ofthe booking details to the different KSMS servers. To implement the sign functionwe first hash the message, this is implemented as SHA-2 with 512 bit output fromthe OpenSSL library. Afterwards we sign the hashed booking details by using RSAfrom the OpenSSL library using the owner’s secret key. The servers decrypt theshares of the booking details and save these in their database. These values aresaved in case of a law enforcement request to provide forensic evidence when a carincident occurs.

3.3.4 Step 2: Retrieval of the Car Key and Creation of the Access Token

For the car key extraction, the different servers have access to a set of records thatcorrespond to an owner ~Duo ,

~Duo =

IDuo [IDcaruo1 ] [Kcar1 ]

......

...IDuo [ID

caruoy ] [Kcary ]

......

...IDuo [ID

caruon ] [Kcarn ]

,

with n the number of cars the owner has. By extracting [ID]car from the bookingdetails and performing a comparison, eqz, with each of the n entries in ~Duo . It

32

3.3. Evaluation of SePCAR

results in a vector ~Dcar where,

~Dcar =( 1[0] · · · [0]

y

[1][0] · · ·n

[0])

.

The servers then multiply ~Dcar and ~Duo to generate a third vector

~Dcar × ~Duo =(IDuo [ID

caruoy ] [K

caruoy ]

),

where the key in shared form [Kcar] is retrieved from. Using the extracted car keythe servers encrypt the booking details twice, E, once with [Kcar] and once with[K1]. To get access to the shares of K1 and K2 the KSMS servers decrypt the CSimessage using the dec function with their secret key, this is implemented using theOpenSSL library [48] with 2048 bit keys. As we want to reduce the running time ofthe protocol, we want to minimise the number of communication rounds the partiesneed to encrypt the booking details. For this reason we make use of AES in CTRmode as this allows us to securely parallelise the encryption of the different blocksof the booking details. This parallelisation is implemented via threads. For the MACoperation in SePCAR, mac, we have opted for CBC-MAC as this is implementedusing only AES calls over MPC. Note that CBC-MAC is secure as the bookingdetails have a fixed length, as is shown in Bellare et al. [42]. Thus, the KSMS serversgenerate the MAC over the booking details using the mac function using the [K2]key which they received in encrypted form from the owner. The separate shares ofthe resulting encrypted access token and MAC are sent to the PL, which publiclystores these separate shares. The PL is implemented as a database.

3.3.5 Step 3: Retrieval, Reconstruction, and Verification of the AssignedAccess Token by the Consumer

The consumer verifies the MAC of the booking details, using the mac function. Theconsumer, using a time stamp received from the owner, requests the correspondingshares on the PL. This is done via an anonymous channel using the queryan function.This anonymous channel is not implemented, however the performance overheadcan be calculated using the Tor Metric website [44]. The consumer opens the result-ing encrypted access token and generates a MAC, mac, of the booking details whichwere agreed on with the owner. By using the MAC in the access token from the PLand the MAC, the consumer verifies the two access tokens for an equality. Uponsuccessful termination, the consumer agrees on the received access token otherwisethe consumer rejects the received token. To further test if we correctly made theaccess token, the encrypted access token Cuc is verified as well. This is done bylocally encrypting the original booking details and again verifying if the two are thesame. The simulation was tested over a thousand times where it always succeededwithout error.

33


3.4 Evaluation of the MPC Protocol

Here we discuss the simulation of the MPC protocol with the different operationsover MPC in detail. We start by choosing the suitable MPC protocol for SePCAR.

3.4.1 The Link between MPC and SePCAR

We dissect the SePCAR protocol to examine the necessary properties the MPCprotocol needs to fulfil. SePCAR consists of several MPC operations to privatelyextract the correct car key and to encrypt and MAC between multiple parties usingAES as block cipher. The MPC circuit of SePCAR mainly makes operations overF28 , since AES works on bytes, and over F2 since we need comparisons of the carkey extraction. As we will see in Subsection 3.4.3, equality tests perform faster overBoolean circuits than over arithmetic circuits and AES over MPC works well overBoolean circuits. Thus, for the MPC operations in SePCAR, using Boolean circuits isadvantageous over using arithmetic circuits. We assume that there are not manyindependent parties in the KSMS, for example, from two to five parties. However,note that using the SePCAR protocol with only two KSMS parties removes the abilityto provide forensic evidence to authorities. We assume that the connection betweenthe parties is fast, i.e., LAN connection. This way we can work with MPC protocolsthat have a high throughput instead of MPC protocols which achieve low latencyat the cost of throughput, e.g., using garbled circuits. To support forensic evidencewhen there is one or more none-cooperating parties, we need an MPC protocolwhich uses threshold secret sharing so that a subgroup of parties can constructthe original inputs and/or outputs. In the SePCAR protocol the adversaries areassumed to be semi-honest. This means that the protocol entities follow the protocolspecification but they may try to learn as much as possible private informationabout the users. Intuitively, tampering with shares would break the correctness ofthe calculation, for SePCAR this means the consumer cannot access the car and thusa discrepancy is noted. However, in the appendix we explain that it is possible fora malicious adversary to break privacy without harming the correctness of a semi-honest secure protocol using the protocol by Bogdanov et al. as an example. Westick with a protocol which is secure against semi-honest adversaries but we prefera protocol which is easily upgradeable to be secure against malicious adversaries.As a final note, SePCAR does not benefit from a slow preprocessing phase, such asthe one from SPDZ, it needs to be able to handle multiple booking details at thesame time.

Comparison of MPC Protocols

We give an overview of possible MPC protocols for a several number of independentparties. Each protocol has advantages and disadvantages for SePCAR as illustratedin Tables 3.3, 3.4 and 3.5. Recall that the specific protocols are explained in moredetail in Section 2.2.

34

3.4. Evaluation of the MPC Protocol

Two Parties: In the two party case, threshold security cannot be obtained. In-stead we need to turn to protocols such as GMW or SPDZ. We can also make useof Yao’s protocol. As Yao’s protocol is constant-round it performs better when thedifferent entities are connected via a network with high latency. When the networkhas low latency the GMW protocol would perform better. SPDZ performs well withmany parties and large circuits. However, it is slow compared to other protocolswhen we are working with a few parties and a tiny circuit. As mentioned previously,SePCAR needs to be able to handle multiple access token requests at the same timewhich forces a preprocessing phase to be calculated on the fly. As a consequence,computations using SPDZ need to be measured both in offline and online time. Asmentioned before, for the two party case, if one of the two parties refuses to givethe correct share in case of incidents, the forensics property cannot be enforced.With this in mind, two party computation might not be suitable for the car sharingprotocol.

Table 3.3: Classification of MPC protocols in the case of two parties. Positive andnegative aspects when using the MPC protocol for SePCAR are considered.

Classification of 2PC protocols

Yao [29] GMW [20] SPDZ [18]

Circuit Boolean Boolean Arithmetic

Security Computational Computational Computational

Positive aspects Extensions: [32] [30] Fast OT extensions O(n|C|+n2/s+n3)Low latency Fast for 2 parties complexityFairplay software

Negative aspects Insecure against Slow offline phasemalicious sender (→MASCOT [33])Low throughput

Three Parties: For the three party case we may use different protocols such asBogdanov et al.’s protocol [41] or the protocol proposed by Araki et al. [39]. Inthis case we may also use the protocols explained in the multiparty case, whichis advantageous if the protocol needs to be able to handle an incremental setupfrom three to multiple parties. However, note that these three-party protocols aremuch faster than the multiparty protocols. For example, the protocol of Araki et al.requires a party to send only one bit to a single party for each multiplication,whereas the BGW multiplication protocol requires two bits. For the three partycase, the protocol of Araki et al. is the fastest protocol in terms of communication,however, if the network is extremely slow the BMR protocol might be faster since it isconstant round. The performance of the BGW protocol does not compare against the

35


protocols of Bogdanov et al. or Araki et al., however BGW has the flexibility to workwith more than three parties. As was mentioned in the subsection on Bogdanov etal.’s protocol 2.3.7, this protocol has threshold security only when a multiplicationis done. Thus, to get the forensics property with Bogdanov et al.’s protocol thethree parties need not only to hold the original inputs to the computation but also atranscript of the booking details being multiplied by 1.

Table 3.4: Classification of MPC protocols in the case of three parties. Positive andnegative aspects when using the MPC protocol for SePCAR are considered.

Classification of 3PC protocols

Araki et al. [39] Bogdanov et al. [41]

Circuit Boolean Arithmetic

Security Information theoretic Information theoreticHonest majority Honest majority

Positive aspects High throughput Easy implementationCan be made secureagainst a malicious party [40]

Negative aspects No threshold secret sharingOnly semi-honest adversaries

Multiple Parties: In this case the BGW protocol or the BMR protocol which usesBGW to garble the circuit are the possible protocols available in the literature.

Table 3.5: Classification of MPC protocols in the case of more than three parties.Positive and negative aspects when using the MPC protocol for SePCAR are consid-ered.

Classification of MPC protocols

BGW [26] BMR [28]

Circuit Arithmetic Boolean

Security Information theoretic ComputationalHonest majority Honest majority

Positive aspects Well researched Constant roundFairplayMP

36


Table 3.6: A comparison between different MPC protocols to use for SePCAR. Forthe adversarial security, note that security against malicious adversaries may alwaysbe reduced to semi-honest adversaries to increase performance. We mark whichproperties are good for SePCAR in green (otherwise in grey).

Protocol Threshold Security Adv. Security # Parties Circuit

GMW Dishonest Majority Malicious > 1 BooleanBGW Honest Majority Malicious > 2 ArithmeticYao Dishonest Majority Malicious 2 BooleanBMR Honest Majority Malicious > 2 BooleanSPDZ Dishonest Majority Malicious > 1 ArithmeticAraki et al. Honest Majority Malicious 3 BooleanBogdanov et al. Honest Majority Semi-Honest 3 Arithmetic

The MPC Protocol for SePCAR: Using Table 3.6 we can choose a suitable MPCprotocol for SePCAR. As mentioned before, ideally we want an MPC protocol whichworks on Boolean circuits since the MPC circuit consists of multiple comparisons.We also need threshold security for the forensics property. For the two-party onlyprotocols we need to turn to protocols that are secure against a dishonest majority,in which case the forensics property cannot be fulfilled. We assumed the adversariesare semi-honest, however, as previously discussed, we need to keep security againstmalicious adversaries in mind, e.g., as seen in the example in the appendix . Notethat working with only three parties gives higher performance and allows SePCARto fulfil all of its properties. Thus, for this work we assume to work strictly withthree independent parties where there is a fast connection between them. In thiscase the Araki et al. protocol [39] is a better candidate as it offers a much higherthroughput of multiplications than the BMR protocol. In the case where the connec-tion between the three parties is insufficient we can make use of the BMR protocolinstead. If we want to be able to work with more than three parties we can tradeoff some performance and choose the BGW protocol. We conclude that using theprotocol of Araki et al. for the car sharing protocol is preferred. This means we havesecurity against a semi-honest adversary, though the security can be upgraded tooffer security against a malicious adversary.

3.4.2 Evaluation of Araki et al.’s Protocol

Araki et al.’s protocol consists of an implementation of a secret shared XOR andAND gate over multiple parties. Without communication these gates take just a fewnanoseconds to compute. This means that if we use unnecessary overhead, i.e., alot of calls to different addresses, a bad list structure, we risk that the arithmeticcost becomes too large slowing down everything build on top of these simple gates.Thus, a careful design of the MPC protocol is needed. Similar to the discussion inSubsection 3.3.1, we implemented the logic described by Araki et al. [39]. How-ever, we simulated the network between the different parties, where we used an

37


estimation of the network latency to create an approximation of the run-time. Thedifferent parties are implemented using a class where we instantiate three objectswhich represent the three parties for the MPC protocol. Each party has a privatedynamic list of shares. To send or receive shares, we create functions that allow aparty to get a share from the list of another party. The basic XOR and AND gateare created following the protocol described by Araki et al. [39]. However, for theAND gate we need the three parties to share some randomness. This is done inthe same way as it is done in the computational secure protocol described in thepaper of Araki et al. [39]. This means that at the start of the computation the threeparties create a symmetric key ki and share this with the other parties such thateach party holds their own secret key and the key of one other party. Using thesekeys the parties create correlated randomness ri such that r1 ⊕ r2 ⊕ r3 = 0. Thepseudo-random function (prf) is made by using AES and as AES works on blocks of128 bits we create 128 bits of randomness at a time. Thus, we also create an arrayof correlated randomness that gets refreshed after all its randomness is used up.Recall that the basic data structure at the hardware level of general purpose CPU’sis a byte. Thus, to work with single bits is difficult, for example, when a Booleanvariable is used to store this bit, we use a byte instead of just one bit, which impliesunnecessary memory overhead. Instead, we use a vector of characters where everybit in the character is set separately. Thus, while the MPC protocol works on Booleancircuits, the XOR and AND gates in the implementation work on eight bits at a time.

3.4.3 MPC Operations

Different MPC operations which are needed for the SePCAR protocol are analysed.As these are the basic building blocks for the car sharing protocol, their performanceaffects the whole overlying structure.

Sharing a random number

The operation to share a random number, where the number is unknown to allparties is essential if we want to speed up operations via masking. While for someMPC protocols it might be easy to share a random number, it is not evident for theAraki et al. protocol. For example, for the GMW protocol, each party generatesa random bit ri ∈ F2. This results in the parties holding each a share of

∑ni=1 ri

mod 2 which is a random bit. However, for the Araki et al. protocol, applying thismethod does not create valid shares as we need the following equalities.

a1 ⊕ x3 = x1 ⊕ a2 = x2 ⊕ a3

These equalities are not valid if all xi,ai for i ∈ {1, 2, 3} are taken randomly. Insteadit is possible to create a sharing method without any need of communication usingthe symmetric keys the parties shared at the start of the protocol. As mentionedin the paper of Araki et al., these keys are used to generate correlated randomness.However, if we tweak this method, we create the following way to share a fullyrandom bit between the parties.

38


• Each party Pi for i ∈ {0, 1, 2} has the keys ki and kj with j ≡ i+ 1 mod 3.

• Using these keys Pi generates the random bits ri = Fki(id) and rj = Fkj(id)by using the keyed prf F, with j ≡ i+ 1 mod 3.

• Party Pi then generates the shares (xi,ai) = (ri ⊕ rj, rj).

One can see that every party opens the same value, since

x2 ⊕ a0 = x0 ⊕ a1 = x1 ⊕ a2 = r0 ⊕ r1 ⊕ r2.

This way we can share randomness using the protocol of Araki et al. without anyneed of communication. This method is also found and used in the follow-up paperwhich handles the malicious adversarial case [40].

Multiplication in F(256)

The standard way of multiplying over the finite field F(256) is depicted in thefollowing pseudocode. Note that this field has X8 +X4 +X3 +X+ 1 as the reducingpolynomial. Given a and b calculate c ≡ a · b mod 256:

F256mul(a, b) {c = 0;while (b > 0) {

if (b & 1 == 1) {c ^= a;

}if (a & 0x80 > 0) {

a = (a << 1) ^ 0x11b;} else {

a <<= 1;}b >>= 1;

}return c;

}

This leads to a circuit of depth n, where n is the bitsize of a and b, since we gothrough all the bits of b and check if it is equal to 1. However, we can parallelise thisby creating n parallel AND gates to check if the ith bit is equal to 1, for i ∈ [1, ...,n].Thus, we are able to multiply in F(256) with one round of communication.

Equality Test over MPC

For this operation we are given two shared values [a] and [b] consisting of n bits. We

wish to check if the two shares are equal or not, i.e., [a] ?= [b] = [c], where c ∈ {0, 1}.

The standard way is the following.

• XOR [a] and [b] and save the result in [c]. If a = b then the result is the zerobit-string, otherwise the resulting string contains at least one 1.

39


Figure 3.6: Different ways of creating a circuit to calculate an equality test.

• We calculate the NOT from [c]. If a = b then this results in a bit-stringconsisting of only ones.

• We calculate the AND between all the n bits in [c]. The result is one shared bitgiving an answer to [a]

?= [b].

This results in a circuit of depth n, with n the number of bits in the input, depictedon the left side in Figure 3.6. A second way of doing this is to create a tree oflogarithmic depth, depicted on the right side in Figure 3.6. For 8 bit operands thisresults in a tree of depth 3 instead of a tree with depth 8. So far we found no betterway to improve this result. It is possible to make a tree of depth one if a high fan-inAND gate is allowed, this is a gate where there are multiple wires as input for theoperation. However, we have not found a way to create a high fan-in AND gatein one communication round using Araki et al.’s protocol. We can also achieveequality tests in a constant number of rounds but this requires an offline phase andthe number of rounds with the offline phase included is larger than using the resultwith a logarithmic depth [49].

3.4.4 S-Box Calls over MPC

This is the central operation in the calculation of an AES call over MPC. Modularinversion is used in the calculation of the S-Box call. Everything else for the calcu-lation of an AES call is done locally for Boolean circuits. Note that for arithmeticcircuits we need an extra round of communication for a bit decomposition for theaffine transformation (Ax+ b) of the S-Box. The implementation of this operation isdone following Damgård’s and Keller’s article on secure multiparty AES [50]. They

40


Table 3.7: Different ways of inverting in F(256).

Method Bits Sent Rounds

Standard square and multiply 104 14Square and multiply, least rounds [50] 104 9Masking [50] 39 + 16

255 7 + 2255

Masked exponentiation [50] 112 5 + 7# AES rounds

Improved masking method 23 + 16255 5 + 2

255

introduce three different ways of inverting an element over F(256), these are listedin Table 3.7. Note that the methods from Damgård and Keller’s article are madeover arithmetic circuits. For Boolean circuits this makes no difference as we can dothe affine transform for the S-Box locally without communication.

While the masked exponentiation requires the least number of rounds in thepaper, the masking method is easier to implement as it does not require a sepa-rate preprocessing phase before every AES call. The masking method can alsobe improved over Boolean circuits as we require no communication to get the bitdecomposition of a number. The masking method looks as follows, given a as inputwe output c as the inverse of a.

256Inver(a) {b = (a == 0); // 3 rounds

c = 0;temp = 0;while(c == 0) {

r = share_random(); // share a random number

temp = (b ^ a);temp = temp * r; // 1 roundc = open(temp); // 1 round

}c = pow(c,254); // local inversion

c = (r * c) ^ b;

return c;}

This way we are able to do modular inversion in 5 + 2255 rounds which is only

slightly worse than the masked exponentiation. We may improve this methodfurther as explained in Section 4.2.

41


3.4.5 AES Calls over MPC

Given the operations described above, we can make an AES call over MPC. Cal-culating AES over MPC only requires communication to calculate its S-Boxes inKeyExpansion and SubBytes steps, other steps such as AddRoundKey are donelocally. To make the AES call we used an implementation from a public repositorywhich can be found on Github 2. To create the AES call over MPC we need to switchthe operations in the code describing AES with the operations of the MPC protocol.We can optimise the AES call using threads to parallelise the S-Boxes in each round.To this end, we want to make multithreading possible for the MPC simulation, thiscan be done by creating three new parties that get the necessary shares as input tocalculate the S-Box. These three new parties run everything needed to calculate theS-Box from their input and give this output back to the original parties. This waythe threads work on different parts in memory, which makes the S-Box call threadsafe.

Using this techniques together with the masking method we described earlier wemake a 10-round AES call with key expansion in 10 · 5+ 10 · 5 = 100 communicationrounds. This makes quick AES calls possible if the parties are connected by highspeed networks. However, if the parties are connected by slower networks, e.g.,using mobile data, an AES call would take several second. In such conditionswe need a different method, e.g., an MPC protocol which is constant-round. Forexample, in the some situations we can achieve encryption in a constant number ofrounds. This is possible if one of the parties has access to the key. This party canuse CTR mode encryption locally to create a random string which has the lengthof the message effectively creating a stream cipher. This is possible because thecounter is public and the key is known to that party. This random string alongwith the plaintext message is then shared among the parties with the cost of onecommunication round. The shares of the random string and the shares of themessage are then XORed creating a sharing of the ciphertext. While this techniqueis optimal in the number of communication rounds, it might be costly for the partyholding the key since this party needs to share a potentially very long random string,e.g., via mobile data. Before we give results of the performance of the AES call overMPC, we note that in the MPC situation, a key expansion over MPC is very costlyas we need to perform 10 rounds of S-Box calls. Thus if we want to compare AESperformance results we need to be careful whether the key expansion is part of thisperformance or not.

Via the simulation we are able to make an AES call with key expansion in 53ms.Note that this AES call is faster than the one described in the original article ofAraki et al., which takes 0.121s [39]. A fair comparison with their implementationis not possible since the code is private. The authors of the Araki et al. papercommented that no particular optimisations to the AES call were made, insteadthe implementation worked directly on a Boolean circuit describing the AES call.This means the S-Box call is probably made using the standard square and multiplymethod which makes an S-Box call run in 13 rounds, whereas we implemented the

2Free to use AES implementation: https://github.com/kokke/tiny-AES128-C

42

https://github.com/kokke/tiny-AES128-C

3.5. Performance Tweaks

Table 3.8: A comparison between the AES call of this work and the AES call describedin the paper of Araki et al. [39].

AES Implementation Average Time

Araki et al. [39] 0.1212 sThis work using square and multiply 0.1158 s

Table 3.9: Efficiency of the simulation with multiple parallel AES calls.

# Parallel AES Calls Average Time

1 0.053 s5 0.210 s10 0.401 s15 0.504 s

Table 3.10: Comparison of the performance of SePCAR where either the certificate isleft in plain form versus where the certificate is hashed.

Protocol variation Average Time

Certificate in plain form 8.37 sHashed certificate 1.55 s

S-Box call using 5 rounds. To compare the two implementations we implement theAES call with the standard square and multiply method. However, this is only avague comparison since we simulate the communication and use different hardware.The result of the comparison is depicted in Table 3.8.

For the SePCAR protocol we need to run several AES calls in parallel. Similar tothe parallel S-Boxes we implemented this via threads where we again make surethe threads work on different parts of the memory. However, the creation of thesethreads cost time and the threads do not fully parallelise the AES calls or the S-Boxcalls. This is a limitation of the simulation. The effect is noticed if we run multipleAES calls in parallel, the results are shown in Table 3.9.

3.5 Performance Tweaks

To make the SePCAR protocol perform better we made some tweaks to the protocolwithout making changes to its security and privacy properties. Some of these tweakswere implemented in the SePCAR protocol (in green). The others are possible tweaksif more performance is needed (in grey), these are seen as future work as discussedin Chapter 5.

43


Data Authentication over MPC: Originally data authentication was done by hash-ing the data and performing encryption over MPC. While it is fully possible toperform hashing over MPC, as any polynomial time function can be calculatedover MPC, there is no literature describing this. It is also not evident that hash-ing over MPC can be performed in a fast way, which could slow down the carsharing protocol. Instead of hashing and encrypting data over MPC, a MAC wasused. For this MAC we opted for CBC-MAC using AES as this is efficient and secure.

Improved Key Extraction: Another contribution of the work was to parallelisethe car key extraction. Initially, such an extraction was performed sequentially,with the cost of the extraction bounded to the number of cars an owner holds. Byparallelising the process, the performance of key extraction becomes independent tothe number of cars of an owner.

Hashing the Certificate: A third adaption on the protocol consists of reducingthe length of the booking details by hashing the consumer’s certificate and includ-ing the digest, rather than the whole certificate, in the booking details. Originally theaccess token consisted of 8660 bits, whereas after hashing the certificate the accesstoken consists only of 1408 bits. This adaptation is justified since the consumer cangive the certificate in plain form to the car when accessing the car. The car can verifythis certificate by hashing it and comparing it to the certificate in the booking details.This adaption made a significant improvement on the performance of SePCAR, asseen in Table 3.10.

Encrypting by One-Time Pad: A tweak in performance can be made if the CMcreates a stream of random numbers using the car key. With this we can encrypt bysimply XORing the booking details with the random bit string. The same can bedone by the consumer for the keys K1 and K2. However, this method is not preferredfor SePCAR as this means the consumer needs to send more data to the servers andthis might be costly, for example, when using mobile data. This would also makethe SePCAR protocol more complex as the CM needs to send data to the KSMSevery time a booking is made, which the original SePCAR protocol avoids doing.For these reasons we opted not to use this technique, however the change wouldcreate a significant increase in performance.

Avoiding Double Encryption: In SePCAR we encrypt the booking details twice,with Kcar and K1. This encryption is sequential and thus is costly in terms of perfor-mance. In order to improve this we can first make a secret shared XOR between thetwo keys, [Kcar] and [K1], creating a new key. Note that this new key is in sharedform, so it is not made public. This new key is then used to encrypt the bookingdetails. As an XOR is done locally over MPC this operation is very cheap, creatinga technique to encrypt the booking details just once. The user accesses the car bygiving the encrypted access token along with the key K1. Assuming Kcar and K1 areuniformly distributed, the protocol is secure since the new key is again uniformlydistributed.

44

3.6. Complexity and Efficiency

Parallelising MACing and Encryption: The protocol can be improved by MACingthe booking details in parallel with the encryption of the booking details, since thetwo operations are independent of each other. This significantly reduces the numberof communication rounds needed for the SePCAR protocol assuming the packagessent by the KSMS servers do not exceed the network throughput. Note that using aMAC which allows the separate AES calls to be in parallel would further improvethe running time of SePCAR. This tweak was not implemented due to the currentlimitation of the simulation, it is not able to efficiently parallelise a lot of operationsas is depicted in Table 3.9.

3.6 Complexity and Efficiency

Complexity: Considering the high cost of doing operations over MPC, e.g., AESover MPC costs around 53ms, we assume the complexity of SePCAR is dominated bythe complexity of its MPC circuit. As mentioned in Subsection 2.2.2, the complexityof MPC is determined by the multiplicative depth of the MPC circuit. The nonlinearoperations over MPC of SePCAR consist of (i) the retrieval of the car key by callingseveral equality tests to extract the car key and (ii) encrypting the booking detailstwice and generating a MAC.

For (i), recall that we needed to compute an equality test between IDcar inMB

and the car identities in the different entries in ~Duo . We made the equality test witha logarithmic complexity. The non-linear operations in (i) have a complexity of

dlog(|IDcar|)e+ 1. (3.1)

Notice that this result demonstrates that the performance is independent of thenumber of cars the owner has. Such independence allows the protocol to workvery fast even if the owner is a company possessing a large number of cars, e.g.,thousands of cars.

For (ii), we need to encrypt the signed booking details twice with different keysand generate a MAC over the unsigned booking details once. For the encryption wehave chosen to use AES in CTR mode. This way we parallelise the AES calls, reduc-ing the number of communication rounds for the encryption. For the MAC we havechosen to use AES in CBC mode, making the required AES calls in series. Denoteν the number of rounds needed to encrypt a single block with AES. Using AES onCTR mode for the encryptions we have the following number of communicationrounds needed for (ii)

2 · ν+⌈|MB|

128

⌉· ν. (3.2)

Note that using a MAC where the AES calls would be made in parallel would speedup SePCAR. Combining (i) and (ii), the total number of communication rounds forSePCAR can thus be expressed as

(dlog(|IDcar|)e+ 1

)+ 2 · ν+

⌈|MB|

128

⌉· ν. (3.3)

45


Table 3.11: Performance of SePCAR, where time is averaged over 1000 runs as foundin Symeonidis et al. [1].

Phase Description Time (in sec)

Step 1 Sharing the booking details and keys 0.220± 0.027Step 2 Extracting car key and making access token 1.274± 0.032Step 3 Verifying the access token 0.055 (+1 Tor [44])Total 1.551± 0.043 (+1 Tor)

Efficiency: The SePCAR protocol only needs 1.55 seconds for a car access pro-vision. A detailed overview of the time each step of the protocol takes is givenin Table 3.11. We have the following message configuration size: the hash of theconsumer’s certificate hash(Certuc) of 512 bits, the ID of the car IDcar of 32 bits, thelocation of the car Lcar of 64 bits, the access conditions CDuc of 96 bits, the accessrights ACuc of 8 bits, the ID of the booking details IDB of 32 bits and the ownerssignature σuo of 512 bits. The booking details MB are of size 768 bits (includingpadding) and the final access token ATuc is of size 1408 bits (including padding).The simulation requires 5 communication rounds to evaluate a single S-Box call overMPC. As AES requires 20 sequential S-Box calls, where we include the key expansionpart, we see that we can perform an AES call in ν = 100 rounds of communication.For equation 3.3 and ν = 100, SePCAR performs in total in

(5 + 1

)

︸︷︷︸Key Extraction

+ 2 · 100 + 6 · 100︸︷︷︸AES calls over MPC

= 806,

communication rounds. We run SePCAR on a machine equipped with an In-tel i7, 2.6Ghz CPU and 8GB of RAM. The simulation is found on Bitbucket from thefollowing link https://bitbucket.org/Siemen11/sepcar.

3.7 Concluding Remarks

Implementations using MPC need to be handled with care as the performanceof MPC can be really slow. Fast connections between parties are necessary if theMPC circuit requires multiple communication rounds. The software described inthis chapter is able to make a fast simulation of the SePCAR protocol as it is ableto make AES calls in 53ms. Several tweaks to the SePCAR protocol were madein order to make the protocol feasible. More specifically, SePCAR runs within arealistic environment, e.g., using a network latency of 50ms for WiFi [43], in only1.55 seconds. Several MPC functions were needed for the SePCAR protocol. InTable 3.12 a list of the performance of these operations over MPC is given. In the

46

https://bitbucket.org/Siemen11/sepcar

3.7. Concluding Remarks

Table 3.12: The run time of the MPC operations with and without communicationcost with 8 bit inputs. Note that the average time it takes to make a communicationcall in the simulation is 2.9439e-4s.

Operation Rounds Without Communication With Communication

XOR 0 1.1854e-07 s 1.1871e-07 sAND 1 6.7242e-07 s 2.9543e-04 sF28 mult 1 5.8791e-06 s 3.1786e-04 sEqz 3 4.1615e-06 s 9.6718e-04 sF28 inverse 5 1.4114e-05 s 1.8707e-03 sAES 100 1.7235e-02 s 5.2395e-02 s

next chapter, the S-Box call and the multiplication operation are discussed in detailto improve the current state-of-the-art. A limitation of the current simulation isthat it is not capable of handling multiple operations in parallel. In Chapter 5 wedescribe an implementation which overcomes this limitation.

47

Chapter 4

Optimised MPC Operations

4.1 Introduction

During the design and development of the SePCAR simulation we noticed thatthe performance of AES over MPC could be improved. In this chapter we discussimprovements on the S-Box call and to securely multiply shares over Booleancircuits.

4.2 Improved S-Box Calls over MPC

We previously discussed the S-Box call over MPC in Subsection 3.4.4, in this sectionwe discuss this further, as we propose novel methods to calculate the operation. Anoverview of the known and novel methods is given in Table 4.1.

4.2.1 An Improved Masking Method

We further improve the masking method described in Subsection 3.4.4. Recall thatthe implementation was given as follows.

Table 4.1: Different ways to invert in F(256).

Method Bits Sent Rounds

Standard square and multiply 104 14Square and multiply, least rounds [50] 104 9Masking [50] 39 + 16

255 7 + 2255

Masked exponentiation [50] 112 5 + 7# AES rounds

Improved masking method 23 + 16255 5 + 2

255Improved masking method with public mult. 23 + 16

255 4 + 1255

Lookup table method 1792 3First masked lookup table method 1808 1 + 3

# AES roundsSecond masked lookup table method 2056 1 + 2

# AES rounds

49

4. OPTIMISED MPC OPERATIONS

256Inver(a) {check = (a == 0); // 3 rounds

c = 0;temp = 0;while(c == 0) {

r = share_random(); // share a random number

temp = (check ^ a);temp = temp * r; // 1 roundc = open(temp); // 1 round

}c = pow(c,254); // local inversion

c = (r * c) ^ check;

return c;}

This way we were able to calculate modular inversions over F256 in 5 + 2255 rounds.

We can improve this result with a method which multiplies two shared numbersover F(256) and publicly outputs the result. This can be done with only one commu-nication round. This was also found by Chen [51] for the BGW protocol. We create asimilar result for the protocol of Araki et al. [39].

Multiply and Open in One Round: Consider only the operations which requirescommunication: finite field multiplication consists of 8 parallel AND gates wherewe XOR the results of these gates. We create an AND gate where the result ofthe AND gate is opened in the same round. Recall that to AND shared values,(xi,ai) and (yi,bi) for i ∈ 0, 1, 2, in Araki et al’s protocol, each party Pi computesri = xiyi ⊕ aibi ⊕ αi and sends ri to Pi+1. Each Pi has (ri ⊕ ri−1, ri) as the shareof the result. We see that if each party Pi creates and sends their ri to every otherparty, each party holds the opened result of the AND gate and the inputs are keptprivate. To apply these new AND gates directly to the finite field multiplicationwould reveal the inputs of the multiplication protocol. However, we can secure thisby masking. For n bit operands we make random numbers εi such that

⊕ni=1 εi = 0,

this requires no rounds. We XOR the shares of these random values with the outputof the new AND gates. Let party Pi hold the share (δli ⊕ δli+1, δli) for εl. We sendvalues to publically open the AND gate of two shared value where we XOR a mask.Thus, each Pi sends ri = xiyi ⊕ aibi ⊕ αi ⊕ δli for the lth AND gate, where theinputs for the AND gate are (xi,ai), (yi,bi) for i ∈ {0, 1, 2}.

This creates a method to multiply two shared values over F and open the resultin one round. This means we are able to invert values over F(256) in around 4rounds, thus we are able to improve the results of Damgård and Keller’s method.

50

4.2. Improved S-Box Calls over MPC

Table 4.2: An S-Box lookup table of size 256.

index inverse0 01 12 2−1

......

254 254−1

255 255−1

4.2.2 Lookup Table Method

Another way of to compute this modular inversion was proposed by Launch-bury et al. [45]. The method is similar to the key extraction protocol in SePCAR.It works via a lookup table where all the numbers with their inverse in F(256) arelisted. This is depicted in Table 4.2. Note that this method avoids the calculation ofthe affine transform of the S-Box.

The method is implemented via equality tests between the input of S-Box andthe indices of the lookup table. The results are then multiplied with the corre-sponding value in the lookup table where afterwards, we XOR the results of thesemultiplications. The pseudocode is given as follows.

SboxLookupTable(a) {res[256];

for (i = 0 ... 255) { // in parallel, 3 roundsres[i] = (a == i); // res[i] is 0 or 255

}

for (i = 0 ... 255) {res[i] = res[i] & s_box[i]; // s_box[i] is constant

}

for (i = 0 ... 255) {c = c ^ res[i];

}

return c;}

We can evaluate the equality tests in parallel, this gives us a method that takesonly 3 communication calls, compared to the 4 rounds for the masking method.However, the improvement in latency comes at a cost, the throughput of the methodis diminished. The size complexity of the circuit is equal to O(n2n) with n thesize of the input. Thus, the arithmetic cost is exponential, same for the number ofbits sent through the network, whereas the depth of the circuit is log(n). Table 4.1gives an overview of the different methods to calculate an S-Box call over MPC. The

51


implementation by Launchbury et al. [45] achieves a fast AES call with a latency of14ms without key expansion.

4.2.3 Masked Lookup Table Method

The lookup table method gives a good indication on how we might be able to reducethe number of communication rounds needed for modular inversion. The lookuptable method allows for a fast S-Box call, although the throughput is reduced. Bymasking the S-Box lookup table we can generate an offline phase which allows us toparallelise the work and create an online phase which costs 1 round.

We generate a shared random number [r], the S-Box lookup table is representedas {(i, i−1) : i ∈ [0, 255]}, we use the shared random number to mask the lookuptable, i.e., {(i+ r, i−1) : i ∈ [0, 255]}. The first elements in the lookup table, i.e., i+ r,are then opened. An example is given in Table 4.3. We create the following method,where the arrayms_box denotes the masked S-Box lookup table.

MaskedLookupTable(x) {r = share_random();

x = x ^ r;

mask = open(x); // 1 round

for (i = 0 ... 255) {if (mask == ms_box[i][0]) {

return ms_box[i][1];}

}}

If we assume we have access to such a masked lookup table, e.g., from a prepro-cessing phase, we create a method that requires only 1 round. However, note thatthis method is not secure as the indices in the lookup table monotonically go from 0to 255, thus we need to secretly permute this lookup table first. It is obvious that thecreation of these masked lookup tables can be done in an offline phase where wecan make all these lookup tables in parallel. To secretly permute a list is costly, thebest known result works in O(n log(n)) rounds with n the length of the vector [52].Instead, we give alternative methods to create such a masked S-Box lookup table.

This method was discovered separately and published in 2017 by Keller et al. [47],where they create the masked lookup tables in a different way. Their method onlyrequires N− 2 AND gates, with N the size of the lookup table, whereas this methodrequires log2(N)N AND gates, the latency of the methods are the same. Keller et al.further improve this result by working over a larger binary field, where they reportto have computed AES calls in 0.9ms with a throughput of 230000 AES calls persecond using 32 threads.

52

4.2. Improved S-Box Calls over MPC

Table 4.3: Masked S-Box lookup table of size 256 with a shared random numberr. Note that this lookup table is only secure if we secretly permute it between theparties.

index inverser [0]

r+ 1 [1]r+ 2 [2−1]

......

r+ 254 [254−1]r+ 255 [255−1]

Table 4.4: Labels of the permuted lookup tables for the first masking method.

0 1 . . . 255

0 01 12 2−1

......

254 254−1

255 255−1

1 12 2−1

3 3−1

......

255 255−1

0 0

. . .

255 255−1

0 01 1...

...253 253−1

254 254−1

4.2.4 Create the Masked Lookup Table: First Method

The first method to create the needed masked lookup tables needed by our pre-vious protocol is described as follows. Before the computation the parties create256 cyclically permuted S-Box lookup tables. These lookup tables are public andrepresent all possible cyclic permutations. We index these lookup tables, i.e., to givean index j ∈ [0, 255], this is depicted in Table 4.4. To make a new secretly permutedlookup table, we generate a random number v ∈ [0, 255] and run a protocol whichresembles the previous lookup method. Thus, we make an equality test between vand the indices j. The results are multiplied with the second column in the lookuptable, which are then XORed together. We mask the first column of the lookup tableby an XOR of the random number r with the indices i in the lookup table whichcreates the indices i+ r, which are then opened. This method takes log(n) roundsof communication, with n the size of the input, to create a masked lookup table.For n = 8, the preprocessing phase takes 3 communication rounds as opening thefirst column can be done simultaniously with opening the input for the S-Box call.We get an overall communication cost for an AES call, without key expansion, of13 rounds as opposed to the 30 communication calls from the normal lookup tablemethod. This makes the AES circuit twice as shallow as the method described byLaunchbury et al. [45]. However, we still need to make an analysis on the arithmetic

53


𝑃1

𝑃2 𝑃3

Permute lookup tableMask lookup tableSend to 𝑃2

𝑖 + 𝜈𝑖 + 1 + 𝜈

⋮𝑖 + 𝑛 − 1 + 𝜈

𝑖−1 + 𝑟0(𝑖 + 1)−1 + 𝑟1

⋮(𝑖 + 𝑛 − 1)−1 + 𝑟𝑛−1

Permuted masked lookup table

Lookup table shares

Permute lookup tableShare lookup table

First step

Second step

Figure 4.1: The protocol to create a masked S-Box lookup table via the secondmethod.

cost. The online phase requires only 1 open, 1 XOR and 1 shared random number.The offline phase requires much more as it has an arithmetic cost of O(n2n), with nthe size of the input. In the case we have a small lookup table, the trade-off is verybeneficial. The method is depicted as the first masked lookup method in Table 4.1.

4.2.5 Create the Masked Lookup Table: Second Method

We explain the second method in the case of three independent parties with onesemi-honest adversary, the method is depicted in Figure 4.1.

• The first party P1 generates random numbers v and ri for i going from 0 to255. P1 makes shares of these and sends them to the other parties. P1 takesthe S-Box lookup table, permutes it locally and cyclically. P1 masks the firstcolumn of the lookup table with v and the second column with the ri andsends this masked permuted S-Box lookup table to the second party. This isdone in one communication round.

• The second party P2 takes the received S-Box lookup table and permutes itlocally and cyclically. P2 then proceeds to share this lookup table with the restof the parties. This again costs one communication round.

• All parties then XOR the shared [v] and [ri] for i ∈ [0, 255] with the sharedS-Box lookup table.

• The parties XOR the shared random number [r] with the first column of thelookup table and open the values.

Notice that the third party does not need to do anything, thus the parties do notbear computation burdens equally among themselves. To improve this, we createthree masked lookup tables at once, where every party initialises a new masked

54

4.3. Improved Multiplication over MPC

Table 4.5: Different ways to calculate a multiplication over MPC. The first threemethods are described in the article of Büscher et al. [19]. The inputs consist of nbits.

Algorithm RoundsStandard 2n− 1MulCSA 3dlog2(n)e+ 4Wallace-opt 2dlog2(n)e+ 3Lookup Table dlog2(n)e+ 1Masked Lookup Table 1 +

dlog2(n)e+1# mult

Schönhage-Strassen O(ndlog2(log2(n))e)

lookup table. This method requires only 2 communication rounds. The openingof the first column can be done in the online phase along with the opening of themasked input for the S-Box call. By creating three of these masked lookup tables inparallel, we have a method which requires the parties to send 6168 bits (3 times 257bytes) for three masked lookup tables. We see that this method creates an AES callwith low latency, however again at the cost of throughput. The method is listed asthe second masked lookup method in Table 4.1.

4.3 Improved Multiplication over MPC

While multiplication over MPC is not necessary for the car sharing protocol, it isinteresting to study how well this operation is done over Boolean circuits. Researchis done on multipliers using basic logic gates with the least number of gates andthe least depth. The same is done for multiplication over MPC. The current state-of-the-art can be found in the article of Büscher et al. [19]. This article provides threemethods to secretly compute the multiplication of shares, listed in Table 4.5. Wenext investigate whether we can reduce the number of communication rounds toimprove the current known state-of-the-art.

4.3.1 Multiplication via Lookup Tables

In the case the bit-length of the input arguments is not too large, we can apply thesame method seen in Section 4.2. The lookup table we use for the multiplicationis depicted in Table 4.6. Via equality tests we can, in a secret way, determine whatthe two inputs are equal to. By using an AND gate between the results of theseequality tests we get a matrix which consists of only zeros and a one. This matrix ismultiplied with the lookup table to get a secret sharing of the multiplication of theinputs. This method takes only log2(n) + 1 rounds, however the arithmetic cost isagain very high as we saw earlier.

55


Table 4.6: Lookup table to multiply two shared values. The multiplication is doneover Z, but the value is brought back to F2n .

× 0 1 2 . . . 2n − 2 2n − 10 0 0 0 . . . 0 01 0 1 2 . . . 2n − 2 2n − 12 0 2 4 . . . 2n − 4 2n − 2...

......

.... . .

......

2n − 2 0 2n − 2 2n − 4 . . . 4 22n − 1 0 2n − 1 2n − 2 . . . 2 1

Table 4.7: Masked lookup table to multiply two shared values. The multiplication isdone over Z, but the value is brought back to F2n .

× 0 +w 1 +w 2 +w . . . 2n − 2 +w 2n − 1 +w

0 + v [0] [0] [0] . . . [0] [0]1 + v [0] [1] [2] . . . [2n − 2] [2n − 1]2 + v [0] [2] [4] . . . [2n − 4] [2n − 2]

......

......

. . ....

...2n − 2 + v [0] [2n − 2] [2n − 4] . . . [4] [2]2n − 1 + v [0] [2n − 1] [2n − 2] . . . [2] [1]

Table 4.8: Labels of the permutations of the lookup table for the preprocessing phaseto multiply over MPC.

0 1 . . . n− 1

0

0 0 0 . . . 0 00 1 2 . . . 2n − 2 2n − 10 2 4 . . . 2n − 4 2n − 2...

......

. . ....

...0 2n − 2 2n − 4 . . . 4 20 2n − 1 2n − 2 . . . 2 1

0 0 0 . . . 0 02n − 1 0 1 . . . 2n − 3 2n − 22n − 2 0 2 . . . 2n − 6 2n − 4

......

.... . .

......

2 0 2n − 2 . . . 6 41 0 2n − 1 . . . 3 2

. . .

0 0 0 . . . 0 01 2 3 . . . 2n − 1 02 4 6 . . . 2n − 2 0...

......

. . ....

...2n − 2 2n − 4 2n − 6 . . . 2 02n − 1 2n − 2 2n − 3 . . . 1 0

1

0 2n − 1 2n − 2 . . . 2 10 0 0 . . . 0 00 1 2 . . . 2n − 2 2n − 1...

......

. . ....

...0 2n − 3 2n − 6 . . . 6 30 2n − 2 2n − 4 . . . 4 2

1 0 2n − 1 . . . 3 20 0 0 . . . 0 0

2n − 1 0 1 . . . 2n − 3 2n − 2...

......

. . ....

...3 0 2n − 3 . . . 9 62 0 2n − 2 . . . 6 4

. . .

2n − 1 2n − 2 2n − 3 . . . 1 00 0 0 . . . 0 01 2 3 . . . 2n − 1 0...

......

. . ....

...2n − 3 2n − 6 2n − 9 . . . 3 02n − 2 2n − 4 2n − 6 . . . 2 0

......

.... . .

...

n− 1

0 1 2 . . . 2n − 2 2n − 10 2 4 . . . 2n − 4 2n − 20 3 6 . . . 2n − 6 2n − 3...

......

. . ....

...0 2n − 1 2n − 2 . . . 2 10 0 0 . . . 0 0

2n − 1 0 1 . . . 2n − 3 2n − 22n − 2 0 2 . . . 2n − 6 2n − 42n − 3 0 3 . . . 2n − 9 2n − 6

......

.... . .

......

1 0 2n − 1 . . . 3 20 0 0 . . . 0 0

. . .

1 2 3 . . . 2n − 1 02 4 6 . . . 2n − 2 03 6 9 . . . 2n − 3 0...

......

. . ....

...2n − 1 2n − 2 2n − 3 . . . 1 0

0 0 0 . . . 0 0

56

4.3. Improved Multiplication over MPC

4.3.2 Multiplication via Masked Lookup Tables

Just as we did in the previous section on lookup tables for S-Box calls, we can makea masked lookup table method for the multiplication of shares. The online phaseof the method is very similar to the masked lookup table method for the S-Boxcall. We mask the two inputs, say with r1 and r2, and open them. We search in themasked lookup table, as depicted in Table 4.7, for the opened masked inputs and theparties take the corresponding share. Thus, the online phase costs only one round ofcommunication. To create the masked lookup tables we make use a similar methodto the first method for a masked lookup table for an S-Box call. Note that this lookuptable is considerably larger than the lookup table for the S-Box call.

We start by a list of possible permutations of the multiplication lookup table,depicted in Table 4.8. The parties generate two shared random values [v] and [w].These values correspond to the horizontal and vertical cyclic permutation of thelookup table. The parties compute equality tests between their shared random valueand the indices of the big lookup table. This costs the parties n communicationrounds where they send a total of 2 · 2n · (n− 1) bits. We again cross multiply theresults of the equality tests which costs another communication round. However,this requires the parties to send 22n bits. This creates a 2n by 2n table which consistsof zeros and one 1, this is multiplied locally with the list of permuted lookup tablesas depicted in Table 4.8. The results are then locally XORed to create a randomlypermuted lookup table for the multiplication.

This creates for a method which requires only one round of communicationduring the online phase and just 4 rounds for the offline phase. This is an improve-ment on the current state-of-the-art but it requires us to work over a small field asotherwise the number of permutations of the lookup table is too large. As shown byKeller et al. [47], by embedding F2 in a bigger binary field F2k the number of bitssent can be reduced by using a clever “demux” operation.

By using this masked lookup table method we can optimise every operation inthe same way, e.g., additions, equality tests, inequality tests, etc... This creates amethod which, for every operation over a small field, requires only one communi-cation round and a small preprocessing phase, trading off throughput for reducedlatency.

4.3.3 The Schönhage-Strassen algorithm on base 2

The aforementioned method achieves fast multiplications, however, when the bit-length of the input is too high the method becomes too expensive in terms ofthroughput. Thus, we need a method which can replace a multiplication overlarge integers to multiple multiplications over smaller integers. The well knownSchönhage-Strassen algorithm [53], which uses Fast Fourier Transformations (FFT)to convolve the two numbers instead of multiplying them, does exactly what weneed. Moreover, this algorithm has not yet been implemented over MPC. However,this method was asymptotically the fastest known multiplication algorithm until2007, due to Fürer’s algorithm [54]. We investigate the complexity of the algorithm

57


over MPC to fill this gap in the literature. We explain the algorithm on a high leveltogether with its complexity over MPC. We first start with the code for the algorithmfor only one party, later we investigate the changes when using it over MPC. Thealgorithm works over a chosen base as the algorithm performs over any chosen ring.Typically, the algorithm uses a decimal base, base = 10, however as we are workingover Boolean circuits it is optimal to work over a different base. The parameter lis the number of digits in the set base of the numbers x,y. We work on F2n , thuswe multiply two n bit integers and get an n bit result which effectively removes theoverflow.

FFTMult(x, y, l, base) {

LC[l];for (i = 0 ... l - 1) {

LC[i] = 0;}

w = y;for (i = 0 ... l - 1) {

p = x;for (j = 0 ... l - i - 1) {

LC[i + j] += (w % base) * (p % base);p /= base;

}w /= base;

}

product = 0;carry = 0;index = 1;

for (i = 0 ... l - 1) {LC[i] += carry;product += index * (LC[i] % base);carry = LC[i] / base;index *= base;

}

return product;}

If base is chosen to be equal to 2, we can implement the Schönhage-Strassenalgorithm over MPC where the smaller multiplication, (w % base) * (p % base),is simply an AND gate. We investigate the complexity of this method over the MPCenvironment on base 2, note that l = n. We first remark that the multiplications(w % base) * (p % base) can all be evaluated in parallel. On base 2 this is done inone round, as this is just an AND gate. To make the LC vector, we need to implementan addition. We assume this is done via the Sklansky-opt described in the article ofBüscher et al. [19], which has a depth dlog2(n)e+ 1. To create LC naively, we need

58

4.4. Concluding Remarks

n2 additions, though we can improve this by creating all LC[i] for i ∈ [0,n− 1] inparallel. The additions for each LC[i] can be done using a tree of logarithmic depth,in which case creating LC costs dlog2(n)e(dlog2(dlog2(n+ 1)e)e+ 1) + 1 rounds. Theaddition has a depth of only dlog2(log2(n+ 1))e+ 1 because LC[i] is maximallyequal to n + 1, where we also count in the carry which we add later, meaningLC[i] is of bit-length dlog2(n+ 1)e. Further on, we need to add a carry n− 1 timesto an element in LC, each taking dlog2(dlog2(n+ 1)e)e+ 1 rounds. This means theSchönhage-Strassen algorithm over MPC on base 2 requires

dlog2(n)e(dlog2(dlog2(n+ 1)e)e+ 1) + 1 + (n− 1)(dlog2(dlog2(n+ 1)e)e+ 1)

rounds of communication. Or in short a complexity of O(ndlog2(log2(n))e) asdepicted in Table 4.5.

4.3.4 The Schönhage-Strassen algorithm on base 256

We can combine the lookup table method together with the Schönhage-Strassenalgorithm on base 256 to try and further improve the previous result. Note that achange of the base does not change the complexity but it reduces the run-time ofthe algorithm. Thus, the multiplication (w % 256) * (p % 256) is made via thelookup table method that needs only 4 rounds. The way to create LC still remains thesame. However, note that the number of additions reduces since l becomes smalleras l = dn log256(2)e. The Schönhage-Strassen algorithm on base 256 thus requires

dlog2(n log256(2))e(dlog2(log2(2562 log256(2)n))e+ 1) + 4+

(dn log256(2)e− 1)(dlog2(log2(2562 log256(2)n))e+ 1)

communication rounds. Note, LC[i] is maximally equal to 2562l = 2562 log256(2)n.We can improve the (n−1) part, which is due to the ripple carry, by using generation-propagation trees. This would give the Schönhage-Strassen algorithm a complexityof O(dlog2(n)edlog2(log2(n))e). In certain cases this algorithm can do better thanthe Wallace-opt but asymptotically its complexity is worse.

4.4 Concluding Remarks

If the basic operations over MPC are improved, every structure build on top of thesebuilding blocks are improved as well. To this end, the performance of the basicoperations is key to make protocols using MPC feasible in practice. The goal isset to improve the state-of-the-art of certain operations over Boolean circuits, morespecifically, the S-Box call and the multiplication over MPC. Via a lookup tablemethod the S-Box call and the multiplication can be improved, this can be evenfurther improved by masking this lookup table. The latter results in a method whichrequires only one round of communication during the online phase and an efficientoffline phase. The same method can be extended to work for the multiplication overMPC as well, which again creates a method which requires only a constant number

59


of rounds. Similarly, the masked lookup table method can be used for any operationover a small field where the method requires just one round of communicationduring the online phase and a small offline phase. This creates a method whichmakes every operation in constant rounds. The chapter finishes by research on theSchönhage-Strassen algorithm with the goal to improve the multiplication operationover Boolean circuits over a large field. The method fills a gap in literature as themethod was never described over MPC before. While the method does not improvethe current state-of-the-art, it can lead to more efficient methods to multiply twoshares.

60

Chapter 5

Conclusions and Future Work

5.1 Conclusions

With this work, we helped to complete the protocol protocol for car access provi-sion proposed by Symeonidis et al. [1], SePCAR, by providing a detailed proof ofconcept and an approximation of the run-time of the protocol. Moreover, we haveproposed several tweaks to SePCAR to improve its efficiency and make it feasible fordeployment. Our simulation of SePCAR demonstrates that it allows a consumer toobtain an access token in only 1.55 seconds. This shows that the car access provisionprotocol is practically applicable.

After comparing different possible MPC protocols the work by Araki et al. [39]was chosen to be used for SePCAR. Our simulation succeeds in encrypting a 128 bitblock using AES over MPC in only 53ms. Using the simulation of the MPC protocol,new methods to improve S-Box calls of shares as well as multiplying shares overBoolean circuits have been proposed. The end result is a method using maskedlookup tables to allow fast encryption over MPC. Using the same method, themultiplication operation over MPC for small binary fields has been improved suchthat the multiplication requires only one round of communication during the onlinephase with a small offline phase. To improve multiplication of larger values, theSchönhage-Strassen algorithm over MPC has been investigated. While our proposedmethod does not improve the current state-of-the-art, it fills a gap in literature andit can lead to more efficient methods.

5.2 Future Work

This section reviews possible future work such as improving the performance of theSePCAR protocol, making a demo of SePCAR and further research on symmetricencryption over MPC.

61

5. CONCLUSIONS AND FUTURE WORK

Figure 5.1: Scanning in an MPC circuit.

5.2.1 An Improved Implementation

The current simulation of Araki et al.’s protocol in Chapter 3 makes fast AES calls,however, it is not able to efficiently compute multiple operations calls in paral-lel. This is an important limitation of the software as parallelising operations cansignificantly improve the run-time of protocols.

The software proposed by Büscher et al. [19] overcomes this limitation. Thisconsists of a tool that first sets up a circuit, Boolean or arithmetic, of the MPCfunction. The tool then minimises the multiplicative depth of this circuit by settingall independent gates in the same layer of the circuit. Using such a tool, the MPCprotocol would only consist of an implementation of the four basic operations: share,open, XOR and AND. To compute the function, the implementation scans in theMPC circuit made by the tool. It starts by scanning in the first layer in the MPCcircuit from left to right until the end of that layer is reached. The needed informationwould then be sent to the different parties to perform the nonlinear operations andthe implementation would continue to the next layer. This is depicted in Figure 5.1.

However, to further optimise the depth of the circuit, the tool should be able towork with methods which mask values or need a preprocessing phase, for example,the operations described in Chapter 4. Thus, the tool should also scan in gates whichare working over plain values and it should be able to scan in multiple “open” and“share” gates. To the best of our knowledge, this is currently not possible with thetool proposed by Büscher et al. [19], though perhaps the code can be adapted. Sucha tool is needed not only for research on MPC but also to ease the implementationof cryptographic protocols making use of MPC as this new implementation shouldbe very flexible to adapt.

5.2.2 A Demo of SePCAR

The implementation described above in Subsection 5.2.1 would allow the differentparties to work in a real setting, e.g., the different entities in SePCAR would work ondifferent physical devices. Such an implementation will allow for a proof of conceptbut also a fully working demo with an application for a smartphone, differentservers and perhaps separate hardware to represent the car.

62

5.2. Future Work

5.2.3 Improved Run-Time of SePCAR

The run-time of SePCAR can be improved by running the key expansion of thecar key Kcar just once when the car key is added to the database of the CM. Thesame can be done for the consumer’s second key K2, where the key expansionalgorithm is called once for the CBC-MAC. The encryption using Kcar and K1 canbe run in parallel with the MAC using K2, as explained in Section 3.5. Apart fromthis, the S-Box calls can be improved by using the masked lookup table methodfrom Section 4.2. Using a preprocessing phase which costs 2 rounds, the AES callscan be optimised to need only 10 communication rounds without key expansion.Optimising the key expansion and making more AES calls, with the improved S-Boxcalls, in parallel reduces the amount of communication calls needed for SePCAR to

(5 + 1

)

︸︷︷︸Key extraction

+ 12 + 6 · 10︸︷︷︸AES calls over MPC

= 78.

This significantly improves the run-time of SePCAR, as currently SePCAR needs806 communication rounds.

5.2.4 Improved Symmetric Ciphers over MPC

Cryptographic protocols using MPC are gaining popularity as MPC becomes moreand more practical in the real world setting [55] [56] [57]. The implementation fromSubsection 5.2.1 can be used as a research tool to improve symmetric ciphers in orderto reduce their latency or increase their throughput. For example, this work wasalready able to make some research on this as it investigated different methods toimprove the S-Box call over MPC as seen in Section 4.2. Another potential directionis to investigate the performance of different symmetric ciphers over MPC. In thearticle by Albrecht et al. [58] a comparison between the different known symmetricciphers is given, however the ciphers were not implemented thus only a theoreticcomparison is given. Alongside with investigating and comparing different blockciphers, a comparison between different hash functions over MPC can be made. Tothe best of our knowledge, there is no related work that implements a hash functionover MPC. However, more details and comparisons on this would be appreciatedby the research community as this can lead to better performing symmetric ciphersover MPC and in turn to better cryptographic protocols using MPC.

63

Bibliography

[1] Iraklis Symeonidis, Abdelrahaman Aly, Mustafa A. Mustafa, Bart Mennink,Siemen Dhooghe, and Bart Preneel. SePCAR: A Secure and Privacy-enhancingProtocol for Car Access Provision (Extended Version). Cryptology ePrintArchive, Report 2017/039, 2017. http://eprint.iacr.org/2017/039.

[2] Susan Shaheen and Adam Cohen. Innovative mobility carsharing outlook.University of Berkeley, California, 2013.

[3] Deloitte. Smart mobility: Reducing congestion and fostering faster, greener,and cheaper transportation options. https://www.mysql.com/. AccessedApril, 2017.

[4] ACEA. Carsharing: Evolution, Challenges and Opportunities.https://goo.gl/NTec4l. Accessed April, 2017.

[5] Alexandra Dmitrienko and Christian Plappert. Secure free-floating car sharingfor offline cars. In Proceedings of the Seventh ACM on Conference on Data andApplication Security and Privacy, CODASPY 2017, Scottsdale, AZ, USA, March22-24, 2017, pages 349–360, 2017.

[6] Susan A Shaheen and Adam P Cohen. Car sharing and personal vehicleservices: worldwide market developments and emerging trends. Int. Journal ofSustainable Transportation, 7(1):5–34, 2013.

[7] The Guardian. Hell of a ride: even a PR powerhouse couldn’t get Uber on track.https://goo.gl/UcIihE. Accessed April, 2017.

[8] Daring Fireball. Regarding uber’s new ‘always’ location tracking.https://goo.gl/L1Elve. Accessed April, 2017.

[9] Council of the EU Final Compromised Resolution. General Data ProtectionRegulation. http://www.europarl.europa.eu. Accessed Feb, 2015.

[10] Carmela Troncoso, George Danezis, Eleni Kosta, Josep Balasch, and Bart Pre-neel. PriPAYD: Privacy-Friendly Pay-As-You-Drive Insurance. IEEE Transac-tions on Dependable and Secure Computing, 8(5):742–755, 2011.

65

http://eprint.iacr.org/2017/039

BIBLIOGRAPHY

[11] Josep Balasch, Alfredo Rial, Carmela Troncoso, Bart Preneel, Ingrid Ver-bauwhede, and Christophe Geuens. PrETP: Privacy-Preserving ElectronicToll Pricing. In 19th USENIX Security Symposium, Washington, DC, USA, August11-13, 2010, Proceedings, pages 63–78, 2010.

[12] Florian Kerschbaum and Hoon Wei Lim. Privacy-preserving observation inpublic spaces. In Computer Security - ESORICS 2015 - 20th European Sympo-sium on Research in Computer Security, Vienna, Austria, September 21-25, 2015,Proceedings, Part II, pages 81–100, 2015.

[13] Mustafa A. Mustafa, N. Zhang, G. Kalogridis, and Z. Fan. Roaming electricvehicle charging and billing: An anonymous multi-user protocol. In IEEESmartGridComm, pages 939–945, Nov 2014.

[14] Ronald Cramer, Ivan Damgård, and Jesper Buus Nielsen. Secure MultipartyComputation and Secret Sharing. Cambridge University Press, 2015.

[15] Rashid Sheikh, Beerendra Kumar, and Durgesh Kumar Mishra. A distributed k-secure sum protocol for secure multi-party computations. CoRR, abs/1003.4071,2010.

[16] Adi Shamir. How to share a secret. Commun. ACM, 22(11):612–613, November1979.

[17] Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness theoremsfor non-cryptographic fault-tolerant distributed computation. In Proceedings ofthe Twentieth Annual ACM Symposium on Theory of Computing, STOC ’88, pages1–10, New York, NY, USA, 1988. ACM.

[18] Ivan Damgård, Valerio Pastro, Nigel P. Smart, and Sarah Zakarias. Multipartycomputation from somewhat homomorphic encryption. In Advances in Cryp-tology - CRYPTO 2012 - 32nd Annual Cryptology Conference, Santa Barbara, CA,USA, August 19-23, 2012. Proceedings, pages 643–662, 2012.

[19] Niklas Büscher, Andreas Holzer, Alina Weber, and Stefan Katzenbeisser. Com-piling low depth circuits for practical secure computation. In Computer Security- ESORICS 2016 - 21st European Symposium on Research in Computer Security,Heraklion, Greece, September 26-30, 2016, Proceedings, Part II, pages 80–98, 2016.

[20] O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game. InProceedings of the Nineteenth Annual ACM Symposium on Theory of Computing,STOC ’87, pages 218–229, New York, NY, USA, 1987. ACM.

[21] Gilad Asharov, Yehuda Lindell, Thomas Schneider, and Michael Zohner. Moreefficient oblivious transfer extensions. IACR Cryptology ePrint Archive, 2016:602,2016.

66

BIBLIOGRAPHY

[22] Donald Beaver. Precomputing oblivious transfer. In Advances in Cryptology- CRYPTO ’95, 15th Annual International Cryptology Conference, Santa Barbara,California, USA, August 27-31, 1995, Proceedings, pages 97–109, 1995.

[23] Thomas Schneider and Michael Zohner. Gmw vs. yao? efficient secure two-party computation with low depth circuits. In 17th International Conference onFinancial Cryptography and Data Security (FC’13), volume 7859 of LNCS, pages275–292. Springer, April 2013.

[24] R. Impagliazzo and S. Rudich. Limits on the provable consequences of one-waypermutations. In Proceedings of the Twenty-first Annual ACM Symposium onTheory of Computing, STOC ’89, pages 44–61, New York, NY, USA, 1989. ACM.

[25] David Chaum, Claude Crépeau, and Ivan Damgard. Multiparty uncondition-ally secure protocols. In Proceedings of the Twentieth Annual ACM Symposium onTheory of Computing, STOC ’88, pages 11–19, New York, NY, USA, 1988. ACM.

[26] Gilad Asharov and Yehuda Lindell. A full proof of the BGW protocol forperfectly secure multiparty computation. J. Cryptology, 30(1):58–151, 2017.

[27] Andrew C. Yao. Protocols for secure computations. In Proceedings of the 23rdAnnual Symposium on Foundations of Computer Science, SFCS ’82, pages 160–164,Washington, DC, USA, 1982. IEEE Computer Society.

[28] D. Beaver, S. Micali, and P. Rogaway. The round complexity of secure proto-cols. In Proceedings of the Twenty-second Annual ACM Symposium on Theory ofComputing, STOC ’90, pages 503–513, New York, NY, USA, 1990. ACM.

[29] Andrew Chi-Chih Yao. How to generate and exchange secrets. In Proceedings ofthe 27th Annual Symposium on Foundations of Computer Science, SFCS ’86, pages162–167, Washington, DC, USA, 1986. IEEE Computer Society.

[30] Samee Zahur, Mike Rosulek, and David Evans. Two halves make a whole:Reducing data transfer in garbled circuits using half gates. Cryptology ePrintArchive, Report 2014/756, 2014. http://eprint.iacr.org/2014/756.

[31] Assaf Ben-David, Noam Nisan, and Benny Pinkas. Fairplaymp: A system forsecure multi-party computation. In Proceedings of the 15th ACM Conference onComputer and Communications Security, CCS ’08, pages 257–266, New York, NY,USA, 2008. ACM.

[32] Marshall Ball, Tal Malkin, and Mike Rosulek. Garbling gadgets for booleanand arithmetic circuits. Cryptology ePrint Archive, Report 2016/969, 2016.http://eprint.iacr.org/2016/969.

[33] Marcel Keller, Emmanuela Orsini, and Peter Scholl. Mascot: Faster maliciousarithmetic secure computation with oblivious transfer. Cryptology ePrintArchive, Report 2016/505, 2016. http://eprint.iacr.org/2016/505.

67




BIBLIOGRAPHY

[34] Donald Beaver. Efficient multiparty protocols using circuit randomization.In Advances in Cryptology - CRYPTO ’91, 11th Annual International CryptologyConference, Santa Barbara, California, USA, August 11-15, 1991, Proceedings, pages420–432, 1991.

[35] Ivan Damgård, Marcel Keller, Enrique Larraia, Valerio Pastro, Peter Scholl,and Nigel P. Smart. Practical covertly secure MPC for dishonest majority - or:Breaking the SPDZ limits. In Computer Security - ESORICS 2013 - 18th EuropeanSymposium on Research in Computer Security, Egham, UK, September 9-13, 2013.Proceedings, pages 1–18, 2013.

[36] Jesper Buus Nielsen, Peter Sebastian Nordholt, Claudio Orlandi, and Sai She-shank Burra. A new approach to practical active-secure two-party computation.In Advances in Cryptology - CRYPTO 2012 - 32nd Annual Cryptology Conference,Santa Barbara, CA, USA, August 19-23, 2012. Proceedings, pages 681–700, 2012.

[37] Ivan Damgård and Sarah Zakarias. Constant-overhead secure computation forboolean circuits in the preprocessing model. IACR Cryptology ePrint Archive,2012:512, 2012.

[38] Rikke Bendlin, Ivan Damgård, Claudio Orlandi, and Sarah Zakarias. Semi-homomorphic encryption and multiparty computation. In Advances in Cryp-tology - EUROCRYPT 2011 - 30th Annual International Conference on the Theoryand Applications of Cryptographic Techniques, Tallinn, Estonia, May 15-19, 2011.Proceedings, pages 169–188, 2011.

[39] Toshinori Araki, Jun Furukawa, Yehuda Lindell, Ariel Nof, and Kazuma Ohara.High-throughput semi-honest secure three-party computation with an honestmajority. In Proceedings of the 2016 ACM SIGSAC Conference on Computer andCommunications Security, CCS ’16, pages 805–817, New York, NY, USA, 2016.ACM.

[40] Jun Furukawa, Yehuda Lindell, Ariel Nof, and Or Weinstein. High-throughputsecure three-party computation for malicious adversaries and an honest major-ity. Cryptology ePrint Archive, Report 2016/944, 2016. http://eprint.iacr.org/2016/944.

[41] Dan Bogdanov, Sven Laur, and Jan Willemson. Sharemind: A frameworkfor fast privacy-preserving computations. In Proceedings of the 13th EuropeanSymposium on Research in Computer Security: Computer Security, ESORICS ’08,pages 192–206, Berlin, Heidelberg, 2008. Springer-Verlag.

[42] Mihir Bellare, Joe Kilian, and Phillip Rogaway. The security of the cipher blockchaining message authentication code. J. Comput. Syst. Sci., 61(3):362–399, 2000.

[43] Harish Ramamurthy, BS Prabhu, Rajit Gadh, and Asad M Madni. Wirelessindustrial monitoring and control using a smart sensor platform. IEEE sensorsjournal, 7(5):611–618, 2007.

68



BIBLIOGRAPHY

[44] Tor. TorMETRICS. https://metrics.torproject.org/torperf.html. AccessedApril, 2017.

[45] John Launchbury, Iavor S. Diatchki, Thomas DuBuisson, and Andy Adams-Moran. Efficient lookup-table protocol in secure multiparty computation.SIGPLAN Not., 47(9):189–200, September 2012.

[46] Cavium. Introduction to ethernet latency, 2017. http://www.qlogic.com/Resources/Documents/TechnologyBriefs/Adapters/Tech_Brief_Introduction_to_Ethernet_Latency.pdf.

[47] Marcel Keller, Emmanuela Orsini, Dragos Rotaru, Peter Scholl, Eduardo Soria-Vazquez, and Srinivas Vivek. Faster secure multi-party computation of AESand DES using lookup tables. IACR Cryptology ePrint Archive, 2017:378, 2017.

[48] OpenSSL. Cryptography and SSL/TLS Toolkit. https://www.openssl.org/.Accessed April, 2017.

[49] Octavian Catrina and Sebastiaan de Hoogh. Improved primitives for securemultiparty integer computation. In Security and Cryptography for Networks, 7thInternational Conference, SCN 2010, Amalfi, Italy, September 13-15, 2010. Proceed-ings, pages 182–199, 2010.

[50] Ivan Damgård and Marcel Keller. Secure multiparty AES. In Financial Cryptog-raphy and Data Security, 14th International Conference, FC 2010, Tenerife, CanaryIslands, January 25-28, 2010, Revised Selected Papers, pages 367–374, 2010.

[51] P Chen. Secure multiparty computation for privacy preserving data mining,2012. https://pure.tue.nl/ws/files/47045607/738905-1.pdf.

[52] Artur Czumaj, Przemka Kanarek, Miroslaw Kutylowski, and Krzyztof Lorys.Delayed path coupling and generating random permutations via distributedstochastic processes. In SODA ’99, pages 271–280. SIAM, 1999.

[53] A. Schönhage and V. Strassen. Schnelle multiplikation großer zahlen. Comput-ing, 7(3):281–292, 1971.

[54] Martin Fürer. Faster integer multiplication. In Proceedings of the Thirty-ninthAnnual ACM Symposium on Theory of Computing, STOC ’07, pages 57–66, NewYork, NY, USA, 2007. ACM.

[55] Aysajan Abidin, Abdelrahaman Aly, Sara Cleemput, and Mustafa A. Mustafa.An mpc-based privacy-preserving protocol for a local electricity trading market.In Cryptology and Network Security - 15th International Conference, CANS 2016,Milan, Italy, November 14-16, 2016, Proceedings, pages 615–625, 2016.

[56] Peter Bogetoft, Ivan Damgård, Thomas P. Jakobsen, Kurt Nielsen, Jakob Pagter,and Tomas Toft. A practical implementation of secure auctions based onmultiparty integer computation. In Financial Cryptography and Data Security,

69

http://www.qlogic.com/Resources/Documents/TechnologyBriefs/Adapters/Tech_Brief_Introduction_to_Ethernet_Latency.pdf



https://pure.tue.nl/ws/files/47045607/738905-1.pdf

BIBLIOGRAPHY

10th International Conference, FC 2006, Anguilla, British West Indies, February27-March 2, 2006, Revised Selected Papers, pages 142–147, 2006.

[57] Carsten Baum, Ivan Damgard, and Claudio Orlandi. Publicly auditable securemulti-party computation. Cryptology ePrint Archive, Report 2014/075, 2014.http://eprint.iacr.org/2014/075.

[58] Martin R. Albrecht, Christian Rechberger, Thomas Schneider, Tyge Tiessen, andMichael Zohner. Ciphers for MPC and FHE. IACR Cryptology ePrint Archive,2016:687, 2016.

70


Appendix

Breaking Privacy while Retaining Correctness

In this section we give an example of a malicious adversary attacking a semi-honestsecure MPC protocol. The goal is to break the privacy of the protocol while retainingthe correctness of it. For the example, we make use of the protocol of Bogdanovet al. [41], where the first party P1 is malicious. Note that this protocol is onlyclaimed to be secure against one semi-honest party, instead we want to investigatewhat would happen if an adversary does deviate from the protocol. We assumethat the malicious adversary is able to delay sending shares. Recall that the onlycommunication between parties happens due to multiplications, sharing numbersor opening shares.

Manipulation of Shares

We take a look at the case where we only have one multiplication gate and oneof the inputs is equal to 0. The malicious party P1 is able to either set the otherparties resulting shares to 0 or to keep their resulting shares equal to the shares ofthe second input.

Remember that the multiplication by Bogdanov et al. consists of one localmultiplication and 6 intermediate calculations which require communication. Thisintermediate calculation looks as follows.

• The third party P3 generates α1,α2 ∈ F232 , α1 is given to the first party and α2is given to the second party.

• The first party calculates their masked share x1 +α1 and shares this with thesecond party. The second party does the same and shares x2 +α2 with the firstparty.

• Each party calculates their new shares.The first party calculates (x1 +α1)(x2 +α2) + x1(x2 +α2).The second party calculates x2(x1 +α1).The third party calculates α1α2.

We describe step by step how P1 manipulates the other party’s shares. We look atthe multiplication between 0 and y.

71

APPENDIX

• P1 knows: [y]1.

• P2 has: [0] and [y]2.

• P3 has: [0] and [y]3.

Note that these intermediate multiplications happen in parallel thus P1 can delaythe answer until P1 receives the needed shares.

Step 1: Local Addition

Each party multiplies their two shares locally. Note that P2 and P3 multiply theirshare with 0. Thus, we have the following resulting shares:

• P1 learns: [y]1,

• P2 adds: 0,

• P3 adds: 0.

Step 2: P1 First, P3 Second, P2 Third

Here P1 sends back −α1 instead of the right share. Thus, we have the followingresulting shares:

• P1 learns: α1, α2 + [y]3,

• P2 adds: α1α2,

• P3 adds: −α1[y]3.

72

APPENDIX


P1 sends back −δ1δ2β1

instead of the right share. Note that P1 learns δ1, δ2 in anotherround, P1 can delay the answer until this is received. Thus, we have the followingresulting shares:

• P1 learns: β1, β2,

• P2 adds: β1β2,

• P3 adds: −δ1δ2.


P1 sends back −γ1 instead of the right share. Thus, we have the following resultingshares:

• P1 learns: γ1, [y]2 + γ2,

• P2 adds: −γ1[y]2,

• P3 adds: γ1γ2.

73

APPENDIX


P1 sends back −β1β2δ1

instead of the right share. Note that P1 learns β1,β2 in anotherround, though P1 delays the answer until this is received. Thus, we have thefollowing resulting shares:

• P1 learns: δ1, δ2,

• P2 adds: −β1β2,

• P3 adds: −δ1δ2.


P1 sends α1 and −[y]3 − α2 instead of a random number. The values P1 sends arefrom the other intermediate multiplications. Thus, we have the following resultingshares:

• P2 adds: −α1α2,

• P3 adds: [y]3α1.

74

APPENDIX


P1 sends γ1 and −[y]2 − γ2 instead of a random number. The values P1 sends arefrom the other intermediate multiplications. Thus, we have the following resultingshares:

• P2 adds: γ1[y]2,

• P3 adds: −γ1γ2.

Resulting Shares

We add the shares of P2 from the previous 7 steps to gain the resulting share of P2,we do the same for P3. We end up with the following shares:

• P2 has: α1α2 +β1β2 − γ1[y]2 −β1β2 −α1α2 + γ1[y]2 = 0,

• P3 has: −α1[y]3 − δ1δ2 + γ1γ2 − δ1δ2 + [y]3α1 − γ1γ2 = 0.

Thus, the resulting shares of P2 and P3 are brought to zero. Note that by adding a1 to the malicious share P1 sends to P3 in step 2 we bring P3’s share to the originalsecond input. The same can be done to the share of P2. Thus, P1 can transformthe multiplication to the identity operation. P1 is also capable of adding knownparameters to P2 and P3’s share by adding these parameters in the answer in step3 and step 5. Finally note that P1 did not learn anything about y during thiscommunication, P1 only learns randomness.

The Attacker’s Possibilities

In conclusion we sum up the possibilities of the malicious adversary.

• When multiplying shares: given one input is 0, the malicious adversary canset the resulting shares of all parties to 0.

• When multiplying shares: given one input is 0, the malicious adversary canset the other party’s share to their original nonzero input. The adversary isalso capable of adding known parameters to these shares or scale P2 or P3’snonzero input by a chosen constant.

75

APPENDIX

• Given one input is known: the other input can be determined when we knowthe result of the gate (also if one input is equal to 0, the attack follows parallelto the one in the previous subsection).

• The malicious adversary can delay giving the shares when a share is opened.With this technique the adversary might learn about the other parties inputsand send back shares in such a way that correctness is preserved.

An attacker can use these techniques to learn about the private information of theother parties and manipulate the output of the circuit. If the malicious adversarylearns all the inputs in the circuit or manipulates the circuit in an intelligent man-ner the adversary may learn the inputs of the other parties while preserving thecorrectness of the protocol by manipulating the sent shares of the opening protocol.If the MPC circuit has multiple open gates, the malicious party can easily learn allthe other parties inputs and thus break the protocol’s privacy while retaining itscorrectness.

Paper: SePCAR: A Secure and Privacy-enhancing Protocolfor Car Access Provision

The following paper has been submitted to ESORICS 2017. Several contributionswere made to this work, e.g., the implementation described in section 3.3.1, improve-ments to make the scheme more feasible and a detailed analysis on the complexityof the protocol.

76

SePCAR: A Secure and Privacy-enhancingProtocol for Car Access Provision

(Extended Version)

Iraklis Symeonidis1, Abdelrahaman Aly1, Mustafa A. Mustafa1, BartMennink2, Siemen Dhooghe3, Bart Preneel1

1 imec-COSIC, KU Leuven, Belgium [email protected] Radboud University, The Netherlands [email protected]

3 KU Leuven, Belgium [email protected]

Abstract. We present an efficient secure and privacy-enhancing pro-tocol for car access provision, named SePCAR. The protocol is fullydecentralised and allows users to share their cars conveniently in sucha way that the security and privacy of the users is not sacrificed. Itprovides generation, update, revocation, and distribution mechanismsfor access tokens to shared cars, as well as procedures to solve disputesand to deal with law enforcement requests, for instance in the case ofcar incidents. We prove that SePCAR meets its appropriate securityand privacy requirements and that it is efficient: our practical efficiencyanalysis through a proof-of-concept implementation shows that SePCARtakes only 1.55 seconds for a car access provision.

1 Introduction

As opposed to the traditional car ownership, the idea of car sharing, which allowsusers to share their cars conveniently, is gaining popularity. Statistics have shownthat the worldwide number of users for car sharing services has grown from 2012to 2014 by 170% (4.94 million) [1–4] with a tendency to increase by 2021 [5].With the use of portable devices and in-vehicle telematics, physical car keys areslowly becoming obsolete. Keyless car Sharing Systems (KSSs) allow car ownersto rather use their portable devices such as smartphones to distribute temporarydigital car keys (access tokens) to other users and several car manufacturers(including Volvo [6], BMW [7] and Toyota [8]) have started investing in suchsystems. Moreover, unlike traditional car rental companies, KSSs can provide arelatively inexpensive alternative to users who need a car occasionally and on-demand [9]. The use of KSSs can also contribute to a decrease in the number ofcars, effectively reducing CO2 emissions [10] and the need for parking space [11].

In spite of these advantages, information collection in car sharing systemsdoes not only jeopardise a system’s security, but also the users’ privacy. Uberused a tool called “Hell” to spy on their rival company drivers [12], whereastheir mobile app always tracks their users’ locations [13]. In short, an adversarymay try to eavesdrop and collect information exchanged within the KSS, tamperwith the car sharing details, extract the key of a car stored in untrusted devices,generate a rogue access token to maliciously access a car or to deny havingaccessed a car. Regarding users’ privacy, an adversary may try to correlate and

link two car sharing requests for the same user or the car, to identify which userused which car and deduce the users’ sharing preferences. These preferencescan be established by collecting information about sharing patterns such asrental time, duration, pickup location, when, where and with whom someoneis sharing a car. An adversary may even attempt to infer sensitive informationabout users such as racial and religious beliefs [14] or their health status, byidentifying users who use cars for disabled passengers or visit hospitals regularly.Sensitive personal data are related to fundamental rights and freedoms, and meritprotection regarding the collection and processing as it is articulated in thenew EU General Data Protection Regulation (GDPR) [15]. A KSS may furtherintroduce various other concerns with respect to connectivity issues [4], car keyrevocations in case users’ device is stolen [16, 17], and the fact that malicioususers may attempt to manipulate or even completely destroy potential forensicevidence on the car or their devices.

A naive way to mitigate the security and privacy concerns is to implementa peer-to-peer protocol between both the users and the car. The car owner cangenerate a temporary access token for her car using the car key and distributeit to the other user, the consumer, who can use the token to access the car.This approach has two main limitations: (i) the owner and the consumer maynot trust each other, thus affecting the accountability of the system, and (ii) theowner has to have a copy of the car key on her personal device which is proneto get lost or stolen. These limitations can be overcome by having a centralisedentity, which is trusted by both users, to perform the access token generation onbehalf of the car owner. However, such a centralised entity will have to be fullytrusted, which might not be realistic under real world scenarios. It can jeopardisethe users’ privacy as it will have access to users’ booking details and car keys.

Our Contributions. We design a concrete and fully decentralised secure andprivacy-enhancing protocol for car access provision, named SePCAR. The pro-tocol provides generation and distribution of access tokens for car access provi-sion, as well as update and revocation operations used for facilitating mutuallyagreed modifications of the booking details and protecting against misbehavingconsumers, respectively. It internally uses secure multiparty computation to fa-cilitate forensic evidence provision in case of car incidents or at the request oflaw enforcement. SePCAR is described in detail in Section 4.

We prove that the protocol fulfils the desired security and privacy require-ments bound to the standards of connected cars. First, departing from Syme-onidis et al. [18], we give a detailed list of security and privacy requirements inSection 2. Then, in Section 5, we prove that SePCAR meets its security andprivacy requirements as long as its underlying cryptographic primitives (listedin Section 3) are secure.

Our theoretical complexity and practical efficiency analysis in Section 6demonstrates SePCAR’s competitiveness. In particular, we implemented a pro-totype as a proof-of-concept in C++ and we achieved a car access provision in≈ 1.55 seconds.

Related Work. Enev et al. [19] showed that it is possible to reach high identifi-cation rates of drivers, from 87% to 99% accuracy, based on data collected by the

2

Information flow

Authorities

OBU

Owner PDs

Consumer PDs

DatabasePersonal DeviceKey-less Sharing Management SystemOn-Board Unit

DBPDKSMSOBUPublic Ledger

KSMS

Car ManufacturerDB

Fig. 1. System model of a physical Keyless car Sharing System (KSS) [18].

sensors of a car from 15 minutes of open-road driving. Troncoso et al. [20] pro-posed a pay-as-you-drive scheme that enhances the location privacy of driversby sending only aggregated data to insurance companies. Balasch et al. [21]proposed an electronic toll pricing protocol where a car’s on-board unit calcu-lates locally the driver’s annual toll fee while disclosing a minimum amount oflocation information. To mitigate colluding (dishonest) users, Floriat et al. [22]presented a privacy-preserving spot checking protocol that allows observations inpublic spaces. Mustafa et al. [23] proposed an anonymous electric vehicle charg-ing protocol with billing support. The EVITA [24] and PRESERVE [25, 26] aredesignated projects on the design and specifications of the secure architecture ofon-board units of cars. Driven by the PRESERVE instantiation, Raya et al. [27]described the need for Vehicular Public Key Infrastructure (VPKI), and Khodaeiet al. [28] proposed a generic pseudonymization approach aiming to preserve theunlinkability of messages exchanged between vehicles and VPKI servers. Noneof these solutions provides a full-fledged keyless car sharing system, though.

Dmitrienko and Plappert [4] designed a secure two-factor authentication pro-tocol using mobile platforms and RFID tags, e.g., smart-cards. However, in con-trast to our solution, their protocol assumes a fully trusted car sharing providerwhich has access to the master key of smart-cards and also collects and storesall the information exchanged between the car provider and their users for everycar access provision.

2 System Model and Requirements

In this section, we describe the system model and functionalities of a KSS. More-over, we specify the threat model, the security, privacy and functional require-ments which it needs to satisfy and the assumptions we will use.

System Model. We follow the KSS system model of Symeonidis et al. [18].See also Fig. 1. Users are individuals who are willing to share their cars, owners(uo), and use cars which are available for sharing, consumers (uc), with the useof Portable Devices (PDs) such as smartphones. An On-Board Unit (OBU) isan embedded or a standalone hardware/software component [29] which is partof the secure access management system of a car. It has a wireless interfacesuch as Bluetooth, NFC or LTE. The Car manufacturer (CM) is responsible for

3

generating and embedding a digital key into each car. These keys are used forcar sharing and are stored in the manufacturers’ Database (DB). The KeylessSharing Management System (KSMS) is a complex of multiparty computation(MPC) servers that assists owners with a car access token generation, distribu-tion, update and revocation. Each server individually retrieves its share of thecar key, Kcar, and the servers jointly encrypt the booking details, MB , to gen-erate an access token, AT car. The access token is published on a Public Ledger(PL), which serves as a public bulletin board that guarantees the integrity of thedata [30]. The booking details are typically agreed upon by owner and consumerprior to the beginning of the protocol.

Threat Model. Within the KSS the KSMS, the CM, and the PL are consideredhonest-but-curious entities. They will perform the protocol honestly, but theyare curious to extract private information about users. Owners are passive adver-saries while consumers and outsiders may be malicious. The car’s OBU is trustedand equipped with Hardware Security Module (HSM) [25, 31] that supports se-cure key storage and cryptographic operations such as symmetric and public keyencryption, following the EVITA [24] and PRESERVE [25] specifications. Users’PDs are untrusted as they can get stolen, lost or broken.

Protocol Design Requirements. The keyless car sharing system should sat-isfy the following security, privacy, and functional requirements, which we denoteby SR, PR and FR, respectively. Here, we recall that MB refers to the bookingdetails, AT car the access token to the car and Kcar the car key.

– SR1 - Confidentiality of MB. No one but the shared car, uo and uc shouldhave access to MB .

– SR2 - Authenticity of MB. The shared car should verify the origin andintegrity of MB from uo.

– SR3 - Confidentiality of AT car. No one but the shared car and uc shouldhave access to AT car.

– SR4 - Confidentiality of Kcar. No one but the shared car and the car man-ufacturer should have access to Kcar.

– SR5 - Backward and forward secrecy of AT car. Compromise of a key usedto encrypt any AT car should not compromise other tokens (future and past)published on the PL of any honest consumer.

– SR6 - Non-repudiation of origin of AT car. The uo should be able to proveto uc and the shared car that AT car delivered to the car was originated byuo.

– SR7 - Non-repudiation of delivery of AT car. The uc should be able to proveto uo that the agreed AT car was delivered to the shared car.

– PR1 - Unlinkability of uc and the car. No one but the shared car, uo and ucshould be able to link two booking requests of the same uc for the car.

– PR2 - Anonymity of uc and the car. No one but the shared car, uo and ucshould learn the identity of uc and the car.

– PR3 - Undetectability of AT car operation. No one but the shared car, uo anduc (if necessary) should be able to distinguish between AT car generation,update and revocation.

4

– PR4 - Forensic evidence provision. The KSMS should be able to provideauthorities with forensic evidence for an access provision to a car at lawenforcement requests without violating the other users’ privacy.

– FR1 - Offline authentication. Access provision should be provided for loca-tions where cars have limited (or no) network connection.

Assumptions. For SePCAR, we assume that before every evaluation, the book-ing details are agreed upon by owner and consumer, but that both keep thesebooking details confidential against external parties. SePCAR relies on PKI in-frastructure [11, 25, 28], and we assume that each entity has her private/publickey pair with their corresponding digital certificates distributed authentically.The communication channels are secure and authenticated among entities usingSSL-TLS and NFC. For an OBU, it is reasonable to assume that the cost forany adversary to perform a physical attack while renting a car is higher thanthe adversary’s capabilities due to the presence of the HSM [25, 31]. The MPCservers are held by non-colluding organisations, i.e., organisations with conflict-ing interests such as authorities, owner unions and car manufacturers.

3 Cryptographic Building Blocks

3.1 Cryptographic Functionalities

SePCAR uses the following cryptographic building blocks. The suggested instan-tiations are the ones used in our proof-of-concept implementation.

– σ ← sign(Sk,m) and true/false← verify(Pk,m, σ) are public key operationsfor signing and verification respectively. These can be implemented usingRSA.

– z ← prf(K, counter) is a pseudorandom function (PRF) using as input akey and a counter. This function can be implemented using CTR mode withAES (as the message input is small).

– c ← enc(Pk,m) and m ← dec(Sk, c) are public key encryption and decryp-tion functions. These can be implemented using RSA.

– c← E(K,m) and m← D(K, c) are symmetric key encryption and decryptionfunctions. These can be implemented using CTR mode with AES.

– v ← mac(K,m) is a symmetric key MAC function. This function can beimplemented using CBC-MAC with AES.4

– z ← hash(m) is a cryptographic hash function. This function can be imple-mented using SHA-2.

We will furthermore use the notation z ← query(x, y) to denote the retrievalof the xth value from the yth database DB (to be defined in Section 4), andz ← query an(y) to denote the retrieval of the yth value from the public ledgerPL through an anonymous communication channel such as Tor [33], aiming toanonymously retrieve a published record submitted using the publish(y) function.

4 CBC-MAC is proven to be secure as long as it is only evaluated on equal-size mes-sages (or on prefix-free messages) [32], which is the case for SePCAR. For variablelength messages, one should resort to encrypted CBC-MAC.

5

3.2 Multiparty Computation

Ben-or et al. [34] (commonly referred to as BGW) and Chaum et al. [35] provedthat it is possible to calculate any function with perfect security in the presenceof active and passive adversaries under the information-theoretic model, as longas there is an honest majority: 1/2 for passive and 2/3 for active adversaries.The former can be achieved by assuming the use of private channels among theservers and the latter using Verifiable Secret Sharing (VSS).

Our protocol is MPC-agnostic, meaning that it does not depend on the solu-tion that implements the MPC functionality, and example protocols that couldbe executed within our protocol are SPDZ [36], BDOZ [37] and MASCOT [38].However, the three-party protocol for Boolean circuits that was recently in-troduced by Araki et al. [39] is fairly suited for our current needs, given itsperformance and threshold properties. Thus, this is the protocol we use in oursimulation. It can perform non-linear operations with relatively high throughputand somewhat low latency (when tested on 10 Gbps connections). The schemeprovides threshold security against semi-honest parties. Note that Furukawa etal. [40] further adapt the protocol to provide security against a malicious adver-sary.

On an incremental setup for KSMS. In essence, our protocol can support an in-cremental setup and deployment where an (l>2)-case of KSMS servers is trivial,e.g., using BGW [34]. The 2-party case setting could also be trivially achieved byusing l-party MPC protocols such as SPDZ [36], however, the forensic propertiesof our setup would no longer be attainable.

Multiparty Computation Functionalities. SePCAR uses the following cryp-tographic functionalities for MPC:

– [x] ← share(x) is used to secretly share an input. This function can be in-stantiated using Araki et al.’s sharing functionality.

– x← open([x]) reconstructs the private input based on the secret shares.– [z]← XOR([x], [y]) outputs a secret shared bit, representing the XOR of se-

cret shared inputs [x] and [y]. Note that for both the arithmetic or Booleancircuits, such functionality could be implemented without requiring any com-munication cost.

– [z] ← AND([x], [y]) outputs a secret shared bit, representing the AND oftwo secret shared inputs [x] and [y]. This function can be instantiated usingAraki et al.’s AND operation.

– [z] ← eqz([x], [y]) outputs a secret shared bit, corresponding to an equalitytest of two secret shared inputs [x] and [y]. This is equivalent to computing

[z]← [x]?= [y] where z ∈ {0, 1}.

– [C] ← E([K], [M ]) secretly computes a symmetric encryption from a secretshared key [K] and a secret shared message [M ]. Several protocols have beenproposed to achieve this, e.g., [41, 42]. We include a succinct review on howto implement AES below.

– [V ]← mac([K], [M ]) secretly computes a MAC from a secret shared key [K]and a secret shared message [M ].

6

Table 1. Notations.

Symbol Description

KSMS, Si, PL, CM, uo, uc Set of KSMS servers, the ith server for i ∈ {1 . . . l}, Public Ledger, Car Manu-facturer, owner, consumer

IDB , IDuo , IDuc , IDcar ID of booking, uo, uc, carCDuc/ACuc , Lcar Set of conditions/access rights under which uc is allowed to access a car, car’s

locationDBCM / DBSi Database that CM holds with (IDuo , IDcaruo , Kcaruo ) / that Si holds with

(IDuo , [IDcaruo ], [Kcaruo ]) for all owners (uo’s) and their registered cars~Duo Car records (IDuo

x , [IDcaruoy ], [K

caruoy ]) of the xth uo for the yth car extracted

(query) from DBSi , where |~Duo | = n

~Dcar The matched (eqz output) yth car key (1

[0] · · · [0]y

[1][0] · · ·n

[0]), where |~Dcar| = nPkx / Skx, Certuc Public/private key pair of the KSS entity x, certificate of uc

MB Booking details, i.e, {hash(Certuc ), IDcar, Lcar, CDuc , ACuc , IDB}σuo , σcar

Access Signature (sign output) of MB with Skuo , and {MB , TScarAccess} with Skcar

Kcar, Kuc , Kuc1 /Kuc

2 Symmetric key of the car, uc’s master key, uc’s session keys generated be (prfoutput) Kuc and counter/counter + 1

Muc , ATuc Concatenation of MB with σuo , a secure access token as the encryption (Eoutput) of Muc with Kcar

CSi Ciphertext (enc output) of session keys {[Kuc1 ], [Kuc

2 ]} with PkSi

[Cuc ] Ciphertext (E output) of {[ATuc ], [IDcar]} with [Kuc1 ]

CB , [CB ] Message digest (mac output) of MB with Kuc2 , and [MB ] with [Kuc

2 ]TSPub

i , TScarAccess Time-stamp of uc accessing the shared car, a record published (publish) on the

PL submitted by Si

Owner (uo)

MB

Consumer (uc)MB

Kuc1 ,Kuc

2

OBU

Kcar

Car

Public Ledger (PL)

TSPubi [CB ] [Cuc ]

14774098 ersdf3tx0 fwefw234. . . . . . . . .14827104 fsd23f0x0 l2jhusa3u

1.1 CSi ← enc(PkSi , {[Kuc1 ], [Kuc

2 ]})

Server 1

[Kcar]

Server i

[Kcar]

Server l

[Kcar]

KSMS

Car manufacturer1.2 IDuo , CSi , [Muc ]

0. [Kcar]

2. [CB ], [Cuc ]

3.1 query an([CB ], [Cuc ])

3.2 AT car, IDcar4. Auth.

Fig. 2. SePCAR high level overview.

On the secure equality test. Various protocols have been proposed to implementthe equality tests (previously referred eqz functionality). Common approachesprovide either constant rounds or a logarithmic number of them on the bit sizeof its inputs, which could be proven more efficient for sufficiently small sizes.Furthermore, they also offer different security levels, i.e., perfect or statisticalsecurity. We refer the reader to the constructions presented in [43–45] for fur-ther details on their implementation and inner working. We assume the use oflogarithmic depth comparison circuits.

On AES over MPC. AES has been the typical functionality used for bench-marking MPC protocols during the last few years. This and its usability onMPC based applications have motivated faster and leaner MPC implementa-tions of the cipher. As it was previously stated, they consider the case where thecomputational parties hold a secret shared key K and a secret shared messageM . The product of the operation is a secret shared AES encrypted ciphertext.We refer the reader to [42, 46–48] for further details and treatment on the stateof the art. Note that in this paper we assume the use of Damgard and Keller [46]with some minor code optimisations.

7

4 SePCAR

In this section, we provide a detailed description of SePCAR. For simplicity andwithout loss of generality, we consider a single owner, consumer and a sharedcar. The description straightforwardly scales to a larger set of owners, consumers,and cars. Table 1 lists the notation used in the paper and Fig. 2 illustrates thehigh-level overview of SePCAR.

SePCAR consists of four steps: session keys generation and data distribution,access token generation, access token distribution and verification and car access.We will discuss these steps in detail in the remainder of the section, with a generaloverview picture given in Fig. 8 in Appendix A. Before discussing these steps,we first discuss a few prerequisite steps which have to be performed. After thediscussion of the fourth (and last) step, we complete the section with an overviewof the possible operations after SePCAR: access token update and revocation.

Prerequisite. Before SePCAR can commence, two prerequisite steps need totake place: car key distribution and setting the details for the car booking.

Car key distribution takes place immediately after the xth owner, IDuox , has

registered her yth car, IDcaruoy , with the KSMS. The KSMS forwards ID

caruoy

to the Car Manufacturer (CM) to request the symmetric key, Kcaruoy , of the car.

The CM retrieves Kcaruoy from its DB, DBCM and generates l secret shares of

Kcaruoy and ID

caruoy , denoted by [K

caruoy ] and [ID

caruoy ], respectively. Then, it

forwards each share to the corresponding KSMS server, i.e., Si. Upon receipt ofthe shares, each Si stores IDuo together with the shares, [ID

caruoy ] and [K

caruoy ],

in its local DB, DBSi . The representations of the DB of CM and Si are shownin Fig. 3. For simplicity, in some parts of SePCAR we will use IDuo , IDcar andKcar instead of IDuo

x , IDcaruoy and K

caruoy .

DBCM =

IDuo1 ID

caruo1 K

caruo1

......

...IDuo

x IDcaruoy K

caruoy

......

...IDuo

m IDcaruon K

caruon

DBSi =

IDuo1 [ID

caruo1 ] [K

caruo1 ]

......

...IDuo

x [IDcaruoy ] [K

caruoy ]

......

...IDuo

m [IDcaruon ] [K

caruon ]

Fig. 3. The car manufacturer CM (left) and the DB of the ith server Si (right).

Car booking allows uo and uc to agree on the booking details, i.e., MB ={hash(Certuc), IDcar, Lcar, CDuc , ACuc , IDB}, where hash(Certuc) is the hashof the digital certificate of uc, L

car is the pick-up location of the car, CDuc isthe set of conditions under which uc is allowed to use the car (e.g., restrictionson locations, time period), ACuc are the access control rights under which ucis allowed to access the car and IDB is the booking identifier. Recall that it isassumed that an owner and a consumer agree on the booking details beforehand.

Step 1: Session Keys Generation and Data Distribution. uc generatestwo symmetric session keys, Kuc

1 and Kuc2 . Key Kuc

1 will be used by each Si

8

Owner (uo) Consumer (uo) S1 . . .Si . . .Sl

msg{SES K GEN REQ, IDB}Kuc

1 ← prf(Kuc , counter)Kuc

2 ← prf(Kuc , counter + 1)counter ← counter + 2[Kuc

1 ]← share(Kuc1 )



1 ], [Kuc2 ]})

end for

σuo ← sign(Skuo ,MB)Muc ← {MB , σuo}[Muc ]← share(Muc)


Fig. 4. Step 1: session keys generation and data distribution.

to encrypt the access token, such that only uc has access to it. Kuc2 will be

used to generate an authentication tag which will allow uc to verify that theaccess token contains MB which was agreed upon during the car booking. Inaddition, uo sends the necessary data to each Si, such that the access token canbe generated. In detail, as it is shown in Fig. 4, uo sends a session-keys-generationrequest, SES K GEN REQ, along with IDB to uc. Upon receipt of the request,uc generates Kuc

1 and Kuc2 using the prf() function instantiated by uc’s master

key, i.e., Kuc and counter and counter+1. Then, uc transforms these into l secretshares, [Kuc

1 ] and [Kuc2 ], one for each Si in such a way that none of the servers will

have access to the keys but that they can jointly evaluate functions using thesekeys securely. Then, it encrypts [Kuc

1 ] and [Kuc2 ] with the public key of each

Si, CSi = enc(PkSi , {[Kuc

1 ], [Kuc2 ]}), such that only the corresponding Si can

access the corresponding shares. Finally, uc forwards to uo an acknowledgmentmessage, SES K GEN ACK, along with IDB and {CS1 , . . . , CSl}.

While waiting for the response of uc, the owner uo signs MB with her privatekey, i.e., σuo = sign(Skuo ,MB). In a later stage, the car will use σuo to verifythat MB has been approved by uo. Then uo transforms Muc = {MB , σuo} intol secret shares, i.e., [Muc ]. Upon receipt of the response of uc, uo forwards toeach Si an access-token-generation request, AT GEN REQ, along with IDuo ,the corresponding CSi and [Muc ].

Step 2: Access Token Generation. The servers generate an access tokenand publish it on the PL. In detail, as it is shown in Fig. 5, upon receipt ofAT GEN REQ from uo, each Si uses the IDuo to extract [Kcar] from DBSi asfollows. Initially, each Si uses IDuo to retrieve the list of identities of all carsand car key shares related to the set of records that correspond to uo. The result

is stored in a vector ~Duo of size n× 3, i.e.,

~Duo =

IDuo [IDcaruo1 ] [Kcar

1 ]...

......

IDuo [IDcaruoy ] [Kcar

y ]...

......

IDuo [IDcaruon ] [Kcar

n ]

,

where n is the number of cars which uo has registered with the KSS.

9

Public Ledger (PL) S1 . . .Si . . .Sl

~Duo ← query(IDuo , DBSi)for y = 1 . . . n do~Dcar

y ← eqz([IDcar], [IDcaruoy ])

end for[Kcar]← ~Dcar × ~Duo

[AT car]← E([Kcar], [Muc ]){[Kuc

1 ], [Kuc2 ]} ← dec(SkSi , CSi)

[Cuc ]← E([Kuc1 ], {[AT car], [IDcar]})

[CB ]← mac([Kuc2 ], [MB ])


Fig. 5. Step 2: access token generation.

To retrieve the record for the car to be shared, each Si extracts [IDcar] from

[Muc ] and performs a comparison with each of the n records of ~Duo using theeqz() function. The comparison outcomes 0 for mismatch and 1 for identifying

the car at position y. The result of each iteration is stored in a vector ~Dcar withsize 1× n, i.e.,

~Dcar =( 1

[0] · · · [0]y

[1][0] · · ·n

[0]).

Each Si then multiplies ~Dcar and ~Duo to generate a third vector of size 1 × 3,i.e.,

~Dcar × ~Duo =(IDuo [ID

caruoy ] [K

caruoy ]

),

from which the share of the car’s secret key, [Kcar], can be retrieved. Then,the KSMS servers Si collaboratively encrypt [Muc ] using the retrieved [Kcar] togenerate an access token for the car in a shared form, [AT car].

As AT car and IDcar need to be available only to uc, a second layer of en-cryption is performed using Kuc

1 . To retrieve the shares of the session keys,{[Kuc

1 ], [Kuc2 ]}, each Si decrypts CSi using its private key. Then, the servers

encrypt [AT car] and [IDcar] with [Kuc1 ] to generate [Cuc ]. In addition, they

generate an authentication tag, [CB ], using the mac() function with [Kuc2 ] and

[MB ] as inputs. Finally, each Si sends to PL an access-token-publication request,AT PUB REQ, along with [CB ] and [Cuc ].

Step 3: Access Token Verification and Distribution. The PL publishesthe shares of the encrypted access token which are then retrieved by uc. Onceretrieved, uc can obtain the access token and use it to access the car. In detail,as it is shown in Fig. 6, upon receipt of AT PUB REQ, PL publishes [CB ], [Cuc ]and TSPub, which is the time-stamp of publishing the encrypted token. ThenPL sends an acknowledgement of publication, AT PUB ACK, along with TSPubito at least one Si which forwards it to uo who, in turn, forwards it to uc.

Upon receipt of AT PUB ACK, uc uses TSPubi to anonymously retrieve [Cuc ]and [CB ] from PL, such that PL cannot identify uc. Then, uc uses the open()function to reconstruct CB and Cuc using the retrieved shares. Next, uc verifiesthe authentication tag CB locally using the mac() function with Kuc

2 and MB

as inputs. In case of successful verification, uc is assured that the token containsthe same details as the ones agreed during car booking. Then, uc decrypts Cuc

using Kuc1 to obtain the access token and the car identity, {AT car, IDcar}.

10

Owner (uo) Consumer (uo) Public Ledger (PL) S1 . . .Si . . .Sl





query an(TSPubi )

TSPubi [CB ] [Cuc ]

14774098 ersdf3tx0 fwefw234. . . . . . . . .


if CB ?= mac(Kuc


1 , Cuc)else

Breakend if

Fig. 6. Step 3: access token distribution and verification.

Step 4: Car Access. The consumer uses the access token to obtain accessto the car. In detail, uc sends {AT car, IDcar,Certuc} to the car using a secureand close range communication channel such as NFC or Bluetooth (see Fig. 7).Upon receipt, the car’s OBU obtains Muc = {MB , σuo} by decrypting AT car

with Kcar. It then performs three verifications. It checks if the access attemptsatisfies the conditions specified in MB . Then, it verifies σuo to be assured thatthe booking details, MB , have not been modified and have been indeed approvedby the car owner. Finally, it verifies the identity of uc. For the last verification,as the OBU receives Certuc (along with the hash(Certuc) in MB), it can useany challenge-response protocol based on public/private key [49] and RFIDs [4].If any of these verifications fails, the OBU terminates the car access processand denies access to the car. Otherwise, it grants uc access to the car, signs{MB , TScarAccess}, where TScarAccess is the time-stamp of granting the access andasynchronously sends msg{σcarAccess, TS

carAccess} to uo.

Access Token Update and Revocation. Upon an agreement between uo anduc to update or revoke an access token, SePCAR can be performed as describedin steps 1-3. The values of an update request can be changed according to newbooking details, MB , whereas for revocation, each of the parameters in MB

can receive a predefined value indicating the revocation action. However, thereare occasions when uo may need to enforce an update or revocation of an accesstoken. To prevent uc from blocking such operations, SePCAR should be executedonly by uo, without the involvement of uc. More detailed, uo generates session

Owner (uo) Car Consumer (uo)msg{AT car, IDcar,Certuc}

{MB , σuo} ← D(Kcar, AT car)verify(Pkuo ,MB , σuo)



Access})msg{σcar



Access)

Fig. 7. Step 4: car access. Dashed lines represent close range communication.

11

keys, requests an access token, queries the PL, and sends the token to the carusing long range asynchronous communication channel such as LTS.

5 Security and Privacy Analysis

We prove that SePCAR satisfies the security and privacy requirements of Sec-tion 2, provided that its underlying cryptographic primitives are sufficiently se-cure. Below theorem statement and proof are informal; a formal description ofthe security models and the stand-alone proof are given in Appendix B.

Theorem 1. If communication takes place over private channels, the MPC isstatistically secure,

– the signature scheme sign is multi-key existentially unforgeable [50],– the pseudorandom function prf is multi-key secure [51],– the public key encryption scheme enc is multi-key semantically secure [52],– the symmetric key encryption scheme E is multi-key chosen-plaintext se-

cure [53],– the MAC function mac is multi-key existentially unforgeable [50], and– the hash function hash is collision resistant [54],

then SePCAR fulfils the security and privacy requirements of Section 2.

Note that, indeed, for each of the keyed cryptographic primitives we requiresecurity in the multi-key setting, as these are evaluated under different keys.For example, sign is used by all owners, each with a different key; enc is usedfor different keys, each for a different party in the KSMS, and E and mac areused for independent keys for every fresh evaluation of the protocol. We refer toBellare et al. [52] for a discussion on generalizing semantic security of public keyencryption to multi-key security; the adaptation straightforwardly generalizes tothe other security models.

Proof (sketch). We treat the security and privacy requirements, and discuss howthese are achieved from the cryptographic primitives, separately. We recall thatconsumer and owner have agreed upon the booking details prior to the evaluationof SePCAR, hence they know each other.

SR1 - Confidentiality of MB. In one evaluation of the protocol, uc, uo, and theshared car learn the booking details by default or design. The KSMS servers onlylearn shares of the booking data, and under the assumption that the MPC isstatistically secure, nothing about the booking data is revealed during the MPC.The outcomes of the MPC are CB and Cuc satisfying

CB = mac(Kuc2 ,MB) , (1)

Cuc = E(Kuc1 , {E(K

caruoy , {MB , σuo}), IDcar}) , (2)

both of which reveal nothing about MB to a malicious outsider due to theassumed security of mac, E, and the independent uniform drawing of the keysKuc

1 and Kuc2 . The nested encryption E does not influence the analysis due to

the mutual independence of the keys Kuc1 and K

caruoy .

12

SR2 - Authenticity of MB. An owner who initiates the access token generationand distribution, first signs the booking details using its private key before send-ing those to the KSMS in shares. Therefore, once the car receives the token andobtains the booking details, it can verify the owner’s signature on the bookingdetails. In other words, the car can verify the source of the booking details, theowner and their integrity. Suppose, to the contrary, that a malicious consumercan get access to a car of an owner uo. This particularly means that it createda tuple (MB , σuo) such that verify(Pkuo ,MB , σuo) holds. If σuo is new, thismeans that uc forges a signature for the secret signing key Skuo . This is impossi-ble by assumption that the signature scheme is existentially unforgeable. On theother hand, if (MB , σuo) is old but the evaluation is fresh, this means a collisionhash(Certuc) = hash(Certuc′), which happens with negligible probability as hashis collision resistant.

SR3 - Confidentiality of AT car. The access token is generated by the KSMSservers obliviously (as the MPC is statistically secure), and only revealed to thepublic in encrypted form, through Cuc of (8). Due to the uniform drawing of thekey Kuc

1 (and the security of the public-key encryption scheme used to transmitthis key), only the legitimate user can decrypt and learn the access token. Itshares it with the car over a secure and private channel.

SR4 - Confidentiality of Kcar. Only the car manufacturer and the car itself holdcopies of the car key. The KSMS servers learn these in shared form, hence learnnothing about it by virtue of the statistical security of the MPC. Retrieving acar key from encryptions made under this key constitutes a key recovery attack,which in turn allows to break the chosen-plaintext security of the symmetric keyencryption scheme.

SR5 - Backward and forward secrecy of AT car. The access token is publishedon the public ledger as Cuc of (8), encrypted under symmetric key Kuc

1 . Everyhonest consumer generates a fresh key Kuc

1 for every new evaluation, using apseudorandom function prf that is secure, i.e., that is indistinguishable from arandom function. This implies that all session keys are drawn independent anduniformly at random. In addition, the symmetric encryption scheme E is multi-key secure. Concluding, all encryptions Cuc are independent and reveal nothingof each other. (Note that nothing can be said about access tokens for malicioususers who may deviate from the protocol and reuse one-time keys.)

SR6 - Non-repudiation of origin of AT car. The car, who is a trusted identity,verifies the origin through verification of the signature, verify(Pkuo ,MB , σuo).The consumer uc verifies the origin through the verification of the MAC function,

CB?= mac(Kuc

2 ,MB). Note that the consumer does not effectively verify AT car,but rather CB , which suffices under the assumption that the MPC servers eval-uate their protocol correctly. In either case, security fails only if the asymmetricsignature scheme or the MAC function are forgeable.

SR7 - Non-repudiation of delivery of AT car. The owner can verify correct de-livery through the verification of the message sent by the car to the owner,verify(Pkcar, {MB , TScarAccess}, σcarAccess) at the end of the protocol. Security breaksonly if the signature scheme is forgeable.

13

PR1 - Unlinkability of uc and the car. The only consumer-identifiable data isin the consumer’s certificate included in the booking details. Note that theseare agreed upon between the consumer and the owner, so the owner learns theidentity of the consumer by default. Beyond that, the consumer only communi-cates with the car, which is supposed to learn the consumer’s identity so thatit can perform proper access control. The consumer consults the public ledgerover an anonymous channel. The booking details are transferred to and from theKSMS, but these are encrypted and do not leak by virtue of their confidentiality(security requirement SR1).

PR2 - Anonymity of uc and the car. The reasoning is identical to that of PR1.

PR3 - Undetectability of AT car operation. Access token generation, update, orrevocation is performed using the same steps and the same type of messages sentto the KSMS and PL. Hence, outsiders and system entities can not distinguishwhich operation has been requested.

PR4 - Forensic evidence provision. In the case of disputes, the informationrelated to a specific transaction (and only this information) may need to bereconstructed. This reconstruction can be done only if the KSMS servers colludeand reveal their shares. In our setting, these servers have competing interests,thus they would not collude unless law authorities enforce them to do so. Due tothe properties of threshold secret sharing, the private inputs can be reconstructedby a majority coalition. This is, if the KSMS consists of three parties, it sufficestwo of such parties to reconstruct the secrets (for semi-honest and maliciouscases).

FR1 - Offline authentication. Note that steps 1-3 of the protocol require a net-work connection, but step 4, car access, is performed using close range communi-cation and with no need of a network connection. The decryption and verificationof the access token can be performed by the car offline (it has its key Kcar andthe owner’s public key Pkuo stored). Sending the confirmation signature σcarAccesscan also be done offline. ut

6 Performance Evaluation

In this section, we provide a theoretical complexity and practical efficiency anal-ysis of SePCAR.

Theoretical Complexity. The complexity of multiparty protocols is typicallymeasured by the number of communication rounds produced by non-linear op-erations, as linear operations can usually be done without any information ex-change and are virtually free of charge. We refer the reader to [55] for an extendedreview on complexity analysis on MPC. In one evaluation of SePCAR, the non-linear operations performed by the KSMS servers are (i) the retrieval of the carkey by means of using multiple calls of the eqz functionality using the IDcar

and their counterparts in ~Dcar as parameters, and (ii) two evaluations of theencryption scheme E and one evaluation of mac.

14

For (i) the evaluations of the eqz functionality, we consider a multiplicativedepth of dlog(|IDcar|)e+ 1, where |IDcar| is the amount of bits in IDcar. Note

that we can parallelize the eqz call for all ~Dcar entries. Therefore, the bulk of theoverhead of extracting the car key comes from implementing the equality test inlogarithmic depth [44]. Besides executing the eqz tests, we also have to performan extra communication round since we need to multiply the result of eachequality test with its corresponding car key. The total number of communicationrounds for (i) is thus dlog(|IDcar|)e+ 1.

For (ii) the two evaluations of the encryption scheme E and the single evalu-ation of mac we use, as mentioned in Section 3, CTR mode with AES and CBC-MAC with AES, respectively. Note that in a single AES evaluation the numberof non-linear operations equals the number of S-Boxes evaluated in these func-tions, but many can be parallelized. Denote by ν the number of communicationrounds needed to encrypt a single 128-bit block using AES. The two evaluationsof CTR mode can be performed in parallel, and cost 2 · ν rounds. The evalua-

tion of CBC-MAC is inherently sequential and costs⌈|MB |128

⌉· ν communication

rounds.The total amount of communication rounds can thus be expressed as

(dlog(|IDcar|)e+ 1

)+ 2 · ν +

⌈ |MB |128

⌉· ν . (3)

Practical Efficiency. Our protocol, as well as above computation, is agnostictowards the underlying multiparty protocol. In our experiments we have incor-porated the 3-party semi-honest protocol by Araki et al. [39], given its relativeefficiency of AES calls compared to alternatives such as Sharemind [56] andothers [57–59]. The upshot of our experiments is that SePCAR needs only 1.55seconds for a car access provision. We elaborate on our simulation below, follow-ing the steps of Section 4. A detailed segregation of the time into the differentsteps is given in Table 2.

Step 1. Recall that step 1 handles the preparation and sharing of the bookingdetails and generation of keys. For enc we use RSA with 2048 bit keys (≈ 2ms)and for sign we use RSA with SHA-2 with a 512 bit output (≈ 50µs). The prfis implemented using AES in CTR mode (≈ 2µs). For all these functions weuse OpenSSL [60]. The share function is implemented by the sharing primitiveintroduced by Araki et al. [39].

Step 2. In this step, the KSMS servers retrieve the car key and perform thecorresponding encryption and other subroutines linked to generating the MAC.We consider the following message configuration size: hash(Certuc) of 512 bits,IDcar of 32 bits, Lcar of 64 bits, CDuc of 96 bits, ACuc of 8 bits, IDB of 32bits and σuo of 512 bits. The booking details MB are of size 768 bits (includingpadding) and the final access token ATuc is of size 1408 bits (including padding).For the dec function we use RSA with 2048 bit keys (≈ 2ms). The symmetricencryption E is implemented in CTR mode and the mac in CBC mode. Asmentioned before, the functions E, mac, and eqz use the basic primitives from

15

Table 2. Performance of SePCAR, where time is averaged over 1000 runs.

Phase Description Time (in sec)

Step 1 Sharing the booking details and keys 0.220± 0.027Step 2 Extracting car key and making access token 1.274± 0.032Step 3 Verifying the access token 0.055 (+1 Tor [62])Total 1.551± 0.043 (+1 Tor)

Araki et al. [39], and we use the multiparty AES implementation of Damgardand Keller [46].

Step 2 also includes the MPC. Using Damgard and Keller [46], a single S-Boxevaluation takes 5 communication rounds. A single evaluation of AES consistsof 20 sequential evaluations of an S-Box, where we included the key expansionand took into account that parallelizable S-Boxes do not add up to the numberof communication rounds, and can thus be encrypted in ν = 100 communica-tion rounds. From (3) we obtain that in our simulation the total number ofcommunication rounds is

(5 + 1

)+ 2 · 100 + 6 · 100 = 806 .

We remark that key expansion for different keys only needs to be performed once,and for multiple evaluations of SePCAR for the same car the round complexityreduces.

Step 3. In this step the consumer retrieves, reconstructs, and verifies the as-signed access token. The PL is implemented using SQLite. The implementationof open again follows the basic primitive given by Araki et al. [39], and mac isimplemented using AES in CBC mode (≈ 13µs).

Step 4. The final step consists of a challenge-response protocol between uc andthe car, but it does not directly affect the performance of SePCAR and we omitit from our implementation.

Environment Settings. We implemented a realistic simulation for SePCAR inC++ and evaluated it using a machine equipped with an Intel i7, 2.6Ghz CPUand 8GB of RAM.5 The communication within the KSMS was simulated usingsocket calls and latency parameters. We used Araki et al. [39] to simulate theLAN latency (≈ 0.13ms) and Ramamurthy et al. [61] for Wi-Fi (≈ 0.50ms). Wedid not assume any specific network configuration for our experimentation.

7 Conclusion

SePCAR is proven to be secure and privacy-enhancing, efficiently performing in≈ 1.55 seconds for a car access provision. We presented a formal analysis of thesecurity and privacy requirements of our protocol and we provided a prototypeas proof-of-concept. As future work, we plan to extend SePCAR to supportadditional operations such as booking and payment.

5 The implementation can be obtained from https://bitbucket.org/Siemen11/sepcar.

16

References

1. Shaheen, S., Cohen, A.: Innovative mobility carsharing outlook. University ofBerkeley, California (2013)

2. Deloitte: Smart mobility: Reducing congestion and fostering faster, greener, andcheaper transportation options. https://www.mysql.com/ Accessed April, 2017.

3. ACEA: Carsharing: Evolution, Challenges and Opportunities.https://goo.gl/NTec4l Accessed April, 2017.

4. Dmitrienko, A., Plappert, C.: Secure free-floating car sharing for offline cars. In:Proceedings of the Seventh ACM on Conference on Data and Application Securityand Privacy, CODASPY 2017, Scottsdale, AZ, USA, March 22-24, 2017. 349–360

5. Bert, J., Collie, B., Gerrits, M., Xu, G.: What’s ahead for car sharing?: The newmobility and its impact on vehicle sales. (2016)

6. Volvo: Volvo Keyless Cars. https://youtu.be/FF6JtS3y1xA Accessed Nov., 2016.7. BMW: DriveNow Car Sharing. https://drive-now.com/ Accessed November, 2016.8. USA TODAY: Toyota will test keyless car sharing. http://tinyurl.com/hl8m6a7

Accessed November, 2016.9. Wielinski, G., Trepanier, M., Morency, C.: Electric and hybrid car use in a free-

floating carsharing system. International Journal of Sustainable Transportation11(3) (2017) 161–169

10. Shaheen, S.A., Cohen, A.P.: Car sharing and personal vehicle services: worldwidemarket developments and emerging trends. Int. Journal of Sustainable Transporta-tion 7(1) (2013) 5–34

11. Naphade, M.R., Banavar, G., Harrison, C., Paraszczak, J., Morris, R.: Smartercities and their innovation challenges. IEEE Computer 44(6) (2011) 32–39

12. The Guardian: Hell of a ride: even a PR powerhouse couldn’t get Uber on track.https://goo.gl/UcIihE Accessed April, 2017.

13. Daring Fireball: Regarding Ubers New Always Location Tracking.https://goo.gl/L1Elve Accessed April, 2017.

14. reddit: Identifying Muslim cabbies from trip data and prayer times.https://goo.gl/vLrW1s Accessed April, 2017.

15. Council of the EU Final Compromised Resolution: General Data Protection Reg-ulation. http://www.europarl.europa.eu Accessed Feb, 2015.

16. statista: Number of smartphone users in the United States from 2010 to2021. https://www.statista.com/statistics/201182/forecast-of-smartphone-users-in-the-us/ Accessed April, 2017.

17. GOV.UK: Reducing mobile phone theft and improving security.https://www.gov.uk/government/publications/reducing-mobile-phone-theft-and-improving-security Accessed April, 2017.

18. Symeonidis, I., Mustafa, M.A., Preneel, B.: Keyless car sharing system: A securityand privacy analysis. In: IEEE International Smart Cities Conference, ISC2 2016,Trento, Italy, September 12-15, 2016. 1–7

19. Enev, M., Takakuwa, A., Koscher, K., Kohno, T.: Automobile driver fingerprinting.PoPETs 2016(1) (2016) 34–50

20. Troncoso, C., Danezis, G., Kosta, E., Balasch, J., Preneel, B.: PriPAYD: Privacy-Friendly Pay-As-You-Drive Insurance. IEEE Trans. Dependable Sec. Comput. 8(5)742–755

21. Balasch, J., Rial, A., Troncoso, C., Preneel, B., Verbauwhede, I., Geuens, C.:PrETP: Privacy-Preserving Electronic Toll Pricing. In: 19th USENIX SecuritySymposium, Washington, DC, USA, August 11-13, 2010, Proceedings. 63–78

22. Kerschbaum, F., Lim, H.W.: Privacy-preserving observation in public spaces. In:Computer Security - ESORICS 2015 - 20th European Symposium on Research inComputer Security, Vienna, Austria, September 21-25, 2015, Proceedings, Part II.(2015) 81–100

17

23. Mustafa, M.A., Zhang, N., Kalogridis, G., Fan, Z.: Roaming electric vehicle charg-ing and billing: An anonymous multi-user protocol. In: IEEE SmartGridComm.(Nov 2014) 939–945

24. EVITA: E-safety Vehicle Intrusion Protected Applications (EVITA).http://www.evita-project.org/ Accessed November, 2016.

25. PRESERVE: Preparing Secure Vehicle-to-X Communication Systems (PRE-SERVE). https://www.preserve-project.eu/ Accessed November, 2016.

26. Stotz, J., Bißmeyer, N., Kargl, F., Dietzel, S., Papadimitratos, P., Schleiffer, C.: Se-curity requirements of vehicle security architecture, preserve-deliverable 1.1 (2011)

27. Raya, M., Papadimitratos, P., Hubaux, J.: Securing vehicular communications.IEEE Wireless Commun. 13(5) 8–15

28. Khodaei, M., Jin, H., Papadimitratos, P.: Towards deploying a scalable &robust vehicular identity and credential management infrastructure. CoRRabs/1601.00846

29. INVERS: Make Mobility Shareable. https://invers.com/ Accessed April, 2017.30. Micali, S.: Algorand: The efficient and democratic ledger. arXiv preprint

arXiv:1607.01341 (2016)31. Trusted Computing Group: TPM 2.0 Library Profile for Automotive-Thin.

http://tinyurl.com/jrklfqj Accessed June, 2016.32. Bellare, M., Kilian, J., Rogaway, P.: The security of the cipher block chaining

message authentication code. J. Comput. Syst. Sci. 61(3) 362–39933. Tor Project: Protect your privacy. Defend yourself against network surveillance

and traffic analysis. https://www.torproject.org/ Accessed April, 2017.34. Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-

cryptographic fault-tolerant distributed computation. In: STOC, ACM (1988) 1–1035. Chaum, D., Crepeau, C., Damgard, I.: Multiparty unconditionally secure protocols.

In: STOC, ACM (1988) 11–1936. Damgard, I., Pastro, V., Smart, N.P., Zakarias, S.: Multiparty computation from

somewhat homomorphic encryption. In: CRYPTO ’12. Volume 7417 of LNCS.,Springer (2012) 643–662

37. Bendlin, R., Damgard, I., Orlandi, C., Zakarias, S.: Semi-homomorphic encryp-tion and multiparty computation. In: EUROCRYPT ’11. Volume 6632 of LNCS.,Springer (2011) 169–188

38. Keller, M., Orsini, E., Scholl, P.: MASCOT: faster malicious arithmetic securecomputation with oblivious transfer. In: Proceedings of the 2016 ACM SIGSACConference on Computer and Communications Security, Vienna, Austria, October24-28, 2016. (2016) 830–842

39. Araki, T., Furukawa, J., Lindell, Y., Nof, A., Ohara, K.: High-throughput semi-honest secure three-party computation with an honest majority. In: Proceedings ofthe 2016 ACM SIGSAC Conference on Computer and Communications Security.CCS ’16

40. Furukawa, J., Lindell, Y., Nof, A., Weinstein, O.: High-throughput secure three-party computation for malicious adversaries and an honest majority. In: Advancesin Cryptology - EUROCRYPT 2017 - 36th Annual International Conference onthe Theory and Applications of Cryptographic Techniques, Paris, France, April 30- May 4, 2017, Proceedings, Part II. 225–255

41. Albrecht, M., Rechberger, C., Schneider, T., Tiessen, T., Zohner, M.: Ciphers forMPC and FHE. Cryptology ePrint Archive, Report 2016/687 (2016)

42. Albrecht, M.R., Rechberger, C., Schneider, T., Tiessen, T., Zohner, M.: Ciphersfor MPC and FHE. In: Annual International Conference on the Theory and Ap-plications of Cryptographic Techniques, Springer (2015) 430–454

43. Damgard, I., Fitzi, M., Kiltz, E., Nielsen, J.B., Toft, T.: Unconditionally secureconstant-rounds multi-party computation for equality, comparison, bits and expo-nentiation. In: TCC 2006. Volume 3876 of LNCS., Springer (2006) 285–304

18

44. Lipmaa, H., Toft, T.: Secure equality and greater-than tests with sublinear onlinecomplexity. In: ICALP (2). (2013) 645–656

45. Catrina, O., Hoogh, S.D.: Improved primitives for secure multiparty integer com-putation. In: SCN. (2010) 182–199

46. Damgard, I., Keller, M.: Secure multiparty AES. In: International Conference onFinancial Cryptography and Data Security, Springer (2010) 367–374

47. Damgard, I., Keller, M., Larraia, E., Miles, C., Smart, N.: Implementing AES viaan Actively/Covertly Secure Dishonest-Majority MPC Protocol. In: Security andCryptography for Networks. Volume 7485 of LNCS., Springer (2012) 241–263

48. Grassi, L., Rechberger, C., Rotaru, D., Scholl, P., Smart, N.P.: MPC-FriendlySymmetric Key Primitives. Cryptology ePrint Archive, Report 2016/542 (2016)

49. Diffie, W., van Oorschot, P.C., Wiener, M.J.: Authentication and authenticatedkey exchanges. Des. Codes Cryptography 2(2) 107–125

50. Goldwasser, S., Micali, S., Rivest, R.L.: A digital signature scheme secure againstadaptive chosen-message attacks. SIAM J. Comput. 17(2) 281–308

51. Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J.ACM 33(4) (1986) 792–807

52. Bellare, M., Boldyreva, A., Micali, S.: Public-key encryption in a multi-user setting:Security proofs and improvements. In: Advances in Cryptology - EUROCRYPT2000, International Conference on the Theory and Application of CryptographicTechniques, Bruges, Belgium, May 14-18, 2000, Proceeding. 259–274

53. Bellare, M., Desai, A., Jokipii, E., Rogaway, P.: A concrete security treatment ofsymmetric encryption. In: 38th Annual Symposium on Foundations of ComputerScience, FOCS ’97, Miami Beach, Florida, USA, October 19-22, 1997. 394–403

54. Rogaway, P., Shrimpton, T.: Cryptographic hash-function basics: Definitions, im-plications, and separations for preimage resistance, second-preimage resistance,and collision resistance. In: FSE. Volume 3017 of LNCS., Springer (2004) 371–388

55. Cramer, R., Damgard, I., Nielsen, J.B.: Secure Multiparty Computation and SecretSharing. Cambridge University Press (2015)

56. Bogdanov, D., Laur, S., Willemson, J.: Sharemind: A framework for fast privacy-preserving computations. In: Computer Security - ESORICS 2008, 13th EuropeanSymposium on Research in Computer Security, Malaga, Spain, October 6-8, 2008.Proceedings. (2008) 192–206

57. Talviste, R.: Applying secure multi-party computation in practice. Ph.D disserta-tion (2016)

58. Laur, S., Talviste, R., Willemson, J.: From oblivious AES to efficient and securedatabase join in the multiparty setting. In: Applied Cryptography and NetworkSecurity - 11th International Conference, ACNS 2013, Banff, AB, Canada, June25-28, 2013. Proceedings. (2013) 84–101

59. Launchbury, J., Diatchki, I.S., DuBuisson, T., Adams-Moran, A.: Efficient lookup-table protocol in secure multiparty computation. SIGPLAN Not. 47(9) (September2012) 189–200

60. OpenSSL: Cryptography and SSL/TLS Toolkit. https://www.openssl.org/ Ac-cessed April, 2017.

61. Ramamurthy, H., Prabhu, B., Gadh, R., Madni, A.M.: Wireless industrial moni-toring and control using a smart sensor platform. IEEE sensors journal 7(5) (2007)611–618

62. Tor: TorMETRICS. https://metrics.torproject.org/torperf.html Accessed April,2017.

63. Stinson, D.R.: Some observations on the theory of cryptographic hash functions.Des. Codes Cryptography 38(2) (2006) 259–277

64. Rogaway, P.: Formalizing human ignorance. In: Progressin Cryptology - VI-ETCRYPT 2006, First International Conferenceon Cryptology in Vietnam, Hanoi,Vietnam, September 25-28, 2006, Revised Selected Papers. (2006) 211–228

19

A SePCAR Complete Representation.

20

Owner (uo) Car Consumer (uc) Public Ledger (PL) S1 . . .Si . . .Sl

MB = {hash(Certuc), IDcar, Lcar, CDuc , ACuc , IDB}msg{SES K GEN REQ, IDB}

Kuc1 ← prf(Kuc , counter)

Kuc2 ← prf(Kuc , counter + 1)

counter ← counter + 2[Kuc

1 ]← share(Kuc1 )



1 ], [Kuc2 ]})

end for

σuo ← sign(Skuo , {MB})Muc ← {MB , σuo}[Muc ]← share(Muc)


~Duo ← query(IDuo , DBSi)for y = 1 . . . n do~Dcar

y ← eqz([IDcar], [IDcaruoy ])

end for[K

caruoy ]← ~Dcar × ~Duo

[AT car]← E([Kcaruoy ], [Muc ])

{[Kuc1 ], [Kuc

2 ]} ← dec(SkSi , CSi)[Cuc ]← E([Kuc

1 ], {[AT car], [IDcar]})[CB ]← mac([Kuc

2 ], [MB ])



msg{M PUB ACK,TSPubi }



query an(TSPubi )

TSPubi [CB ] [Cuc ]

14774098 ersdf3tx0 fwefw234. . . . . . . . .


if CB ?= mac(Kuc


1 , Cuc)else

Breakend if

msg{AT car, IDcar,Certuc}{MB , σuo} ← D(Kcar, AT car)verify(Pkuo ,MB , σuo)



Access})msg{σcar



Access)

Fig. 8. SePCAR complete representation.

21

B Extended Security and Privacy Analysis

We prove that SePCAR satisfies the security and privacy requirements of Sec-tion 2, provided that its underlying cryptographic primitives are sufficiently se-cure. In Section B.1 we describe the security models of the cryptographic prim-itives. Then, the formal reasoning is given in Section B.2.

B.1 Cryptographic Primitives

The security definitions for signature schemes and MAC functions are inspiredby Goldwasser et al. [50], for pseudorandom functions by Goldreich et al. [51],for public key encryption by Bellare et al. [52], and for symmetric key encryptionby Bellare et al. [53].

We will, in fact, need security of the cryptographic primitives in the multi-keysetting, as these are evaluated under different keys. For example, sign is used byall owners uo, each with a different key; enc is used for different keys, each fora different party in the KSMS, and E and mac are used for independent keysfor every fresh evaluation of the protocol. We refer to Bellare et al. [52] for adiscussion on generalizing semantic security of public key encryption to multi-key security; the adaptation straightforwardly generalizes to the other securitymodels.

In below definitions, for a function f , we define by Func(f) the set of allfunctions with the exact same interface as fK . We denote a random drawing by$←−.

Definition 1. Let µ ≥ 1. Consider a signature scheme sign = (keygen, sign, verify).For any adversary A, we define its advantage in breaking the µ-multikey exis-tential unforgeability as

Advµ-eufsign (A) =

Pr(

(Pk1, Sk1), . . . , (Pkµ, Skµ)$←− keygen : Asign(Ski,·)(Pki) forges

),

where “forges” means that A outputs a tuple (i,M, σ) such that verify(Pki,M, σ) =1 and M has never been queried to the i-th signing oracle. We define by

Advµ-eufsign (q, t) the supremum over all adversaries making at most q queries and

running in time at most t.

Definition 2. Let µ ≥ 1. Consider a pseudorandom function prf = (keygen, prf).For any adversary A, we define its advantage in breaking the µ-multikey pseu-dorandom function security as

Advµ-prfprf (A) =

∣∣∣Pr(K1, . . . ,Kµ $←− keygen : Aprf(Ki,·) = 1

)−

Pr(

$1, . . . , $µ$←− Func(prf) : A$i

= 1)∣∣∣ .

We define by Advµ-prfprf (q, t) the supremum over all adversaries making at most

q queries and running in time at most t.

22

Definition 3. Let µ ≥ 1. Consider a public-key encryption scheme enc =(keygen, enc, dec). For any adversary A, we define its advantage in breaking theµ-multikey semantic security as

Advµ-pkeenc (A) =

∣∣∣Pr(

(Pk1, Sk1), . . . , (Pkµ, Skµ)$←− keygen : AO0(Pki) = 1

)−

Pr(

(Pk1, Sk1), . . . , (Pkµ, Skµ)$←− keygen : AO1(Pki) = 1

)∣∣∣ ,

where Ob for b ∈ {0, 1} gets as input a tuple (i,m0,m1) with i ∈ {1, . . . , µ} and

|m0| = |m1| and outputs encPki(mb). We define by Advµ-pkeenc (t) the supremum

over all adversaries running in time at most t.

Definition 4. Let µ ≥ 1. Consider a symmetric-key encryption scheme E =(keygen,E,D). For any adversary A, we define its advantage in breaking theµ-multikey chosen-plaintext security as

Advµ-skeE (A) =

∣∣∣Pr(K1, . . . ,Kµ $←− keygen : AE(Ki,·) = 1

)−

Pr(

$1, . . . , $µ$←− Func(E) : A$i

= 1)∣∣∣ .

We define by Advµ-skeE (q, t) the supremum over all adversaries making at most

q queries and running in time at most t.

Definition 5. Let µ ≥ 1. Consider a MAC function mac = (keygen,mac). Forany adversary A, we define its advantage in breaking the µ-multikey existentialunforgeability as

Advµ-macmac (A) = Pr

(K1, . . . ,Kµ $←− keygen : Amac(Ki,·) forges

),

where “forges” means that A outputs a tuple (i,M, σ) such that mac(Ki,M) = σand M has never been queried to the i-th MAC function. We define byAdvµ-mac

mac (q, t) the supremum over all adversaries making at most q queries andrunning in time at most t.

Finally, we consider the hash function hash to be collision-resistant. We denotethe supremal probability of any adversary in finding a collision for hash in ttime by Advcol

hash(t). The definition is, acknowledgeably, debatable: for any hashfunction there exists an adversary that can output a collision in constant time(namely one that has a collision hardwired in its code). We ignore this techni-cality for simplicity and refer to [54, 63, 64] for further discussion.

B.2 Analysis

We prove that SePCAR satisfies the security and privacy requirements of Sec-tion 2 provided that its underlying cryptographic primitives are sufficiently se-cure.

23

Theorem 2. Suppose that communication takes place over private channels, theMPC is statistically secure, hash is a random oracle, and

Advµo+µcar-eufsign (2q, t) + Advµc-prf

prf (2q, t) + Advl-pkeenc (t)+

Advq+µcar-skeE (2q, t) + Advq-mac

mac (q, t) + Advcolhash(t)� 1 ,

where µo denotes the maximum number of uos, µc the maximum number of ucs,µcar the maximum number of cars, l the number of servers in the KSMS, q thetotal times the protocol gets evaluated, and t the maximum time of any adversary.

Then, SePCAR fulfills the security and privacy requirements of Section 2.

Proof. Recall from Section 2 that uos and CM are honest-but-curious whereasucs and outsiders may be malicious and actively deviate from the protocol. Carsare trusted.

Via a hybrid argument, we replace the pseudorandom functions prf(Kuc , ·)by independent random functions $uc . This step is performed at the cost of

Advµc-prfprf (2q, t) , (4)

as in every of the q evaluations of SePCAR there are two evaluations of a func-tion prf, and there are at most µc instances of these functions. As we assume thatthe MPC is performed statistically secure, we can replace the KSMS by a singletrusted authority (with l interfaces) that is trusted, perfectly evaluates the pro-tocol, and does not reveal/leak any information. Assuming that the public-keyencryption reveals nothing, which can be done at the cost of

Advl-pkeenc (t) , (5)

we can for simplicity replace it with a perfectly secure public-key encryptionρKSMS to the KSMS directly (an encryption does not reveal its origin and con-tent, and only KSMS can magically decrypt), therewith eliminating the fact thatKSMS has l interfaces and has to perform multiparty computation. Now, as thepseudorandom functions are replaced by random functions, the keys to the sym-metric encryption scheme E are all independently and uniformly distributed, andas the public-key encryption scheme is secure, these keys never leak. Therefore,we can replace the symmetric encryption functionalities by perfectly random in-vertible functions, πcaruo for the cars and unique πuc ’s for every new encryptionunder uc’s session keys, at the cost of

Advq+µcar-skeE (2q, t) , (6)

as there are q + µcar different instances involved and at most 2q evaluationsare made in total. Note that this means that, instead of randomly drawing

Kuc1 ← $uc , we now randomly draw πuc

$←− Func(E).We are left with a simplified version of SePCAR, namely one where the

KSMS is replaced by a single trusted authority, the pseudorandom functions arereplaced by independent random drawings (uc uses $uc which generates freshoutputs for every call), public-key encryptions are replaced with a perfectly se-cure public-key encryption function ρKSMS, and symmetric-key encryptions are

24

replaced by perfectly random invertible functions πcaruo and πuc . The simplifiedprotocol is given in Figure 9. Here, the derivation of the car key (or, formally,the random function corresponding to the encryption) from the database is ab-breviated to πcaruo ← query(IDuo , DBKSMS) for conciseness.

We will now treat the security and privacy requirements, and discuss how theseare achieved from the cryptographic primitives, separately. We recall that ucand uo have agreed upon the booking details prior to the evaluation of SePCAR,hence they know each other by design.

SR1 - Confidentiality of MB. In one evaluation of the protocol, uc, uo, thetrusted KSMS, and the shared car learn the booking details by default or de-sign. The booking details only become public through the values CB and Cuc

satisfying

CB = mac(Kuc2 ,MB) , (7)

Cuc = πuc({πcaruo ({MB , σuo}), IDcar}) . (8)

The latter value reveals nothing about MB as πuc is randomly generated forevery evaluation, whereas the former value reveals nothing about MB as Kuc

2 israndomly generated for every evaluation. The nested encryption πuc◦πcaruo doesnot influence the analysis due to the mutual independence of the two functions.

SR2 - Authenticity of MB. An owner who initiates the access token genera-tion and distribution, first signs the booking details using its private key beforesending those to the KSMS in shares. Therefore, once the car receives the tokenand obtains the booking details, it can verify uo’s signature on the booking de-tails. In other words, the car can verify the source of MB , uo, and its integrity.Suppose, to the contrary, that a malicious consumer can get access to a carof an uo. This particularly means that it created a tuple (MB , σuo) such thatverify(Pkuo ,MB , σuo) holds. If σuo is new, this means that uc forges a signaturefor the secret signing key Skuo . Denote the event that this happens by

E1 : A forges sign(Skuo , ·) for some Skuo . (9)

On the other hand, if (MB , σuo) is old but the evaluation is fresh, this means acollision hash(Certuc) = hash(Certuc′). Denote the event that this happens by

E2 : A finds a collision for hash . (10)

We thus obtain that a violation of SR2 implies E1 ∨ E2.

SR3 - Confidentiality of AT car. The access token is generated by the KSMSobliviously (as it is trusted), and only revealed to the public in encrypted form,through Cuc of (8). Due to the uniform drawing of πuc (and the security of ρKSMS

used to transmit this function), only the legitimate user can decrypt and learnthe access token. It shares it with the car over a secure and private channel.

25

SR4 - Confidentiality of Kcar. By virtue of our hybrid argument on the useof the symmetric-key encryption scheme, EKcar got replaced with πcaruo , whichitself is a keyless random encryption scheme. As the key is now absent, it cannotleak.

SR5 - Backward and forward secrecy of AT car. The access token is publishedon PL as Cuc of (8), encrypted using πuc . Every honest uc generates a uniformlyrandomly drawn function πuc for every new evaluation. Therefore, all encryptionsCuc are independent and reveal nothing of each other. (Note that nothing can besaid about access tokens for malicious users who may deviate from the protocoland reuse one-time keys.)

SR6 - Non-repudiation of origin of AT car. The car, who is a trusted identity,verifies the origin through verification of the signature, verify(Pkuo ,MB , σuo).The consumer uc verifies the origin through the verification of the MAC function,

CB?= mac(Kuc

2 ,MB). Note that uc does not effectively verify AT car, but ratherCB . In either case, security fails only if the asymmetric signature scheme or theMAC function are forgeable. The former is already captured by event E1 in (9).For the latter, denote the event that this happens by

E3 : A forges mac(Kuc2 , ·) for some Kuc

2 . (11)

We thus obtain that a violation of SR6 implies E1 ∨ E3.

SR7 - Non-repudiation of delivery of AT car. uo can verify correct deliverythrough the verification of the message sent by the car to the him/her,verify(Pkcar, {MB , TScarAccess}, σcarAccess) at the end of the protocol. Security breaksonly if the signature scheme is forgeable. Denote the event that this happens by

E4 : A forges sign(Skcar, ·) for some Skcar . (12)

We thus obtain that a violation of SR7 implies E4.

PR1 - Unlinkability of uc and the car. The only consumer-identifiable data is inuc’s certificate included in the booking details. Note that these are agreed uponbetween uc and uo, so uo learns the identity of uc by default. Beyond that, uc onlycommunicates with the car, which is supposed to learn uc’s identity so that it canperform proper access control. uc consults PL over an anonymous channel. Thebooking details are transferred to and from the KSMS, but these are encryptedand do not leak by virtue of their confidentiality (security requirement SR1).

PR2 - Anonymity of uc and the car. The reasoning is identical to that of PR1.

PR3 - Undetectability of AT car operation. Access token generation, update, orrevocation is performed using the same steps and the same type of messages sentto the KSMS and PL. Hence, outsiders and system entities can not distinguishwhich operation has been requested.

26

PR4 - Forensic evidence provision. In the case of disputes, the informationrelated to a specific transaction (and only this information) may need to bereconstructed. This reconstruction can be done only if the KSMS servers colludeand reveal their shares. In our setting, these servers have competing interests,thus they would not collude unless law authorities enforce them to do so. Due tothe properties of threshold secret sharing, the private inputs can be reconstructedby a majority coalition. This is, if the KSMS consists of three parties, it sufficestwo of such parties to reconstruct the secrets (for semi-honest and maliciouscases).

FR1 - Offline authentication. Note that steps 1-3 of the protocol require a net-work connection, but step 4, car access, is performed using close range communi-cation and with no need of a network connection. The decryption and verificationof the access token can be performed by the car offline (it has its πcaru0 and uo’spublic key Pkuo stored). Sending the confirmation signature σcarAccess can also bedone offline.

Conclusion. In conclusion, SePCAR operates securely as long as the costs of(4-6), together with the probability that one of the events (9-12) occurs, aresufficiently small:

Advµc-prfprf (2q, t) + Advl-pke

enc (t) + Advq+µcar-skeE (2q, t) + Pr (E1 ∨ E2 ∨ E3 ∨ E4)� 1 .

By design, the probability that event E1 ∨ E4 occurs is upper bounded by

Advµo+µcar-eufsign (2q, t), the probability that event E3 occurs is upper bounded

by Advq-macmac (q, t), and the probability that E2 occurs is upper bounded by

Advcolhash(t). We thus obtain

Pr (E1 ∨ E2 ∨ E3 ∨ E4) ≤ Advµo+µcar-eufsign (2q, t) + Advq-mac

mac (q, t) + Advcolhash(t) ,

which completes the proof. ut

27

Owner (uo) Car Consumer (uc) Public Ledger (PL) KSMS (trusted)

MB = {hash(Certuc), IDcar, Lcar, CDuc , ACuc , IDB}msg{SES K GEN REQ, IDB}

πuc $←− Func(E)Kuc

2 ← $uc

CKSMS ← ρKSMS({πuc ,Kuc2 })

σuo ← sign(Skuo , {MB})Muc ← {MB , σuo}

msg{SES K GEN ACK, IDB , CKSMS}msg{AT GEN REQ, IDuo , CKSMS,Muc}

πcaruo ← query(IDuo , DBKSMS)AT car ← πcaruo (Muc){πuc ,Kuc

2 } ← (ρKSMS)−1(CKSMS)Cuc ← πuc({AT car, IDcar})CB ← mac(Kuc

2 ,MB)

msg{AT PUB REQ,CB , Cuc}

publish(TSPub, CB , Cuc)

msg{M PUB ACK,TSPub}msg{AT PUB ACK,TSPub}

msg{AT PUB ACK,TSPub}query an(TSPub)

TSPub CB Cuc

14774098 ersdf3tx0 fwefw234. . . . . . . . .

msg{CB , Cuc}

if CB ?= mac(Kuc

2 ,MB) then{AT car, IDcar} ← (πuc)−1(Cuc)

elseBreak

end if

msg{AT car, IDcar,Certuc}{MB , σuo} ← (πcaruo )−1(AT car)verify(Pkuo ,MB , σuo)



Access})msg{σcar



Access)

Fig. 9. Simplified representation of SePCAR for the proof of Theorem 2.

28

APPENDIX

Poster

A poster presentation of this work was given to master and PhD students as well asto professors. The presentation took place on the 9th of May 2017 at the ComputerScience department of KU Leuven.

105

Car Access Provision

• Calculating a Functionbetween Multiple Parties

• Correctness:

•The output is calculated correctly

• Privacy:

•Parties only learn their own input and output

• Digital Car Keys

• Share Cars with Users

• Security:

•Data Confidentiality, Data Authentication,…

• Privacy:

•Anonymity, Unlinkability, ForensicEvidence Provision,…

Multiparty Computation

Master Mathematical Engineering

Master studentSiemen Dhooghe

PromotorProf. dr. ir. B.

Preneel

SupervisorsIraklis Symeonidis

Abdelrahaman Aly

Mustafa A. Mustafa

Year2016-2017

Applying Multiparty Computation to Car Access Provision

KU Leuven Faculteit Ingenieurswetenschappen 2017 – 2018

Fiche masterproef

Student: Siemen Dhooghe

Titel: Applying Multiparty Computation to Car Access Provision

Nederlandse titel: Toepassen van Multiparty Computation Technieken op CarpoolingSystemen

UDC: 681.3

Korte inhoud:Car sharing systems such as car2go or Zipcar are becoming more and more popular.Physical key-less car sharing systems allow users to share their cars convenientlywithout the need of physical keys. Such systems introduce several security andprivacy challenges and a solution is currently missing by the state-of-the-art litera-ture. The protocol proposed by Symeonidis et al. [1] provides a protocol designedto protect the system’s security and the users’ privacy for car access provision. Assuch a protocol needs strong security and privacy properties, it relies on multipartycomputation techniques to ensure the privacy of the data given by the differententities in the protocol and a forensics system to retrace this data when an incidentoccurs. Several contributions to the work proposed by Symeonidis et al. [1] are madeduring this work. To support the decentralised architecture, a suitable candidate forthe multiparty protocol is selected by a comparison of the studied protocols withrespect to their performance and their characteristics, e.g., threshold secret sharing,Boolean circuits. Moreover, a proof of concept of the car access provision protocolis implemented. The proof of concept achieves to deliver an access token in 1.55seconds which proves the practicality of the protocol. Several tweaks are made tothe protocol to enhance the operational speed and improve the communication costof the multiparty computation part of the protocol. To this end, different operationsusing multiparty computation are researched, implemented and improved. Morespecifically, novel techniques are proposed for the S-Box call and the multiplicationover Boolean circuits.

Thesis voorgedragen tot het behalen van de graad van Master of Science in deingenieurswetenschappen: wiskundige ingenieurstechniekenPromotor: Prof. dr. ir. Bart PreneelAssessor: Prof. dr. ir. Vincent Rijmen

Prof. dr. Raf VandebrilBegeleider: Iraklis Symeonidis

Dr. Abdelrahaman AlyDr. Mustafa A. Mustafa