[116] Arpita Patra, Thomas Schneider, Ajith Suresh, and Hossein Yalame. ABY2.0: Improved mixed-protocol secure two-party computation. In 30. USENIX Security Symposium (USENIX Security'21), USENIX, Vancouver, B.C., Canada, August 11-13, 2021. To appear. Full version: https://ia.cr/2020/1225. CORE rank A*. [ bib | web ]
[115] Christoph Hagen, Christian Weinert, Christoph Sendner, Alexandra Dmitrienko, and Thomas Schneider. All the numbers are US: Large-scale abuse of contact discovery in mobile messengers. In 28. Network and Distributed System Security Symposium (NDSS'21), Internet Society, San Diego, CA, USA, February 21-24, 2021. To appear. Online: https://ia.cr/2020/1119. CORE rank A*. [ bib | pdf | web ]
Our study of three popular mobile messengers (WhatsApp, Signal, and Telegram) shows that, contrary to expectations, large-scale crawling attacks are (still) possible. Using an accurate database of mobile phone number prefixes and very few resources, we have queried 10% of US mobile phone numbers for WhatsApp and 100% for Signal. For Telegram we find that its API exposes a wide range of sensitive information, even about numbers not registered with the service. We present interesting (cross-messenger) usage statistics, which also reveal that very few users change the default privacy settings. Regarding mitigations, we propose novel techniques to significantly limit the feasibility of our crawling attacks, especially a new incremental contact discovery scheme that strictly improves over Signal's current approach.
Furthermore, we show that currently deployed hashing-based contact discovery protocols are severely broken by comparing three methods for efficient hash reversal of mobile phone numbers. For this, we also propose a significantly improved rainbow table construction for non-uniformly distributed inputs that is of independent interest.
[114] Heiko Mantel, Lukas Scheidel, Thomas Schneider, Alexandra Weber, Christian Weinert, and Tim Weißmantel. RiCaSi: Rigorous Cache Side channel mitigation via selective circuit compilation. In 19. International Conference on Cryptology And Network Security (CANS'20), LNCS, Springer, Vienna, Austria, December 14-16, 2020. CORE rank B. [ bib | web ]
[113] Thomas Schneider. Engineering privacy-preserving machine learning protocols. In Privacy-Preserving Machine Learning in Practice (PPMLP@CCS'20) – CCS'20 Workshop, ACM, Orlando, USA, November 9, 2020. Keynote. To appear. [ bib | DOI | pdf | web ]
Privacy-preserving machine learning (PPML) protocols allow to privately evaluate or even train machine learning (ML) models on sensitive data while simultaneously protecting the data and the model. So far, most of these protocols were built and optimized by hand, which requires expert knowledge in cryptography and also a thorough understanding of the ML models. Moreover, the design space is very large as there are many technologies that can even be combined with several trade-offs. Examples for the underlying cryptographic building blocks include homomorphic encryption (HE) where computation typically is the bottleneck, and secure multi-party computation protocols (MPC) that rely mostly on symmetric key cryptography where communication is often the bottleneck.
In this keynote, I will describe our research towards engineering practical PPML protocols that protect models and data. First of all, there is no point in designing PPML protocols for too simple models such as Support Vector Machines (SVMs) or Support Vector Regression Machines (SVRs), because they can be stolen easily [WPES'19] and hence do not benefit from protection. Complex models can be protected and evaluated in real-time using Trusted Execution Environments (TEEs) which we demonstrated for speech recognition using Intel SGX [INTERSPEECH'18] and for keyword recognition using ARM TrustZone [DATE'20] as respective commercial TEE technologies. Our goal is to build tools for non-experts in cryptography to automatically generate highly optimized mixed PPML protocols given a high-level specification in a ML framework like TensorFlow. Towards this, we have built tools to automatically generate optimized mixed protocols that combine HE and different MPC protocols [CCS'10,NDSS'15,CCS'18]. Such mixed protocols can for example be used for the efficient privacy-preserving evaluation of decision trees [ESORICS'09,TIFS'11,PoPETs'19] and neural networks [ICISC'08,TIFS'11,ASIACCS'18]. The first PPML protocols for these ML classifiers were proposed long before the current hype on PPML started [ICISC'08,ESORICS'09,TIFS'11]. We already have first results for compiling high-level ML specifications via our tools into mixed protocols for neural networks (from TensorFlow) [ARES'20] and sum-product networks (from SPFlow) [ECAI'20], and I will conclude with major open challenges.
[112] Amos Treiber, Alejandro Molina, Christian Weinert, Thomas Schneider, and Kristian Kersting. CryptoSPN: Expanding PPML beyond neural networks. In Privacy-Preserving Machine Learning in Practice (PPMLP@CCS'20) – CCS'20 Workshop, ACM, Orlando, USA, November 9, 2020. To appear. [ bib | pdf | web ]
[111] Fabian Boemer, Rosario Cammarota, Daniel Demmler, Thomas Schneider, and Hossein Yalame. MP2ML: A mixed-protocol machine learning framework for private inference (Extended Abstract). In Privacy-Preserving Machine Learning in Practice (PPMLP@CCS'20) – CCS'20 Workshop, ACM, Orlando, USA, November 9, 2020. Short paper. To appear. [ bib | pdf | web ]
We present an extended abstract of MP2ML, a machine learning framework which integrates Intel nGraph-HE, a homomorphic encryption (HE) framework, and the secure two-party computation framework ABY, to enable data scientists to perform private inference of deep learning (DL) models trained using popular frame- works such as TensorFlow at the push of a button. We benchmark MP2ML on the CryptoNets network with ReLU activations, on which it achieves a throughput of 33.3 images/s and an accuracy of 98.6%. This throughput matches the previous state-of-the-art frameworks.
[110] Niklas Büscher, Daniel Demmler, Nikolaos P. Karvelas, Stefan Katzenbeisser, Juliane Krämer, Deevashwer Rathee, Thomas Schneider, and Patrick Struck. Secure two-party computation in a quantum world. In 18. International Conference on Applied Cryptography and Network Security (ACNS'20), volume 12146 of LNCS, pages 461–480, Springer, Rome, Italy, October 19-22, 2020. Full version: https://ia.cr/2020/411. Acceptance rate 21.5%. CORE rank B. [ bib | DOI | pdf | web ]
Secure multi-party computation has been extensively studied in the past years and has reached a level that is considered practical for several applications. The techniques developed thus far have been steadily optimized for performance and were shown to be secure in the classical setting, but are not known to be secure against quantum adversaries.
In this work, we start to pave the way for secure two-party computation in a quantum world where the adversary has access to a quantum computer. We show that post-quantum secure two-party computation has comparable efficiency to their classical counterparts. For this, we develop a lattice-based OT protocol which we use to implement a post-quantum secure variant of Yao’s famous garbled circuits (GC) protocol (FOCS’82). Along with the OT protocol, we show that the oblivious transfer extension protocol of Ishai et al. (CRYPTO’03), which allows running many OTs using mainly symmetric cryptography, is post-quantum secure. To support these results, we prove that Yao’s GC protocol achieves post-quantum security if the underlying building blocks do.
[109] Johannes Buchmann, Ghada Dessouky, Tommaso Frassetto, Ágnes Kiss, Ahmad-Reza Sadeghi, Thomas Schneider, Giulia Traverso, and Shaza Zeitouni. SAFE: A secure and efficient long-term distributed storage system. In 8. ACM International Workshop on Security in Blockchain and Cloud Computing (SBC'20), ACM, Taipei, Taiwan, October 6, 2020. To appear. Online: https://ia.cr/2020/690. [ bib | DOI | pdf | web ]
Secret sharing-based distributed storage systems are one approach to provide long-term protection of data even against quantum computing. Confidentiality is provided because the shares of data are renewed periodically while integrity is provided by commitment schemes. However, this solution is prohibitively costly and impractical: share renewal requires an information-theoretically secure channel between any two nodes and long-term confidential commitment schemes are computationally impractical for large files. In this paper, we present SAFE, a secret sharing-based long-term secure distributed storage system that leverages a Trusted Execution Environment (TEE) to overcome the above limitations. Share generation and renewal are performed inside the TEE and the shares are securely distributed to the storage servers. We prototype SAFE protocols using a TEE instantiation, and show their efficiency, even for large files, compared to existing schemes.
[108] Lennart Braun, Daniel Demmler, Thomas Schneider, and Oleksandr Tkachenko. MOTION - a framework for mixed-protocol multi-party computation. Cryptology ePrint Archive, Report 2020/1137, September 18, 2020. https://ia.cr/2020/1137. [ bib ]
[107] Marco Holz, Ágnes Kiss, Deevashwer Rathee, and Thomas Schneider. Linear-complexity private function evaluation is practical. In 25. European Symposium on Research in Computer Security (ESORICS'20), volume 12309 of LNCS, pages 401–420, Springer, Surrey, UK, September 14-18, 2020. Full version: https://ia.cr/2020/853. Code: https://encrypto.de/code/linearPFE. Acceptance rate 19.7%. CORE rank A. [ bib | DOI | pdf | web ]
Private function evaluation (PFE) allows to obliviously evaluate a private function on private inputs. PFE has several applications such as privacy-preserving credit checking and user-specific insurance tariffs. Recently, PFE protocols based on universal circuits (UCs), that have an inevitable superlinear overhead, have been investigated thoroughly. Specialized public key-based protocols with linear complexity were believed to be less efficient than UC-based approaches.
In this paper, we take another look at the linear-complexity PFE protocol by Katz and Malka (ASIACRYPT’11): We propose several optimizations and split the protocol in different phases that depend on the function and inputs respectively. We show that HE-based PFE is practical when instantiated with state-of-the-art ECC and RLWE-based homomorphic encryption. Our most efficient implementation outperforms the most recent UC-based PFE implementation of Alhassan et al. (JoC’20) in communication for all circuit sizes and in computation starting from circuits of a few thousand gates already.
[106] Amos Treiber, Alejandro Molina, Christian Weinert, Thomas Schneider, and Kristian Kersting. CryptoSPN: Privacy-preserving sum-product network inference. In 24. European Conference on Artificial Intelligence (ECAI'20), IOS Press, Santiago de Compostela, Spain, Aug 29-Sep 5, 2020. To appear. Online: https://arxiv.org/abs/2002.00801. Acceptance rate 26.8%. CORE rank A. [ bib | pdf | web ]
AI algorithms, and machine learning (ML) techniques in particular, are increasingly important to individuals’ lives, but have caused a range of privacy concerns addressed by, e.g., the European GDPR. Using cryptographic techniques, it is possible to perform inference tasks remotely on sensitive client data in a privacy-preserving way: the server learns nothing about the input data and the model predictions, while the client learns nothing about the ML model (which is often considered intellectual property and might contain traces of sensitive data). While such privacy-preserving solutions are relatively efficient, they are mostly targeted at neural networks, can degrade the predictive accuracy, and usually reveal the network’s topology. Furthermore, existing solutions are not readily accessible to ML experts, as prototype implementations are not well-integrated into ML frameworks and require extensive cryptographic knowledge.
In this paper, we present CryptoSPN, a framework for privacy- preserving inference of sum-product networks (SPNs). SPNs are a tractable probabilistic graphical model that allows a range of exact inference queries in linear time. Specifically, we show how to efficiently perform SPN inference via secure multi-party computation (SMPC) without accuracy degradation while hiding sensitive client and training information with provable security guarantees. Next to foundations, CryptoSPN encompasses tools to easily transform existing SPNs into privacy-preserving executables. Our empirical results demonstrate that CryptoSPN achieves highly efficient and accurate inference in the order of seconds for medium-sized SPNs.
[105] Fabian Boemer, Rosario Cammarota, Daniel Demmler, Thomas Schneider, and Hossein Yalame. MP2ML: A mixed-protocol machine learning framework for private inference. In 15. International Conference on Availability, Reliability and Security (ARES'20), pages 14:1–14:10, ACM, Virtual Event, Ireland, August 25-28, 2020. To appear. Full version: https://ia.cr/2020/721. Code: https://ngra.ph/he. Acceptance rate 21.3%. CORE rank B. [ bib | DOI | pdf | web ]
Privacy-preserving machine learning (PPML) has many applications, from medical image classification and anomaly detection to financial analysis. nGraph-HE enables data scientists to perform private inference of deep learning (DL) models trained using popular frameworks such as TensorFlow. nGraph-HE computes linear layers using the CKKS homomorphic encryption (HE) scheme. The non-polynomial activation functions, such as MaxPool and ReLU, are evaluated in the clear by the data owner who obtains the intermediate feature maps. This leaks the feature maps to the data owner from which it may be possible to deduce the DL model weights. As a result, such protocols may not be suitable for deployment, especially when the DL model is intellectual property.
In this work, we present MP2ML, a machine learning framework which integrates nGraph-HE and the secure two-party computation framework ABY, to overcome the limitations of leaking the intermediate feature maps to the data owner. We introduce a novel scheme for the conversion between CKKS and secure multi-party computation to execute DL inference while maintaining the privacy of both the input data and model weights. MP2ML is compatible with popular DL frameworks such as TensorFlow that can infer pre-trained neural networks with native ReLU activations. We benchmark MP2ML on the CryptoNets network with ReLU activations, on which it achieves a throughput of 33.3 images/s and an accuracy of 98.6%. This throughput matches the previous state-of-the-art work, even though our protocol is more accurate and scalable.
[104] Rosario Cammarota, Matthias Schunter, Anand Rajan, Fabian Boemer, Ágnes Kiss, Amos Treiber, Christian Weinert, Thomas Schneider, Emmanuel Stapf, Ahmad-Reza Sadeghi, Daniel Demmler, Huili Chen, Siam Umar Hussain, Sadegh Riazi, Farinaz Koushanfar, Saransh Gupta, Tajan Simunic Rosing, Kamalika Chaudhuri, Hamid Nejatollahi, Nikil Dutt, Mohsen Imani, Kim Laine, Anuj Dubey, Aydin Aysu, Fateme Sadat Hosseini, Chengmo Yang, Eric Wallace, and Pamela Norton. Trustworthy AI inference systems: An industry research view, August 10, 2020. https://arxiv.org/abs/2008.04449. [ bib | arXiv ]
[103] Kimmo Järvinen, Ágnes Kiss, Thomas Schneider, Oleksandr Tkachenko, and Zheng Yang. Faster privacy-preserving location proximity schemes for circles and polygons. IET Information Security, 14(3):254–265, May, 2020. CORE rank C. [ bib | DOI | pdf | web ]
In the last decade, location information became easily obtainable using off-the-shelf mobile devices. This gave a momentum to developing Location Based Services (LBSs) such as location proximity detection, which can be used to find friends or taxis nearby. LBSs can, however, be easily misused to track users, which draws attention to the need of protecting privacy of these users.
In this work, we address this issue by designing, implementing, and evaluating multiple algorithms for Privacy-Preserving Location Proximity (PPLP) that are based on different secure computation protocols. Our PPLP protocols support both circle and polygon range queries and have runtimes from a few to some hundreds of milliseconds and bandwidth requirements from a few hundreds of bytes to one megabyte. Consequently, they are well-suited for different scenarios and offer faster runtimes and savings in bandwidth and computational power as well as security improvements compared to previous PPLP schemes. In addition, the computationally most expensive parts of the PPLP computation can be precomputed in our protocols, such that the input-dependent online phase runs in just a few milliseconds.
[102] Masaud Y. Alhassan, Daniel Günther, Ágnes Kiss, and Thomas Schneider. Efficient and scalable universal circuits. Journal of Cryptology (JoC), 33(3):1216–1271, April 8, 2020. Preliminary version: https://ia.cr/2019/348. Code: https://encrypto.de/code/UC. CORE rank A*. [ bib | DOI | pdf | web ]
A universal circuit (UC) can be programmed to simulate any circuit up to a given size n by specifying its program inputs. It provides elegant solutions in various application scenarios, e.g., for private function evaluation (PFE) and for improving the flexibility of attribute-based encryption (ABE) schemes. The asymptotic lower bound for the size of a UC is Ω(nlogn) and Valiant (STOC'76) provided two theoretical constructions, the so-called 2-way and 4-way UCs (i.e., recursive constructions with 2 and 4 substructures), with asymptotic sizes ∼5nlog2n and ∼4.75nlog2n, respectively.
In this article, we present and extend our results published in (Kiss and Schneider, EUROCRYPT'16) and (Günther et al., ASIACRYPT'17). We validate the practicality of Valiant's UCs, by realizing the 2-way and 4-way UCs in our modular open-source implementations. We also provide an example implementation for PFE using these size-optimized UCs. We propose a 2/4-hybrid approach that combines the 2-way with the 4-way UC in order to minimize the size of the resulting UC. We realize that the bottleneck in universal circuit generation and programming becomes the memory consumption of the program since the whole structure of size O(nlogn) is handled by the algorithms in memory.
In this work, we overcome this by designing novel scalable algorithms for the UC generation and programming. Both algorithms use only O(n) memory at any point in time. We prove the practicality of our scalable design with a scalable proof-of-concept implementation for generating Valiant's 4-way UC. We note that this can be extended to work with optimized building blocks analogously. Moreover, we substantially improve the size of our UCs by including and implementing the recent optimization of Zhao et al. (ASIACRYPT'19) that reduces the asymptotic size of the 4-way UC to ∼4.5nlog2n. Furthermore, we include their optimization in the implementation of our 2/4-hybrid UC which yields the smallest UC construction known so far.
[101] Sebastian P. Bayerl, Tommaso Frassetto, Patrick Jauernig, Korbinian Riedhammer, Ahmad-Reza Sadeghi, Thomas Schneider, Emmanuel Stapf, and Christian Weinert. Offline model guard: Secure and private ML on mobile devices. In 23. Design, Automation & Test in Europe Conference & Exhibition (DATE'20), pages 460–465, IEEE, Grenoble, France, March 9-13, 2020. Online: https://arxiv.org/abs/2007.02351. Acceptance rate 26%. CORE rank B. [ bib | DOI | pdf | web ]
Performing machine learning tasks in mobile applications yields a challenging conflict of interest: highly sensitive client information (e.g., speech data) should remain private while also the intellectual property of service providers (e.g., model parameters) must be protected. Cryptographic techniques offer secure solutions for this, but have an unacceptable overhead and moreover require frequent network interaction.
In this work, we design a practically efficient hardware-based solution. Specifically, we build Offline Model Guard (OMG) to enable privacy-preserving machine learning on the pre- dominant mobile computing platform ARM - even in offline scenarios. By leveraging a trusted execution environment for strict hardware-enforced isolation from other system components, OMG guarantees privacy of client data, secrecy of provided models, and integrity of processing algorithms. Our prototype implementation on an ARM HiKey 960 development board performs privacy-preserving keyword recognition using TensorFlow Lite for Microcontrollers in real time.
[100] Thomas Schneider and Amos Treiber. A comment on privacy-preserving scalar product protocols as proposed in “SPOC”. IEEE Transactions on Parallel and Distributed Systems (TPDS), 31(3):543–546, March, 2020. Full version: https://arxiv.org/abs/1906.04862. Code: https://encrypto.de/code/SPOCattack. CORE rank A*. [ bib | DOI | pdf | web ]
Privacy-preserving scalar product (PPSP) protocols are an important building block for secure computation tasks in various applications. Lu et al. (TPDS’13) introduced a PPSP protocol that does not rely on cryptographic assumptions and that is used in a wide range of publications to date. In this comment paper, we show that Lu et al.’s protocol is insecure and should not be used. We describe specific attacks against it and, using impossibility results of Impagliazzo and Rudich (STOC’89), show that it is inherently insecure and cannot be fixed without relying on at least some cryptographic assumptions.
[99] Amos Treiber, Andreas Nautsch, Jascha Kolberg, Thomas Schneider, and Christoph Busch. Privacy-preserving PLDA speaker verification using outsourced secure computation. Speech Communication, 114:60–71, November, 2019. CORE rank A. [ bib | DOI | pdf | web ]
The usage of biometric recognition has become prevalent in various verification processes, ranging from unlocking mobile devices to verifying bank transactions. Automatic speaker verification (ASV) allows an individual to verify its identity towards an online service provider by comparing freshly sampled speech data to reference information stored on the service provider’s server. Due to the sensitive nature of biometric data, the storage and usage thereof is subject to recent EU regulations introduced as means to protect the privacy of individuals enrolled in an automatic biometric verification system. Stored biometric data need to be unlinkable, irreversible, and renewable to satisfy international standards. Preserving privacy in ASV is also important because, contrary to other biometric characteristics such as fingerprints, speech data can be used to infer a lot of sensitive information about the data subject. As a result, some architectures have been proposed to enable privacy-preserving ASV in the encrypted domain. Recently, homomorphic encryption (HE) was proposed to protect both subject features and vendor models in an embedding-based ASV. This architecture improves on previous privacy-preserving ASV by using (probabilistic) embeddings (i-vectors) and by additionally protecting the vendor’s model. However, the usage of HE comes with a rather heavy overhead and significantly slows down the verification process.
In this work, we align the cryptographic notion of outsourced secure two-party computation to embedding-based ASV. Our architecture protects biometric information in ASV and can also be used for any automatic biometric verification task. We show that unlinkability, irreversibility, and renewability are granted. Compared to the HE solution, our architecture results in considerably lower communication and computation overhead. Our architecture has been implemented and is experimentally evaluated on the NIST i-vector challenge 2014 using the cosine distance and log-likelihood ratio (LLR) scores from probabilistic linear discriminant analysis (PLDA) and two-covariance (2Cov) comparators. The results show that verification accuracy is retained while efficiency is improved. For instance, a PLDA verification with an embedding dimension of 200 takes about 77 milliseconds over a LAN. This is an improvement of more than 3000× over the HE-based solution and shows that privacy of subject and vendor data can be preserved in ASV while retaining practical verification times. Moreover, our system is secure against malicious client devices.
[98] Sebastian P. Bayerl, Ferdinand Brasser, Christoph Busch, Tommaso Frassetto, Patrick Jauernig, Jascha Kolberg, Andreas Nautsch, Korbinian Riedhammer, Ahmad-Reza Sadeghi, Thomas Schneider, Emmanuel Stapf, Amos Treiber, and Christian Weinert. Privacy-preserving speech processing via STPC and TEEs. 2. Privacy Preserving Machine Learning (PPML@CCS'19) – CCS'19 Workshop, London, UK, November 15, 2019. Poster. Acceptance rate 55.0%. [ bib | pdf | poster | web ]
With the advent of mobile and smart-home devices such as Amazon Alexa or the Google Assistant providing voice-based interfaces, voice data is commonly transferred to corresponding cloud services. This is necessary to quickly and accurately perform tasks like automatic speaker verification (ASV) and speech recognition (ASR) that heavily rely on machine learning.
While enabling intriguing new applications, this development also poses significant risks: Voice data is highly sensitive since it contains biometric information of the speaker as well as the spoken words. Thus, the security and privacy of billions of end-users is at stake if voice data is not protected properly. When developing privacy-preserving solutions to mitigate such risks, it is also important to keep in mind that the involved machine learning models represent intellectual property of the service providers and therefore must not be revealed to users.
The contribution of our work is three-fold: First, we present an efficient architecture for privacy-preserving ASV via outsourced secure two-party computation (STPC). Compared to existing solutions based on homomorphic encryption (HE), the verification process is 4,000x faster, while retaining a high verification accuracy and guaranteeing unlinkability, irreversibility, and renewability of stored biometric data.
Since cryptographic secure computation protocols currently do not scale to more involved tasks like ASR, we then present VoiceGuard, an architecture that efficiently protects speech processing inside a trusted execution environment (TEE). We provide a proof-of-concept implementation and evaluate it on speech recognition tasks isolated with Intel SGX, a widely available TEE imple- mentation, demonstrating even real time processing capabilities.
Finally, we present Offline Model Guard (OMG) to enable privacy- preserving speech processing on the predominant mobile comput- ing platform ARM even in offline scenarios. Beyond relying on the Intel SGX equivalent ARM TrustZone, we employ the security architecture SANCTUARY (NDSS’19) for strict hardware-enforced isolation from all other system components. Our prototype imple- mentation performs privacy-preserving keyword recognition using TensorFlow Lite in real time.
[97] Daniel Günther, Ágnes Kiss, Lukas Scheidel, and Thomas Schneider. Framework for semi-private function evaluation with application to secure insurance rate calculation. In 26. ACM Conference on Computer and Communications Security (CCS'19) Poster/Demo, pages 2541–2543, ACM, London, UK, November 11-15, 2019. Acceptance rate 67.2%. CORE rank A*. [ bib | DOI | pdf | poster | web ]
Private Function Evaluation (PFE) allows two parties to jointly compute a private function provided by one party on the secret input of the other party. However, in many applications it is not required to hide the whole function, which is called Semi-Private Function Evaluation (SPFE). In this work, we develop a framework for SPFE which allows to split a function into public and private parts. We show the practicability of using SPFE in a real world scenario by developing a car insurance application for computing user-specific tariffs. We evaluate the performance of our SPFE framework on this concrete example which results in a circuit consisting of 377,032 AND gates which improves over PFE by a factor of 9x.
[96] Robert Nikolai Reith, Thomas Schneider, and Oleksandr Tkachenko. Efficiently stealing your machine learning models. In 18. Workshop on Privacy in the Electronic Society (WPES'19), pages 198–210, ACM, London, UK, November 11, 2019. Acceptance rate 20.9%. [ bib | DOI | pdf | web ]
Machine Learning as a Service (MLaaS) is a growing paradigm in the Machine Learning (ML) landscape. More and more ML models are being uploaded to the cloud and made accessible from all over the world. Creating good ML models, however, can be expensive and the used data is often sensitive. Recently, Secure Multi-Party Computation (SMPC) protocols for MLaaS have been proposed, which protect sensitive user data and ML models at the expense of substantially higher computation and communication than plain- text evaluation.
In this paper, we show that for a subset of ML models used in MLaaS, namely Support Vector Machines (SVMs) and Support Vector Regression Machines (SVRs) which have found many applications to classifying multimedia data such as texts and images, it is possible for adversaries to passively extract the private models even if they are protected by SMPC, using known and newly devised model extraction attacks. We show that our attacks are not only theoretically possible but also practically feasible and cheap, which makes them lucrative to financially motivated attackers such as competitors or customers. We perform model extraction attacks on the homomorphic encryption-based protocol for privacy-preserving SVR-based indoor localization by Zhang et al. (International Work- shop on Security 2016). We show that it is possible to extract a highly accurate model using only 854 queries with the estimated cost of $0.09 on the Amazon ML platform, and our attack would take only 7 minutes over the Internet. Also, we perform our model extraction attacks on SVM and SVR models trained on publicly available state-of-the-art ML datasets.
[95] Susanne Felsen, Ágnes Kiss, Thomas Schneider, and Christian Weinert. Secure and private function evaluation with Intel SGX. In 10. ACM Cloud Computing Security Workshop (CCSW'19), pages 165–181, ACM, London, UK, November 11, 2019. Acceptance rate 37.5%. [ bib | DOI | pdf | web ]
Secure function evaluation (SFE) allows two parties to jointly evaluate a publicly known function without revealing their respective inputs. SFE can be realized via well-known cryptographic protocols, such as Yao’s garbled circuits (GC) and the protocol of Goldreich, Micali, and Wigderson (GMW), which obliviously evaluate a Boolean circuit representation of the function. Unfortunately, even with the most recent optimizations that touch known lower bounds, these protocols incur an impractical high communication overhead.
In this work, we efficiently realize SFE by evaluating the function in a trusted execution environment (TEE), concretely the widely available Intel Software Guard Extensions (SGX). We address the unresolved issue of countless software side-channel vulnerabilities in a unique way, namely by evaluating Boolean circuits – as used by cryptographic SFE protocols – inside an Intel SGX enclave. This way, all possible paths of the function are executed and all memory accesses are guaranteed to be independent of the actual input data.
The communication of our protocol depends only on the number of inputs and outputs (it is optimal up to an additive constant), but not on the circuit size (in contrast to Yao’s GC and the GMW protocol). Furthermore, we are the first to also address efficient private function evaluation (PFE) via TEEs, where one of the parties provides a function that represents intellectual property and is computed obliviously on the other party’s input. For realizing PFE, we securely evaluate universal circuits (UCs) that can be programmed via input bits to emulate any function up to a given size.
We provide a prototype implementation of our SFE and PFE protocols based on Intel SGX. We empirically compare its performance to the ABY framework (Demmler et al., NDSS’15) that provides state-of-the-art implementations of Yao’s GC and the GMW protocol as well as an adapter for evaluating UCs. For PFE with a UC emulating a circuit with 10 000 gates (representing, e.g., a secret function to calculate individual car insurance rates), we improve the run-time by factor 2.3x over Yao’s GC and by at least two orders of magnitude over the GMW protocol in a high-latency Internet setting. The communication is reduced by factors 106x and 131x compared to Yao’s GC and the GMW protocol, respectively.
[94] Andreas Nautsch, Abelino Jiménez, Amos Treiber, Jascha Kolberg, Catherine Jasserand, Els Kindt, Héctor Delgado, Massimiliano Todisco, Mohamed Amine Hmani, Aymen Mtibaa, Mohammed Ahmed Abdelraheem, Alberto Abad, Francisco Teixeira, Driss Matrouf, Marta Gomez-Barrero, Dijana Petrovska-Delacrétaz, Gérard Chollet, Nicholas Evans, Thomas Schneider, Jean-François Bonastre, Bhiksha Raj, Isabel Trancoso, and Christoph Busch. Preserving privacy in speaker and speech characterisation. Computer Speech and Language (CSL), 2019(58):441–480, November, 2019. CORE rank A. [ bib | DOI | pdf | web ]
Speech recordings are a rich source of personal, sensitive data that can be used to support a plethora of diverse applications, from health profiling to biometric recognition. It is therefore essential that speech recordings are adequately protected so that they cannot be misused. Such protection, in the form of privacy-preserving technologies, is required to ensure that: (i) the biometric profiles of a given individual (e.g., across different biometric service operators) are unlinkable; (ii) leaked, encrypted biometric information is irreversible, and that (iii) biometric references are renewable. Whereas many privacy-preserving technologies have been developed for other biometric characteristics, very few solutions have been proposed to protect privacy in the case of speech signals. Despite privacy preservation this is now being mandated by recent European and international data protection regulations. With the aim of fostering progress and collaboration between researchers in the speech, biometrics and applied cryptography communities, this survey article provides an introduction to the field, starting with a legal perspective on privacy preservation in the case of speech data. It then establishes the requirements for effective privacy preservation, reviews generic cryptography-based solutions, followed by specific techniques that are applicable to speaker characterisation (biometric applications) and speech characterisation (non-biometric applications). Glancing at non-biometrics, methods are presented to avoid function creep, preventing the exploitation of biometric information, e.g., to single out an identity in speech-assisted health care via speaker characterisation. In promoting harmonised research, the article also outlines common, empirical evaluation metrics for the assessment of privacy-preserving technologies for speech data.
[93] Deevashwer Rathee, Thomas Schneider, and K. K. Shukla. Improved multiplication triple generation over rings via RLWE-based AHE. In 18. International Conference on Cryptology And Network Security (CANS'19), volume 11829 of LNCS, pages 347–359, Springer, Fuzhou, China, October 25-27, 2019. Short paper. Full version: https://ia.cr/2019/577. Acceptance rate 52.7%. CORE rank B. [ bib | DOI | pdf | web ]
An important characteristic of recent MPC protocols is an input independent preprocessing phase in which most computations are offloaded, which greatly reduces the execution overhead of the online phase where parties provide their inputs. For a very efficient evaluation of arithmetic circuits in an information-theoretic online phase, the MPC protocols consume Beaver multiplication triples generated in the preprocessing phase. Triple generation is generally the most expensive part of the protocol, and improving its efficiency is the aim of our work.
We specifically focus on computation over rings of the form Z2^ in the semi-honest model and the two-party setting, for which an Oblivious Transfer (OT)-based protocol is currently the best solution. To improve upon this method, we propose a protocol based on RLWE-based Additive Homomorphic Encryption. Our experiments show that our protocol is more scalable, and it outperforms the OT-based protocol in most cases. For example, we improve communication by up to 6.9x and runtime by up to 3.6x for 64-bit triple generation.
[92] Andreas Nautsch, Jose Patino, Amos Treiber, Themos Stafylakis, Petr Mizera, Massimiliano Todisco, Thomas Schneider, and Nicholas Evans. Privacy-preserving speaker recognition with cohort score normalisation. In 20. Conference of the International Speech Communication Association (INTERSPEECH'19), pages 2868–2872, International Speech Communication Association (ISCA), Graz, Austria, September 15-19, 2019. Online: https://arxiv.org/abs/1907.03454. Acceptance rate 49.3%. CORE rank A. [ bib | DOI | pdf | web ]
In many voice biometrics applications there is a requirement to preserve privacy, not least because of the recently enforced General Data Protection Regulation (GDPR). Though progress in bringing privacy preservation to voice biometrics is lagging behind developments in other biometrics communities, recent years have seen rapid progress, with secure computation mechanisms such as homomorphic encryption being applied successfully to speaker recognition. Even so, the computational overhead incurred by processing speech data in the encrypted domain is substantial. While still tolerable for single biometric comparisons, most state-of-the-art systems perform some form of cohort-based score normalisation, requiring many thousands of biometric comparisons. The computational overhead is then prohibitive, meaning that one must accept either degraded performance (no score normalisation) or potential for privacy violations. This paper proposes the first computationally feasible approach to privacy-preserving cohort score normalisation. Our solution is a cohort pruning scheme based on secure multi-party computation which enables privacy-preserving score normalisation using probabilistic linear discriminant analysis (PLDA) comparisons. The solution operates upon binary voice representations. While the binarisation is lossy in biometric rank-1 performance, it supports computationally-feasible biometric rank-n comparisons in the encrypted domain.
[91] Daniel Kales, Christian Rechberger, Thomas Schneider, Matthias Senker, and Christian Weinert. Mobile private contact discovery at scale. In 28. USENIX Security Symposium (USENIX Security'19), pages 1447–1464, USENIX, Santa Clara, CA, USA, August 14-16, 2019. Website: https://contact-discovery.github.io. Full version: https://ia.cr/2019/517. Acceptance rate 16.2%. CORE rank A*. [ bib | pdf | web ]
Mobile messengers like WhatsApp perform contact discovery by uploading the user's entire address book to the service provider. This allows the service provider to determine which of the user's contacts are registered to the messaging service. However, such a procedure poses significant privacy risks and legal challenges. As we find, even messengers with privacy in mind currently do not deploy proper mechanisms to perform contact discovery privately.
The most promising approaches addressing this problem revolve around private set intersection (PSI) protocols. Unfortunately, even in a weak security model where clients are assumed to follow the protocol honestly, previous protocols and implementations turned out to be far from practical when used at scale. This is due to their high computation and/or communication complexity as well as lacking optimization for mobile devices. In our work, we remove most obstacles for large-scale global deployment by significantly improving two promising protocols by Kiss et al. (PoPETS'17) while also allowing for malicious clients.
Concretely, we present novel precomputation techniques for correlated oblivious transfers (reducing the online communication by factor 2x), Cuckoo filter compression (with a compression ratio of ≈70%), as well as 4.3x smaller Cuckoo filter updates. In a protocol performing oblivious PRF evaluations via garbled circuits, we replace AES as the evaluated PRF with a variant of LowMC (Albrecht et al., EUROCRYPT'15) for which we determine optimal parameters, thereby reducing the communication by factor 8.2x. Furthermore, we implement both protocols with security against malicious clients in C/C++ and utilize the ARM Cryptography Extensions available in most recent smartphones. Compared to previous smartphone implementations, this yields a performance improvement of factor 1000x for circuit evaluations. The online phase of our fastest protocol takes only 2.92s measured on a real WiFi connection (6.53s on LTE) to check 1024 client contacts against a large-scale database with 228 entries. As a proof-of-concept, we integrate our protocols in the client application of the open-source messenger Signal.
[90] Ágnes Kiss, Oliver Schick, and Thomas Schneider. Web application for privacy-preserving scheduling using secure computation. In 16. International Conference on Security and Cryptography (SECRYPT'19), pages 456–463, SciTePress, Prague, Czech Republic, July 26-28, 2019. Short paper. Code: https://encrypto.de/code/scheduling. Acceptance rate 15.2%. CORE rank B. [ bib | DOI | pdf | poster | web ]
Event scheduling applications such as Doodle allow for very limited privacy protection. Even if the participants are anonymous, their inputs are revealed to the poll administrator and the application server. There exist privacy-enhanced scheduling services (e.g., Kellermann and Böhme, CSE’09), but they require heavy computation and communication on the client’s side, leak information to the participants or poll administrator, and allow only for a restricted scheduling functionality.
In this work, we present a privacy-preserving scheduling system based on secure two-party computation, that allows to schedule meetings between a large number of participants efficiently, without requiring any participant to reveal its availability pattern or other sensitive information to any other participant, server, or even the poll administrator. The protocol allows for various functional extensions and requires the client to perform very little work when securely submitting its inputs. Our protocol is secure against semi-honest non-colluding servers and malicious participants.
[89] Thomas Schneider and Oleksandr Tkachenko. EPISODE: Efficient Privacy-PreservIng Similar Sequence Queries on Outsourced Genomic DatabasEs. In 14. ACM Asia Conference on Information, Computer and Communications Security (ASIACCS'19), pages 315–327, ACM, Auckland, New Zealand, July 7-12, 2019. Acceptance rate 17.1%. CORE rank B. [ bib | DOI | pdf | web ]
Nowadays, genomic sequencing has become much more affordable for many people and, thus, many people own their genomic data in a digital format. Having paid for genomic sequencing, they want to make use of their data for different tasks that are possible only using genomics, and they share their data with third parties to achieve these tasks, e.g., to find their relatives in a genomic database. As a consequence, more genomic data get collected worldwide. The upside of the data collection is that unique analyses on these data become possible. However, this raises privacy concerns because the genomic data uniquely identify their owner, contain sensitive data about his/her risk for getting particular diseases, and even sensitive information about his/her family members.
In this paper, we introduce EPISODE – a highly efficient privacy-preserving protocol for Similar Sequence Queries (SSQs), which can be used for finding genetically similar individuals in an outsourced genomic database, i.e., securely aggregated from data of multiple institutions. Our SSQ protocol is based on the edit distance approximation by Asharov et al. (PETS'18), which we further optimize and extend to the outsourcing scenario. We improve their protocol by using more efficient building blocks and achieve a 5–6× run-time improvement compared to their work in the same two-party scenario.
Recently, Cheng et al. (ASIACCS'18) introduced protocols for outsourced SSQs that rely on homomorphic encryption. Our new protocol outperforms theirs by more than factor 24000× in terms of run-time in the same setting and guarantees the same level of security. In addition, we show that our algorithm scales for practical database sizes by querying a database that contains up to a million short sequences within a few minutes, and a database with hundreds of whole-genome sequences containing 75 million alleles each within a few hours.
[88] Kimmo Järvinen, Helena Leppäkoski, Elena Simona Lohan, Philipp Richter, Thomas Schneider, Oleksandr Tkachenko, and Zheng Yang. PILOT: Practical privacy-preserving Indoor Localization using OuTsourcing. In 4. IEEE European Symposium on Security and Privacy (EuroS&P'19), pages 448–463, IEEE, Stockholm, Sweden, June 17-19, 2019. Acceptance rate 20.0%. [ bib | DOI | pdf | web ]
In the last decade, we observed a constantly growing number of Location-Based Services (LBSs) used in indoor environments, such as for targeted advertising in shopping malls or finding nearby friends. Although privacy-preserving LBSs were addressed in the literature, there was a lack of attention to the problem of enhancing privacy of indoor localization, i.e., the process of obtaining the users’ locations indoors and, thus, a prerequisite for any indoor LBS.
In this work we present PILOT, the first practically efficient solution for Privacy-Preserving Indoor Localization (PPIL) that was obtained by a synergy of the research areas indoor localization and applied cryptography. We design, implement, and evaluate protocols for Wi-Fi fingerprint-based PPIL that rely on 4 different distance metrics. To save energy and network bandwidth for the mobile end devices in PPIL, we securely outsource the computations to two non-colluding semi-honest parties. Our solution mixes different secure two-party computation protocols and we design size- and depth-optimized circuits for PPIL. We construct efficient circuit building blocks that are of independent interest: Single Instruction Multiple Data (SIMD) capable oblivious access to an array with low circuit depth and selection of the k-Nearest Neighbors with small circuit size. Additionally, we reduce Received Signal Strength (RSS) values from 8 bits to 4 bits without any significant accuracy reduction. Our most efficient PPIL protocol is 553x faster than that of Li et al. (INFOCOM’14) and 500x faster than that of Ziegeldorf et al. (WiSec’14). Our implementation on commodity hardware has practical run-times of less than 1 second even for the most accurate distance metrics that we consider, and it can process more than half a million PPIL queries per day.
[87] Benny Pinkas, Thomas Schneider, Oleksandr Tkachenko, and Avishay Yanai. Efficient circuit-based PSI with linear communication. In 38. Advances in Cryptology – EUROCRYPT'19, volume 11478 of LNCS, pages 122–153, Springer, Darmstadt, Germany, May 19-23, 2019. Online: https://ia.cr/2019/241. Code: https://encrypto.de/code/OPPRF-PSI. Acceptance rate 23.2%. CORE rank A*. [ bib | DOI | pdf | web ]
We present a new protocol for computing a circuit which implements the private set intersection functionality (PSI). Using circuits for this task is advantageous over the usage of specific protocols for PSI, since many applications of PSI do not need to compute the intersection itself but rather functions based on the items in the intersection.
Our protocol is the first circuit-based PSI protocol to achieve linear communication complexity. It is also concretely more efficient than all previous circuit-based PSI protocols. For example, for sets of size 220 it improves the communication of the recent work of Pinkas et al. (EUROCRYPT'18) by more than 10 times, and improves the run time by a factor of 2.8x in the LAN setting, and by a factor of 5.8x in the WAN setting.
Our protocol is based on the usage of a protocol for computing oblivious programmable pseudo-random functions (OPPRF), and more specifically on our technique to amortize the cost of batching together multiple invocations of OPPRF.
[86] Ágnes Kiss, Masoud Naderpour, Jian Liu, N. Asokan, and Thomas Schneider. SoK: Modular and efficient private decision tree evaluation. Proceedings on Privacy Enhancing Technologies (PoPETs), 2019(2):187–208, April 2019. Full version: https://ia.cr/2018/1099. Code: https://encrypto.de/code/PDTE. Acceptance rate 21.1%. CORE rank B. [ bib | DOI | pdf | web ]
Decision trees and random forests are widely used classifiers in machine learning. Service providers often host classification models in a cloud service and provide an interface for clients to use the model remotely. While the model is sensitive information of the server, the input query and prediction results are sensitive information of the client. This motivates the need for private decision tree evaluation, where the service provider does not learn the client's input and the client does not learn the model except for its size and the result.
In this work, we identify the three phases of private decision tree evaluation protocols: feature selection, comparison, and path evaluation. We systematize protocols for each of these phases to identify the best available instantiations using the two main paradigms for secure computation: garbling techniques and homomorphic encryption. There is a natural tradeoff between runtime and communication considering these two paradigms: garbling techniques use fast symmetric-key operations but require a large amount of communication, while homomorphic encryption is computationally heavy but requires little communication.
Our contributions are as follows: Firstly, we systematically review and analyse state-of-the-art protocols for the three phases of private decision tree evaluation. Our methodology allows us to identify novel combinations of these protocols that provide better tradeoffs than existing protocols. Thereafter, we empirically evaluate all combinations of these protocols by providing communication and runtime measures, and provide recommendations based on the identified concrete tradeoffs.
[85] Niklas Büscher, Daniel Demmler, Stefan Katzenbeisser, David Kretzmer, and Thomas Schneider. HyCC: Compilation of hybrid protocols for practical secure computation. In 25. ACM Conference on Computer and Communications Security (CCS'18), pages 847–861, ACM, Toronto, Canada, October 15-19, 2018. Code: https://gitlab.com/securityengineering/HyCC. Acceptance rate 16.6%. CORE rank A*. [ bib | DOI | pdf | web ]
While secure multi-party computation (MPC) is a vibrant research topic and a multitude of practical MPC applications have been presented recently, their development is still a tedious task that requires expert knowledge. Previous works have made first steps in compiling high-level descriptions from various source descriptions into MPC protocols, but only looked at a limited set of protocols.
In this work we present HyCC, a tool-chain for automated compilation of ANSI C programs into hybrid protocols that efficiently and securely combine multiple MPC protocols with optimizing compilation, scheduling, and partitioning. As a result, our compiled protocols are able to achieve performance numbers that are comparable to hand-built solutions. For the MiniONN neural network (Liu et al., CCS 2017), our compiler improves performance of the resulting protocol by more than a factor of 3x. Thus, for the first time, highly efficient hybrid MPC becomes accessible for developers without cryptographic background.
[84] Oleksandr Tkachenko and Thomas Schneider. Towards efficient privacy-preserving similar sequence queries on outsourced genomic databases. In 17. Workshop on Privacy in the Electronic Society (WPES'18), pages 71–75, ACM, Toronto, Canada, October 15, 2018. Acceptance rate 36.5%. [ bib | DOI | pdf | web ]
Nowadays, genomic sequencing has become affordable for many people. Since more people let analyze their genome, more genome data gets collected. The good side of this is that analyses on this data become possible. However, this raises privacy concerns because the genomic data uniquely identify their owner, contain sensitive information about his/her risk for getting diseases, and even sensitive information about his/her family members.
In this paper, we introduce a highly efficient privacy-preserving protocol for Similar Sequence Queries (SSQs), which can be used for finding genetically similar individuals in an outsourced genomic database aggregated from data of multiple institutions. Our SSQ protocol is based on the edit distance approximation by Asharov et al. (PETS'18), which we extend to the outsourcing scenario. We also improve their protocol by using more efficient building blocks and achieve a 5-6x run-time improvement compared to their work in the two-party scenario.
Recently, Cheng et al. (ASIACCS'18) introduced protocols for outsourced SSQs that rely on homomorphic encryption. Our approach outperforms theirs by more than factor 20 000x in terms of run-time in the outsourcing scenario.
[83] Ágnes Kiss, Oliver Schick, and Thomas Schneider. Web application for privacy-preserving scheduling. 27. USENIX Security Symposium (USENIX Security'18) Poster Session, Baltimore, MD, USA, August 15-17, 2018. CORE rank A*. [ bib | poster | web ]
[82] Kimmo Järvinen, Ágnes Kiss, Thomas Schneider, Oleksandr Tkachenko, and Zheng Yang. Faster privacy-preserving location proximity schemes. In 17. International Conference on Cryptology And Network Security (CANS'18), volume 11124 of LNCS, pages 3–22, Springer, Naples, Italy, September 30-October 3, 2018. Full version: https://ia.cr/2018/694. Acceptance rate 32.9%. CORE rank B. [ bib | DOI | pdf | web ]
In the last decade, location information became easily obtainable using off-the-shelf mobile devices. This gave a momentum to developing Location Based Services (LBSs) such as location proximity detection, which can be used to find friends or taxis nearby. LBSs can, however, be easily misused to track users, which draws attention to the need of protecting privacy of these users.
In this work, we address this issue by designing, implementing, and evaluating multiple algorithms for Privacy-Preserving Location Proximity (PPLP) that are based on different secure computation protocols. Our PPLP protocols are well-suited for different scenarios: for saving bandwidth, energy/computational power, or for faster runtimes. Furthermore, our algorithms have runtimes of a few milliseconds to hundreds of milliseconds and bandwidth of hundreds of bytes to one megabyte. In addition, the computationally most expensive parts of the PPLP computation can be precomputed in our protocols, such that the input-dependent online phase runs in just a few milliseconds.
[81] Ferdinand Brasser, Tommaso Frassetto, Korbinian Riedhammer, Ahmad-Reza Sadeghi, Thomas Schneider, and Christian Weinert. VoiceGuard: Secure and private speech processing. In 19. Conference of the International Speech Communication Association (INTERSPEECH'18), pages 1303–1307, International Speech Communication Association (ISCA), Hyderabad, India, September 2-6, 2018. Acceptance rate 54%. CORE rank A. [ bib | DOI | pdf | poster | web ]
With the advent of smart-home devices providing voice-based interfaces, such as Amazon Alexa or Apple Siri, voice data is constantly transferred to cloud services for automated speech recognition or speaker verification.
While this development enables intriguing new applications, it also poses significant risks: Voice data is highly sensitive since it contains biometric information of the speaker as well as the spoken words. This data may be abused if not protected properly, thus the security and privacy of billions of end-users is at stake.
We tackle this challenge by proposing an architecture, dubbed VoiceGuard, that efficiently protects the speech processing task inside a trusted execution environment (TEE). Our solution preserves the privacy of users while at the same time it does not require the service provider to reveal model parameters. Our architecture can be extended to enable user-specific models, such as feature transformations (including fMLLR), i-vectors, or model transformations (e.g., custom output layers). It also generalizes to secure on-premise solutions, allowing vendors to securely ship their models to customers.
We provide a proof-of-concept implementation and evaluate it on the Resource Management and WSJ speech recognition tasks isolated with Intel SGX, a widely available TEE implementation, demonstrating even real time processing capabilities.
[80] Philipp Richter, Zheng Yang, Oleksandr Tkachenko, Helena Leppäkoski, Kimmo Järvinen, Thomas Schneider, and Elena Simona Lohan. Received signal strength quantization for secure indoor positioning via fingerprinting. In 8. International Conference on Localization and GNSS (ICL-GNSS'18), pages 1–6, IEEE, Guimarães, Portugal, June 26-28, 2018. [ bib | DOI | pdf | web ]
The increasingly connected world magnifies the threats to users' location privacy. Encryption protocols offer solutions to privacy concerns, but they are computationally very demanding. A reduction of the bit-length of the Received Signal Strength (RSS) measurements is required for a realistic, privacy-preserving positioning system based on fingerprinting. This paper studies the practical design of quantizers for RSS fingerprinting data and analyses the effect of the quantization on the positioning performance, with several real data sets and positioning algorithms. Our results show that 4-bit quantization deteriorate the accuracy compared to no-quantization case by only 20cm and that 1-bit approaches (i.e. proximity based positioning) are also feasible for certain applications.
[79] Oleksandr Tkachenko, Christian Weinert, Thomas Schneider, and Kay Hamacher. Large-scale privacy-preserving statistical computations for distributed genome-wide association studies. In 13. ACM Asia Conference on Information, Computer and Communications Security (ASIACCS'18), pages 221–235, ACM, Songdo, South Korea, June 4-8, 2018. Acceptance rate 16.8%. CORE rank B. [ bib | DOI | pdf | web ]
We present privacy-preserving solutions for Genome-Wide Association Studies (GWAS) based on Secure Multi-Party Computation (SMPC). Using SMPC, we protect the privacy of patients when medical institutes collaborate for computing statistics on genomic data in a distributed fashion. Previous solutions for this task lack efficiency and/or use inadequate algorithms that are of limited practical value. Concretely, we optimize and implement multiple algorithms for the χ2-, G-, and P-test in the ABY framework (Demmler et al., NDSS'15) and evaluate them in a distributed GWAS scenario.
Statistical tests generally require advanced mathematical operations. For operations that cannot be calculated in integer arithmetic, we make use of the existing IEEE 754 floating point arithmetic implementation in ABY (Demmler et al., CCS'15). To improve performance, we extend the mixed-protocol capabilities of ABY by optimizing and implementing the integer to floating point conversion protocols of Aliasgari et al. (NDSS'13), which may be of independent interest. Furthermore, we consider extended contingency tables for the χ2- and G-test that use codeword counts instead of counts for only two alleles, thereby allowing for advanced, realistic analyses. Finally, we consider an outsourcing scenario where two non-colluding semi-trusted third parties process secret-shared input data from multiple institutes.
Our extensive evaluation shows, compared to the prior art of Constable et al. (BMC Medical Informatics and Decision Making'15), an improved run-time efficiency of the χ2-test by up to factor 37x. We additionally demonstrate practicality in scenarios with millions of participants and hundreds of collaborating institutes.
[78] M. Sadegh Riazi, Christian Weinert, Oleksandr Tkachenko, Ebrahim M. Songhori, Thomas Schneider, and Farinaz Koushanfar. Chameleon: A hybrid secure computation framework for machine learning applications. In 13. ACM Asia Conference on Information, Computer and Communications Security (ASIACCS'18), pages 707–721, ACM, Songdo, South Korea, June 4-8, 2018. Preliminary version: https://ia.cr/2017/1164. Acceptance rate 16.8%. CORE rank B. [ bib | DOI | pdf | web ]
We present Chameleon, a novel hybrid (mixed-protocol) framework for secure function evaluation (SFE) which enables two parties to jointly compute a function without disclosing their private inputs. Chameleon combines the best aspects of generic SFE protocols with the ones that are based upon additive secret sharing. In particular, the framework performs linear operations in the ring Z2^l using additively secret shared values and nonlinear operations using Yao's Garbled Circuits or the Goldreich-Micali-Wigderson protocol. Chameleon departs from the common assumption of additive or linear secret sharing models where three or more parties need to communicate in the online phase: the framework allows two parties with private inputs to communicate in the online phase under the assumption of a third node generating correlated randomness in an offline phase. Almost all of the heavy cryptographic operations are precomputed in an offline phase which substantially reduces the communication overhead. Chameleon is both scalable and significantly more efficient than the ABY framework (NDSS'15) it is based on. Our framework supports signed fixed-point numbers. In particular, Chameleon's vector dot product of signed fixed-point numbers improves the efficiency of mining and classification of encrypted data for algorithms based upon heavy matrix multiplications. Our evaluation of Chameleon on a 5 layer convolutional deep neural network shows 133x and 4.2x faster executions than Microsoft CryptoNets (ICML'16) and MiniONN (CCS'17), respectively.
[77] Benny Pinkas, Thomas Schneider, Christian Weinert, and Udi Wieder. Efficient circuit-based PSI via cuckoo hashing. In 37. Advances in Cryptology – EUROCRYPT'18, volume 10822 of LNCS, pages 125–157, Springer, Tel Aviv, Israel, April 29-May 3, 2018. Full version: https://ia.cr/2018/120. Acceptance rate 23.0%. CORE rank A*. [ bib | DOI | pdf | web ]
While there has been a lot of progress in designing efficient custom protocols for computing Private Set Intersection (PSI), there has been less research on using generic Multi-Party Computation (MPC) protocols for this task. However, there are many variants of the set intersection functionality that are not addressed by the existing custom PSI solutions and are easy to compute with generic MPC protocols (e.g., comparing the cardinality of the intersection with a threshold or measuring ad conversion rates).
Generic PSI protocols work over circuits that compute the intersection. For sets of size n, the best known circuit constructions conduct O(n logn) or O(n logn / loglogn) comparisons (Huang et al., NDSS'12 and Pinkas et al., USENIX Security'15). In this work, we propose new circuit-based protocols for computing variants of the intersection with an almost linear number of comparisons. Our constructions are based on new variants of Cuckoo hashing in two dimensions.
We present an asymptotically efficient protocol as well as a protocol with better concrete efficiency. For the latter protocol, we determine the required sizes of tables and circuits experimentally, and show that the run-time is concretely better than that of existing constructions.
The protocol can be extended to a larger number of parties. The proof technique presented in the full version for analyzing Cuckoo hashing in two dimensions is new and can be generalized to analyzing standard Cuckoo hashing as well as other new variants of it.
[76] Benny Pinkas, Thomas Schneider, and Michael Zohner. Scalable private set intersection based on OT extension. ACM Transactions on Privacy and Security (TOPS), 21(2):7:1–7:35, January 2018. Preliminary version: https://ia.cr/2016/930. Code: https://encrypto.de/code/JournalPSI. CORE rank A. [ bib | DOI | pdf | web ]
Private set intersection (PSI) allows two parties to compute the intersection of their sets without revealing any information about items that are not in the intersection. It is one of the best studied applications of secure computation and many PSI protocols have been proposed. However, the variety of existing PSI protocols makes it difficult to identify the solution that performs best in a respective scenario, especially since they were not compared in the same setting. In addition, existing PSI protocols are several orders of magnitude slower than an insecure naive hashing solution which is used in practice.
In this work, we review the progress made on PSI protocols and give an overview of existing protocols in various security models. We then focus on PSI protocols that are secure against semi-honest adversaries and take advantage of the most recent efficiency improvements in OT extension and propose significant optimizations to previous PSI protocols and to suggest a new PSI protocol whose run-time is superior to that of existing protocols. We compare the performance of the protocols both theoretically and experimentally, by implementing all protocols on the same platform, give recommendations on which protocol to use in a particular setting, and evaluate the progress on PSI protocols by comparing them to the currently employed insecure naive hashing protocol. We demonstrate the feasibility of our new PSI protocol by processing two sets with a billion elements each.
[75] Marco Chiesa, Daniel Demmler, Marco Canini, Michael Schapira, and Thomas Schneider. SIXPACK: Securing Internet eXchange Points Against Curious onlooKers. In 13. International Conference on emerging Networking EXperiments and Technologies (CoNEXT'17), pages 120–133, ACM, Seoul, South Korea, December 12-15, 2017. Acceptance rate 18.1%. CORE rank A. [ bib | DOI | pdf | web ]
Internet eXchange Points (IXPs) play an ever-growing role in Internet inter-connection. To facilitate the exchange of routes amongst their members, IXPs provide Route Server (RS) services to dispatch the routes according to each member's peering policies. Nowadays, to make use of RSes, these policies must be disclosed to the IXP. This poses fundamental questions regarding the privacy guarantees of route-computation on con dential business information. Indeed, as evidenced by interaction with IXP administrators and a survey of network operators, this state of a airs raises privacy concerns among network administrators and even deters some networks from subscribing to RS services. We design sixpack1, an RS service that leverages Secure Multi-Party Computation (SMPC) to keep peering policies con dential, while extending, the functionalities of today's RSes. As SMPC is notoriously heavy in terms of communication and computation, our design and implementation of sixpack aims at moving computation outside of the SMPC without compromising the privacy guarantees. We assess the e ectiveness and scalability of our system by evaluating a prototype implementation using traces of data from one of the largest IXPs in the world. Our evaluation results indicate that sixpack can scale to support privacy-preserving route-computation, even at IXPs with many hundreds of member networks.
[74] Daniel Günther, Ágnes Kiss, and Thomas Schneider. More efficient universal circuit constructions. In 23. Advances in Cryptology – ASIACRYPT'17, volume 10625 of LNCS, pages 443–470, Springer, Hong Kong, China, December 3-7, 2017. Full version: https://ia.cr/2017/798. Code: https://encrypto.de/code/UC. Acceptance rate 27.6%. CORE rank A. [ bib | DOI | pdf | web ]
A universal circuit (UC) can be programmed to simulate any circuit up to a given size n by specifying its program bits. UCs have several applications, including private function evaluation (PFE). The asymptotical lower bound for the size of a UC is proven to be Ω(nlogn). In fact, Valiant (STOC'76) provided two theoretical UC constructions using so-called 2-way and 4-way constructions, with sizes 5nlog2n and 4.75nlog2n, respectively. The 2-way UC has recently been brought into practice in concurrent and independent results by Kiss and Schneider (EUROCRYPT'16) and Lipmaa et al. (Eprint 2016/017). Moreover, the latter work generalized Valiant's construction to any k-way UC.
In this paper, we revisit Valiant's UC constructions and the recent results, and provide a modular and generic embedding algorithm for any k-way UC. Furthermore, we discuss the possibility for a more efficient UC based on a 3-way recursive strategy. We show with a counterexample that even though it is a promising approach, the 3-way UC does not yield an asymptotically better result than the 4-way UC. We propose a hybrid approach that combines the 2-way with the 4-way UC in order to minimize the size of the resulting UC. We elaborate on the concrete size of all discussed UC constructions and show that our hybrid UC yields on average 3.65% improvement in size over the 2-way UC. We implement the 4-way UC in a modular manner based on our proposed embedding algorithm, and show that our methods for programming the UC can be generalized for any k-way construction.
[73] Daniel Demmler, Kay Hamacher, Thomas Schneider, and Sebastian Stammler. Privacy-preserving whole-genome variant queries. In 16. International Conference on Cryptology And Network Security (CANS'17), volume 11261 of LNCS, pages 1–22, Springer, Hong Kong, China, November 30-December 2, 2017. Acceptance rate 31.8%. CORE rank B. [ bib | DOI | pdf | web ]
Medical research and treatments rely increasingly on genomic data. Queries on so-called variants are of high importance in, e.g., biomarker identification and general disease association studies. However, the human genome is a very sensitive piece of information that is worth protecting. By observing queries and responses to classical genomic databases, medical conditions can be inferred. The Beacon project is an example of a public genomic querying service, which undermines the privacy of the querier as well as individuals in the database.
By secure outsourcing via secure multi-party computation (SMPC), we enable privacy-preserving genomic database queries that protect sensitive data contained in the queries and their respective responses. At the same time, we allow for multiple genomic databases to combine their datasets to achieve a much larger search space, without revealing the actual databases' contents to third parties. SMPC is generic and allows to apply further processing like aggregation to query results.
We measure the performance of our approach for realistic parameters and achieve convincingly fast runtimes that render our protocol applicable to real-world medical data integration settings. Our prototype implementation can process a private query with 5 genetic variant conditions against a person's exome with 100000 genomic variants in less than 180 ms online runtime, including additional range and equality checks for auxiliary data.
[72] Ágnes Kiss, Jian Liu, Thomas Schneider, N. Asokan, and Benny Pinkas. Private set intersection for unequal set sizes with mobile applications. Proceedings on Privacy Enhancing Technologies (PoPETs), 2017(4):177–197, October 2017. Full version: https://ia.cr/2017/670. Code: https://encrypto.de/code/MobilePSI. Acceptance rate 21.7%. CORE rank B. [ bib | DOI | pdf | web ]
Private set intersection (PSI) is a cryptographic technique that is applicable to many privacy-sensitive scenarios. For decades, researchers have been focusing on improving its efficiency in both communication and computation. However, most of the existing solutions are inefficient for an unequal number of inputs, which is common in conventional client-server settings.
In this paper, we analyze and optimize the efficiency of existing PSI protocols to support precomputation so that they can efficiently deal with such input sets. We transform four existing PSI protocols into the precomputation form such that in the setup phase the communication is linear only in the size of the larger input set, while in the online phase the communication is linear in the size of the smaller input set. We implement all four protocols and run experiments between two PCs and between a PC and a smartphone and give a systematic comparison of their performance. Our experiments show that a protocol based on securely evaluating a garbled AES circuit achieves the fastest setup time by several orders of magnitudes, and the fastest online time in the PC setting where AES-NI acceleration is available. In the mobile setting, the fastest online time is achieved by a protocol based on the Diffie-Hellman assumption.
[71] Gilad Asharov, Yehuda Lindell, Thomas Schneider, and Michael Zohner. More efficient oblivious transfer extensions. Journal of Cryptology (JoC), 30(3):805–858, July 2017. Updated version: https://ia.cr/2016/602. CORE rank A*. [ bib | DOI | pdf | web ]
Oblivious transfer (OT) is one of the most fundamental primitives in cryptography and is widely used in protocols for secure two-party and multi-party computation. As secure computation becomes more practical, the need for practical large scale oblivious transfer protocols is becoming more evident. Oblivious transfer extensions are protocols that enable a relatively small number of “base-OTs” to be utilized to compute a very large number of OTs at low cost. In the semi-honest setting, Ishai et al. (CRYPTO 2003) presented an OT extension protocol for which the cost of each OT (beyond the base-OTs) is just a few hash function operations. In the malicious setting, Nielsen et al. (CRYPTO 2012) presented an efficient OT extension protocol for the setting of malicious adversaries, that is secure in a random oracle model.
In this work we improve OT extensions with respect to communication complexity, computation complexity, and scalability in the semi-honest, covert, and malicious model. Furthermore, we show how to modify our maliciously secure OT extension protocol to achieve security with respect to a version of correlation robustness instead of the random oracle. We also provide specific optimizations of OT extensions that are tailored to the use of OT in various secure computation protocols such as Yao's garbled circuits and the protocol of Goldreich-Micali-Wigderson, which reduce the communication complexity even further. We experimentally verify the efficiency gains of our protocols and optimizations.
[70] Daniel Demmler, Marco Holz, and Thomas Schneider. OnionPIR: Effective protection of sensitive metadata in online communication networks. In 15. International Conference on Applied Cryptography and Network Security (ACNS'17), volume 10355 of LNCS, pages 599–619, Springer, Kanazawa, Japan, July 10-12, 2017. Code: https://encrypto.de/code/onionPIR. Acceptance rate 22.8%. CORE rank B. [ bib | DOI | pdf | web ]
While great effort has been put into securing the content of messages transmitted over digital infrastructures, practical protection of metadata is still an open research problem. Scalable mechanisms for protecting users' anonymity and hiding their social graph are needed.
One technique that we focus on in this work is private information retrieval (PIR), an active field of research that enables private querying of data from a public database without revealing which data has been requested and a fundamental building block for private communication. We introduce two significant improvements for the multi-server scheme RAID-PIR (ACM CCSW'14): precomputing queries using the Method of four Russians and optimizing the database layout for parallel queries.
We then propose OnionPIR, an anonymous messaging service as example application for PIR combined with onion routing that prevents the leakage of communication meta-data. By providing and evaluating a prototype, we show that OnionPIR is usable in practice. Based on our results, we conclude that it is possible to build and deploy such a service today, while its operating expenses are within the order of magnitude of those of traditional messaging services that leak metadata.
[69] Gilad Asharov, Daniel Demmler, Michael Schapira, Thomas Schneider, Gil Segev, Scott Shenker, and Michael Zohner. Privacy-preserving interdomain routing at Internet scale. Proceedings on Privacy Enhancing Technologies (PoPETs), 2017(3):143–163, July 2017. Full version: https://ia.cr/2017/393. Acceptance rate 18.6%. CORE rank B. [ bib | DOI | pdf | web ]
The Border Gateway Protocol (BGP) computes routes between the organizational networks that make up today's Internet. Unfortunately, BGP suffers from deficiencies, including slow convergence, security problems, a lack of innovation, and the leakage of sensitive information about domains' routing preferences. To overcome some of these problems, we revisit the idea of centralizing and using secure multi-party computation (MPC) for interdomain routing which was proposed by Gupta et al. (ACM HotNets'12). We implement two algorithms for interdomain routing with state-of-the-art MPC protocols. On an empirically derived dataset that approximates the topology of today's Internet (55809 nodes), our protocols take as little as 6s of topology-independent precomputation and only 3 s of online time. We show, moreover, that when our MPC approach is applied at country/region-level scale, runtimes can be as low as 0.17 s online time and 0.20 s pre-computation time. Our results motivate the MPC approach for interdomain routing and furthermore demonstrate that current MPC techniques are capable of efficiently tackling real-world problems at a large scale.
[68] Jesper Buus Nielsen, Thomas Schneider, and Roberto Trifiletti. Constant round maliciously secure 2PC with function-independent preprocessing using LEGO. In 24. Network and Distributed System Security Symposium (NDSS'17), Internet Society, San Diego, CA, USA, February 26-March 1, 2017. Acceptance rate 16.1%. CORE rank A*. [ bib | DOI | pdf | web ]
Secure two-party computation (S2PC) allows two parties to compute a function on their joint inputs while leaking only the output of the function. At TCC 2009 Orlandi and Nielsen proposed the LEGO protocol for maliciously secure 2PC based on cut-and-choose of Yao's garbled circuits at the gate level and showed that this is asymptotically more efficient than on the circuit level. Since then the LEGO approach has been improved upon in several theoretical works, but never implemented. In this paper we describe further concrete improvements and provide the first implementation of a protocol from the LEGO family. Our protocol has a constant number of rounds and is optimized for the offline/online setting with function-independent preprocessing. We have benchmarked our prototype and find that our protocol can compete with all existing implementations and that it is often more efficient. As an example, in a LAN setting we can evaluate an AES-128 circuit with online latency down to 1.13ms, while if evaluating 128 AES-128 circuits in parallel the amortized cost is 0.09 ms per AES-128. This online performance does not come at the price of offline inefficiency as we achieve comparable performance to previous, less general protocols, and significantly better if we ignore the cost of the function-independent preprocessing. Also, as our protocol has an optimal 2-round online phase it is significantly more efficient than previous protocols when considering a high latency network.
[67] Ghada Dessouky, Farinaz Koushanfar, Ahmad-Reza Sadeghi, Thomas Schneider, Shaza Zeitouni, and Michael Zohner. Pushing the communication barrier in secure computation using lookup tables. In 24. Network and Distributed System Security Symposium (NDSS'17), Internet Society, San Diego, CA, USA, February 26-March 1, 2017. Full version: https://ia.cr/2018/486. Acceptance rate 16.1%. CORE rank A*. [ bib | DOI | pdf | web ]
Secure two-party computation has witnessed significant efficiency improvements in the recent years. Current implementations of protocols with security against passive adversaries generate and process data much faster than it can be sent over the network, even with a single thread. This paper introduces novel methods to further reduce the communication bottleneck and round complexity of semi-honest secure two-party computation. Our new methodology creates a trade-off between communication and computation, and we show that the added computing cost for each party is still feasible and practicable in light of the new communication savings. We first improve communication for Boolean circuits with 2-input gates by factor 1.9x when evaluated with the protocol of Goldreich-Micali-Wigderson (GMW). As a further step, we change the conventional Boolean circuit representation from 2-input gates to multi-input/multi-output lookup tables (LUTs) which can be programmed to realize arbitrary functions. We construct two protocols for evaluating LUTs offering a trade-off between online communication and total communication. Our most efficient LUT-based protocol reduces the communication and round complexity by a factor 2-4x for several basic and complex operations. Our proposed scheme results in a significant overall runtime decrease of up to a factor of 3x on several benchmark functions.
[66] M. Sadegh Riazi, Ebrahim M. Songhori, Ahmad-Reza Sadeghi, Thomas Schneider, and Farinaz Koushanfar. Toward practical secure stable matching. Proceedings on Privacy Enhancing Technologies (PoPETs), 2017(1):62–78, January 2017. Acceptance rate 37.9%. CORE rank B. [ bib | DOI | pdf | web ]
The Stable Matching (SM) algorithm has been deployed in many real-world scenarios including the National Residency Matching Program (NRMP) and financial applications such as matching of suppliers and consumers in capital markets. Since these applications typically involve highly sensitive information such as the underlying preference lists, their current implementations rely on trusted third parties. This paper introduces the first provably secure and scalable implementation of SM based on Yao's garbled circuit protocol and Oblivious RAM (ORAM). Our scheme can securely compute a stable match for 8k pairs four orders of magnitude faster than the previously best known method. We achieve this by introducing a compact and efficient sub-linear size circuit. We even further decrease the computation cost by three orders of magnitude by proposing a novel technique to avoid unnecessary iterations in the SM algorithm. We evaluate our implementation for several problem sizes and plan to publish it as open-source.
[65] Marco Chiesa, Daniel Demmler, Marco Canini, Michael Schapira, and Thomas Schneider. Towards Securing Internet eXchange Points Against Curious onlooKers. In ACM, IRTF & ISOC Applied Networking Research Workshop (ANRW'16), pages 32–34, ACM, Berlin, Germany, July 16, 2016. Short paper. [ bib | DOI | pdf | web ]
The growing relevance of Internet eXchange Points (IXPs), where an increasing number of networks exchange routing information, poses fundamental questions regarding the privacy guarantees of confidential business information. To facilitate the exchange of routes among their members, IXPs provide Route Server (RS) services to dispatch the routes according to each member's export policies. Nowadays, to make use of RSes, these policies must be disclosed to the IXP. This state of affairs raises privacy concerns among network administrators and even deters some networks from subscribing to RS services. We design SIXPACK (which stands for “Securing Internet eXchange Points Against Curious onlooKers”), a RS service that leverages Secure Multi-Party Computation (SMPC) techniques to keep export policies confidential, while maintaining the same functionalities as today's RSes. We assess the effectiveness and scalability of our system by evaluating our prototype implementation and using traces of data from one of the largest IXPs in the world.
[64] Ebrahim M. Songhori, Shaza Zeitouni, Ghada Dessouky, Thomas Schneider, Ahmad-Reza Sadeghi, and Farinaz Koushanfar. GarbledCPU: A MIPS processor for secure computation in hardware. In 53. Design Automation Conference (DAC'16), pages 73:1–73:6, ACM, Austin, TX, USA, June 5-9, 2016. Acceptance rate 17.4%. CORE rank A. [ bib | DOI | pdf | web ]
We present GarbledCPU, the first framework that realizes a hardware-based general purpose sequential processor for secure computation. Our MIPS-based implementation enables development of applications (functions) in a high-level language while performing secure function evaluation (SFE) using Yao's garbled circuit protocol in hardware. GarbledCPU provides three degrees of freedom for SFE which allow leveraging the trade-off between privacy and performance: public functions, private functions, and semi-private functions. We synthesize GarbledCPU on a Virtex-7 FPGA as a proof-of-concept implementation and evaluate it on various benchmarks including Hamming distance, private set intersection and AES. Our results indicate that our pipelined hardware framework outperforms the fastest available software implementation.
[63] Ágnes Kiss and Thomas Schneider. Valiant's universal circuit is practical. In 35. Advances in Cryptology – EUROCRYPT'16, volume 9665 of LNCS, pages 699–728, Springer, Vienna, Austria, May 8-12, 2016. Full version: https://ia.cr/2016/093. Code: https://encrypto.de/code/UC. Acceptance rate 22.6%. CORE rank A*. [ bib | DOI | pdf | web ]
Universal circuits (UCs) can be programmed to evaluate any circuit of a given size k. They provide elegant solutions in various application scenarios, e.g. for private function evaluation (PFE) and for improving the flexibility of attribute-based encryption (ABE) schemes. The optimal size of a universal circuit is proven to be Ω(klogk). Valiant (STOC'76) proposed a size-optimized UC construction, which has not been put in practice ever since. The only implementation of universal circuits was provided by Kolesnikov and Schneider (FC'08), with size O(klog2 k).
In this paper, we refine the size of Valiant's UC and further improve the construction by (at least) 2k. We show that due to recent optimizations and our improvements, it is the best solution to apply in the case for circuits with a constant number of inputs and outputs. When the number of inputs or outputs is linear in the number of gates, we propose a more efficient hybrid solution based on the two existing constructions. We validate the practicality of Valiant's UC, by giving an example implementation for PFE using these size-optimized UCs.
[62] Daniel Demmler, Ghada Dessouky, Farinaz Koushanfar, Ahmad-Reza Sadeghi, Thomas Schneider, and Shaza Zeitouni. Automated synthesis of optimized circuits for secure computation. In 22. ACM Conference on Computer and Communications Security (CCS'15), pages 1504–1517, ACM, Denver, CO, USA, October 12-16, 2015. Acceptance rate 19.8%. CORE rank A*. [ bib | DOI | pdf | web ]
In the recent years, secure computation has been the subject of intensive research, emerging from theory to practice. In order to make secure computation usable by non-experts, Fairplay (USENIX Security 2004) initiated a line of research in compilers that allow to automatically generate circuits from high-level descriptions of the functionality that is to be computed securely. Most recently, TinyGarble (IEEE S&P 2015) demonstrated that it is natural to use existing hardware synthesis tools for this task.
In this work, we present how to use industrial-grade hardware synthesis tools to generate circuits that are not only optimized for size, but also for depth. These are required for secure computation protocols with non-constant round complexity. We compare a large variety of circuits generated by our toolchain with hand-optimized circuits and show reduction of depth by up to 14%.
The main advantages of our approach are developing customized libraries of depth-optimized circuit constructions which we map to high-level functions and operators, and using existing libraries available in the industrial-grade logic synthesis tools which are heavily tested. In particular, we show how to easily obtain circuits for IEEE 754 compliant floating-point operations. We extend the open source ABY framework (NDSS 2015) to securely evaluate circuits generated with our toolchain and show between 0.5 to 21.4 times faster floating-point operations than previous protocols of Aliasgari et al. (NDSS 2013), even though our protocols work for two parties instead of three or more. As application we consider privacy-preserving proximity testing on Earth.
[61] Patrick Koeberl, Vinay Phegade, Anand Rajan, Thomas Schneider, Steffen Schulz, and Maria Zhdanova. Time to rethink: Trust brokerage using trusted execution environments. In 8. International Conference on Trust and Trustworthy Computing (TRUST'15), volume 9229 of LNCS, pages 181–190, Springer, Heraklion, Crete, Greece, August 24-26, 2015. Short paper. [ bib | DOI | pdf | web ]
Mining and analysis of digital data has the potential to provide improved quality of life and offer even life-saving insights. However, loss of privacy or secret information would be detrimental to these goals and inhibit widespread application. Traditional data protection measures tend to result in the formation of data silos, severely limiting the scope and yield of “Big Data”. Technology such as privacy-preserving multi-party computation (MPC) and data de-identification can break these silos enabling privacy-preserving computation. However, currently available de-identification schemes tend to suffer from privacy/utility trade-offs, and MPC has found deployment only in niche applications. As the assurance and availability of hardware-based Trusted Execution Environments (TEEs) is increasing, we propose an alternative direction of using TEEs as “neutral” environments for efficient yet secure multi-party computation. To this end, we survey the current state of the art, propose a generic initial solution architecture and identify remaining challenges.
[60] Benny Pinkas, Thomas Schneider, Gil Segev, and Michael Zohner. Phasing: Private set intersection using permutation-based hashing. In 24. USENIX Security Symposium (USENIX Security'15), pages 515–530, USENIX, Washington, DC, USA, August 12-14, 2015. Full version: https://ia.cr/2015/634. Code: https://encrypto.de/code/PSI. Acceptance rate 15.7%. CORE rank A*. [ bib | pdf | web ]
Private Set Intersection (PSI) allows two parties to compute the intersection of private sets while revealing nothing more than the intersection itself. PSI needs to be applied to large data sets in scenarios such as measurement of ad conversion rates, data sharing, or contact discovery. Existing PSI protocols do not scale up well, and therefore some applications use insecure solutions instead.
We describe a new approach for designing PSI protocols based on permutation-based hashing, which enables to reduce the length of items mapped to bins while ensuring that no collisions occur. We denote this approach as Phasing, for Permutation-based Hashing Set Intersection. Phasing can dramatically improve the performance of PSI protocols whose overhead depends on the length of the representations of input items.
We apply Phasing to design a new approach for circuit-based PSI protocols. The resulting protocol is up to 5 times faster than the previously best Sort-Compare-Shuffle circuit of Huang et al. (NDSS 2012). We also apply Phasing to the OT-based PSI protocol of Pinkas et al. (USENIX Security 2014), which is the fastest PSI protocol to date. Together with additional improvements that reduce the computation complexity by a logarithmic factor, the resulting protocol improves run-time by a factor of up to 20 and can also have better communication overhead than the previously best PSI protocol in that respect. The new protocol is only moderately less efficient than an insecure PSI protocol that is currently used by real-world applications, and is therefore the first secure PSI protocol that is scalable to the demands and the constraints of current real-world settings.
[59] Ebrahim M. Songhori, Siam U. Hussain, Ahmad-Reza Sadeghi, Thomas Schneider, and Farinaz Koushanfar. TinyGarble: Highly compressed and scalable sequential garbled circuits. In 36. IEEE Symposium on Security and Privacy (IEEE S&P'15), pages 411–428, IEEE, San Jose, CA, USA, May 18-20, 2015. Acceptance rate 13.5%. CORE rank A*. [ bib | DOI | pdf | web ]
We introduce TinyGarble, a novel automated methodology based on powerful logic synthesis techniques for generating and optimizing compressed Boolean circuits used in secure computation, such as Yao's Garbled Circuit (GC) protocol. TinyGarble achieves an unprecedented level of compactness and scalability by using a sequential circuit description for GC. We introduce new libraries and transformations, such that our sequential circuits can be optimized and securely evaluated by interfacing with available garbling frameworks. The circuit compactness makes the memory footprint of the garbling operation fit in the processor cache, resulting in fewer cache misses and thereby less CPU cycles. Our proof-of-concept implementation of benchmark functions using TinyGarble demonstrates a high degree of compactness and scalability. We improve the results of existing automated tools for GC generation by orders of magnitude; for example, TinyGarble can compress the memory footprint required for 1024-bit multiplication by a factor of 4,172, while decreasing the number of non-XOR gates by 67%. Moreover, with TinyGarble we are able to implement functions that have never been reported before, such as SHA-3. Finally, our sequential description enables us to design and realize a garbled processor, using the MIPS I instruction set, for private function evaluation. To the best of our knowledge, this is the first scalable emulation of a general purpose processor.
[58] Gilad Asharov, Yehuda Lindell, Thomas Schneider, and Michael Zohner. More efficient oblivious transfer extensions with security for malicious adversaries. In 34. Advances in Cryptology – EUROCRYPT'15, volume 9056 of LNCS, pages 673–701, Springer, Sofia, Bulgaria, April 26-30, 2015. Full version: https://ia.cr/2015/061. Code: https://encrypto.de/code/OTExtension. Acceptance rate 29.4%. CORE rank A*. [ bib | DOI | pdf | web ]
Oblivious transfer (OT) is one of the most fundamental primitives in cryptography and is widely used in protocols for secure two-party and multi-party computation. As secure computation becomes more practical, the need for practical large scale oblivious transfer protocols is becoming more evident. Oblivious transfer extensions are protocols that enable a relatively small number of “base-OTs” to be utilized to compute a very large number of OTs at low cost. In the semi-honest setting, Ishai et al. (CRYPTO 2003) presented an OT extension protocol for which the cost of each OT (beyond the base-OTs) is just a few hash function operations. In the malicious setting, Nielsen et al. (CRYPTO 2012) presented an efficient OT extension protocol for the setting of active adversaries, that is secure in the random oracle model. In this work, we present an OT extension protocol for the setting of malicious adversaries that is more efficient and uses less communication than previous works. In addition, our protocol can be proven secure in both the random oracle model, and in the standard model with a type of correlation robustness. Given the importance of OT in many secure computation protocols, increasing the efficiency of OT extensions is another important step forward to making secure computation practical.
[57] Martin Albrecht, Christian Rechberger, Thomas Schneider, Tyge Tiessen, and Michael Zohner. Ciphers for MPC and FHE. In 34. Advances in Cryptology – EUROCRYPT'15, volume 9056 of LNCS, pages 430–454, Springer, Sofia, Bulgaria, April 26-30, 2015. Full version: https://ia.cr/2016/687. Acceptance rate 29.4%. CORE rank A*. [ bib | DOI | pdf | web ]
Designing an efficient cipher was always a delicate balance between linear and non-linear operations. This goes back to the design of DES, and in fact all the way back to the seminal work of Shannon. Here we focus, for the first time, on an extreme corner of the design space and initiate a study of symmetric-key primitives that minimize the multiplicative size and depth of their descriptions. This is motivated by recent progress in practical instantiations of secure multi-party computation (MPC), fully homomorphic encryption (FHE), and zero-knowledge proofs (ZK) where linear computations are, compared to non-linear operations, essentially “free”. We focus on the case of a block cipher, and propose the family of block ciphers “LowMC”, beating all existing proposals with respect to these metrics by far. We sketch several applications for such ciphers and give implementation comparisons suggesting that when encrypting larger amounts of data the new design strategy translates into improvements in computation and communication complexity by up to a factor of 5 compared to AES-128, which incidentally is one of the most competitive classical designs. Furthermore, we identify cases where “free XORs” can no longer be regarded as such but represent a bottleneck, hence refuting this commonly held belief with a practical example.
[56] Daniel Demmler, Thomas Schneider, and Michael Zohner. ABY – a framework for efficient mixed-protocol secure two-party computation. In 22. Network and Distributed System Security Symposium (NDSS'15), Internet Society, San Diego, CA, USA, February 8-11, 2015. Code: https://encrypto.de/code/ABY. Acceptance rate 18.4%. CORE rank A*. [ bib | pdf | web ]
Secure computation enables mutually distrusting parties to jointly evaluate a function on their private inputs without revealing anything but the function's output. Generic secure computation protocols in the semi-honest model have been studied extensively and several best practices have evolved.
In this work, we design and implement a mixed-protocol framework, called ABY, that efficiently combines secure computation schemes based on Arithmetic sharing, Boolean sharing, and Yao's garbled circuits and that makes available best practice solutions in secure two-party computation. Our framework allows to pre-compute almost all cryptographic operations and provides novel, highly efficient conversions between secure computation schemes based on pre-computed oblivious transfer extensions. ABY supports several standard operations and we perform benchmarks on a local network and in a public intercontinental cloud. From our benchmarks we deduce new insights on the efficient design of secure computation protocols, most prominently that oblivious transfer-based multiplications are much more efficient than multiplications based on homomorphic encryption. We use ABY to construct mixed-protocols for three example applications – private set intersection, biometric matching, and modular exponentiation – and show that they are more efficient than using a single protocol.
[55] Daniel Demmler, Amir Herzberg, and Thomas Schneider. RAID-PIR: Practical multi-server PIR. In 6. ACM Cloud Computing Security Workshop (CCSW'14), pages 45–56, ACM, Scottsdale, AZ, USA, November 7, 2014. Code: https://encrypto.de/code/RAID-PIR. Acceptance rate 33.3%. [ bib | DOI | pdf | web ]
Private Information Retrieval (PIR) allows to privately request a block of data from a database such that no information about the queried block is revealed to the database owner. With the rapid rise of cloud computing, data is often shared across multiple servers, making multi-server PIR a promising privacy-enhancing technology.
In this paper, we introduce RAID-PIR, an efficient and simple multi-server PIR scheme, which has similar approach to RAID (Redundant Arrays of Inexpensive Disks) systems. Each server stores only a part of the database, its computational complexity depends only on this part, and multiple blocks can be queried efficiently in parallel. RAID-PIR improves efficiency over known PIR protocols, using only very efficient cryptographic primitives (pseudo-random generator). We demonstrate that RAID-PIR is practical and well-suited for cloud deployment as it reduces the communication as well as the computational workload per server.
[54] Daniel Demmler, Thomas Schneider, and Michael Zohner. Ad-hoc secure two-party computation on mobile devices using hardware tokens. In 23. USENIX Security Symposium (USENIX Security'14), pages 893–908, USENIX, San Diego, CA, USA, August 20-22, 2014. Full version: https://ia.cr/2014/467. Acceptance rate 19.1%. CORE rank A*. [ bib | pdf | web ]
Secure two-party computation allows two mutually distrusting parties to jointly compute an arbitrary function on their private inputs without revealing anything but the result. An interesting target for deploying secure computation protocols are mobile devices as they contain a lot of sensitive user data. However, their resource restrictions make this a challenging task.
In this work, we optimize and implement the secure computation protocol by Goldreich-Micali-Wigderson (GMW) on mobile phones. To increase performance, we extend the protocol by a trusted hardware token (i.e., a smartcard). The trusted hardware token allows to pre-compute most of the workload in an initialization phase, which is executed locally on one device and can be pre-computed independently of the later communication partner. We develop and analyze a proof-of-concept implementation of generic secure two-party computation on Android smart phones making use of a microSD smartcard. Our use cases include private set intersection for finding shared contacts and private scheduling of a meeting with location preferences. For private set intersection, our token-aided implementation on mobile phones is up to two orders of magnitude faster than previous generic secure two-party computation protocols on mobile phones and even as fast as previous work on desktop computers.
[53] Benny Pinkas, Thomas Schneider, and Michael Zohner. Faster private set intersection based on OT extension. In 23. USENIX Security Symposium (USENIX Security'14), pages 797–812, USENIX, San Diego, CA, USA, August 20-22, 2014. Full version: https://ia.cr/2014/447. Code: https://encrypto.de/code/PSI. Acceptance rate 19.1%. CORE rank A*. [ bib | pdf | web ]
Private set intersection (PSI) allows two parties to compute the intersection of their sets without revealing any information about items that are not in the intersection. It is one of the best studied applications of secure computation and many PSI protocols have been proposed. However, the variety of existing PSI protocols makes it difficult to identify the solution that performs best in a respective scenario, especially since they were not all implemented and compared in the same setting.
In this work, we give an overview on existing PSI protocols that are secure against semi-honest adversaries. We take advantage of the most recent efficiency improvements in OT extension to propose significant optimizations to previous PSI protocols and to suggest a new PSI protocol whose runtime is superior to that of existing protocols. We compare the performance of the protocols both theoretically and experimentally, by implementing all protocols on the same platform, and give recommendations on which protocol to use in a particular setting.
[52] Julien Bringer, Hervé Chabanne, Mélanie Favre, Alain Patey, Thomas Schneider, and Michael Zohner. GSHADE: Faster privacy-preserving distance computation and biometric identification. In 2. ACM Workshop on Information Hiding and Multimedia Security (IH&MMSEC'14), pages 187–198, ACM, Salzburg, Austria, June 11-13, 2014. Code: https://encrypto.de/code/GSHADE. Acceptance rate 37.5%. CORE rank C. [ bib | DOI | pdf | web ]
At WAHC'13, Bringer et al. introduced a protocol called SHADE for secure and efficient Hamming distance computation using oblivious transfer only. In this paper, we introduce a generalization of the SHADE protocol, called GSHADE, that enables privacy-preserving computation of several distance metrics, including (normalized) Hamming distance, Euclidean distance, Mahalanobis distance, and scalar product. GSHADE can be used to efficiently compute one-to-many biometric identification for several traits (iris, face, fingerprint) and benefits from recent optimizations of oblivious transfer extensions. GSHADE allows identification against a database of 1000 Eigenfaces in 1.28 seconds and against a database of 10000 IrisCodes in 17.2 seconds which is more than 10 times faster than previous works.
[51] Matthias Schneider and Thomas Schneider. Notes on non-interactive secure comparison in “image feature extraction in the encrypted domain with privacy-preserving SIFT”. In 2. ACM Workshop on Information Hiding and Multimedia Security (IH&MMSEC'14), pages 432–440, ACM, Salzburg, Austria, June 11-13, 2014. Acceptance rate 37.5%. CORE rank C. [ bib | DOI | pdf | web ]
Protocols for secure comparison are a fundamental building block of many privacy-preserving protocols such as privacy-preserving face recognition or privacy-preserving fingerprint authentication. So far, all existing secure comparison protocols that have been used in practical implementations require interaction.
In recent work, Hsu et al. (IEEE Transactions on Image Processing 2012) propose protocols for privacy-preserving computation of the scale-invariant feature transform (SIFT) in the encrypted domain. Their fundamental building block is a new protocol for performing secure comparisons under additively homomorphic encryption that requires no interaction.
In this paper we present potential for optimization and shortcomings of their secure comparison protocol. More specifically, we show that it 1) allows optimizations by shifting computation from the server to the user, 2) removes the gain that the user has in outsourcing computations to the server, and most importantly is 3) either computationally intractable for the server or insecure. As alternatives we propose to use either interactive comparison protocols or non-interactive somewhat or fully homomorphic encryption.
[50] Florian Kerschbaum, Thomas Schneider, and Axel Schröpfer. Automatic protocol selection in secure two-party computations. In 12. International Conference on Applied Cryptography and Network Security (ACNS'14), volume 8479 of LNCS, pages 566–584, Springer, Lausanne, Switzerland, June 10-13, 2014. Full version: https://ia.cr/2014/200. Acceptance rate 22.4%. CORE rank B. [ bib | DOI | pdf ]
Performance of secure computation is still often an obstacle to its practical adaption. There are different protocols for secure computation that compete for the best performance.
In this paper we propose automatic protocol selection which selects a protocol for each operation resulting in a mix with the best performance so far. Based on an elaborate performance model, we propose an optimization algorithm and an efficient heuristic for this selection problem. We show that our mixed protocols achieve the best performance on a set of use cases. Furthermore, our results underpin that the selection problem is so complicated and large in size, that a programmer is unlikely to manually make the optimal selection. Our proposed algorithms nevertheless can be integrated into a compiler in order to yield the best (or near-optimal) performance.
[49] Daniel Demmler, Thomas Schneider, and Michael Zohner. Hardware-assisted ad-hoc secure two-party computation on smartphones. In 19. Workshop der Fachgruppe Kryptographie in der Gesellschaft für Informatik (Kryptotag), Stuttgart, Germany, November 14-15, 2013. [ bib | pdf ]
[48] Gilad Asharov, Yehuda Lindell, Thomas Schneider, and Michael Zohner. More efficient oblivious transfer and extensions for faster secure computation. In 20. ACM Conference on Computer and Communications Security (CCS'13), pages 535–548, ACM, Berlin, Germany, November 4-8, 2013. Full version: https://ia.cr/2013/552. Code: https://encrypto.de/code/OTExtension. Acceptance rate 19.8%. CORE rank A*. [ bib | DOI | pdf ]
Protocols for secure computation enable parties to compute a joint function on their private inputs without revealing anything but the result. A foundation for secure computation is oblivious transfer (OT), which traditionally requires expensive public key cryptography. A more efficient way to perform many OTs is to extend a small number of base OTs using OT extensions based on symmetric cryptography.
In this work we present optimizations and efficient implementations of OT and OT extensions in the semi-honest model. We propose a novel OT protocol with security in the standard model and improve OT extensions with respect to communication complexity, computation complexity, and scalability. We also provide specific optimizations of OT extensions that are tailored to the secure computation protocols of Yao and Goldreich-Micali-Wigderson and reduce the communication complexity even further. We experimentally verify the efficiency gains of our protocols and optimizations. By applying our implementation to current secure computation frameworks, we can securely compute a Levenshtein distance circuit with 1.29 billion AND gates at a rate of 1.2 million AND gates per second. Moreover, we demonstrate the importance of correctly implementing OT within secure computation protocols by presenting an attack on the FastGC framework.
[47] N. Asokan, Alexandra Dmitrienko, Marcin Nagy, Elena Reshetova, Ahmad-Reza Sadeghi, Thomas Schneider, and Stanislaus Stelle. CrowdShare: Secure mobile resource sharing. In 11. International Conference on Applied Cryptography and Network Security (ACNS'13), volume 7954 of LNCS, pages 432–440, Springer, Banff, Alberta, Canada, June 25-28, 2013. Short paper. Full version: https://encrypto.de/papers/ADNRSSS13_TR.pdf. CORE rank B. [ bib | DOI | pdf | web ]
Mobile smart devices and services have become an integral part of our daily life. In this context there are many compelling scenarios for mobile device users to share resources. A popular example is tethering. However, sharing resources also raises privacy and security issues. In this paper, we present CrowdShare, a complete framework and its (Android) implementation for secure and private resource sharing among nearby devices. CrowdShare provides pseudonymity for users, accountability of resource usage, and the possibility of specifying access control in terms of social network relationships. Further, CrowdShare preserves secure connectivity between nearby devices even in the absence of the mobile infrastructure. We have implemented CrowdShare on Android devices and report good performance results.
[46] Vladimir Kolesnikov and Thomas Schneider. Secure function evaluation techniques for circuits containing XOR gates with applications to universal circuits. U.S. patent no 8443205 (applied October 24, 2008; issued May 14, 2013), May 14, 2013. [ bib | pub ]
An embodiment of the present invention provides a method that minimizes the number of entries required in a garbled circuit associated with secure function evaluation of a given circuit. Exclusive OR (XOR) gates are evaluated in accordance with an embodiment of the present invention without the need of associated entries in the garbled table to yield minimal computational and communication effort. This improves the performance of SFE evaluation. Another embodiment of the present invention provides a method that replaces regular gates with more efficient constructions containing XOR gates in an implementation of a Universal Circuit, and circuits for integer addition and multiplication, thereby maximizing the performance improvement provided by the above.
[45] Wilko Henecka and Thomas Schneider. Faster secure two-party computation with less memory. In 8. ACM Symposium on Information, Computer and Communications Security (ASIACCS'13), pages 437–446, ACM, Hangzhou, China, May 7-10, 2013. Code: https://encrypto.de/code/me-sfe. Acceptance rate 16.2% for full papers. CORE rank B. [ bib | DOI | pdf ]
Secure two-party computation is used as the basis for a large variety of privacy-preserving protocols, but often concerns about the low performance hinder the move away from nonprivate solutions.
In this paper we present an improved implementation of Yao's garbled circuit protocol in the semi-honest adversaries setting which is up to 10 times faster than previous implementations. Our improvements include (1) the first multi-threaded implementation of the base oblivious transfers resulting in a speedup of a factor of two, (2) techniques for minimizing the memory footprint during oblivious transfer extensions and processing of circuits, (3) compilation of sub-circuits into files, and (4) caching of circuit descriptions and network packets. We implement improved circuit building blocks from the literature and present for the first time performance results for secure evaluation of the ultra-lightweight block cipher PRESENT within 7 ms online time.
[44] Thomas Schneider and Michael Zohner. GMW vs. Yao? Efficient secure two-party computation with low depth circuits. In 17. International Conference on Financial Cryptography and Data Security (FC'13), volume 7859 of LNCS, pages 275–292, Springer, Okinawa, Japan, April 1-5, 2013. Acceptance rate 12.5% for regular papers. CORE rank B. [ bib | DOI | pdf | web ]
Secure two-party computation is a rapidly emerging field of research and enables a large variety of privacy-preserving applications such as mobile social networks or biometric identification. In the late eighties, two different approaches were proposed: Yao's garbled circuits and the protocol of Goldreich-Micali-Wigderson (GMW). Since then, research has mostly focused on Yao's garbled circuits as they were believed to yield better efficiency due to their constant round complexity.
In this work we give several optimizations for an efficient implementation of the GMW protocol. We show that for semi-honest adversaries the optimized GMW protocol can outperform today's most efficient implementations of Yao's garbled circuits, but highly depends on a low network latency. As a first step to overcome these latency issues, we summarize depth-optimized circuit constructions for various standard tasks. As application scenario we consider privacy-preserving face recognition and show that our optimized framework is up to 100 times faster than previous works even in settings with high network latency.
[43] Florian Kerschbaum, Thomas Schneider, and Axel Schröpfer. Automatic protocol selection in secure two-party computations. 20. Network and Distributed System Security Symposium (NDSS'13) Short Talk, San Diego, CA, USA, February 24-27, 2013. CORE rank A*. [ bib | pdf | web ]
[42] Vladimir Kolesnikov, Ahmad-Reza Sadeghi, and Thomas Schneider. A systematic approach to practically efficient general two-party secure function evaluation protocols and their modular design. Journal of Computer Security (JCS), 21(2):283–315, January 2013. Preliminary version: https://ia.cr/2010/079. CORE rank B. [ bib | DOI | pdf | web ]
General two-party Secure Function Evaluation (SFE) allows mutually distrusting parties to correctly compute any function on their private input data, without revealing the inputs. Two-party SFE can benefit almost any client-server interaction where privacy is required, such as privacy-preserving credit checking, medical classification, or face recognition. Today, SFE is a subject of immense amount of research in a variety of directions and is not easy to navigate.
In this article, we systematize the most practically important works of the vast research knowledge on general SFE. We argue that in many cases the most efficient SFE protocols are obtained by combining several basic techniques, e.g., garbled circuits and (additively) homomorphic encryption.
As a valuable methodological contribution, we present a framework in which today's most efficient techniques for general SFE can be viewed as building blocks with well-defined interfaces that can be easily combined into a complete efficient solution. Further, our approach naturally allows automated protocol generation (compilation) and has been implemented partially in the TASTY framework. In summary, we provide a comprehensive guide in state-of-the-art SFE, with the additional goal of extracting, systematizing and unifying the most relevant and promising general SFE techniques. Our target audience are graduate students wishing to enter the SFE field and advanced engineers seeking to develop SFE solutions. We hope our guide paints a high-level picture of the field, including most common approaches and their trade-offs and gives precise and numerous pointers to formal treatment of its specific aspects.
[41] Thomas Schneider and Michael Zohner. Efficient secure two-party computation. In 17. Workshop der Fachgruppe Kryptographie in der Gesellschaft für Informatik (Kryptotag), Heidelberg, Germany, December 7, 2012. [ bib | pdf ]
[40] Pille Pullonen, Dan Bogdanov, and Thomas Schneider. The design and implementation of a two-party protocol suite for SHAREMIND 3. Technical report, CYBERNETICA Institute of Information Security, 2012. T-4-17. [ bib | pdf ]
[39] Thomas Schneider. Engineering Secure Two-Party Computation Protocols: Design, Optimization, and Applications of Efficient Secure Function Evaluation. Springer-Verlag Berlin Heidelberg, August 4, 2012. https://thomaschneider.de/engineeringSFEbook. [ bib | DOI | pub ]
[38] Vladimir Kolesnikov and Thomas Schneider. Universal circuit for secure function evaluation. U.S. patent no 8175854 (applied July 14, 2008; issued May 8, 2012), May 8, 2012. [ bib | pub ]
An exemplary method enables implementation of a universal circuit capable of emulating each gate of a circuit designed to calculate a function. A first selection module receives inputs associated with the function. It generates outputs that are an ordered series of the inputs. A universal module receives these outputs and generates another set of outputs. A second selection module receives the outputs from the universal module and generates final function outputs that are an ordered series inputs received from the universal module. The selection modules and universal module themselves are also aspects of the present invention.
[37] Junaid Jameel Ahmad, Shujun Li, Ahmad-Reza Sadeghi, and Thomas Schneider. CTL: A platform-independent crypto tools library based on dataflow programming paradigm. In 16. International Conference on Financial Cryptography and Data Security (FC'12), volume 7397 of LNCS, pages 299–313, Springer, Bonaire, February 27 - March 2, 2012. Full version: https://ia.cr/2011/679. Acceptance rate 26.1%. CORE rank B. [ bib | DOI | pdf | web ]
The diversity of computing platforms is increasing rapidly. In order to allow security applications to run on such diverse platforms, implementing and optimizing the same cryptographic primitives for multiple target platforms and heterogeneous systems can result in high costs. In this paper, we report our efforts in developing and benchmarking a platform-independent Crypto Tools Library (CTL). CTL is based on a dataflow programming framework called Reconfigurable Video Coding (RVC), which was recently standardized by ISO/IEC for building complicated reconfigurable video codecs. CTL benefits from various properties of the RVC framework including tools to 1) simulate the platform-independent designs, 2) automatically generate implementations in different target programming languages (e.g., C/C++, Java, LLVM, and Verilog/VHDL) for deployment on different platforms as software and/or hardware modules, and 3) design space exploitation such as automatic parallelization for multi- and many-core systems. We benchmarked the performance of the SHA-256 implementation in CTL on single-core target platforms and demonstrated that implementations automatically generated from platform-independent RVC applications can achieve a run-time performance comparable to reference implementations manually written in C and Java. For a quad-core target platform, we benchmarked a 4-adic hash tree application based on SHA-256 that achieves a performance gain of up to 300% for hashing messages of size 8 MB.
[36] Sven Bugiel, Stefan Nürnberger, Ahmad-Reza Sadeghi, and Thomas Schneider. Twin Clouds: Secure cloud computing with low latency. In 12. Communications and Multimedia Security Conference (CMS'11), volume 7025 of LNCS, pages 32–44, Springer, October 19-21, 2011. Best Paper Award. Acceptance rate 21.2%. CORE rank C. [ bib | DOI | pdf ]
Cloud computing promises a cost effective enabling technology to outsource storage and massively parallel computations. However, existing approaches for provably secure outsourcing of data and arbitrary computations are either based on tamper-proof hardware or fully homomorphic encryption. The former approaches are not scaleable, while the latter ones are currently not efficient enough to be used in practice.
We propose an architecture and protocols that accumulate slow secure computations over time and provide the possibility to query them in parallel on demand by leveraging the benefits of cloud computing. In our approach, the user communicates with a resource-constrained Trusted Cloud (either a private cloud or built from multiple secure hardware modules) which encrypts algorithms and data to be stored and later on queried in the powerful but untrusted Commodity Cloud. We split our protocols such that the Trusted Cloud performs security-critical pre-computations in the setup phase, while the Commodity Cloud computes the time-critical query in parallel under encryption in the query phase.
[35] Sven Bugiel, Stefan Nürnberger, Thomas Pöppelmann, Ahmad-Reza Sadeghi, and Thomas Schneider. AmazonIA: When elasticity snaps back. In 18. ACM Conference on Computer and Communications Security (CCS'11), pages 389–400, ACM, Chicago, IL, USA, October 17-21, 2011. Info: https://encrypto.de/AMID. Acceptance rate 14.0%. CORE rank A*. [ bib | DOI | pdf | web ]
Cloud Computing is an emerging technology promising new business opportunities and easy deployment of web services.
Much has been written about the risks and benefits of cloud computing in the last years. The literature on clouds often points out security and privacy challenges as the main obstacles, and proposes solutions and guidelines to avoid them. However, most of these works deal with either malicious cloud providers or customers, but ignore the severe threats caused by unaware users.
In this paper we consider security and privacy aspects of real-life cloud deployments, independently from malicious cloud providers or customers. We focus on the popular Amazon Elastic Compute Cloud (EC2) and give a detailed and systematic analysis of various crucial vulnerabilities in publicly available and widely used Amazon Machine Images (AMIs) and show how to eliminate them.
Our Amazon Image Attacks (AmazonIA) deploy an automated tool that uses only publicly available interfaces and makes no assumptions on the underlying cloud infrastructure. We were able to extract highly sensitive information (including passwords, keys, and credentials) from a variety of publicly available AMIs. The extracted information allows to (i) start (botnet) instances worth thousands of dollars per day, (ii) provide backdoors into the running machines, (iii) launch impersonation attacks, or (iv) access the source code of the entire web service. Our attacks can be used to completely compromise several real web services offered by companies (including IT-security companies), e.g., for website statistics/user tracking, two-factor authentication, or price comparison. Further, we show mechanisms to identify the AMI of certain running instances.
Following the maxim “security and privacy by design” we show how our automated tools together with changes to the user interface can be used to mitigate our attacks.
[34] Mauro Barni, Pierluigi Failla, Riccardo Lazzeretti, Ahmad-Reza Sadeghi, and Thomas Schneider. Privacy-preserving ECG classification with branching programs and neural networks. IEEE Transactions on Information Forensics and Security (TIFS), 6(2):452–468, June 2011. CORE rank A. [ bib | DOI | pdf | web ]
Privacy protection is a crucial problem in many biomedical signal processing applications. For this reason particular attention has been given to the use of secure multi party computation techniques for processing biomedical signals, whereby non-trusted parties are able to manipulate the signals although they are encrypted.
This paper focuses on the development of a privacy preserving automatic diagnosis system whereby a remote server classifies a biomedical signal provided by the client without getting any information about the signal itself and the final result of the classification. Specifically, we present and compare two methods for the secure classification of ElectroCardioGram (ECG) signals: the former based on Linear Branching Programs (a particular kind of decision tree) and the latter relying on Neural Networks.
The paper faces with all the requirements and difficulties related to working with data that must stay encrypted during all the computation steps, including the necessity of working with fixed point arithmetic with no truncation while guaranteeing the same performance of a floating point implementation in the plain domain. A highly efficient version of the underlying cryptographic primitives is used, ensuring a good efficiency of the two proposed methods, from both a communication and computational complexity perspectives.
The proposed systems prove that carrying out complex tasks like ECG classification in the encrypted domain efficiently is indeed possible in the semi-honest model, paving the way to interesting future applications wherein privacy of signal owners is protected by applying high security standards.
[33] Thomas Schneider. Reden ist Silber - Schweigen ist Gold: Datensparsamkeit durch effizientes Rechnen unter Verschlüsselung. In 12. Deutscher IT-Sicherheitskongress des BSI: Sicher in die digitale Welt von morgen, pages 191–198, SecuMedia-Verlag, Bonn, Germany, May 10-12, 2011. [ bib | pdf | pub ]
Wo immer sensible Daten gespeichert werden zeigt die Praxis, dass es lediglich eine Frage der Zeit ist, bis diese durch ein Sicherheitsleck an unerwünschte Personen gelangen. Die einzige Möglichkeit, um dies zuverlässig zu vermeiden ist Datensparsamkeit, die Daten also erst gar nicht zu speichern. In vielen Fällen werden die Daten jedoch trotzdem für Berechnungen benötigt.
Dieser Beitrag gibt einen überblick über Methoden des effizienten Rechnens unter Verschlüsselung und zeigt, wie diese ermöglichen, beliebige Berechnungen auf sensiblen, verschlüsselten Daten durchzuführen, ohne dass diese im Klartext gespeichert oder zu irgendeinem Zeitpunkt im Klartext vorliegen müssen. Insbesondere wird hierbei auf Erweiterungen durch sichere Hardware auch im Kontext des Rechnens in der “Cloud”, sowie die Unterstützung durch Werkzeuge eingegangen. Als mögliche Anwendungen werden Systeme zur Gesichtserkennung und Klassifikation medizinischer Daten betrachtet, welche die Privatsphäre erhalten.
[32] Sven Bugiel, Stefan Nürnberger, Ahmad-Reza Sadeghi, and Thomas Schneider. Twin Clouds: An architecture for secure cloud computing (Extended Abstract). Workshop on Cryptography and Security in Clouds (WCSC'11), Zurich, Switzerland, March 15-16, 2011. [ bib | pdf | web ]
Cloud computing promises a more cost effective enabling technology to outsource storage and computations. Existing approaches for secure outsourcing of data and arbitrary computations are either based on a single tamper-proof hardware, or based on recently proposed fully homomorphic encryption. The hardware based solutions are not scaleable, and fully homomorphic encryption is currently only of theoretical interest and very inefficient.
In this paper we propose an architecture for secure outsourcing of data and arbitrary computations to an untrusted commodity cloud. In our approach, the user communicates with a trusted cloud (either a private cloud or built from multiple secure hardware modules) which encrypts and verifies the data stored and operations performed in the untrusted commodity cloud. We split the computations such that the trusted cloud is mostly used for security-critical operations in the less time-critical setup phase, whereas queries to the outsourced data are processed in parallel by the fast commodity cloud on encrypted data.
[31] Marc Fischlin, Benny Pinkas, Ahmad-Reza Sadeghi, Thomas Schneider, and Ivan Visconti. Secure set intersection with untrusted hardware tokens. In 11. Cryptographers' Track at the RSA Conference (CT-RSA'11), volume 6558 of LNCS, pages 1–16, Springer, San Francisco, CA, USA, February 14-18, 2011. Acceptance rate 29.9%. CORE rank B. [ bib | DOI | pdf | web ]
Secure set intersection protocols are the core building block for a manifold of privacy-preserving applications.
In a recent work, Hazay and Lindell (ACM CCS 2008) introduced the idea of using trusted hardware tokens for the set intersection problem, devising protocols which improve over previous (in the standard model of two-party computation) protocols in terms of efficiency and secure composition. Their protocol uses only a linear number of symmetric-key computations and the amount of data stored in the token does not depend on the sizes of the sets. The security proof of the protocol is in the universal composability model and is based on the strong assumption that the token is trusted by both parties.
In this paper we revisit the idea and model of hardware-based secure set intersection, and in particular consider a setting where tokens are not necessarily trusted by both participants to additionally cover threats like side channel attacks, firmware trapdoors and malicious hardware. Our protocols are very efficient and achieve the same level of security as those by Hazay and Lindell for trusted tokens. For untrusted tokens, our protocols ensure privacy against malicious adversaries, and correctness facing covert adversaries.
[30] Thomas Schneider. Engineering Secure Two-Party Computation Protocols – Advances in Design, Optimization, and Applications of Efficient Secure Function Evaluation. PhD thesis, Ruhr-University Bochum, Germany, February 9, 2011. [ bib | pdf ]
Secure Function Evaluation (SFE) allows two mutually mistrusting parties to compute an arbitrary function on their inputs without revealing any information beyond the result. We give advances in the design, optimization and application of efficient SFE.
We optimize SFE protocols by reducing the size of Boolean circuits with cheap XOR gates and give efficient circuits for standard functionalities.
Secure hardware reduces the communication of SFE protocols and allows to evaluate arbitrary functions in a side-channel resistant way.
Efficient SFE protocols can be modularly modeled as sequence of operations on encrypted data; TASTY (Tool for Automating Secure Two-partY computations) allows to describe, automatically generate, and execute them.
As applications we improve protocols for secure auctions and face recognition, and give a hardware-assisted protocol to securely outsource data and arbitrary computations to an untrusted (cloud) provider.
[29] Kimmo Järvinen, Vladimir Kolesnikov, Ahmad-Reza Sadeghi, and Thomas Schneider. Efficient secure two-party computation with untrusted hardware tokens. In Ahmad-Reza Sadeghi and David Naccache, editors, Towards Hardware Intrinsic Security: Foundation and Practice, Information Security and Cryptography, pages 367–386. Springer-Verlag Berlin Heidelberg, 2010. [ bib | DOI ]
[28] Wilko Henecka, Stefan Kögl, Ahmad-Reza Sadeghi, Thomas Schneider, and Immo Wehrenberg. TASTY: Tool for Automating Secure Two-partY computations. In 17. ACM Conference on Computer and Communications Security (CCS'10), pages 451–462, ACM, Chicago, IL, USA, October 4-8, 2010. Full version: https://ia.cr/2010/365. Code: https://encrypto.de/code/TASTY. Acceptance rate 17.2%. CORE rank A*. [ bib | DOI | pdf | web ]
Secure two-party computation allows two untrusting parties to jointly compute an arbitrary function on their respective private inputs while revealing no information beyond the outcome. Existing cryptographic compilers can automatically generate secure computation protocols from high-level specifications, but are often limited in their use and efficiency of generated protocols as they are based on either garbled circuits or (additively) homomorphic encryption only.
In this paper we present TASTY, a novel tool for automating, i.e., describing, generating, executing, benchmarking, and comparing, efficient secure two-party computation protocols. TASTY is a new compiler that can generate protocols based on homomorphic encryption and efficient garbled circuits as well as combinations of both, which often yields the most efficient protocols available today. The user provides a high-level description of the computations to be performed on encrypted data in a domain-specific language. This is automatically transformed into a protocol. TASTY provides most recent techniques and optimizations for practical secure two-party computation with low online latency. Moreover, it allows to efficiently evaluate circuits generated by the well-known Fairplay compiler.
We use TASTY to compare protocols for secure multiplication based on homomorphic encryption with those based on garbled circuits and highly efficient Karatsuba multiplication. Further, we show how TASTY improves the online latency for securely evaluating the AES functionality by an order of magnitude compared to previous software implementations. TASTY allows to automatically generate efficient secure protocols for many privacy-preserving applications where we consider the use cases for private set intersection and face recognition protocols.
[27] José Bacelar Almeida, Endre Bangerter, Manuel Barbosa, Stephan Krenn, Ahmad-Reza Sadeghi, and Thomas Schneider. A certifying compiler for zero-knowledge proofs of knowledge based on sigma-protocols. In 15. European Symposium on Research in Computer Security (ESORICS'10), volume 6345 of LNCS, pages 151–167, Springer, Athens, Greece, September 20-22, 2010. Full version: https://ia.cr/2010/339. Acceptance rate 20.9%. CORE rank A. [ bib | DOI | pdf ]
Zero-knowledge proofs of knowledge (ZK-PoK) are important building blocks for numerous cryptographic applications. Although ZK-PoK have a high potential impact, their real world deployment is typically hindered by their significant complexity compared to other (non-interactive) crypto primitives. Moreover, their design and implementation are time-consuming and error-prone.
We contribute to overcoming these challenges as follows: We present a comprehensive specification language and a compiler for ZK-PoK protocols based on Σ-protocols. The compiler allows the fully automatic translation of an Abstract description of a proof goal into an executable implementation. Moreover, the compiler overcomes various restrictions of previous approaches, e.g., it supports the important class of exponentiation homomorphisms with hidden-order co-domain, needed for privacy-preserving applications such as DAA. Finally, our compiler is certifying, in the sense that it automatically produces a formal proof of the soundness of the compiled protocol for a large class of protocols using the Isabelle/HOL theorem prover.
[26] Ahmad-Reza Sadeghi and Thomas Schneider. Verschlüsselt Rechnen: Sichere Verarbeitung verschlüsselter medizinischer Daten am Beispiel der Klassifikation von EKG-Daten. In Workshop Innovative und sichere Informationstechnologie für das Gesundheitswesen von morgen (perspeGKtive'10), volume P-174 of LNI, pages 11–25, Bonner Köllen Verlag, Darmstadt, Germany, September 8, 2010. [ bib | pdf | pub ]
Die rasant fortschreitende Modernisierung des Gesundheitswesens durch neuartige elektronische Dienste wie die elektronische Patientenakte und medizinische online Dienste erlaubt es, medizinische Prozesse effizienter zu gestalten. Andererseits birgt die digitale Verarbeitung sensibler Patientendaten Risiken und Gefahren hinsichtlich des Datenschutzes und des Missbrauchs.
Klassische kryptographische und IT sicherheitstechnische Methoden erlauben die sichere Verteilung und Speicherung medizinischer Daten. Allerdings erfordert die Verarbeitung der Daten deren Entschlüsselung. Zu diesem Zeitpunkt kann auf die Daten im Klartext (z.B. durch Systemadministratoren) zugegriffen und die Vertraulichkeit verletzt werden. Um dies zu verhindern, sollten Daten in verschlüsselter Form verarbeitet werden. Für ebendieses “Rechnen unter Verschlüsselung” wurden in den vergangenen 25 Jahren verschiedene kryptographische Verfahren vorgeschlagen.
Die Ziele dieser Arbeit sind folgende: 1) Der aktuelle Stand der Forschung im Bereich des effizienten Rechnens unter Verschlüsselung wird zusammengefasst. 2) Ein Werkzeug wird vorgestellt, das es erlaubt, effiziente Protokolle zum Rechnen unter Verschlüsselung abstrakt und ohne detaillierte kryptographische Kenntnisse zu beschreiben und automatisch zu generieren. 3) Es wird gezeigt, wie das vorgestellte Werkzeug exemplarisch zum Generieren eines medizinischen Web-Services verwendet werden kann, der EKG Daten in verschlüsselter Form klassifiziert.
[25] Kimmo Järvinen, Vladimir Kolesnikov, Ahmad-Reza Sadeghi, and Thomas Schneider. Garbled circuits for leakage-resilience: Hardware implementation and evaluation of one-time programs. In 12. International Workshop on Cryptographic Hardware and Embedded Systems (CHES'10), volume 6225 of LNCS, pages 383–397, Springer, Santa Barbara, CA, USA, August 17-20, 2010. Full version: https://ia.cr/2010/276. Acceptance rate 27.8%. CORE rank A. [ bib | DOI | pdf | web ]
The power of side-channel leakage attacks on cryptographic implementations is evident. Today's practical defenses are typically attack-specific countermeasures against certain classes of side-channel attacks. The demand for a more general solution has given rise to the recent theoretical research that aims to build provably leakage-resilient cryptography. This direction is, however, very new and still largely lacks practitioners' evaluation with regard to both efficiency and practical security. A recent approach, One-Time Programs (OTPs), proposes using Yao's Garbled Circuit (GC) and very simple tamper-proof hardware to securely implement oblivious transfer, to guarantee leakage resilience.
Our main contributions are (i) a generic architecture for using GC/OTP modularly, and (ii) hardware implementation and efficiency analysis of GC/OTP evaluation. We implemented two FPGA-based prototypes: a system-on-a-programmable-chip with access to hardware crypto accelerator (suitable for smartcards and future smartphones), and a stand-alone hardware implementation (suitable for ASIC design). We chose AES as a representative complex function for implementation and measurements. As a result of this work, we are able to understand, evaluate and improve the practicality of employing GC/OTP as a leakage-resistance approach.
[24] Endre Bangerter, Stephan Krenn, Ahmad-Reza Sadeghi, and Thomas Schneider. YACZK: Yet another compiler for zero-knowledge. 19. USENIX Security Symposium (USENIX Security'10) Poster Session, Washington, DC, USA, August 11-13, 2010. CORE rank A*. [ bib | pdf | poster | web ]
Automatic generation of cryptographic protocols is an emerging field of research which aims to bring complex protocols into practice. In this work we discuss the desired properties of a compiler for automatic generation of zero-knowledge proof of knowledge (ZKPoK) protocols. We evaluate and compare existing approaches with respect to these properties: In particular, it seems to us that the authors of the paper accepted for USENIX Security 2010 (ZKPDL: A Language-Based System for Efficient Zero-Knowledge Proofs and Electronic Cash) were not aware of our previous work done within the European project “Computer Aided Cryptography Engineering” (CACE). We hope that this poster stimulates scientific debates and exchange in this field of research.
[23] Ahmad-Reza Sadeghi, Thomas Schneider, and Marcel Winandy. Token-based cloud computing – secure outsourcing of data and arbitrary computations with lower latency. In 3. International Conference on Trust and Trustworthy Computing (TRUST'10) - Workshop on Trust in the Cloud, volume 6101 of LNCS, pages 417–429, Springer, Berlin, Germany, June 21-23, 2010. [ bib | DOI | pdf | web ]
Secure outsourcing of computation to an untrusted (cloud) service provider is becoming more and more important. Pure cryptographic solutions based on fully homomorphic and verifiable encryption, recently proposed, are promising but suffer from very high latency. Other proposals perform the whole computation on tamper-proof hardware and usually suffer from the same problem. Trusted computing (TC) is another promising approach that uses trusted software and hardware components on computing platforms to provide useful mechanisms such as attestation allowing the data owner to verify the integrity of the cloud and its computation. However, on the one hand these solutions require trust in hardware (CPU, trusted computing modules) that are under the physical control of the cloud provider, and on the other hand they still have to face the challenge of run-time attestation.
In this paper we focus on applications where the latency of the computation should be minimized, i.e., the time from submitting the query until receiving the outcome of the computation should be as small as possible. To achieve this we show how to combine a trusted hardware token (e.g., a cryptographic coprocessor or provided by the customer) with Secure Function Evaluation (SFE) to compute arbitrary functions on secret (encrypted) data where the computation leaks no information and is verifiable. The token is used in the setup phase only whereas in the time-critical online phase the cloud computes the encrypted function on encrypted data using symmetric encryption primitives only and without any interaction with other entities.
[22] Kimmo Järvinen, Vladimir Kolesnikov, Ahmad-Reza Sadeghi, and Thomas Schneider. Embedded SFE: Offloading server and network using hardware tokens. In 14. International Conference on Financial Cryptography and Data Security (FC'10), volume 6052 of LNCS, pages 207–221, Springer, Tenerife, Canary Islands, Spain, January 25-28, 2010. Full version: https://ia.cr/2009/591. Acceptance rate 14.6%. CORE rank B. [ bib | DOI | pdf | web ]
We consider Secure Function Evaluation (SFE) in the client-server setting where the server issues a secure token to the client. The token is not trusted by the client and is not a trusted third party.
We show how to take advantage of the token to drastically reduce the communication complexity of SFE and computation load of the server.
Our main contribution is the detailed consideration of design decisions, optimizations, and trade-offs, associated with the setting and its strict hardware requirements for practical deployment. In particular, we model the token as a computationally weak device with small constant-size memory and limit communication between client and server.
We consider semi-honest, covert, and malicious adversaries. We show the feasibility of our protocols based on a FPGA implementation.
[21] Vladimir Kolesnikov, Ahmad-Reza Sadeghi, and Thomas Schneider. Improved garbled circuit building blocks and applications to auctions and computing minima. In 8. International Conference on Cryptology And Network Security (CANS'09), volume 5888 of LNCS, pages 1–20, Springer, Kanazawa, Japan, December 12-14, 2009. Full version: https://ia.cr/2009/411. Acceptance rate 29.4%. CORE rank B. [ bib | DOI | pdf | web ]
We consider generic Garbled Circuit (GC)-based techniques for Secure Function Evaluation (SFE) in the semi-honest model.
We describe efficient GC constructions for addition, subtraction, multiplication, and comparison functions. Our circuits for subtraction and comparison are approximately two times smaller (in terms of garbled tables) than previous constructions. This implies corresponding computation and communication improvements in SFE of functions using our efficient building blocks. The techniques rely on recently proposed “free XOR” GC technique.
Further, we present concrete and detailed improved GC protocols for the problem of secure integer comparison, and related problems of auctions, minimum selection, and minimal distance. Performance improvement comes both from building on our efficient basic blocks and several problem-specific GC optimizations. We provide precise cost evaluation of our constructions, which serves as a baseline for future protocols.
[20] Benny Pinkas, Thomas Schneider, Nigel P. Smart, and Stephen C. Williams. Secure two-party computation is practical. In 15. Advances in Cryptology – ASIACRYPT'09, volume 5912 of LNCS, pages 250–267, Springer, Tokyo, Japan, December 6-10, 2009. Full version: https://ia.cr/2009/314. Acceptance rate 13.7%. CORE rank A. [ bib | DOI | pdf | web ]
Secure multi-party computation has been considered by the cryptographic community for a number of years. Until recently it has been a purely theoretical area, with few implementations with which to test various ideas. This has led to a number of optimisations being proposed which are quite restricted in their application. In this paper we describe an implementation of the two-party case, using Yao's garbled circuits, and present various algorithmic protocol improvements. These optimisations are analysed both theoretically and empirically, using experiments of various adversarial situations. Our experimental data is provided for reasonably large circuits, including one which performs an AES encryption, a problem which we discuss in the context of various possible applications.
[19] Mauro Barni, Pierluigi Failla, Vladimir Kolesnikov, Riccardo Lazzeretti, Annika Paus, Ahmad-Reza Sadeghi, and Thomas Schneider. Efficient privacy-preserving classification of ECG signals. In 1. IEEE International Workshop on Information Forensics and Security (IEEE WIFS'09), pages 91–95, IEEE, London, UK, December 6-9, 2009. Acceptance rate 32.5%. [ bib | DOI | pdf ]
We describe a privacy-preserving system where a server can classify an ElectroCardioGram (ECG) signal without learning any information about the ECG signal and the client is prevented from gaining knowledge about the classification algorithm used by the server. The system relies on the concept of Linear Branching Programs (LBP) and a recently proposed cryptographic protocol for secure evaluation of private LBPs. We study the trade-off between signal representation accuracy and system complexity both from practical and theoretical perspective. As a result, the inputs to the system are represented with the minimum number of bits ensuring the same classification accuracy of a plain implementation. We show how the overall system complexity can be strongly reduced by modifying the original ECG classification algorithm. Two alternatives of the underlying cryptographic protocol are implemented and their corresponding complexities are analyzed to show suitability of our system in real-life applications for current and future security levels.
[18] Ahmad-Reza Sadeghi, Thomas Schneider, and Immo Wehrenberg. Efficient privacy-preserving face recognition. In 12. International Conference on Information Security and Cryptology (ICISC'09), volume 5984 of LNCS, pages 229–244, Springer, Seoul, South Korea, December 2-4, 2009. Full version: https://ia.cr/2009/507. Acceptance rate 19.8%. CORE rank B. [ bib | DOI | pdf | web ]
Automatic recognition of human faces is becoming increasingly popular in civilian and law enforcement applications that require reliable recognition of humans. However, the rapid improvement and widespread deployment of this technology raises strong concerns regarding the violation of individuals' privacy. A typical application scenario for privacy-preserving face recognition concerns a client who privately searches for a specific face image in the face image database of a server.
In this paper we present a privacy-preserving face recognition scheme that substantially improves over previous work in terms of communication- and computation efficiency: the most recent proposal of Erkin et al. (PETS'09) requires O(logM) rounds and computationally expensive operations on homomorphically encrypted data to recognize a face in a database of M faces. Our improved scheme requires only O(1) rounds and has a substantially smaller online communication complexity (by a factor of 15 for each database entry) and less computation complexity.
Our solution is based on known cryptographic building blocks combining homomorphic encryption with garbled circuits. Our implementation results show the practicality of our scheme also for large databases (e.g., for M = 1000 we need less than 13 seconds and less than 4 MByte online communication on two 2.4GHz PCs connected via Gigabit Ethernet).
[17] Ahmad-Reza Sadeghi and Thomas Schneider. Ask your e-doctor without telling: Privacy-preserving medical diagnostics. Section Days of Ruhr-University Bochum Research School, Bochum, Germany, November 6, 2009. (Poster prize awarded). [ bib | poster | web ]
[16] Vladimir Kolesnikov, Ahmad-Reza Sadeghi, and Thomas Schneider. Improved garbled circuit building blocks and applications to auctions and computing minima. In ECRYPT workshop on Software Performance Enhancements for Encryption and Decryption and Cryptographic Compilers (SPEED-CC'09), Berlin, Germany, October 12-13, 2009. [ bib | pdf | web ]
We consider generic Garbled Circuit (GC)-based techniques for Secure Function Evaluation (SFE) in the semi-honest model.
We describe efficient GC constructions for addition, subtraction, multiplication, and comparison functions. Our circuits for subtraction and comparison are approximately two times smaller (in terms of garbled tables) than previous constructions. This implies corresponding computation and communication improvements in SFE of functions using our efficient building blocks. The techniques rely on recently proposed “free XOR” GC technique.
Further, we present concrete and detailed improved GC protocols for the problem of secure integer comparison, and related problems of auctions, minimum selection, and minimal distance. Performance improvement comes both from building on our efficient basic blocks and several problem-specific GC optimizations. We provide precise cost evaluation of our constructions, which serves as a baseline for future protocols.
[15] Endre Bangerter, Stephan Krenn, Ahmad-Reza Sadeghi, Thomas Schneider, and Joe-Kai Tsay. On the design and implementation of efficient zero-knowledge proofs of knowledge. In ECRYPT workshop on Software Performance Enhancements for Encryption and Decryption and Cryptographic Compilers (SPEED-CC'09), Berlin, Germany, October 12-13, 2009. [ bib | pdf | web ]
Zero-knowledge proofs of knowledge (ZK-PoK) play an important role in many cryptographic applications. Direct anonymous attestation (DAA) and the identity mixer anonymous authentication system are first real world applications using ZK-PoK as building blocks. But although being used for many years now, design and implementation of sound ZK-PoK remains challenging. In fact, there are security flaws in various protocols found in literatur. Especially for non-experts in the field it is often hard to design ZK-PoK, since a unified and easy to use theoretical framework on ZK-PoK is missing.
With this paper we overcome important challenges and facilitate the design and implementation of efficient and sound ZK-PoK in practice. First, Camenisch et al. have presented at EUROCRYPT 2009 a first unified and modular theoretical framework for ZK-PoK. This is compelling, but makes use of a rather inefficient 6-move protocol. We extend and improve their framework in terms of efficiency and show how to realize it using efficient 3-move Σ-protocols. Second, we perform an exact security and efficiency analysis for our new protocol and various protocols found in the literature. The analysis yields novel - and perhaps surprising - results and insights. It reveals for instance that using a 2048 bit RSA modulus, as specified in the DAA standard, only guarantees an upper bound on the success probability of a malicious prover between 1/24 and 1/224. Also, based on that analysis we show how to select the most efficient protocol to realize a given proof goal. Finally, we also provide low-level support to a designer by presenting a compiler realizing our framework and optimization techniques, allowing easy imple- mentation of efficient and sound protocols.
[14] Mauro Barni, Pierluigi Failla, Vladimir Kolesnikov, Riccardo Lazzeretti, Ahmad-Reza Sadeghi, and Thomas Schneider. Secure evaluation of private linear branching programs with medical applications. In 14. European Symposium on Research in Computer Security (ESORICS'09), volume 5789 of LNCS, pages 424–439, Springer, Saint Malo, France, September 21-25, 2009. Full version: https://ia.cr/2009/195. Acceptance rate 19.1%. CORE rank A. [ bib | DOI | pdf | web ]
Diagnostic and classification algorithms play an important role in data analysis, with applications in areas such as health care, fault diagnostics, or benchmarking. Branching programs (BP) is a popular representation model for describing the underlying classification/diagnostics algorithms. Typical application scenarios involve a client who provides data and a service provider (server) whose diagnostic program is run on client's data. Both parties need to keep their inputs private.
We present new, more efficient privacy-protecting protocols for remote evaluation of such classification/diagnostic programs. In addition to efficiency improvements, we generalize previous solutions – we securely evaluate private linear branching programs (LBP), a useful generalization of BP that we introduce. We show practicality of our solutions: we apply our protocols to the privacy-preserving classification of medical ElectroCardioGram (ECG) signals and present implementation results. Finally, we discover and fix a subtle security weakness of the most recent remote diagnostic proposal, which allowed malicious clients to learn partial information about the program.
[13] Endre Bangerter, Thomas Briner, Wilko Henecka, Stephan Krenn, Ahmad-Reza Sadeghi, and Thomas Schneider. Automatic generation of sigma-protocols. In 6. European Workshop on Public Key Services, Applications and Infrastructures (EUROPKI'09), volume 6391 of LNCS, pages 67–82, Springer, Pisa, Italy, September 10-11, 2009. Acceptance rate 45.0%. CORE rank B. [ bib | DOI | pdf ]
Efficient-knowledge proofs knowledge (ZK-PoK) are basic building blocks of many practical cryptographic applications such as identification schemes, group signatures, and secure multi-party computation (SMPC). Currently, first applications that essentially rely on ZK-PoKs are being deployed in the real world. The most prominent example is the Direct Anonymous Attestation (DAA) protocol, which was adopted by the Trusted Computing Group (TCG) and implemented as one of the functionalities of the cryptographic chip Trusted Platform Module (TPM).
Implementing systems using ZK-PoK turns out to be challenging, since ZK-PoK are significantly more complex than standard crypto primitives (e.g., encryption and signature schemes). As a result, the design-implementation cycles of ZK-PoK are time-consuming and error-prone.
To overcome this, we present a compiler with corresponding languages for the automatic generation of sound and efficient ZK-PoK based on Σ-protocols. The protocol designer using our compiler formulates the goal of a ZK-PoK proof in a high-level protocol specification language, which Abstracts away unnecessary technicalities from the designer. The compiler then automatically generates the protocol implementation in Java code; alternatively, the compiler can output a description of the protocol in LATEX which can be used for documentation or verification.
[12] Mauro Barni, Pierluigi Failla, Vladimir Kolesnikov, Riccardo Lazzeretti, Ahmad-Reza Sadeghi, and Thomas Schneider. Combining signal processing and cryptographic protocol design for efficient ECG classification. In 1. International Workshop on Signal Processing in the EncryptEd Domain (SPEED'09), Lausanne, Switzerland, September 10, 2009. [ bib | pdf ]
We describe a privacy-preserving system where a server can classify an ElectroCardioGram (ECG) signal without learning any information about the ECG signal and the client is prevented from gaining knowledge about the classificationalgorithm used by the server. The system relies on the concept of Linear Branching Programs (LBP) and a recently proposed cryptographic protocol for secure evaluation of private LBPs. We study the trade-off between signal representation accuracy and system complexity both from practical and theoretical perspective. We show how the overall system complexity can be strongly reduced by modifying the original ECG classification algorithm. Two alternatives of the underlying cryptographic protocol are implemented and their corresponding complexities are analyzed to show suitability of our system in real-life applications for current and future security levels.
[11] Vladimir Kolesnikov, Ahmad-Reza Sadeghi, and Thomas Schneider. How to combine homomorphic encryption and garbled circuits - improved circuits and computing the minimum distance efficiently. In 1. International Workshop on Signal Processing in the EncryptEd Domain (SPEED'09), Lausanne, Switzerland, September 10, 2009. [ bib | pdf ]
We show how two existing paradigms for two-party secure function evaluation (SFE) in the semi-honest model can be combined securely and efficiently – those based on additively homomorphic encryption (HE) with those based on garbled circuits (GC) and vice versa.
Additionally, we propose new GC constructions for addition, subtraction, multiplication, and comparison functions. Our circuits are approximately two times smaller (in terms of garbled tables) than previous constructions. This implies corresponding computation and communication improvements in SFE of functions using the above building blocks (including the protocols for combining HE and GC).
Based on these results, we present efficient constant-round protocols for secure integer comparison, and the related problems of minimum selection and minimum distance, which are crucial building blocks of many cryptographic schemes such as privacy preserving biometric authentication (e.g., face recognition, fingerprint matching, etc).
[10] Annika Paus, Ahmad-Reza Sadeghi, and Thomas Schneider. Practical secure evaluation of semi-private functions. In 7. International Conference on Applied Cryptography and Network Security (ACNS'09), volume 5536 of LNCS, pages 89–106, Springer, Paris-Rocquencourt, France, June 2-5, 2009. Full version: https://ia.cr/2009/124. Code: https://encrypto.de/code/FairplaySPF. Acceptance rate 21.3%. CORE rank B. [ bib | DOI | pdf | web ]
Two-party Secure Function Evaluation (SFE) is a very useful cryptographic tool which allows two parties to evaluate a function known to both parties on their private (secret) inputs. Some applications with sophisticated privacy needs require the function to be known only to one party and kept private (hidden) from the other one. However, existing solutions for SFE of private functions (PF-SFE) deploy Universal Circuits (UC) and are still very inefficient in practice.
In this paper we bridge the gap between SFE and PF-SFE with SFE of what we call semi-private functions (SPF-SFE), i.e., one function out of a given class of functions is evaluated without revealing which one.
We present a general framework for SPF-SFE allowing a fine-grained trade-off and tuning between SFE and PF-SFE covering both extremes. In our framework, semi-private functions can be composed from several privately programmable blocks (PPB) which can be programmed with one function out of a class of functions. The framework allows efficient and secure embedding of constants into the resulting circuit to improve performance. To show practicability of the framework we have implemented a compiler for SPF-SFE based on the Fairplay SFE framework.
SPF-SFE is sufficient for many practically relevant privacy-preserving applications, such as privacy-preserving credit checking which can be implemented with our framework and compiler as described in the paper.
[9] Endre Bangerter, Jan Camenisch, Stephan Krenn, Ahmad-Reza Sadeghi, and Thomas Schneider. Automatic generation of sound zero-knowledge protocols. 28. Advances in Cryptology – EUROCRYPT'09 Poster Session, Cologne, Germany, April 26-30, 2009. Full version: https://ia.cr/2008/471. Acceptance rate 33% for papers and posters. CORE rank A*. [ bib | pdf | poster | web ]
Efficient zero-knowledge proofs of knowledge (ZK-PoK) are basic building blocks of many practical cryptographic applications such as identification schemes, group signatures, and secure multiparty computation. Currently, first applications that critically rely on ZK-PoKs are being deployed in the real world. The most prominent example is Direct Anonymous Attestation (DAA), which was adopted by the Trusted Computing Group (TCG) and implemented as one of the functionalities of the cryptographic chip Trusted Platform Module (TPM).
Implementing systems using ZK-PoK turns out to be challenging, since ZK-PoK are, loosely speaking, significantly more complex than standard crypto primitives, such as encryption and signature schemes. As a result, implementation cycles of ZK-PoK are time-consuming and error-prone, in particular for developers with minor or no cryptographic skills.
In this paper we report on our ongoing and future research vision with the goal to bring ZK-PoK to practice by automatically generating sound ZK-PoK protocols and make them accessible to crypto and security engineers. To this end we are developing protocols and compilers that support and automate the design and generation of secure and efficient implementation of ZK-PoK protocols.
[8] Endre Bangerter, Stefania Barzan, Stephan Krenn, Ahmad-Reza Sadeghi, Thomas Schneider, and Joe-Kai Tsay. Bringing zero-knowledge proofs of knowledge to practice. In 17. International Workshop on Security Protocols (SPW'09), volume 7028 of LNCS, pages 51–62, Springer, Cambridge, UK, April 1-3, 2009. Full version: https://ia.cr/2009/211. [ bib | DOI | pdf ]
Efficient zero-knowledge proofs of knowledge (ZK-PoK) are basic building blocks of many practical cryptographic applications such as identification schemes, group signatures, and secure multiparty computation. Currently, first applications that critically rely on ZK-PoKs are being deployed in the real world. The most prominent example is Direct Anonymous Attestation (DAA), which was adopted by the Trusted Computing Group (TCG) and implemented as one of the functionalities of the cryptographic Trusted Platform Module (TPM) chip.
Implementing systems using ZK-PoK turns out to be challenging, since ZK-PoK are, loosely speaking, significantly more complex than standard crypto primitives, such as encryption and signature schemes. As a result, implementation cycles of ZK-PoK are time-consuming and error-prone, in particular for developers with minor or no cryptographic skills.
In this paper we report on our ongoing and future research vision with the goal to bring ZK-PoK to practice by making them accessible to crypto and security engineers. To this end we are developing compilers and related tools that support and partially automate the design, implementation, verification and secure implementation of ZK-PoK protocols.
[7] Ahmad-Reza Sadeghi and Thomas Schneider. Generalized universal circuits for secure evaluation of private functions with application to data classification. In 11. International Conference on Information Security and Cryptology (ICISC'08), volume 5461 of LNCS, pages 336–353, Springer, Seoul, South Korea, December 3-5, 2008. Full version: https://ia.cr/2008/453. Acceptance rate 19.8%. CORE rank B. [ bib | DOI | pdf | web ]
Secure Evaluation of Private Functions (PF-SFE) allows two parties to compute a private function which is known by one party only on private data of both. It is known that PF-SFE can be reduced to Secure Function Evaluation (SFE) of a Universal Circuit (UC). Previous UC constructions only simulated circuits with gates of d=2 inputs while gates with d>2 inputs were decomposed into many gates with 2 inputs which is inefficient for large d as the size of UC heavily depends on the number of gates.
We present generalized UC constructions to efficiently simulate any circuit with gates of d ≥2 inputs having efficient circuit representation. Our constructions are non-trivial generalizations of previously known UC constructions.
As application we show how to securely evaluate private functions such as neural networks (NN) which are increasingly used in commercial applications. Our provably secure PF-SFE protocol needs only one round in the semi-honest model (or even no online communication at all using non-interactive oblivious transfer) and evaluates a generalized UC that entirely hides the structure of the private NN. This enables applications like privacy-preserving data classification based on private NNs without trusted third party while simultaneously protecting user's data and NN owner's intellectual property.
[6] Vladimir Kolesnikov and Thomas Schneider. Improved garbled circuit: Free XOR gates and applications. In 35. International Colloquium on Automata, Languages and Programming (ICALP'08), volume 5126 of LNCS, pages 486–498, Springer, Reykjavik, Iceland, July 6-13, 2008. Acceptance rate 30%. CORE rank A. [ bib | DOI | pdf | web ]
We present a new garbled circuit construction for two-party secure function evaluation (SFE). In our one-round protocol, XOR gates are evaluated “for free”, which results in the corresponding improvement over the best garbled circuit implementations (e.g. Fairplay [MNPS04]).
We build permutation networks [Waksman68] and Universal Circuits (UC) [Valiant76] almost exclusively of XOR gates; this results in a factor of up to 4 improvement (in both computation and communication) of their SFE. We also improve integer addition and equality testing by factor of up to 2.
We rely on the Random Oracle (RO) assumption. Our constructions are proven secure in the semi-honest model.
[5] Vladimir Kolesnikov, Thomas Schneider, and Volker Strehl. Practical secure function evaluation. In 8. Workshop der Fachgruppe Kryptographie in der Gesellschaft für Informatik (Kryptotag), volume WSI-2008-02, Tübingen, Germany, April 11, 2008. [ bib | pdf ]
[4] Thomas Schneider. Practical secure function evaluation. In Fachwissenschaftlicher Informatik-Kongress (Informatiktage 2008), volume S-6 of LNI, pages 37–40, GI, Bonn, Germany, March 14, 2008. [ bib | pdf | poster | pub ]
[3] Thomas Schneider. Practical secure function evaluation. Master's thesis, Friedrich-Alexander University Erlangen-Nürnberg, Germany, February 27, 2008. [ bib | pdf ]
This thesis focuses on practical aspects of general two-party Secure Function Evaluation (SFE). We give a new SFE protocol that allows free evaluation of XOR gates and is provably secure against semi-honest adversaries in the random oracle model. Furthermore, the extension of SFE to private functions (PF-SFE) using universal circuits (UC) is considered. Based on our new practical UC construction, FairplayPF is implemented as extension of the well-known Fairplay SFE system to demonstrate practicability of UC-based PF-SFE. Also new protocols for SFE and PF-SFE of functions alternatively represented as Ordered Binary Decision Diagram (OBDD) are given.
[2] Vladimir Kolesnikov and Thomas Schneider. A practical universal circuit construction and secure evaluation of private functions. In 12. International Conference on Financial Cryptography and Data Security (FC'08), volume 5143 of LNCS, pages 83–97, Springer, Cozumel, Mexico, January 28-31, 2008. Code: https://encrypto.de/code/FairplayPF. Acceptance rate 19.1%. CORE rank B. [ bib | DOI | pdf | pub | web ]
We consider general secure function evaluation (SFE) of private functions (PF-SFE). Recall, privacy of functions is often most efficiently achieved by general SFE [Yao82,Yao86,LP04] of a Universal Circuit (UC).
Our main contribution is a new simple and efficient UC construction. Our circuit UCk, universal for circuits of k gates, has size ∼1.5 k log2 k and depth ∼k logk. It is up to 50% smaller than the best UC (of Valiant [Valiant76], of size ∼19klogk) for circuits of size up to ≈5000 gates.
Our improvement results in corresponding performance improvement of SFE of (small) private functions. Since, due to cost, only small circuits (i.e. <5000 gates) are practical for PF-SFE, our construction appears to be the best fit for many practical PF-SFE.
We implement PF-SFE based on our UC and Fairplay SFE system [MNPS04].
[1] Thomas Schneider. Secure task migration and interprocess communication in reconfigurable, distributed, embedded systems. Bachelor's thesis, Friedrich-Alexander University Erlangen-Nürnberg, Germany, July 10, 2007. [ bib | pdf ]