Search

Presented on 15 February 2023 at the Research Software Engineering in Data and AI workshop hosted by The Alan Turing Institute and The University of Warwick (15-17 February 2023). The recording of this talk can be streamed on YouTube. Abstract Researchers often need to analyse sensitive data in order to answer important questions for health, government and society. Balancing the need to protect individual privacy and commercial confidentiality with the need to ensure that reliable insights can be made using sensitive data is challenging, and Trusted Research Environments (TREs) that provide secure analysis environments for working with sensitive data are a key part of striking this balance. The Alan Turing Institute has recently open-sourced its Data Safe Haven, a secure, scalable, reproducibly deployable, cloud-based TRE that we have been using for the last 4 years to support our researchers in working safely and productively with sensitive data. By openly publishing the code and documentation required to deploy, configure and manage a Data Safe Haven instance, we make it easier for others to deploy their own Trusted Research Environments, reducing the effort required to support their researchers in working safely with sensitive data. We've also been working closely with the wider community to better align work in this area, initially on the development of the information governance principals and design choices for our Data Safe Haven, which we published in 2019. More recently, we've been working closely with the DARE UK programme to define common requirements for Trusted Research Environments and have co-founded the RSE TRE Community, bringing together those who are developing and deploying TREs to more closely co-ordinate our work. In this talk we will give an overview of the Turing's Data Safe Haven and the information governance and design principals behind it, as well as the work we have been doing with the wider community to develop a common set of TRE requirements and to co-ordinate across organisations on the development, deployment and management of TREs., This work was supported by The UKRI Strategic Priorities Fund under the EPSRC Grant EP/T001569/1, particularly the "Tools, Practices and Systems" theme within that grant, and by The Alan Turing Institute under the EPSRC grants EP/N510129/1, EP/W001381/1, EP/W037211/1 and EP/X03870X/1., {"references":["Arenas, Diego et al. (2019). Design choices for productive, secure, data-intensive research at scale in the cloud. https://doi.org/10.48550/arXiv.1908.08737"]}

A private intersection-sum (PIS) scheme considers the private computing problem of how parties jointly compute the sum of associated values in the set intersection. In scenarios such as electronic voting, corporate credit investigation, and ad conversions, private data are held by different parties. However, despite two-party PIS being well-developed in many previous works, its extended version, multi-party PIS, has rarely been discussed thus far. This is because, depending on the existing works, directly initiating multiple two-party PIS instances is considered to be a straightforward way to achieve multi-party PIS; however, by using this approach, the intersection-sum results of the two parties and the data only belonging to the two-party intersection will be leaked. Therefore, achieving secure multi-party PIS is still a challenge. In this paper, we propose a secure and lightweight multi-party private intersection-sum scheme called SLMP-PIS. We maintain data privacy based on zero sharing and oblivious pseudorandom functions to compute the multi-party intersection and consider the privacy of associated values using arithmetic sharing and symmetric encryption. The security analysis results show that our protocol is proven to be secure in the standard semi-honest security model. In addition, the experiment results demonstrate that our scheme is efficient and feasible in practice. Specifically, when the number of participants is five, the efficiency can be increased by 22.98%.

Secure two-party computation is a cryptographic technique that enables two parties to compute a function jointly while keeping each input secret. It is known that most functions cannot be realized by information-theoretically secure two-party computation, but any function can be realized in the correlated randomness (CR) model, where a trusted dealer distributes input-independent CR to the parties beforehand. In the CR model, three kinds of complexities are mainly considered; the size of CR, the number of rounds, and the communication complexity. Ishai et al. (TCC 2013) showed that any function can be securely computed with optimal online communication cost, i.e., the number of rounds is one round and the communication complexity is the same as the input length, at the price of exponentially large CR. In this paper, we prove that exponentially large CR is necessary to achieve perfect security and online optimality for a general function and that the protocol by Ishai et al. is asymptotically optimal in terms of the size of CR. Furthermore, we also prove that exponentially large CR is still necessary even when we allow multiple rounds while keeping the optimality of communication complexity., LIPIcs, Vol. 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023), pages 18:1-18:16

We present a new algorithmic framework for distributed network optimization in the presence of eavesdropper adversaries, also known as passive wiretappers. In this setting, the adversary is listening to the traffic exchanged over a fixed set of edges in the graph, trying to extract information on the private input and output of the vertices. A distributed algorithm is denoted as f-secure, if it guarantees that the adversary learns nothing on the input and output for the vertices, provided that it controls at most f graph edges. Recent work has presented general simulation results for f-secure algorithms, with a round overhead of D^Θ(f), where D is the diameter of the graph. In this paper, we present a completely different white-box, and yet quite general, approach for obtaining f-secure algorithms for fundamental network optimization tasks. Specifically, for n-vertex D-diameter graphs with (unweighted) edge-connectivity Ω(f), there are f-secure congest algorithms for computing MST, partwise aggregation, and (1+ε) (weighted) minimum cut approximation, within Õ(D+f √n) congest rounds, hence nearly tight for f = Õ(1). Our algorithms are based on designing a secure algorithmic-toolkit that leverages the special structure of congest algorithms for global optimization graph problems. One of these tools is a general secure compiler that simulates light-weight distributed algorithms in a congestion-sensitive manner. We believe that these tools set the ground for designing additional secure solutions in the congest model and beyond., LIPIcs, Vol. 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), pages 71:1-71:20

IoT data markets in public and private institutions have become increasingly relevant in recent years because of their potential to improve data availability and unlock new business models. However, exchanging data in markets bears considerable challenges related to disclosing sensitive information. Despite considerable research focused on different aspects of privacy-enhancing data markets for the IoT, none of the solutions proposed so far seems to find a practical adoption. Thus, this study aims to organize the state-of-the-art solutions, analyze and scope the technologies that have been suggested in this context, and structure the remaining challenges to determine areas where future research is required. To accomplish this goal, we conducted a systematic literature review on privacy enhancement in data markets for the IoT, covering 50 publications dated up to July 2020, and provided updates with 24 publications dated up to May 2022. Our results indicate that most research in this area has emerged only recently, and no IoT data market architecture has established itself as canonical. Existing solutions frequently lack the required combination of anonymization and secure computation technologies. Furthermore, there is no consensus on the appropriate use of blockchain technology for IoT data markets and a low degree of leveraging existing libraries or reusing generic data market architectures. We also identified significant challenges remaining, such as the copy problem and the recursive enforcement problem that-while solutions have been suggested to some extent-are often not sufficiently addressed in proposed designs. We conclude that privacy-enhancing technologies need further improvements to positively impact data markets so that, ultimately, the value of data is preserved through data scarcity and users' privacy and businesses-critical information are protected., Comment: 49 pages, 17 figures, 11 tables

Consumers in electricity markets are becoming more proactive because of the rapid development of demand–response management and distributed energy resources, which boost the transformation of peer-to-peer (P2P) energy-trading mechanisms. However, in the P2P negotiation process, it is a challenging task to prevent private information from being attacked by malicious agents. In this paper, we propose a privacy-preserving, two-party, secure computation mechanism for consensus-based P2P energy trading. First, a novel P2P negotiation mechanism for energy trading is proposed based on the consensus + innovation (C + I) method and the power transfer distribution factor (PTDF), and this mechanism can simultaneously maximize social welfare and maintain physical network constraints. In addition, the C + I method only requires a minimum set of information to be exchanged. Then, we analyze the strategy of malicious neighboring agents colluding to attack in order to steal private information. To defend against this attack, we propose a two-party, secure computation mechanism in order to realize safe negotiation between each pair of prosumers based on Paillier homomorphic encryption (HE), a smart contract (SC), and zero-knowledge proof (ZKP). The energy price is updated in a safe way without leaking any private information. Finally, we simulate the functionality of the privacy-preserving mechanism in terms of convergence performance, computational efficiency, scalability, and SC operations.

Clustering is a popular unsupervised machine learning technique that groups similar input elements into clusters. It is used in many areas ranging from business analysis to health care. In many of these applications, sensitive information is clustered that should not be leaked. Moreover, nowadays it is often required to combine data from multiple sources to increase the quality of the analysis as well as to outsource complex computation to powerful cloud servers. This calls for efficient privacy-preserving clustering. In this work, we systematically analyze the state-of-the-art in privacy-preserving clustering. We implement and benchmark today’s four most efficient fully private clustering protocols by Cheon et al. (SAC’19), Meng et al. (ArXiv’19), Mohassel et al. (PETS’20), and Bozdemir et al. (ASIACCS’21) with respect to communication, computation, and clustering quality. We compare them, assess their limitations for a practical use in real-world applications, and conclude with open challenges.

Fully homomorphic encryption (FHE) allows to compute any function on encrypted values. However, in practice, there is no universal FHE scheme that is effi-cient in all possible use cases. In this work, we show that FHE schemes suitable for arithmetic circuits (e.g. BGV or BFV) have a similar performance as FHE schemes for non-arithmetic circuits (TFHE) in basic comparison tasks such as less-than, maximum and minimum operations. Our implementation of the less-than function in the HElib library is up to 3 times faster than the prior work based on BGV/BFV. It allows to compare a pair of 64-bit integers in 11 milliseconds, sort 64 32-bit integers in 19 seconds and find the minimum of 64 32-bit integers in 9.5 seconds on an average laptop without multi-threading.

We consider a scenario where multiple organizations holding large amounts of sensitive data from their users wish to compute aggregate statistics on this data while protecting the privacy of individual users. To support large-scale analytics we investigate how this privacy can be provided for the case of sketching algorithms running in time sub-linear of the input size. We begin with the well-known LogLog sketch for computing the number of unique elements in a data stream. We show that this algorithm already achieves differential privacy (even without adding any noise) when computed using a private hash function by a trusted curator. Next, we show how to eliminate this requirement of a private hash function by injecting a small amount of noise, allowing us to instantiate an efficient LogLog protocol for the multi-party setting. To demonstrate the practicality of this approach, we run extensive experimentation on multiple data sets, including the publicly available IP address data set from University of Michigan’s scans of internet IPv4 space, to determine the trade-offs among efficiency, privacy and accuracy of our implementation for varying numbers of parties and input sizes. Finally, we generalize our approach for the LogLog sketch and obtain a general framework for constructing multi-party differentially private protocols for several other sketching algorithms.

When scaling a distributed ORAM to a two-party secure computation, the overhead is dominated by the number of pseudo-random generator (PRG) calls in generation and evaluation of a distributed point function (DPF), which are O(logn) and O(n) respectively, where n is the number of data blocks. We propose a distributed ORAM scheme, in which the PRG calls are reduced to O(log(zn/λ)) for generation and O(2log(zn/λ)) for evaluation, where λ is the secure parameter and z is the length of outputs in DPF. Technically, we first extend the optimization of Function Secret Sharing (FSS), early termination for functions with small output groups, to the context of ORAM for secure computation. Then, we design a scheme named etoram to exploit the high efficiency achieved by early termination. In etoram, we introduce an access counter for each data block. Then, instead of {0,1}λ, the output of the point function becomes the maximum value of these counters, i.e.,{0,1}z. Data blocks are privately updated by masking random strings generated by their counters. In practice, according to different access rates, z ranges from 1 to logn in sequential mode and from 3 to logn in random mode if the total number of accesses is n.

For k = ω(log n), we prove a Ω(k²n / log(kn)) lower bound on private simultaneous messages (PSM) with k parties who receive n-bit inputs. This extends the Ω(n) lower bound due to Appelbaum, Holenstein, Mishra and Shayevitz [Journal of Cryptology, 2019] to the many-party (k = ω(log n)) setting. It is the first PSM lower bound that increases quadratically with the number of parties, and moreover the first unconditional, explicit bound that grows with both k and n. This note extends the work of Ball, Holmgren, Ishai, Liu, and Malkin [ITCS 2020], who prove communication complexity lower bounds on decomposable randomized encodings (DREs), which correspond to the special case of k-party PSMs with n = 1. To give a concise and readable introduction to the method, we focus our presentation on perfect PSM schemes., LIPIcs, Vol. 230, 3rd Conference on Information-Theoretic Cryptography (ITC 2022), pages 7:1-7:12

It is known that Bitcoin enables to achieve fairness in secure computation by imposing a monetary penalty on adversarial parties. This functionality is called secure computation with penalties. Bentov and Kumaresan (Crypto 2014) showed that it could be realized with O(n) rounds and O(n) broadcasts for any function, where n is the number of parties. Kumaresan and Bentov (CCS 2014) posed an open question: "Is it possible to design secure computation with penalties that needs only O(1) rounds and O(n) broadcasts?" In this work, we introduce secure computation with non-equivalent penalties, and design a protocol achieving this functionality with O(1) rounds and O(n) broadcasts only. The new functionality is the same as secure computation with penalties except that every honest party receives more than a predetermined amount of compensation while the previous one requires that every honest party receives the same amount of compensation. In particular, both are the same if all parties behave honestly. Thus, our result gives a partial answer to the open problem with a slight and natural modification of functionality., OASIcs, Vol. 97, 3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021), pages 5:1-5:16

Теоретично обґрунтовано та розроблено ефективний метод прискорення операції модулярного експоненціювання з використанням віддалених обчислювальних ресурсів. Головною особливістю запропонованого методу є шифрування основи та показника степеня перед їх відправкою на віддалену систему, що забезпечує ефективний захист під час дистанційного обчислення. Теоретично та експериментально показано, що запропонований метод дозволяє приблизно у 18 разів прискорити обчислення модулярної експоненти із збереженням захищеності секретної частини даних. Запропонований спосіб може бути застосований у портативних малопотужних пристроях, які вимагають підтримки протоколів криптографічного захисту інформації. An effective method of accelerating the operation of modular exponentiation with the use of remote computing resources is theoretically substantiated and developed. The main feature of the proposed method is the encryption of the base and exponent before sending them to a remote system, which provides effective protection during remote computing. It has been shown theoretically and experimentally that the proposed method allows to accelerate approximately 18 times the calculation of the modular exponent while maintaining the security of the secret part of the data. The proposed method can be used in portable low-power devices that require support for cryptographic information protection protocols.

TFHE is a fast fully homomorphic encryption scheme proposed by Chillotti et al. in Asiacrypt’ 2018. Integer-wise TFHE is a generalized version of TFHE that can encrypt the plaintext of an integer that was implicitly presented by Chillotti et al., and Bourse et al. presented the actual form of the scheme in CRYPTO’ 2018. However, Bourse et al.’s scheme provides only homomorphic integer additions and homomorphic evaluations of a sign function. In this paper, we construct a technique for operating any 1-variable function in only one bootstrapping of the integer-wise TFHE. For applications of the scheme, we also construct a useful homomorphic evaluation of several integer arithmetics: division, equality test, and multiplication between integer and binary numbers. Our implementation results show that our homomorphic division is approximately 3.4 times faster than any existing work and that its run time is less than 1 second for 4-bit integer inputs.

Blockchain technology plays a pivotal role in the undergoing fourth industrial revolution or Industry 4.0. It is considered a tremendous boost to company digitalization, thus, considerable investments in blockchain are being made. However, there is no single blockchain technology, but various solutions exist, and they cannot interoperate with one each other. The ecosystem envisioned by the Industry 4.0 does not have centralized management or leading organization, so a single blockchain solution cannot be imposed. The various organizations hold their own blockchains, which must interoperate seamlessly. Despite some solutions for blockchain interoperability being proposed, the problem is still open. This paper aims to devise a secure solution for blockchain interoperability. The proposed approach consists of a relay scheme based on Trusted Execution Environment to provide higher security guarantees than the current literature. In particular, the proposed solution adopts an off-chain secure computation element invoked by a smart contract on a blockchain to securely communicate with its peered counterpart. A prototype has been implemented and used for the performance assessment, e.g., to measure the latency increase due to cross-blockchain interactions. The achieved and reported experimental results show that the proposed security solution introduces an additional latency that is entirely tolerable for transactions. At the same time, the usage of the Trusted Execution Environment imposes a negligible overhead.

openaire: EC/H2020/786641/EU//SHERPA Funding Information: Acknowledgements. This project received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (grant agreement No. 850990 PSOTI), was co-funded by the DFG — SFB 1119 CROSSING/236615297 and GRK 2050 Privacy & Trust/251805230, and by the BMBF and HMWK within ATHENE. It was partially funded by the European Commission through the SHERPA Horizon 2020 project under grant agreement No. 786641. It was partially funded by the Private AI Collaborative Research Institute (PrivateAI) established by Intel, Avast, and Borsetta. Publisher Copyright: © 2021 IEEE. Federated learning (FL) is an emerging distributed machine learning paradigm which addresses critical data privacy issues in machine learning by enabling clients, using an aggregation server (aggregator), to jointly train a global model without revealing their training data thereby, it improves not only privacy but is also efficient as it uses the computation power and data of potentially millions of clients for training in parallel. However, FL is vulnerable to so-called inference attacks by malicious aggregators which can infer information about clients' data from their model updates. Secure aggregation restricts the central aggregator to only learn the summation or average of the updates of clients. Unfortunately, existing protocols for secure aggregation for FL suffer from high communication, computation, and many communication rounds.In this work, we present SAFELearn, a generic design for efficient private FL systems that protects against inference attacks that have to analyze individual clients' model updates using secure aggregation. It is flexibly adaptable to the efficiency and security requirements of various FL applications and can be instantiated with MPC or FHE. In contrast to previous works, we only need 2 rounds of communication in each training iteration, do not use any expensive cryptographic primitives on clients, tolerate dropouts, and do not rely on a trusted third party. We implement and benchmark an instantiation of our generic design with secure two-party computation. Our implementation aggregates 500 models with more than 300K parameters in less than 0.5 seconds.

Can a sender encode a pair of messages \((m_0,m_1)\) jointly, and send their encoding over (say) a binary erasure channel, so that the receiver can decode exactly one of the two messages and the sender does not know which one?

Correlated random variables are a key tool in cryptographic applications like secure multi-party computation. We investigate the power of a class of correlations that we term group correlations: A group correlation is a uniform distribution over pairs (x,y) ∈ G² such that x+y ∈ S, where G is a (possibly non-abelian) group and S is a subset of G. We also introduce bi-affine correlation{s}, and show how they relate to group correlations. We present several structural results, new protocols and applications of these correlations. The new applications include a completeness result for black box group computation, perfectly secure protocols for evaluating a broad class of black box "mixed-groups" circuits with bi-affine homomorphisms, and new information-theoretic results. Finally, we uncover a striking structure underlying OLE: In particular, we show that OLE over 𝔽_{2ⁿ}, is isomorphic to a group correlation over ℤ_4^n., LIPIcs, Vol. 199, 2nd Conference on Information-Theoretic Cryptography (ITC 2021), pages 1:1-1:23

We consider the problem of secure distributed matrix multiplication (SDMM). Coded computation has been shown to be an effective solution in distributed matrix multiplication, both providing privacy against workers and boosting the computation speed by efficiently mitigating stragglers. In this work, we present a non-direct secure extension of the recently introduced bivariate polynomial codes. Bivariate polynomial codes have been shown to be able to further speed up distributed matrix multiplication by exploiting the partial work done by the stragglers rather than completely ignoring them while reducing the upload communication cost and/or the workers' storage's capacity needs. We show that, especially for upload communication or storage constrained settings, the proposed approach reduces the average computation time of SDMM compared to its competitors in the literature., Comment: To appear in IEEE Journal on Selected Areas in Communications. arXiv admin note: text overlap with arXiv:2102.08304

Data-oblivious algorithms are a key component of many secure computation protocols. In this work, we show that advances in secure multiparty shuffling algorithms can be used to increase the efficiency of several key cryptographic tools. The key observation is that many secure computation protocols rely heavily on secure shuffles. The best data-oblivious shuffling algorithms require O(n log n), operations, but in the two-party or multiparty setting, secure shuffling can be achieved with only O(n) communication. Leveraging the efficiency of secure multiparty shuffling, we give novel, information-theoretic algorithms that improve the efficiency of securely sorting sparse lists, secure stable compaction, and securely merging two sorted lists. Securely sorting private lists is a key component of many larger secure computation protocols. The best data-oblivious sorting algorithms for sorting a list of n elements require O(n log n) comparisons. Using black-box access to a linear-communication secure shuffle, we give a secure algorithm for sorting a list of length n with t ≪ n nonzero elements with communication O(t log² n + n), which beats the best oblivious algorithms when the number of nonzero elements, t, satisfies t < n/log² n. Secure compaction is the problem of removing dummy elements from a list, and is essentially equivalent to sorting on 1-bit keys. The best oblivious compaction algorithms run in O(n)-time, but they are unstable, i.e., the order of the remaining elements is not preserved. Using black-box access to a linear-communication secure shuffle, we give an information-theoretic stable compaction algorithm with only O(n) communication. Our main result is a novel secure merge protocol. The best previous algorithms for securely merging two sorted lists into a sorted whole required O(n log n) secure operations. Using black-box access to an O(n)-communication secure shuffle, we give the first multi-party secure merge algorithm that requires only O(n log log n) communication. Our algorithm takes as input n secret-shared values, and outputs a secret-sharing of the sorted list. All our algorithms are generic, i.e., they can be implemented using generic secure computations techniques and make black-box access to a secure shuffle. Our techniques extend naturally to the multiparty situation (with a constant number of parties) as well as to handle malicious adversaries without changing the asymptotic efficiency. These algorithm have applications to securely computing database joins and order statistics on private data as well as multiparty Oblivious RAM protocols., LIPIcs, Vol. 199, 2nd Conference on Information-Theoretic Cryptography (ITC 2021), pages 7:1-7:29

The enhancements in computation technologies in the last decades enabled businesses to analyze the data that is collected through their systems which helps to improve their services.However, performing data analytics remains a challenging task for small- and medium-scale companies due to the lack of in-house experience and computational resources. Data Analytics-as-a-Service (DAaaS) paradigm provides such companies outsourced data analytics, where a company that is specialized in data analytics serves its knowledge and computational resources to the other companies, which need data analytics for their businesses. A major challenge in DAaaS is preserving the privacy of the outsourced data, which might contain sensitive customer or employee information or the intellectual property of the outsourcing company. Leakage of sensitive information has several consequences both for outsourcing and service provider companies as legal obligations, loss of reputation, and financial loss. Therefore, a well functioning outsourced analytics service should achieve several data protection measures such as confidentiality, integrity, and availability. In this thesis, we focus on the preservation of confidentiality in data analytics-as-a-service applications. We select three analytics applications that are becoming popular in outsourced data analytics, which are process analytics, machine learning, and marketing analytics. Despite there exist several other techniques that are commonly used in outsourced data analytics, we decide to focus on the algorithms of process analytics, machine learning, and marketing analytics since the privacy concerns in these analytics have not been investigated thoroughly. In confidential data analytics-as-a-service, our goal is to achieve confidentiality by protecting input/output privacy and maintaining the correctness and efficiency of analytics computations. To protect the privacy of data we use two secure computation techniques, which are homomorphic encryption and secure multiparty computation. To assure correctness, we propose several hybrid protocol designs that minimize the loss of accuracy in computations. For the efficiency of our protocols, we use several optimization techniques that reduce the computation and communication costs of private data analytics. Our protocols show promising results for confidential data analytics in the outsourced setting.

We consider the secure computation problem in a minimal model, where Alice and Bob each holds an input and wish to securely compute a function of their inputs at Carol without revealing any additional information about the inputs. For this minimal secure computation problem, we propose a novel coding scheme built from two steps. First, the function to be computed is expanded such that it can be recovered while additional information might be leaked. Second, a randomization step is applied to the expanded function such that the leaked information is protected. We implement this expand-and-randomize coding scheme with two algebraic structures—the finite field and the modulo ring of integers, where the expansion step is realized with the addition operation and the randomization step is realized with the multiplication operation over the respective algebraic structures.

Many privacy protections in distributed setting are based on secure comparison, according to which two distrusted users try to jointly determine whether a > b, a = b, or a 1)/(kb + k1)), which implies the potential relationship (a > b, a = b, and a 1, and b belong to the party who doesn't have the secret of the system. Based on this system, two distrusted users in distributed setting can learn whether a > b, a = b, or a

This paper showcase protocols of secure computation with complexity characteristics suitable to practical hiding the coordinates of point objects in unspecified local traffic control zone. Hiding of the coordinates will ensure the protection of road users from both semi-honest adversary who, having taken control of one or several objects, may disclose movement coordinates of fair users, thus violating privacy policy in part of objects’ locations, or from the malicious adversary, who, having taken control of one or several objects may disclose movement coordinates of fair users and, therefore, affect the speed of movement of the controlled objects to facilitate a dangerous closeness and/or collision of the objects.

Data generalization is a widely-used privacy technique, in which an accurate value of sensitive information is replaced with a more general representation. The problem of data generalization becomes challenging when data is distributed among several agents, who are interested in releasing their table of data to shape a data mining algorithm on the whole of their data. The main issue originates from the fact that when each agent generalizes her own dataset locally, the released tables of data suffer from non-homogeneity. To sole the issue, all agents can generalize their data to the widest range of generalization. However, this approach causes utility loss. To optimally address this problem, in this study we present a framework that serves as a tool for data owners to generalize their data homogeneously before being published. The effectiveness of the proposed mechanism is validated through an experimental analysis on a benchmark dataset.

Secure report is the problem of a client that retrieves all records matching specified attributes from a database table at the server (e.g. cloud), as in SQL SELECT queries, but where the query and the database are encrypted. Here, only the client has the secret key, but still the server is expected to compute and return the encrypted result. Secure report is theoretically possible with Fully Homomorphic Encryption (FHE). However, the current state-of-the-art solutions are realized by a polynomial of degree that is at least linear in the number m of records, which is too slow in practice even for very small databases. We present the first solution that is realized by a polynomial that attains degree independent of the number of records m, as well as the first implementation of an FHE solution to Secure report. This is by suggesting a novel paradigm that forges a link between cryptography and modern data summarization techniques known as coresets (core-sets), and sketches in particular. The key idea is to compute only a coreset of the desired report. Since the coreset is small, the client can quickly decode the desired report that the server computes after decrypting the coreset. We implemented our main reporting system in an open source library. This is the first implemented system that can answer such database queries when processing only FHE encrypted data and queries. As our analysis promises, the experimental results show that we can run Secure report queries on billions records in minutes on an Amazon EC2 server, compared to less than a hundred-thousands in previous FHE based solutions., IACR Transactions on Cryptographic Hardware and Embedded Systems, Volume 2019, Issue 2

Smartphones have achieved ubiquitous presence in people’s everyday life as communication, entertainment and work tools. Touch screens and a variety of sensors offer a rich experience and make applications increasingly diverse, complex and resource demanding. Despite their continuous evolution and enhancements, mobile devices are still limited in terms of battery life, processing power, storage capacity and network bandwidth. Computation offloading stands out among the efforts to extend device capabilities and face the growing gap between demand and availability of resources. As most popular technologies, mobile devices are attractive targets for malicious at- tackers. They usually store sensitive private data of their owners and are increasingly used for security sensitive activities such as online banking or mobile payments. While computation offloading introduces new challenges to the protection of those assets, it is very uncommon to take security and privacy into account as the main optimization objectives of this technique. Mobile OS security relies heavily on cryptography. Available hardware and software cryptographic providers are usually designed to resist software attacks. This kind of protection is not enough when physical control over the device is lost. Secure elements, on the other hand, include a set of protections that make them physically tamper-resistant devices. This work proposes a computation offloading technique that prioritizes enhancing security capabilities in mobile phones by offloading cryptographic operations to the SIM card, the only universally present secure element in those devices. Our contributions include an architecture for this technique, a proof-of-concept prototype developed under Android OS and the results of a performance evaluation that was conducted to study its execution times and battery consumption. Despite some limitations, our approach proves to be a valid alternative to enhance security on any smartphone. Los smartphones están omnipresentes en la vida cotidiana de las personas como herramientas de comunicación, entretenimiento y trabajo. Las pantallas táctiles y una variedad de sensores ofrecen una experiencia superior y hacen que las aplicaciones sean cada vez más diversas, complejas y demanden más recursos. A pesar de su continua evolución y mejoras, los dispositivos móviles aún están limitados en duración de batería, poder de procesamiento, capacidad de almacenamiento y ancho de banda de red. Computation offloading se destaca entre los esfuerzos para ampliar las capacidades del dispositivo y combatir la creciente brecha entre demanda y disponibilidad de recursos. Como toda tecnología popular, los smartphones son blancos atractivos para atacantes maliciosos. Generalmente almacenan datos privados y se utilizan cada vez más para actividades sensibles como banca en línea o pagos móviles. Si bien computation offloading presenta nuevos desafíos al proteger esos activos, es muy poco común tomar seguridad y privacidad como los principales objetivos de optimización de dicha técnica. La seguridad del SO móvil depende fuertemente de la criptografía. Los servicios criptográficos por hardware y software disponibles suelen estar diseñados para resistir ataques de software, protección insuficiente cuando se pierde el control físico sobre el dispositivo. Los elementos seguros, en cambio, incluyen un conjunto de protecciones que los hacen físicamente resistentes a la manipulación. Este trabajo propone una técnica de computation offloading que prioriza mejorar las capacidades de seguridad de los teléfonos móviles descargando operaciones criptográficas a la SIM, único elemento seguro universalmente presente en los mismos. Nuestras contribuciones incluyen una arquitectura para esta técnica, un prototipo de prueba de concepto desarrollado bajo Android y los resultados de una evaluación de desempeño que estudia tiempos de ejecución y consumo de batería. A pesar de algunas limitaciones, nuestro enfoque demuestra ser una alternativa válida para mejorar la seguridad en cualquier smartphone.

Cryptography grew to be much more than "the study of secret writing". Modern cryptography is concerned with establishing properties such as privacy, integrity and authenticity in protocols for secure communication and computation. This comes at a price: Cryptographic tools usually introduce an overhead, both in terms of communication complexity (that is, number and size of messages transmitted) and computational efficiency (that is, time and memory required). As in many settings communication between the parties involved is the bottleneck, this thesis is concerned with improving communication complexity in cryptographic protocols. One direction towards this goal is scalable cryptography: In many cryptographic schemes currently deployed, the security degrades linearly with the number of instances (e.g. encrypted messages) in the system. As this number can be huge in contexts like cloud computing, the parameters of the scheme have to be chosen considerably larger - and in particular depending on the expected number of instances in the system - to maintain security guarantees. We advance the state-of-the-art regarding scalable cryptography by constructing schemes where the security guarantees are independent of the number of instances. This allows to choose smaller parameters, even when the expected number of instances is immense. - We construct the first scalable encryption scheme with security against active adversaries which has both compact public keys and ciphertexts. In particular, we significantly reduce the size of the public key to only about 3% of the key-size of the previously most efficient scalable encryption scheme. (Gay,Hofheinz, and Kohl, CRYPTO, 2017) - We present a scalable structure-preserving signature scheme which improves both in terms of public-key and signature size compared to the previously best construction to about 40% and 56% of the sizes, respectively. (Gay, Hofheinz, Kohl, and Pan, EUROCRYPT, 2018) Another important area of cryptography is secure multi-party computation, where the goal is to jointly evaluate some function while keeping each party’s input private. In traditional approaches towards secure multi-party computation either the communication complexity scales linearly in the size of the function, or the computational efficiency is poor. To overcome this issue, Boyle, Gilboa, and Ishai (CRYPTO, 2016) introduced the notion of homomorphic secret sharing. Here, inputs are shared between parties such that each party does not learn anything about the input, and such that the parties can locally evaluate functions on the shares. Homomorphic secret sharing implies secure computation where the communication complexity only depends on the size of the inputs, which is typically much smaller than the size of the function. A different approach towards efficient secure computation is to split the protocol into an input-independent preprocessing phase, where long correlated strings are generated, and a very efficient online phase. One example for a useful correlation are authenticated Beaver triples, which allow to perform efficient multiplications in the online phase such that privacy of the inputs is preserved and parties deviating the protocol can be detected. The currently most efficient protocols implementing the preprocessing phase require communication linear in the number of triples to be generated. This results typically in high communication costs, as the online phase requires at least one authenticated Beaver triple per multiplication. We advance the state-of-the art regarding efficient protocols for secure computation with low communication complexity as follows. - We construct the first homomorphic secret sharing scheme for computing arbitrary functions in NC 1 (that is, functions that are computably by circuits with logarithmic depth) which supports message spaces of arbitrary size, has only negligible correctness error, and does not require expensive multiplication on ciphertexts. (Boyle, Kohl, and Scholl, EUROCRYPT, 2019) - We introduce the notion of a pseudorandom correlation generator for general correlations. Pseudorandom correlation generators allow to locally extend short correlated seeds into long pseudorandom correlated strings. We show that pseudorandom correlation generators can replace the preprocessing phase in many protocols, leading to a preprocessing phase with sublinear communication complexity. We show connections to homomorphic secret sharing schemes and give the first instantiation of pseudorandom correlation generators for authenticated Beaver triples at reasonable computational efficiency. (Boyle, Couteau, Gilboa, Ishai, Kohl, and Scholl, CRYPTO, 2019)

We revisit the problem of universally composable (UC) secure multiparty computation in the stateless hardware token model.

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 constant-round 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.

A privacy-preserving framework in which a computational resource provider receives encrypted data from a client and returns prediction results without decrypting the data, i.e., oblivious neural network or encrypted prediction, has been studied in machine learning. In this work, we introduce and explore a new problem called the model-oblivious problem, where a trainer can delegate a protected model to a resource provider without revealing the original model itself to the resource provider. The resource provider can then offer prediction on a client's input data, which is additionally kept private from the resource provider. To solve this problem, we present MOBIUS (Model-Oblivious BInary neUral networkS), a new system that combines Binarized Neural Networks (BNNs) and secure computation based on secret sharing as tools for scalable and fast privacy-preserving machine learning. BNNs improve computational performance by binarizing values in training to -1 and +1, while secure computation based on secret sharing provides fast and various computations under encrypted forms via modulo operations with a short bit length. However, combining these tools is not trivial because their operations have different algebraic structures. MOBIUS uses improved procedures of BNNs and secure computation that have compatible algebraic structures without downgrading prediction accuracy. We present an implementation of MOBIUS in C++ using the ABY library (NDSS 2015). Then, we conduct experiments using several datasets, including the MNIST, Cancer, and Diabetes datasets, and the results show that MOBIUS outperforms SecureML (IEEE S&P 2017), which is the only other work that can potentially tackle the model-oblivious problem, in terms of both accuracy and computational time. Compared with TAPAS (ICML 2018) as a state-of-the-art BNN-based system, MOBIUS is three orders of magnitude faster without downgrading the accuracy despite solving the model-oblivious problem.

Decision trees and random forests are common classifiers with widespread use. In this paper, we develop two protocols for privately evaluating decision trees and random forests. We operate in the standard two-party setting where the server holds a model (either a tree or a forest), and the client holds an input (a feature vector). At the conclusion of the protocol, the client learns only the model’s output on its input and a few generic parameters concerning the model; the server learns nothing. The first protocol we develop provides security against semi-honest adversaries. We then give an extension of the semi-honest protocol that is robust against malicious adversaries. We implement both protocols and show that both variants are able to process trees with several hundred decision nodes in just a few seconds and a modest amount of bandwidth. Compared to previous semi-honest protocols for private decision tree evaluation, we demonstrate a tenfold improvement in computation and bandwidth.

© 2016 ACM. Hardware support for isolated execution (such as Intel SGX) enables development of applications that keep their code and data confidential even while running on a hostile or compromised host. However, automatically verifying that such applications satisfy confidentiality remains challenging. We present a methodology for designing such applications in a way that enables certifying their confidentiality. Our methodology consists of forcing the application to communicate with the external world through a narrow interface, compiling it with runtime checks that aid verification, and linking it with a small runtime library that implements the interface. The runtime library includes core services such as secure communication channels and memory management. We formalize this restriction on the application as Information Release Confinement (IRC), and we show that it allows us to decompose the task of proving confidentiality into (a) one-time, human-assisted functional verification of the runtime to ensure that it does not leak secrets, (b) automatic verification of the application's machine code to ensure that it satisfies IRC and does not directly read or corrupt the runtime's internal state. We present /CONFIDENTIAL: A verifier for IRC that is modular, automatic, and keeps our compiler out of the trusted computing base. Our evaluation suggests that the methodology scales to real-world applications.

Issues related to ensuring patient privacy and data ownership in clinical repositories prevent the growth of translational research. Previous studies have used an aggregator agent to obscure clinical repositories from the data user, and to ensure the privacy of output using statistical disclosure control. However, there remain several issues that must be considered. One such issue is that a data breach may occur when multiple nodes conspire. Another is that the agent may eavesdrop on or leak a user's queries and their results. We have implemented a secure computing method so that the data used by each party can be kept confidential even if all of the other parties conspire to crack the data. We deployed our implementation at three geographically distributed nodes connected to a high-speed layer two network. The performance of our method, with respect to processing times, suggests suitability for practical use., Proceedings of MIE2016 at HEC2016

Social media websites are blocked in many regimes where Internet censorship is applied. In this paper, we introduce Mailet, an unobservable transport proxy which enables the users to access social websites by email applications. Without assuming the Mailet servers are trustworthy, Mailet can support the services requiring privileges without having the complete credential. Particularly, the credential is split and distributed in two Mailet servers, and neither of them can recover the credential alone. To recover the credential in a TLS record message, we propose a highly efficient Galois/ Counter Mode(GCM) based secure computation, which can enable the two servers to conceal their separate credential copies in the computation. We implemented a prototype for Twitter.com to demonstrate the usability and security of Mailet.

In vehicular ad hoc networks (VANETs), the security and privacy of vehicle data are core issues. In order to analyze vehicle data, they need to be computed. Encryption is a common method to guarantee the security of vehicle data in the process of data dissemination and computation. However, encrypted vehicle data cannot be analyzed easily and flexibly. Because homomorphic encryption supports computations of the ciphertext, it can completely solve this problem. In this paper, we provide a comprehensive survey of secure computation based on homomorphic encryption in VANETs. We first describe the related definitions and the current state of homomorphic encryption. Next, we present the framework, communication domains, wireless access technologies and cyber-security issues of VANETs. Then, we describe the state of the art of secure basic operations, data aggregation, data query and other data computation in VANETs. Finally, several challenges and open issues are discussed for future research.

The notion of non-interactive secure computation (NISC) first introduced in the work of Ishai et al. [EUROCRYPT 2011] studies the following problem: Suppose a receiver R wishes to publish an encryption of her secret input y so that any sender S with input x can then send a message m that reveals f(x, y) to R (for some function f). Here, m can be viewed as an encryption of f(x, y) that can be decrypted by R. NISC requires security against both malicious senders and receivers, and also requires the receiver’s message to be reusable across multiple computations (w.r.t. a fixed input of the receiver).

An Oblivious RAM (ORAM) protocol allows a client to access memory outsourced at the server without leaking the access pattern. A related notion is Multi-Party Computation ORAM (MPC-ORAM), which is a protocol that can implement the RAM functionality for secure computation of any RAM programs on large data, e.g., MPC processing of database queries on a secret-shared database. MPC-ORAM can be constructed from any (client-server) ORAM by implementing the ORAM client algorithm with MPC protocols. However, efficient ORAM does not necessarily translate to efficient MPC-ORAM. Most previous work constructed efficient MPC-ORAM in the two-party secure computation (2PC) setting, but since secure computation of many functions is more efficient in the three-party honest-majority setting than in the two-party setting, it is natural to ask if the cost of an MPC-ORAM scheme can be reduced if one is willing to use three servers instead of two and assumes an honest majority. In this study, we show four constructions of MPC-ORAM in the three-party setting (3PC-ORAM) with honest majority, using customized 3PC protocols for performance optimization, which can make the resulting 3PC-ORAM schemes to be orders of magnitude more efficient than the current best 2PC-ORAM schemes. These improvements help to achieve practical and efficient performance results, and make MPC-ORAM more suitable for real world applications.

In this thesis, we study zero-knowledge proofs, a cryptographic primitive that allows to prove a statement while yielding nothing beyond its truth, and their applications to secure computation. Specifically, we first introduce a new type of zero-knowledge proofs, called implicit zero-knowledge arguments, that stands between two existing notions, interactive zeroknowledge proofs and non-interactive zero-knowledge proofs. Our new notion provides the same efficiency benefits than the latter when used to design roundefficient secure computation protocols, but it can be built from essentially the same cryptographic assumptions than the former, which allows to get improved efficiency and security guarantees. Second, we revisit a zero-knowledge proof system that is particularly useful for secure computation protocols manipulating integers, and show that the known security analysis can be improved to base the proof system on a more wellstudied assumption. Eventually, we introduce a new method to build zero-knowledge proof systems over the integers, which particularly improves over existing methods in a client-server model, where a weak client executes a secure computation protocol with a powerful server., Dans cette thèse, nous étudions les preuves à divulgation nulle de connaissance, une primitive cryptographique permettant de prouver une assertion en ne révélant rien de plus que sa véracité, et leurs applications au calcul sécurisé. Nous introduisons tout d’abord un nouveau type de preuves à divulgation nulle, appelées arguments implicites à divulgation nulle, intermédiaire entre deux notions existantes, les preuves interactives et les preuves non interactives à divulgation nulle. Cette nouvelle notion permet d’obtenir les mêmes bénéfices en terme d’efficacité que les preuves non-interactives dans le contexte de la construction de protocoles de calcul sécurisé faiblement interactifs, mais peut être instanciée à partir des mêmes hypothèses cryptographiques que les preuves interactives, permettant d’obtenir de meilleures garanties d’efficacité et de sécurité. Dans un second temps, nous revisitons un système de preuves à divulgation nulle de connaissance qui est particulièrement utile dans le cadre de protocoles de calcul sécurisé manipulant des nombres entiers, et nous démontrons que son analyse de sécurité classique peut être améliorée pour faire reposer ce système de preuve sur une hypothèse plus standard et mieux connue. Enfin, nous introduisons une nouvelle méthode de construction de systèmes de preuves à divulgation nulle sur les entiers, qui représente une amélioration par rapport aux méthodes existantes, tout particulièrement dans un modèle de type client-serveur, où un client à faible puissance de calcul participe à un protocole de calcul sécurisé avec un serveur à forte puissance de calcul.

Confidential Content-Based Publish/Subscribe (C-CBPS) is an interaction model that allows parties to exchange content while protecting their security and privacy interests. In this paper we advance the state of the art in C-CBPS by showing how all predicate circuits in NC1 (logarithmic-depth, bounded fan-in) can be confidentially computed by a broker while guaranteeing perfect information-theoretic security. Previous work could handle only strictly shallower circuits (e.g. those with depth O(ℑ)). We present three protocols—UGP-Match, FSGP-Match and OFSGP-Match—based on 2-decomposable randomized encodings of group programs for circuits in NC1. UGP-Match is conceptually simple and has a clean proof of correctness but its running time is a polynomial with a high exponent and hence impractical. FSGP-Match uses a “fixed structure” construction that reduces the exponent drastically and achieves efficiency and scalability. OFSGP-Match optimizes the group programs further to shave off a linear factor.

Recent proposals for trusted hardware platforms, such as Intel SGX and the MIT Sanctum processor, offer compelling security features but lack formal guarantees. We introduce a verification methodology based on a trusted abstract platform (TAP), a formalization of idealized enclave platforms along with a parameterized adversary. We also formalize the notion of secure remote execution and present machine-checked proofs showing that the TAP satisfies the three key security properties that entail secure remote execution: integrity, confidentiality and secure measurement. We then present machine-checked proofs showing that SGX and Sanctum are refinements of the TAP under certain parameterizations of the adversary, demonstrating that these systems implement secure enclaves for the stated adversary models.

In recent years we have seen a rise in the amount of fitness tracking and self monitoring devices. These devices which often work in conjunction with a smartphone are becoming more accurate and are becoming widely adopted. This trend goes hand in hand with Electronic Health Care (e-health): the shift of health care to the digital domain. E-health would allow patients to measure their medical condition at home, allowing a diagnosis to be made based on measurements taken over a longer period of time, while reducing the work performed by a doctor. Measurements are tored in the cloud, simplifying the way in which they can be shared with healthcare providers and possibly research nstitutions. Modernizing healthcare this way should give the patient more insight and control over his/her healthcare and medical data. Furthermore the amount of visits required to the hospital can be reduced, an endeavor which can be demanding for many less fit for elderly individuals.However, handling medical data this way causes concern for privacy. Often the data handled by these devices is very sensitive and could easily be used to identify the user and monitor many of their behaviours. In order to achieve privacy there are several approaches. One way is to enforce involved parties through legislation to use the data for specific purposes only. However, this relies on the party being semi-trusted and does not guarantee safety in case of a data-breach. In this work the way in which the integration of wearables into the medical domain is currently taking place and how privacy and security is handled will be explored. Furthermore we will show the current state of research regarding improving this security.

In recent years we have seen a rise in the amount of fitness tracking and self monitoring devices. These devices which often work in conjunction with a smartphone are becoming more accurate and are becoming widely adopted. This trend goes hand in hand with Electronic Health Care (e-health): the shift of health care to the digital domain. E-health would allow patients to measure their medical condition at home, allowing a diagnosis to be made based on measurements taken over a longer period of time, while reducing the work performed by a doctor. Measurements are tored in the cloud, simplifying the way in which they can be shared with healthcare providers and possibly research nstitutions. Modernizing healthcare this way should give the patient more insight and control over his/her healthcare and medical data. Furthermore the amount of visits required to the hospital can be reduced, an endeavor which can be demanding for many less fit for elderly individuals.However, handling medical data this way causes concern for privacy. Often the data handled by these devices is very sensitive and could easily be used to identify the user and monitor many of their behaviours. In order to achieve privacy there are several approaches. One way is to enforce involved parties through legislation to use the data for specific purposes only. However, this relies on the party being semi-trusted and does not guarantee safety in case of a data-breach. In this work the way in which the integration of wearables into the medical domain is currently taking place and how privacy and security is handled will be explored. Furthermore we will show the current state of research regarding improving this security.

In this paper, we study the problem of obtaining $1$-of-$2$ string oblivious transfer (OT) between users Alice and Bob, in the presence of a passive eavesdropper Eve. The resource enabling OT in our setup is a noisy broadcast channel from Alice to Bob and Eve. Apart from the OT requirements between the users, Eve is not allowed to learn anything about the users' inputs. When Alice and Bob are honest-but-curious and the noisy broadcast channel is made up of two independent binary erasure channels (connecting Alice-Bob and Alice-Eve), we derive the $1$-of-$2$ string OT capacity for both $2$-privacy (when Eve can collude with either Alice or Bob) and $1$-privacy (when no such collusion is allowed). We generalize these capacity results to $1$-of-$N$ string OT and study other variants of this problem. When Alice and/or Bob are malicious, we present a different scheme based on interactive hashing. This scheme is shown to be optimal for certain parameter regimes. We present a new formulation of multiple, simultaneous OTs between Alice-Bob and Alice-Cathy. For this new setup, we present schemes and outer bounds that match in all but one regime of parameters. Finally, we consider the setup where the broadcast channel is made up of a cascade of two independent binary erasure channels (connecting Alice-Bob and Bob-Eve) and $1$-of-$2$ string OT is desired between Alice and Bob with $1$-privacy. For this setup, we derive an upper and lower bound on the $1$-of-$2$ string OT capacity which match in one of two possible parameter regimes., Submitted to IEEE Transactions on Information Theory

The big data era has dramatically transformed our lives; however, security incidents such as data breaches can put sensitive data (e.g. photos, identities, genomes) at risk. To protect users' data privacy, there is a growing interest in building secure cloud computing systems, which keep sensitive data inputs hidden, even from computation providers. Conceptually, secure cloud computing systems leverage cryptographic techniques (e.g., secure multiparty computation) and trusted hardware (e.g. secure processors) to instantiate a “secure” abstract machine consisting of a CPU and encrypted memory, so that an adversary cannot learn information through either the computation within the CPU or the data in the memory. Unfortunately, evidence has shown that side channels (e.g. memory accesses, timing, and termination) in such a “secure” abstract machine may potentially leak highly sensitive information, including cryptographic keys that form the root of trust for the secure systems. This thesis broadly expands the investigation of a research direction called trace oblivious computation, where programming language techniques are employed to prevent side channel information leakage. We demonstrate the feasibility of trace oblivious computation, by formalizing and building several systems, including GhostRider, which is a hardware-software co-design to provide a hardware-based trace oblivious computing solution, SCVM, which is an automatic RAM-model secure computation system, and ObliVM, which is a programming framework to facilitate programmers to develop applications. All of these systems enjoy formal security guarantees while demonstrating a better performance than prior systems, by one to several orders of magnitude.

Private Set Intersection (PSI) is a cryptographic primitive that allows two network connected parties with hidden inputs to jointly compute the intersection of these inputs while keeping their specific inputs secret. PSI can be used as a building block for a variety of applications, most notably querying a remote relational database without revealing the query or the database. Many constructions of PSI exist, each building off of a subset of an assortment of cryptographic primitives such as: oblivious transfer, hash functions, garbled circuits, public key encryption and signature schemes, and basic number theoretic hardness assumptions. In this dissertation, we study variations of PSI and their practicality to modern day applications. Specifically, we study new security constraints for PSI that arise from applications such as genomics, consumer applications, and inter-agency information sharing. These constraints lead to several novel secure computation protocols. Through actualized prototypes of these schemes we conclude that, specialized PSI protocols are fast enough for use today, even on resource constrained hardware.

Secure multi-party computation (MPC) is a technique well suited for privacy-preserving data mining. Even with the recent progress in two-party computation techniques such as fully homomorphic encryption, general MPC remains relevant as it has shown promising performance metrics in real-world benchmarks. Sharemind is a secure multi-party computation framework designed with real-life efficiency in mind. It has been applied in several practical scenarios, and from these experiments, new requirements have been identified. Firstly, large datasets require more efficient protocols for standard operations such as multiplication and comparison. Secondly, the confidential processing of financial data requires the use of more complex primitives, including a secure division operation. This paper describes new protocols in the Sharemind model for secure multiplication, share conversion, equality, bit shift, bit extraction, and division. All the protocols are implemented and benchmarked, showing that the current approach provides remarkable speed improvements over the previous work. This is verified using real-world benchmarks for both operations and algorithms.