Publications‎ > ‎

Abstracts

This page is a summary of my publications with links to background information: bibtex entry, preprint as pdf, presentation slides, link to publisher, and web site of event/journal.
A classification into categories (books, book chapters, conference papers, journal articles, patents, theses, etc.) is given in my full CV.
See also my profiles at DBLP, Google Scholar, ArnetMiner, and Microsoft Academic Search.

[51] Julien Bringer, Hervé Chabanne, Mélanie Favre, Alain Patey, Thomas Schneider, and Michael Zohner. GSHADE: Faster privacy-preserving distance computation and biometric identification. In 2nd ACM Workshop on Information Hiding and Multimedia Security (IH&MMSEC'14). ACM, June 11-13, 2014. To appear. [ bib | DOI | 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.

[50] Matthias Schneider and Thomas Schneider. Notes on non-interactive secure comparison in “image feature extraction in the encrypted domain with privacy-preserving SIFT”. In 2nd ACM Workshop on Information Hiding and Multimedia Security (IH&MMSEC'14). ACM, June 11-13, 2014. To appear. [ bib | DOI | web ]
[49] Florian Kerschbaum, Thomas Schneider, and Axel Schröpfer. Automatic protocol selection in secure two-party computations. In 12th International Conference on Applied Cryptography and Network Security (ACNS'14), LNCS. Springer, June 10-13, 2014. To appear. Full version available at http://eprint.iacr.org/2014/200. [ bib | web ]
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.

[48] Gilad Asharov, Yehuda Lindell, Thomas Schneider, and Michael Zohner. More efficient oblivious transfer and extensions for faster secure computation. In 20th ACM Conference on Computer and Communications Security (CCS'13), pages 535-548. ACM, November 4-8, 2013. Full version available at http://eprint.iacr.org/2013/552; code at http://encrypto.de/code/OTExtension. [ bib | DOI | pdf | web ]
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 11th International Conference on Applied Cryptography and Network Security (ACNS'13), volume 7954 of LNCS, pages 432-440. Springer, June 25-28, 2013. [ 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] Wilko Henecka and Thomas Schneider. Faster secure two-party computation with less memory. In 8th ACM Symposium on Information, Computer and Communications Security (ASIACCS'13), pages 437-446. ACM, May 7-10, 2013. [ bib | DOI | pdf | slides | web ]
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.

[45] Thomas Schneider and Michael Zohner. GMW vs. Yao? Efficient secure two-party computation with low depth circuits. In 17th International Conference on Financial Cryptography and Data Security (FC'13), volume 7859 of LNCS, pages 275-292. Springer, April 1-5, 2013. [ 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.

[44] Florian Kerschbaum, Thomas Schneider, and Axel Schröpfer. Automatic protocol selection in secure two-party computations. 20th Network & Distributed System Security Symposium (NDSS'13), February 24-27, 2013. Short Talk. [ bib | pdf | web ]
[43] 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, 01 2013. Preliminary version available at http://eprint.iacr.org/2010/079. [ 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.

[42] Thomas Schneider and Michael Zohner. Efficient secure two-party computation. In 17. Workshop der Fachgruppe Kryptographie in der Gesellschaft für Informatik (Kryptotag), December 7, 2012. [ bib | web ]
[41] 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 ]
[40] Thomas Schneider. Engineering Secure Two-Party Computation Protocols: Design, Optimization, and Applications of Efficient Secure Function Evaluation. Springer-Verlag Berlin Heidelberg, August 4, 2012. http://thomaschneider.de/engineeringSFEbook. [ bib | DOI | pub ]
[39] Junaid Jameel Ahmad, Shujun Li, Ahmad-Reza Sadeghi, and Thomas Schneider. CTL: A platform-independent crypto tools library based on dataflow programming paradigm. In 16th International Conference on Financial Cryptography and Data Security (FC'12), volume 7397 of LNCS, pages 299-313. Springer, February 27 - March 2, 2012. Full version available at http://eprint.iacr.org/2011/679. [ 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.

[38] Sven Bugiel, Stefan Nürnberger, Ahmad-Reza Sadeghi, and Thomas Schneider. Twin Clouds: Secure cloud computing with low latency. In 12th Communications and Multimedia Security Conference (CMS'11), volume 7025 of LNCS, pages 32-44. Springer, October 19-21, 2011. Best Paper Award. [ bib | DOI | pdf | web ]
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.

[37] Sven Bugiel, Thomas Pöppelmann, Stefan Nürnberger, Ahmad-Reza Sadeghi, and Thomas Schneider. AmazonIA: When elasticity snaps back. In 18th ACM Conference on Computer and Communications Security (CCS'11), pages 389-400. ACM, October 17-21, 2011. See http://trust.cased.de/AMID. [ 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.

[36] 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. [ 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.

[35] 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, 10.-12. Mai, 2011. [ bib | pdf | slides | pub | web ]
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.

[34] 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), March 15-16, 2011. [ bib | pdf | slides | 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.

[33] Marc Fischlin, Benny Pinkas, Ahmad-Reza Sadeghi, Thomas Schneider, and Ivan Visconti. Secure set intersection with untrusted hardware tokens. In 11th Cryptographers' Track at the RSA Conference (CT-RSA'11), volume 6558 of LNCS, pages 1-16. Springer, February 14-18, 2011. [ bib | DOI | pdf | slides | 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.

[32] 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.

[31] 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 ]
[30] Wilko Henecka, Stefan Kögl, Ahmad-Reza Sadeghi, Thomas Schneider, and Immo Wehrenberg. TASTY: Tool for Automating Secure Two-partY computations. In 17th ACM Conference on Computer and Communications Security (CCS'10), pages 451-462. ACM, October 4-8, 2010. Full version available at http://eprint.iacr.org/2010/365. http://tastyproject.net. [ bib | DOI | pdf | slides | 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.

[29] 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 15th European Symposium on Research in Computer Security (ESORICS'10), volume 6345 of LNCS, pages 151-167. Springer, September 20-22, 2010. Full version available at http://eprint.iacr.org/2010/339. [ bib | DOI | pdf | web ]
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.

[28] 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, September 8, 2010. [ bib | pdf | slides | pub | web ]
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.

[27] 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 12th International Workshop on Cryptographic Hardware and Embedded Systems (CHES'10), volume 6225 of LNCS, pages 383-397. Springer, August 17-20, 2010. Full version available at http://eprint.iacr.org/2010/276. [ bib | DOI | pdf | slides | 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.

[26] Endre Bangerter, Stephan Krenn, Ahmad-Reza Sadeghi, and Thomas Schneider. YAZKC: Yet Another Zero-Knowledge Compiler. 19th USENIX Security Symposium (Security'10) Poster Session, August 11-13, 2010. [ 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.

[25] Ahmad-Reza Sadeghi, Thomas Schneider, and Marcel Winandy. Token-based cloud computing - secure outsourcing of data and arbitrary computations with lower latency. In 3rd International Conference on Trust and Trustworthy Computing (TRUST'10) - Workshop on Trust in the Cloud, volume 6101 of LNCS, pages 417-429. Springer, June 21-23, 2010. [ bib | DOI | pdf | slides | 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.

[24] Kimmo Järvinen, Vladimir Kolesnikov, Ahmad-Reza Sadeghi, and Thomas Schneider. Embedded SFE: Offloading server and network using hardware tokens. In 14th International Conference on Financial Cryptography and Data Security (FC'10), volume 6052 of LNCS, pages 207-221. Springer, January 25-28, 2010. Full version available at http://eprint.iacr.org/2009/591. [ bib | DOI | pdf | slides | 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.

[23] Vladimir Kolesnikov, Ahmad-Reza Sadeghi, and Thomas Schneider. Improved garbled circuit building blocks and applications to auctions and computing minima. In 8th International Conference on Cryptology And Network Security (CANS'09), volume 5888 of LNCS, pages 1-20. Springer, December 12-14, 2009. Full version available at http://eprint.iacr.org/2009/411. [ bib | DOI | pdf | slides | 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.

[22] Benny Pinkas, Thomas Schneider, Nigel P. Smart, and Stephen C. Williams. Secure two-party computation is practical. In 15th Advances in Cryptology - ASIACRYPT 2009, volume 5912 of LNCS, pages 250-267. Springer, December 6-10, 2009. Full version available at http://eprint.iacr.org/2009/314. [ 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.

[21] Mauro Barni, Pierluigi Failla, Vladimir Kolesnikov, Riccardo Lazzeretti, Annika Paus, Ahmad-Reza Sadeghi, and Thomas Schneider. Efficient privacy-preserving classification of ECG signals. In 1st IEEE International Workshop on Information Forensics and Security (IEEE WIFS'09), pages 91-95. IEEE, December 6-9, 2009. [ 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.

[20] Ahmad-Reza Sadeghi, Thomas Schneider, and Immo Wehrenberg. Efficient privacy-preserving face recognition. In 12th International Conference on Information Security and Cryptology (ICISC'09), volume 5984 of LNCS, pages 229-244. Springer, December 2-4, 2009. Full version available at http://eprint.iacr.org/2009/507. [ 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).

[19] Ahmad-Reza Sadeghi and Thomas Schneider. Ask your e-doctor without telling: Privacy-preserving medical diagnostics. Section Days of Ruhr-University Bochum Research School, November 6, 2009. (Poster prize awarded). [ bib | poster | web ]
[18] 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), 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.

[17] 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), October 12-13, 2009. Implementation available at http://zkc.cace-project.eu. [ 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.

[16] 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 14th European Symposium on Research in Computer Security (ESORICS'09), volume 5789 of LNCS, pages 424-439. Springer, September 21-25, 2009. Full version available at http://eprint.iacr.org/2009/195. [ bib | DOI | pdf | slides | 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.

[15] Endre Bangerter, Thomas Briner, Wilko Henecka, Stephan Krenn, Ahmad-Reza Sadeghi, and Thomas Schneider. Automatic generation of sigma-protocols. In 6th European Workshop on Public Key Services, Applications and Infrastructures (EUROPKI'09), volume 6391 of LNCS, pages 67-82. Springer, September 10-11, 2009. [ bib | DOI | pdf | web ]
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.

[14] 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 1st International Workshop on Signal Processing in the EncryptEd Domain (SPEED'09), September 10, 2009. [ bib | pdf | web ]
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.

[13] 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 1st International Workshop on Signal Processing in the EncryptEd Domain (SPEED'09), September 10, 2009. [ bib | pdf | slides | web ]
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).

[12] Annika Paus, Ahmad-Reza Sadeghi, and Thomas Schneider. Practical secure evaluation of semi-private functions. In 7th International Conference on Applied Cryptography and Network Security (ACNS'09), volume 5536 of LNCS, pages 89-106. Springer, June 2-5, 2009. Implementation available at http://www.trust.rub.de/FairplaySPF. Full version available at http://eprint.iacr.org/2009/124. [ bib | DOI | pdf | slides ]
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.

[11] Endre Bangerter, Jan Camenisch, Stephan Krenn, Ahmad-Reza Sadeghi, and Thomas Schneider. Automatic generation of sound zero-knowledge protocols. 28th Advances in Cryptology - EUROCRYPT 2009 Poster Session, April 26-30, 2009. Full version available at http://eprint.iacr.org/2008/471. [ 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.

[10] Endre Bangerter, Stefania Barzan, Stephan Krenn, Ahmad-Reza Sadeghi, Thomas Schneider, and Joe-Kai Tsay. Bringing zero-knowledge proofs of knowledge to practice. In 17th International Workshop on Security Protocols (SPW'09), volume 7028 of LNCS, pages 51-62. Springer, April 1-3, 2009. Full version available at http://eprint.iacr.org/2009/211. [ bib | DOI | pdf | 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 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.

[9] Ahmad-Reza Sadeghi and Thomas Schneider. Generalized universal circuits for secure evaluation of private functions with application to data classification. In 11th International Conference on Information Security and Cryptology (ICISC'08), volume 5461 of LNCS, pages 336-353. Springer, December 3-5, 2008. Full version available at http://eprint.iacr.org/2008/453. [ bib | DOI | pdf | slides | 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.

[8] 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), October 2008. [ 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.

[7] Vladimir Kolesnikov and Thomas Schneider. Improved garbled circuit: Free XOR gates and applications. In 35th International Colloquium on Automata, Languages and Programming (ICALP'08), volume 5126 of LNCS, pages 486-498. Springer, July 6-13, 2008. [ bib | DOI | pdf | slides | 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.

[6] 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, April 11, 2008. [ bib | pdf | slides | web ]
[5] Thomas Schneider. Practical secure function evaluation. In Fachwissenschaftlicher Informatik-Kongress (Informatiktage 2008), volume S-6 of LNI, pages 37-40. GI, March 14, 2008. [ bib | pdf | poster | pub | web ]
[4] Thomas Schneider. Practical secure function evaluation. Master's thesis, University Erlangen-Nürnberg, Germany, February 27, 2008. http://thomaschneider.de/theses/da/. [ 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.

[3] Vladimir Kolesnikov and Thomas Schneider. Universal circuit for secure function evaluation. U.S. patent no 8175854 (applied July 14, 2008; issued May 8, 2012), July 2008. [ 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.

[2] Vladimir Kolesnikov and Thomas Schneider. A practical universal circuit construction and secure evaluation of private functions. In 12th International Conference on Financial Cryptography and Data Security (FC'08), volume 5143 of LNCS, pages 83-97. Springer, January 28-31, 2008. Implementation available at http://thomaschneider.de/FairplayPF. [ bib | DOI | pdf | slides | 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, University Erlangen-Nürnberg, Germany, July 10, 2007. http://thomaschneider.de/theses/sa/. [ bib | pdf ]