Academic literature on the topic 'Garbled Circuit Protocol'

We propose postquantum universal composable (UC) cut-and-choose oblivious transfer (CCOT) protocol under the malicious adversary model. In secure two-party computation, we construct s copies’ garbled circuits, including half check circuit and half evaluation circuit. The sender can transfer the key to the receiver by CCOT protocol. Compared to PVW-OT [6] framework, we invoke WQ-OT [35] framework with reusability of common random string ( crs ) and better security. Relying on LWE’s assumption and the property of the Rounding function, we construct an UC-CCOT protocol, which can resist quantum attack in secure two-party computation.

Secure Function Evaluation (SFE) has received recent attention due to the massive collection and mining of personal data, but remains impractical due to its large computational cost. Garbled Circuits (GC) is a protocol for implementing SFE which can evaluate any function that can be expressed as a Boolean circuit and obtain the result while keeping each party’s input private. Recent advances have led to a surge of garbled circuit implementations in software for a variety of different tasks. However, these implementations are inefficient, and therefore GC is not widely used, especially for large problems. This research investigates, implements, and evaluates secure computation generation using a heterogeneous computing platform featuring FPGAs. We have designed and implemented SIFO: secure computational infrastructure using FPGA overlays. Unlike traditional FPGA design, a coarse-grained overlay architecture is adopted which supports mapping SFE problems that are too large to map to a single FPGA. Host tools provided include SFE problem generator, parser, and automatic host code generation. Our design allows repurposing an FPGA to evaluate different SFE tasks without the need for reprogramming and fully explores the parallelism for any GC problem. Our system demonstrates an order of magnitude speedup compared with an existing software platform.

In this work, we introduce the system boundary security vs. privacy dilemma, where border devices (e.g., firewall devices) require unencrypted data inspection to prevent data exfiltration or unauthorized data accesses, but unencrypted data inspection violates data privacy. To shortcut this problem, we present Oblivious Inspection, a novel approach based on garbled circuits to perform a stateful application-aware inspection of encrypted network traffic in a privacy-preserving way. We also showcase an inspection algorithm for Fast Healthcare Interoperability Resources (FHIR) standard compliant packets along with its performance results. The results point out the importance of the inspection function being aligned with the underlying garbled circuit protocol. In this line, mandatory encryption algorithms for TLS 1.3 have been analysed observing that packets encrypted using Chacha20 can be filtered up to 17 and 25 times faster compared with AES128-GCM and AES256-GCM, respectively. All together, this approach penalizes performance to align system security and data privacy, but it could be appropriate for those scenarios where this performance degradation can be justified by the sensibility of the involved data such as healthcare scenarios.

Biometrics plays an important role in authentication applications since they are strongly linked to holders. With an increasing growth of e-commerce and e-government, one can expect that biometric-based authentication systems are possibly deployed over the open networks in the near future. However, due to its openness, the Internet poses a great challenge to the security and privacy of biometric authentication. Biometric data cannot be revoked, so it is of paramount importance that biometric data should be handled in a secure way. In this paper we present a scheme achieving privacy-preserving fingerprint authentication between two parties, in which fingerprint minutiae matching algorithm is completed in the encrypted domain. To improve the efficiency, we exploit homomorphic encryption as well as garbled circuits to design the protocol. Our goal is to provide protection for the security of template in storage and data privacy of two parties in transaction. The experimental results show that the proposed authentication protocol runs efficiently. Therefore, the protocol can run over open networks and help to alleviate the concerns on security and privacy of biometric applications over the open networks.

AbstractClustering is a common technique for data analysis, which aims to partition data into similar groups. When the data comes from different sources, it is highly desirable to maintain the privacy of each database. In this work, we study a popular clustering algorithm (K-means) and adapt it to the privacypreserving context.Specifically, to construct our privacy-preserving clustering algorithm, we first propose an efficient batched Euclidean squared distance computation protocol in the amortizing setting, when one needs to compute the distance from the same point to other points. Furthermore, we construct a customized garbled circuit for computing the minimum value among shared values.We believe these new constructions may be of independent interest. We implement and evaluate our protocols to demonstrate their practicality and show that they are able to train datasets that are much larger and faster than in the previous work. The numerical results also show that the proposed protocol achieve almost the same accuracy compared to a K-means plain-text clustering algorithm.

Abstract Decision trees are widespread machine learning models used for data classification and have many applications in areas such as healthcare, remote diagnostics, spam filtering, etc. In this paper, we address the problem of privately evaluating a decision tree on private data. In this scenario, the server holds a private decision tree model and the client wants to classify its private attribute vector using the server’s private model. The goal is to obtain the classification while preserving the privacy of both – the decision tree and the client input. After the computation, only the classification result is revealed to the client, while nothing is revealed to the server. Many existing protocols require a constant number of rounds. However, some of these protocols perform as many comparisons as there are decision nodes in the entire tree and others transform the whole plaintext decision tree into an oblivious program, resulting in higher communication costs. The main idea of our novel solution is to represent the tree as an array. Then we execute only d – the depth of the tree – comparisons. Each comparison is performed using a small garbled circuit, which output secret-shares of the index of the next node. We get the inputs to the comparison by obliviously indexing the tree and the attribute vector. We implement oblivious array indexing using either garbled circuits, Oblivious Transfer or Oblivious RAM (ORAM). Using ORAM, this results in the first protocol with sub-linear cost in the size of the tree. We implemented and evaluated our solution using the different array indexing procedures mentioned above. As a result, we are not only able to provide the first protocol with sublinear cost for large trees, but also reduce the communication cost for the large real-world data set “Spambase” from 18 MB to 1[triangleright]2 MB and the computation time from 17 seconds to less than 1 second in a LAN setting, compared to the best related work.

Abstract 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.

Abstract 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.

With the development of cloud computing, interest in database outsourcing has recently increased. In cloud computing, it is necessary to protect the sensitive information of data owners and authorized users. For this, data mining techniques over encrypted data have been studied to protect the original database, user queries and data access patterns. The typical data mining technique is kNN classification which is widely used for data analysis and artificial intelligence. However, existing works do not provide a sufficient level of efficiency for a large amount of encrypted data. To solve this problem, in this paper, we propose a privacy-preserving parallel kNN classification algorithm. To reduce the computation cost for encryption, we propose an improved secure protocol by using an encrypted random value pool. To reduce the query processing time, we not only design a parallel algorithm, but also adopt a garbled circuit. In addition, the security analysis of the proposed algorithm is performed to prove its data protection, query protection, and access pattern protection. Through our performance evaluation, the proposed algorithm shows about 2∼25 times better performance compared with existing algorithms.

Online ride-hailing (ORH) services allow people to enjoy on-demand transportation services through their mobile devices in a short responding time. Despite the great convenience, users need to submit their location information to the ORH service provider, which may incur unexpected privacy problems. In this paper, we mainly study the privacy and utility of the ride-sharing system, which enables multiple riders to share one driver. To solve the privacy problem and reduce the ride-sharing detouring waste, we propose a privacy-preserving ride-sharing system named pShare. To hide users’ precise locations from the service provider, we apply a zone-based travel time estimation approach to privately compute over sensitive data while cloaking each rider’s location in a zone area. To compute the matching results along with the least-detouring route, the service provider first computes the shortest path for each eligible rider combination, then compares the additional traveling time (ATT) of all combinations, and finally selects the combination with minimum ATT. We designed a secure comparing protocol by utilizing the garbled circuit, which enables the ORH server to execute the protocol with a crypto server without privacy leakage. Moreover, we apply the data packing technique, by which multiple data can be packed as one to reduce the communication and computation overhead. Through the theoretical analysis and evaluation results, we prove that pShare is a practical ride-sharing scheme that can find out the sharing riders with minimum ATT in acceptable accuracy while protecting users’ privacy.

Dealing with secure computation and communication in hardware devices, an attacker that threatens to security of the systems can be of two different types. The first type of attacker is external to the exchange of secret messages and tries to steal some sensitive information. Probing a circuit is a useful technique through which an attacker can derive information correlated with the secret manipulated by a cryptographic circuit. Probing security is the branch of research that tries to devise models, tools and countermeasures against this type of attacks. We define a new methodology that allows to determine if a gadget (i.e., a portion of a circuit) is secure against probing attacks. Moreover, we reason about composability of gadgets, in such a way that also this composition is probing secure. The reasoning is extended also to the case in which glitches are considered, namely when the attacks are mounted when timing hazards are present. The proposed methodology is based on the construction of the Walsh matrix of a Boolean function that describes the operations of the circuit. This method allows reaching an exact solution, but generally needs a lot of computation’s time (mainly for big gadgets). To overcome the problem, we propose to compute the Walsh matrix exploiting the theory and applications of Algebraic Decision Diagrams (ADDs). Different is the case when the malicious part is internal: each party is interested in protecting its own sensitive information from all the others. When the parties are only two, from literature the garbled circuit protocol is a solution that allows to reach a result implying some secrets, without sharing them. The cost of this protocol depends on the number of extit{and} gates in the circuit that implements the Boolean function describing the protocol computations. In this context, we work to reduce the number of multiplications in two classes of particular Boolean functions, called autosymmetric and D-reducible. Moreover, in the context of the garbled circuit protocol, we discuss some innovative solutions to further reduce the protocol's costs, as the application of the 3-valued logic. This logic is an extension of the Boolean one, resulting from the addition of a new element to the set Boolean set ${0,1}$.

Le paysage du monde des téléphones mobiles a changé avec l’introduction des ordiphones (de l’anglais smartphones). En effet, depuis leur avènement, les ordiphones sont devenus incontournables dans des différents aspects de la vie quotidienne. Cela a poussé de nombreux fournisseurs de services de rendre leurs services disponibles sur mobiles. Malgré cette croissante popularité, l’adoption des ordiphones pour des applications sensibles n’a toujours pas eu un grand succès. La raison derrière cela est que beaucoup d’utilisateurs, de plus en plus concernés par la sécurité de leurs appareils, ne font pas confiance à leur ordiphone pour manipuler leurs données sensibles. Cette thèse a pour objectif de renforcer la confiance des utilisateurs en leur mobile. Nous abordons ce problème de confiance en suivant deux approches complémentaires, à savoir la sécurité prouvée et la sécurité ancrée à des dispositifs matériels. Dans la première partie, notre objectif est de montrer les limitations des technologies actuellement utilisées dans les architectures des ordiphones. À cette fin, nous étudions deux systèmes largement déployés et dont la sécurité a reçu une attention particulière dès la conception : l’entrepôt de clés d’Android, qui est le composant protégeant les clés cryptographiques stockées sur les mobiles d’Android, et la famille des protocoles sécurisés SCP (de l’anglais Secure Channel Protocol) qui est définie par le consortium GlobalPlatform. Nos analyses se basent sur le paradigme de la sécurité prouvée. Bien qu’elle soit perçue comme un outil théorique voire abstrait, nous montrons que cet outil pourrait être utilisé afin de trouver des vulnérabilités dans des systèmes industriels. Cela atteste le rôle important que joue la sécurité prouvée pour la confiance en étant capable de formellement démontrer l’absence de failles de sécurité ou éventuellement de les identifier quand elles existent. Quant à la deuxième partie, elle est consacrée aux systèmes complexes qui ne peuvent pas être formellement vérifiés de manière efficace en termes de coût. Nous commençons par examiner l’approche à double environnement d’exécution. Ensuite, nous considérons le cas où cette approche est instanciée par des dispositifs matériels particuliers, à savoir le ARM TrustZone, afin de construire un environnement d’exécution de confiance (TEE de l’anglais Trusted Execution Environment). Enfin, nous explorons deux solutions palliant quelques limitations actuelles du TEE. Premièrement, nous concevons une nouvelle architecture du TEE qui en protège les données sensibles même quand son noyau sécurisé est compromis. Cela soulage les fournisseurs des services de la contrainte qui consiste à faire pleinement confiance aux fournisseurs du TEE. Deuxièmement, nous proposons une solution dans laquelle le TEE n’est pas uniquement utilisé pour protéger l’exécution des applications sensibles, mais aussi pour garantir à des grands composants logiciels (comme le noyau d’un système d’exploitation) des propriétés de sécurité plus complexes, à savoir l’auto-protection et l’auto-remédiation<br>The landscape of mobile devices has been changed with the introduction of smartphones. Sincetheir advent, smartphones have become almost vital in the modern world. This has spurred many service providers to propose access to their services via mobile applications. Despite such big success, the use of smartphones for sensitive applications has not become widely popular. The reason behind this is that users, being increasingly aware about security, do not trust their smartphones to protect sensitive applications from attackers. The goal of this thesis is to strengthen users trust in their devices. We cover this trust problem with two complementary approaches: provable security and hardware primitives. In the first part, our goal is to demonstrate the limits of the existing technologies in smartphones architectures. To this end, we analyze two widely deployed systems in which careful design was applied in order to enforce their security guarantee: the Android KeyStore, which is the component shielding users cryptographic keys in Android smartphones, and the family of Secure Channel Protocols (SCPs) defined by the GlobalPlatform consortium. Our study relies on the paradigm of provable security. Despite being perceived as rather theoretical and abstract, we show that this tool can be handily used for real-world systems to find security vulnerabilities. This shows the important role that can play provable security for trust by being able to formally prove the absence of security flaws or to identify them if they exist. The second part focuses on complex systems that cannot cost-effectively be formally verified. We begin by investigating the dual-execution-environment approach. Then, we consider the case when this approach is built upon some particular hardware primitives, namely the ARM TrustZone, to construct the so-called Trusted Execution Environment (TEE). Finally, we explore two solutions addressing some of the TEE limitations. First, we propose a new TEE architecture that protects its sensitive data even when the secure kernel gets compromised. This relieves service providers of fully trusting the TEE issuer. Second, we provide a solution in which TEE is used not only for execution protection, but also to guarantee more elaborated security properties (i.e. self-protection and self-healing) to a complex software system like an OS kernel

Most large corporations with big data have adopted more privacy measures in handling their sensitive/private data and as a result, employing the use of analytic tools to run across multiple sources has become ineffective. Joint computation across multiple parties is allowed through the use of secure multi-party computations (MPC). The practicality of MPC is impaired when dealing with large datasets as more of its algorithms are poorly scaled with data sizes. Despite its limitations, MPC continues to attract increasing attention from industry players who have viewed it as a better approach to exploiting big data. Secure MPC is however, faced with complexities that most times overwhelm its handlers, so the need for special software engineering techniques for resolving these threat complexities. This research presents cryptographic data security measures, garbed circuits protocol, optimizing circuits, and protocol execution techniques as some of the special techniques for resolving threat complexities associated with MPC’s. Honest majority, asymmetric trust, covert security, and trading off leakage are some of the experimental outcomes of implementing these special techniques. This paper also reveals that an essential approach in developing suitable mitigation strategies is having knowledge of the adversary type.