J.V. Vos | TU Delft Repository

Practical Secure Computation in the Client-Server Model

Doctoral thesis (2025) - J.V. Vos, Z. Erkin, M. Conti

To compute something securely is to do so in a way that does not reveal (some of) the inputs, intermediate values, or outputs, to certain predetermined parties. For example, a hospital might outsource the computation of patients’ medical analyses to the cloud without the cloud provider being able to extract sensitive medical information. Researchers have proposed cryptographic protocols capable of performing secure computation for any function imaginable. However, there are still technical obstacles that hinder practical deployments of secure computation protocols. In this thesis, we identify four such impracticalities and propose techniques to address them.

A crucial building block that forms the basis of all protocols in this thesis is homomorphic encryption. Like ‘regular’ encryption it protects the encrypted values from being seen. However, it also allows one to perform computations on these encrypted values, without decrypting them. We distinguish between partially-homomorphic encryption schemes, which allow for some specific computations to be performed, and fully-homomorphic encryption schemes, which can perform any computation imaginable.... ...

Oraqle

A Depth-Aware Secure Computation Compiler

Conference paper (2024) - Jelle Vos, Mauro Conti, Zekeriya Erkin

In the past decade, tens of homomorphic encryption compilers have been released, and there are good reasons for these compilers to exist. Firstly, homomorphic encryption is a powerful secure computation technique in that it is relatively easy for parties to switch from plaintext computation to secure computations when compared to techniques like secret sharing. However, the technique is mathematically involved and requires expert knowledge to express computations as homomorphic encryption operations. So, these compilers support users who might otherwise not have the time or expertise to optimize the computation manually. Another reason is that homomorphic encryption is still computationally expensive, so compilers allow users to optimize their secure computation tasks. One major shortcoming of these compilers is that they often do not allow users to use high-level primitives, such as equality checks, comparisons, and AND and OR operations between many operands. The compilers that do are either based on TFHE, requiring large bootstrapping keys that must be sent to the evaluator, or they only work in the Boolean domain, excluding many potentially more performant circuits. Moreover, compilers must reduce the multiplicative depth of the circuits they generate to minimize the noise growth inherent to these homomorphic encryption schemes. However, many compilers only consider reducing the depth as an afterthought. We propose the Oraqle compiler, which solves both problems at once by implementing depth-aware arithmetization, a technique for expressing high-level primitives as arithmetic operations that are executable by homomorphic encryption libraries. Instead of generating one possible circuit, the compiler generates multiple circuits that trade off the number of multiplications with the multiplicative depth. If the depth of the resulting circuits is low enough, they may be evaluated using a BFV or BGV library that does not require bootstrapping keys. We demonstrate that our compiler allows for significant performance gains. ...

In the past decade, tens of homomorphic encryption compilers have been released, and there are good reasons for these compilers to exist. Firstly, homomorphic encryption is a powerful secure computation technique in that it is relatively easy for parties to switch from plaintext computation to secure computations when compared to techniques like secret sharing. However, the technique is mathematically involved and requires expert knowledge to express computations as homomorphic encryption operations. So, these compilers support users who might otherwise not have the time or expertise to optimize the computation manually. Another reason is that homomorphic encryption is still computationally expensive, so compilers allow users to optimize their secure computation tasks. One major shortcoming of these compilers is that they often do not allow users to use high-level primitives, such as equality checks, comparisons, and AND and OR operations between many operands. The compilers that do are either based on TFHE, requiring large bootstrapping keys that must be sent to the evaluator, or they only work in the Boolean domain, excluding many potentially more performant circuits. Moreover, compilers must reduce the multiplicative depth of the circuits they generate to minimize the noise growth inherent to these homomorphic encryption schemes. However, many compilers only consider reducing the depth as an afterthought. We propose the Oraqle compiler, which solves both problems at once by implementing depth-aware arithmetization, a technique for expressing high-level primitives as arithmetic operations that are executable by homomorphic encryption libraries. Instead of generating one possible circuit, the compiler generates multiple circuits that trade off the number of multiplications with the multiplicative depth. If the depth of the resulting circuits is low enough, they may be evaluated using a BFV or BGV library that does not require bootstrapping keys. We demonstrate that our compiler allows for significant performance gains.

SoK

Collusion-resistant Multi-party Private Set Intersections in the Semi-honest Model

Conference paper (2024) - Jelle Vos, Mauro Conti, Zekeriya Erkin

Private set intersection protocols allow two parties with private sets of data to compute the intersection between them without leaking other information about their sets. These protocols have been studied for almost 20 years, and have been significantly improved over time, reducing both their computation and communication costs. However, when more than two parties want to compute a private set intersection, these protocols are no longer applicable. While extensions exist to the multi-party case, these protocols are significantly less efficient than the two-party case. It remains an open question to design collusion-resistant multi-party private set intersection (MPSI) protocols that come close to the efficiency of two-party protocols. This work is made more difficult by the immense variety in the proposed schemes and the lack of systematization. Moreover, each new work only considers a small subset of previously proposed protocols, leaving out important developments from older works. Finally, MPSI protocols rely on many possible constructions and building blocks that have not been summarized. This work aims to point protocol designers to gaps in research and promising directions, pointing out common security flaws and sketching a frame of reference. To this end, we focus on the semi-honest model. We conclude that current MPSI protocols are not a one-size-fits-all solution, and instead there exist many protocols that each prevail in their own application setting. ...

Practical Verifiable & Privacy-Preserving Double Auctions

Conference paper (2023) - Armin Memar Zahedani, Jelle Vos, Zekeriya Erkin

Double auctions are procedures to trade commodities such as electricity or parts of the wireless spectrum at optimal prices. Buyers and sellers inform the auctioneer what quantity they want to buy or sell at specific prices. The auctioneer aggregates these offers into demand and supply curves and finds the intersection representing the optimal price. In this way, commodities exchange owners in an economically-efficient manner. Ideally, the auctioneer is a trusted third party that does not abuse the information they gain. However, the offers reveal sensitive information about the traders, which the auctioneer may use for economic gain as insider information. These concerns are not theoretical; investigations against auctioneers in electricity and advertisement auctions for manipulating auctions are ongoing. These concerns call for solutions that conduct double auctions in a privacy-preserving and verifiable way. However, current solutions are impractical: To the best of our knowledge, the only solutions satisfying these properties require full interaction of all participants. In this work, we design a more practical solution. We propose the first privacy-preserving and verifiable double auction scheme that does not require traders to interact actively, tailored to electricity trading on (inter)national exchanges. Our solution relies on homomorphic encryption, commitments, and zero-knowledge proofs. In a simulated auction with 256 traders, we observe that traders take up to 10 seconds to generate their order, the auctioneer takes 10 seconds to verify an order, and the auction result is computed and verified in 30 seconds. We extrapolate these results to larger auctions to show the practical potential. ...

Decentralized Private Freight Declaration & Tracking with Data Validation

Conference paper (2022) - Tianyu Li, Jelle Vos, Zekeriya Erkin

In January 2017, a truck crossed the border between Spain and France for the first time using an e-CMR: An electronic version of the primary transport document required for inter-European logistics. Since that crossing, researchers and logistic organizations have proposed a large number of ideas to further digitize Europe’s supply chain. Many of these ideas involve blockchains, but not all of them validate the data that is posted to them. As a result, participants can make illegitimate claims: Even though the blockchain enables transparency and immutability of the data stores, it does not ensure veracity. We provide several examples of works about information sharing in the supply chain that do not perform such validation. One work that does use the blockchain’s validation functionality is DEFEND. DEFEND addresses customs agencies’ lack of information for international freight inspection by tracking shipping containers throughout their journey. As containers pass from one operator to another, the blockchain participants ensure that containers are not doubly spent. In this work, we propose an extension of DEFEND, in which we further extend the capabilities for validation. Moreover, we provide actual cryptographic protocols to preserve participants’ privacy while DEFEND only described privacy on a high level. Finally, by making a more fine-grained distinction between different actors in the chain, we model the entire supply chain from buyer to seller. As a result, the buyer and seller can now track the respective package’s whereabouts through each leg of its journey. ...

Compare Before You Buy

Privacy-Preserving Selection of Threat Intelligence Providers

Conference paper (2021) - Jelle Vos, Zekeriya Erkin, Christian Dörr

In their pursuit to maximize their return on investment, cybercriminals will likely reuse as much as possible between their campaigns. Not only will the same phishing mail be sent to tens of thousands of targets, but reuse of the tools and infrastructure across attempts will lower their costs of doing business. This reuse, however, creates an effective angle for mitigation, as defenders can recognize domain names, attachments, tools, or systems used in a previous compromisation attempt, significantly increasing the cost to the adversary as it would become necessary to recreate the attack infrastructure each time. However, generating such cyber threat intelligence (CTI) is resource-intensive, so organizations often turn to CTI providers that commercially sell feeds with such indicators. As providers have different sources and methods to obtain their data, the coverage and relevance of feeds will vary for each of them. To cover the multitude of threats one organization faces, they are best served by obtaining feeds from multiple providers. However, these feeds may overlap, causing an organization to pay for indicators they already obtained through another provider. This paper presents a privacy-preserving protocol that allows an organization to query the databases of multiple data providers to obtain an estimate of their total coverage without revealing the data they store. In this way, a customer can make a more informed decision on their choice of CTI providers. We implement this protocol in Rust to validate its performance experimentally: When performed between three CTI providers who collectively have 20,000 unique indicators, our protocol takes less than 6 seconds to execute. The code for our experiments is freely available. ...

Multi-party private set intersection protocols for practical applications

Conference paper (2021) - Asli Bay, Zeki Erkin, Mina Alishahi, Jelle Vos

Multi-Party Private Set Intersection (MPSI) is an attractive topic in research since a practical MPSI protocol can be deployed in several real-world scenarios, including but not limited to finding the common list of customers among several companies or privacy-preserving analyses of data from different stakeholders. Several solutions have been proposed in the literature however, the existing solutions still suffer from performance related challenges such as long run-time and high bandwidth demand, particularly when the number of involved parties grows. In this paper, we propose a new approach based on threshold additively homomorphic encryption scheme, e.g., Paillier, which enables us to process the bit-set representation of sets under encryption. By doing so, it is feasible to securely compute the intersection of several data sets in an efficient manner. To prove our claims on performance, we compare the communication complexity of our approach with the existing solutions and show performance test results. We also show how the proposed protocol can be extended to securely compute other set operations on multi-party data sets. ...