Data imputation is an important data preparation task where the data analyst replaces missing or erroneous values to increase the expected accuracy of downstream analyses. The accuracy improvement of data imputation extends to private data analyses across distributed databases. However, existing data imputation methods violate the privacy of the data rendering the privacy protection in the downstream analyses obsolete. We conclude that private data analysis requires private data imputation. In this paper, we present the first optimized protocols for private data imputation. We consider the case of horizontally and vertically split data sets. Our optimization aims to reduce most of the computation to private set intersection (or at least oblivious programmable pseudo-random function) protocols which can be very efficiently computed. We show that private data imputation has -- on average across all evaluated datasets -- an accuracy advantage of 20\% in case of vertically split data and 5\% in case of horizontally split data over imputing data locally. In case of the worst data split we observed that imputing using our method resulted in an increase of up to 32.7 times in the quality of imputation over the vertically split data and 3.4 times in case of horizontally split data. Our protocols are very efficient and run in 2.4 seconds in case of vertically split data and 8.4 seconds in case of horizontally split data for 100,000 records evaluated in the 10 Gbps network setting, performing one data imputation.

Finding the Minimum Spanning Tree or Forest (MSF) of a weighted graph is one of the most fundamental graph problems. It has many applications, and there are various algorithms to solve it in quasi-linear time. However, in a secure computation setting where the graph is shared between multiple parties, there are no fully satisfactory solutions. Any prior work on this problem either builds a circuit that is fed into a generic multi-party computation protocol, or is limited to graphs that have a unique MSF. In this work, we first identify privacy and fairness issues that arise when the MSF is not necessarily unique, i.e., there exist duplicate edge weights. Subsequently, we consider the notion of a Random Minimum Spanning Forest, which defines a distribution of the desired output in the case where multiple MSFs exist. We carefully design a protocol for this problem in the semi-honest security model. The main insight of our protocol is that we may reveal certain intermediate results over the entire course of the protocol execution (provably without impacting security), which are then used to make decisions that optimize efficiency. No party learns anything about the inputs of other parties except for the produced MSF, not even the number of input edges. Furthermore, the number of communication rounds is low for many typical graphs, which allows running the protocol even when the network latency is high. Our evaluation shows that, depending on the graph structure and its weight distribution, our protocol can outperform the previous baseline by Laud (PoPETs 2015) by up to 2-3 orders of magnitude in terms of running time. From another perspective, this work exposes some disadvantages of using generic compilers to obtain MPC protocols, as their efficiency always equal that of the worst-case input. Our techniques show that even within the context of MPC, it is possible to obtain a secure protocol whose running time is not fixed a-priori, but instead determined by the output that is not known in advance. By carefully studying the desired functionality, this allows for significant efficiency improvements for any realistic inputs.

We present OasisDB, an oblivious and scalable RDBMS framework designed to securely manage relational data while protecting against access and volume pattern attacks. Inspired by plaintext RDBMSs, OasisDB leverages existing oblivious key value stores (KV-stores) as storage engines and securely scales them to enhance performance. Its novel multi-tier architecture allows for independent scaling of each tier while supporting multi-user environments without compromising privacy. We demonstrate OasisDB's flexibility by deploying it with two distinct oblivious KV-stores, PathORAM and Waffle, and show its capability to execute a variety of SQL queries, including point and range queries, joins, aggregations, and (limited) updates. Experimental evaluations on the Epinions dataset show that OasisDB scales linearly with the number of machines. When deployed with a plaintext KV-store, OasisDB introduces negligible overhead in its multi-tier architecture compared to a plaintext database, CockroachDB. We also compare OasisDB with ObliDB and Obliviator, two oblivious RDBMSs, highlighting its advantages with scalability and multi-user support.

Untrustworthy users can misuse image generators to synthesize high-quality deepfakes and engage in unethical activities. Watermarking deters misuse by marking generated content with a hidden message, enabling its detection using a secret watermarking key. A core security property of watermarking is robustness, which states that an attacker can only evade detection by substantially degrading image quality. Assessing robustness requires designing an adaptive attack for the specific watermarking algorithm. When evaluating watermarking algorithms and their (adaptive) attacks, it is challenging to determine whether an adaptive attack is optimal, i.e., the best possible attack. We solve this problem by defining an objective function and then approach adaptive attacks as an optimization problem. The core idea of our adaptive attacks is to replicate secret watermarking keys locally by creating surrogate keys that are differentiable and can be used to optimize the attack's parameters. We demonstrate for Stable Diffusion models that such an attacker can break all five surveyed watermarking methods at no visible degradation in image quality. Optimizing our attacks is efficient and requires less than 1 GPU hour to reduce the detection accuracy to 6.3% or less. Our findings emphasize the need for more rigorous robustness testing against adaptive, learnable attackers.

Web-scraped datasets are vulnerable to data poisoning, which can be used for backdooring deep image classifiers during training. Since training on large datasets is expensive, a model is trained once and reused many times. Unlike adversarial examples, backdoor attacks often target specific classes rather than any class learned by the model. One might expect that targeting many classes through a naïve composition of attacks vastly increases the number of poison samples. We show this is not necessarily true and more efficient, _universal_ data poisoning attacks exist that allow controlling misclassifications from any source class into any target class with a slight increase in poison samples. Our idea is to generate triggers with salient characteristics that the model can learn. The triggers we craft exploit a phenomenon we call _inter-class poison transferability_, where learning a trigger from one class makes the model more vulnerable to learning triggers for other classes. We demonstrate the effectiveness and robustness of our universal backdoor attacks by controlling models with up to 6,000 classes while poisoning only 0.15% of the training dataset.

Despite several works that succeed in generating synthetic data with differential privacy (DP) guarantees, they are inadequate for generating high-quality synthetic data when the input data has missing values. In this work, we formalize the problems of DP synthetic data with missing values and propose three effective adaptive strategies that significantly improve the utility of the synthetic data on four real-world datasets with different types and levels of missing data and privacy requirements. We also identify the relationship between privacy impact for the complete ground truth data and incomplete data for these DP synthetic data generation algorithms. We model the missing mechanisms as a sampling process to obtain tighter upper bounds for the privacy guarantees to the ground truth data. Overall, this study contributes to a better understanding of the challenges and opportunities for using private synthetic data generation algorithms in the presence of missing data.

Private computation, which includes techniques like multi-party computation and private query execution, holds great promise for enabling organizations to analyze data they and their partners hold while maintaining data subjects' privacy. Despite recent interest in communicating about differential privacy, end users' perspectives on private computation have not previously been studied. To fill this gap, we conducted 22 semi-structured interviews investigating users' understanding of, and expectations for, private computation over data about them. Interviews centered on four concrete data-analysis scenarios (e.g., ad conversion analysis), each with a variant that did not use private computation and another that did. While participants struggled with abstract definitions of private computation, they found the concrete scenarios enlightening and plausible even though we did not explain the complex cryptographic underpinnings. Private computation increased participants' acceptance of data sharing, but not unconditionally; the purpose of data sharing and analysis was the primary driver of their attitudes. Through collective activities, participants emphasized the importance of detailing the purpose of a computation and clarifying that inputs to private computation are not shared across organizations when describing private computation to end users.

As machine learning as a service continues gaining popularity, concerns about privacy and intellectual property arise. Users often hesitate to disclose their private information to obtain a service, while service providers aim to protect their proprietary models. Decision trees, a widely used machine learning model, are favoured for their simplicity, interpretability, and ease of training. In this context, Private Decision Tree Evaluation (PDTE) enables a server holding a private decision tree to provide predictions based on a client's private attributes. The protocol is such that the server learns nothing about the client's private attributes. Similarly, the client learns nothing about the server's model besides the prediction and some hyperparameters.

Training machine learning models on privacy-sensitive data has become a popular practice, driving innovation in ever-expanding fields. This has opened the door to new attacks that can have serious privacy implications. One such attack, the Membership Inference Attack (MIA), exposes whether or not a particular data point was used to train a model. A growing body of literature uses Differentially Private (DP) training algorithms as a defence against such attacks. However, these works evaluate the defence under the restrictive assumption that all members of the training set, as well as non-members, are independent and identically distributed. This assumption does not hold for many real-world use cases in the literature. Motivated by this, we evaluate membership inference with statistical dependencies among samples and explain why DP does not provide meaningful protection (the privacy parameter$\epsilon$scales with the training set size$n$) in this more general case. We conduct a series of empirical evaluations with off-the-shelf MIAs using training sets built from real-world data showing different types of dependencies among samples. Our results reveal that training set dependencies can severely increase the performance of MIAs, and therefore assuming that data samples are statistically independent can significantly underestimate the performance of MIAs.

We introduce and investigate the privacy-preserving version of collaborative data cleaning. With collaborative data cleaning, two parties want to reconcile their data sets to filter out badly classified, misclassified data items. In the privacy-preserving (private) version of data cleaning, the additional security goal is that parties should only learn their misclassified data items, but nothing else about the other party’s data set. The problem of private data cleaning is essentially a variation of private set intersection (PSI), and one could employ recent circuit-PSI techniques to compute misclassifications with privacy. However, we design, analyze, and implement three new protocols tailored to the specifics of private data cleaning that outperform a circuit-PSI-based approach. With the first protocol, we exploit the idea that a small additional leakage (the differentially private size of the intersection of data items) allows for a reduction in complexity over circuit-PSI. The other two protocols convert the problem of finding a mismatch in data classifications into finding a match, and then follow the standard technique of using oblivious pseudorandom functions (OPRF) for computing PSI. Depending on the number of data classes, this leads to a concrete runtime improvement over circuit-PSI.

We introduce and investigate the privacy-preserving version of collaborative data cleaning. With collaborative data cleaning, two parties want to reconcile their data sets to filter out badly classified, misclassified data items. In the privacy-preserving (private) version of data cleaning, the additional security goal is that parties should only learn their misclassified data items, but nothing else about the other party’s data set. The problem of private data cleaning is essentially a variation of private set intersection (PSI), and one could employ recent circuit-PSI techniques to compute misclassifications with privacy. However, we design, analyze, and implement three new protocols tailored to the specifics of private data cleaning that outperform a circuit-PSI-based approach. With the first protocol, we exploit the idea that a small additional leakage (the differentially private size of the intersection of data items) allows for a reduction in complexity over circuit-PSI. The other two protocols convert the problem of finding a mismatch in data classifications into finding a match, and then follow the standard technique of using oblivious pseudorandom functions (OPRF) for computing PSI. Depending on the number of data classes, this leads to a concrete runtime improvement over circuit-PSI.

We present Waffle, a datastore that protects an application's data access patterns from a passive persistent adversary. Waffle achieves this without prior knowledge of the input data access distribution, making it the first of its kind to adaptively handle input sequences under a passive persistent adversary. Waffle maintains a constant bandwidth and client-side storage overhead, which can be adjusted to suit the application owner's preferences. This flexibility allows the owner to fine-tune system parameters and strike a balance between security and performance. Our evaluation, utilizing the Yahoo! Cloud Serving Benchmark (YCSB) benchmark and Redis as the backend storage, demonstrates promising results. The insecure baseline outperforms Waffle by a mere 5-6x, whereas Waffle outperforms Pancake-a state-of-the-art oblivious datastore under passive persistent adversaries-by 45-57%, and a concurrent ORAM system, TaoStore, by 102x.

Multi-party computation (MPC) has been a very active area of research, and recent industrial deployments exist. Practical MPC is currently limited to low-latency, high-throughput network setups, i.e., local-area networks (LAN). However, many use cases require the participation of different entities located in different data centers, i.e., communication over wide-area networks (WAN). Although, constant-round MPC exists, it has very high communication cost. In this paper we investigate the reduction of the round complexity of secret-shared based multi-party computation. We propose a new three-party computation protocol that allows to compute multi-fan-in gates in one round without any precomputation. Our protocol outperforms related work, including constant-round protocols, over WANs. For example, we improve throughput of AES-128 over WAN by a factor of more than 2.2x compared to related work.

The differentially private (DP) selection problem is a fundamental building block in the private literature that is commonly solved with the exponential mechanism. It is well known that efficiency is the major drawback of the exponential mechanism, as the utility function must be computed for all elements in the domain. Genetic algorithms (GAs) use the principles of evolution in nature to efficiently search through large domains and select the best candidate. We observe that GAs have many appealing properties for DP Selection. These include being robust to noisy objectives, placing no restriction on the utility function, and efficient runtime for large domains. However, prior work investigating DP GAs has shown poor utility in practice and often gives the highest utility when zero generations are conducted (indicating that GA operations are not beneficial under DP). This work provides a new DPGA based on the simple GA that addresses the weaknesses of prior solutions. We reduce the destructive nature of previous GA operators and utilize several techniques to reduce the noise from DP. Our modifications allow us to utilize the GA operators over multiple generations (under DP) and improve the GA's overall utility over zero generation techniques. Our work shows that private GAs are competitive with state-of-the-art general and problem-specific solutions to the DP selection problem, with runtime sublinear in the domain size.

Private record linkage (PRL) is the problem of identifying pairs of records that approximately match across datasets in a secure, privacy-preserving manner. Two-party PRL specifically allows each of the parties to obtain records from the other party, only given that each record matches with one of their own. The privacy goal is that no other information about the datasets should be released than the matching records. A fundamental challenge is not to leak information while at the same time not comparing all pairs of records. In plaintext record linkage this is done using a blocking strategy, e.g., locality-sensitive hashing. One recent approach proposed by He et al. (ACM CCS 2017) uses locality-sensitive hashing and then releases a provably differential private representation of the hash bins. However, differential privacy still leaks some, although provable bounded information and does not protect against attacks, such as property inference attacks. Another recent approach by Khurram and Kerschbaum (IEEE ICDE 2020) uses locality-preserving hashing and provides cryptographic security, i.e., it releases no information except the output. However, locality-preserving hash functions are much harder to construct than locality-sensitive hash functions and hence accuracy of this approach is limited, particularly on larger datasets. In this paper, we address the open problem of providing cryptographic security of PRL while using locality-sensitive hash functions. Using recent results in oblivious algorithms, we design a new cryptographically secure PRL with locality-sensitive hash functions. Our prototypical implementation can match 40000 records in the British National Library/Toronto Public Library and the North Carolina Voter Registry datasets with 99.3% and 99.9% accuracy, respectively, in less than an hour which is more than an order of magnitude faster than Khurram and Kerschbaum's work at a higher accuracy.

We consider the problem of a client querying an encrypted binary tree structure, outsourced to an untrusted server. While the server must not learn the contents of the binary tree, we also prevent the client from maliciously crafting a query that traverses the tree out-of-order. That is, the client should not be able to retrieve nodes outside one contiguous path from the root to a leaf. Finally, the server should not learn which path the client accesses, but is guaranteed that the access corresponds to one valid path in the tree. This is an extension of protocols such as structured encryption, where it is only guaranteed that the tree's encrypted data remains hidden from the server.

Key-value data is a naturally occurring data type that has not been thoroughly investigated in the local trust model. Existing local differentially private (LDP) solutions for computing statistics over key-value data suffer from the inherent accuracy limitations of each user adding their own noise. Multi-party computation (MPC) maintains better accuracy than LDP and similarly does not require a trusted central party. However, naively applying MPC to key-value data results in prohibitively expensive computation costs. In this work, we present selective multi-party computation, a novel approach to distributed computation that leverages DP leakage to efficiently and accurately compute statistics over key-value data. By providing each party with a view of a random subset of the data, we can capture subtractive noise. We prove that our protocol satisfies pure DP and is provably secure in the combined DP/MPC model. Our empirical evaluation demonstrates that we can compute statistics over 10,000 keys in 20 seconds and can scale up to 30 servers while obtaining results for a single key in under a second.

Encryption provides a method to protect data out-sourced to a DBMS provider, e.g., in the cloud. However, performing database operations over encrypted data requires specialized encryption schemes that carefully balance security and performance. In this paper, we present a new encryption scheme that can efficiently perform equi-joins over encrypted data using only software and a single server with better security than the state-of-the-art. In particular, our encryption scheme reduces the leakage to equality of rows that match a selection criterion and only reveals the transitive closure of the union of the leakages of each query in a series of queries. Our encryption scheme is provable secure. We implemented our encryption scheme and evaluated it over a dataset from the TPC- H benchmark.

Deep Neural Network (DNN) watermarking is a method for provenance verification of DNN models. Watermarking should be robust against watermark removal attacks that derive a surrogate model that evades provenance verification. Many watermarking schemes that claim robustness have been proposed, but their robustness is only validated in isolation against a relatively small set of attacks. There is no systematic, empirical evaluation of these claims against a common, comprehensive set of removal attacks. This uncertainty about a watermarking scheme’s robustness causes difficulty to trust their deployment in practice. In this paper, we evaluate whether recently proposed watermarking schemes that claim robustness are robust against a large set of removal attacks. We survey methods from the literature that (i) are known removal attacks, (ii) derive surrogate models but have not been evaluated as removal attacks, and (iii) novel removal attacks. Weight shifting and smooth retraining are novel removal attacks adapted to the DNN watermarking schemes surveyed in this paper. We propose taxonomies for watermarking schemes and removal attacks. Our empirical evaluation includes an ablation study over sets of parameters for each attack and watermarking scheme on the image classification datasets CIFAR-10 and ImageNet. Surprisingly, our study shows that none of the surveyed watermarking schemes is robust in practice. We find that schemes fail to withstand adaptive attacks and known methods for deriving surrogate models that have not been evaluated as removal attacks. This points to intrinsic flaws in how robustness is currently evaluated. Our evaluation includes a discussion of the runtime of each attack to underpin their practical relevance. While none of the schemes is robust against all attacks, none of the attacks removes all watermarks. We show that attacks can be combined and find combined attacks that remove all watermarks. We show that watermarking schemes need to be evaluated against a more extensive set of removal attacks with a more realistic adversary model. Our source code and a complete dataset of evaluation results are publicly available, which allows to independently verify our conclusions.

While vast amounts of personal data are shared daily on public online platforms and used by companies and analysts to gain valuable insights, privacy concerns are also on the rise: Modern authorship attribution techniques have proven effective at identifying individuals from their data, such as their writing style or behavior of picking and judging movies. It is hence crucial to develop data sanitization methods that allow sharing of users’ data while protecting their privacy and preserving quality and content of the original data.

It is our great pleasure to introduce

It is our great pleasure to introduce

It is our great pleasure to introduce

Encrypting data before sending it to the cloud ensures data confidentiality but requires the cloud to compute on encrypted data. Trusted execution environments, such as Intel SGX enclaves, promise to provide a secure environment in which data can be decrypted and then processed. However, vulnerabilities in the executed program give attackers ample opportunities to execute arbitrary code inside the enclave. This code can modify the dataflow of the program and leak secrets via SGX side channels. Fully homomorphic encryption would be an alternative to compute on encrypted data without data leaks. However, due to its high computational complexity, its applicability to general-purpose computing remains limited. Researchers have made several proposals for transforming programs to perform encrypted computations on less powerful encryption schemes. Yet current approaches do not support programs making control-flow decisions based on encrypted data. We introduce the concept of dataflow authentication (DFAuth) to enable such programs. DFAuth prevents an adversary from arbitrarily deviating from the dataflow of a program. Our technique hence offers protections against the side-channel attacks described previously. We implemented two flavors of DFAuth, a Java bytecode-to-bytecode compiler, and an SGX enclave running a small and program-independent trusted code base. We applied DFAuth to a neural network performing machine learning on sensitive medical data and a smart charging scheduler for electric vehicles. Our transformation yields a neural network with encrypted weights, which can be evaluated on encrypted inputs in \( 12.55 \,\mathrm{m}\mathrm{s} \) . Our protected scheduler is capable of updating the encrypted charging plan in approximately 1.06 seconds.

Several attacks have shown that the leakage from the access pattern in searchable encryption is dangerous. Attacks exploiting leakage from the query pattern are as dangerous, but less explored. While there are known, lightweight countermeasures to hide information in the access pattern by padding the ciphertexts, the same is not true for the query pattern. Oblivious RAM hides the query patterns, but requires a logarithmic overhead in the size of the database and hence will become even slower as data grows. In this paper we present a query smoothing algorithm to hide the frequency information in the query pattern of searchable encryption schemes by introducing fake queries. Our method only introduces a constant overhead of 7 to 13 fake queries per real query in our experiments. Furthermore, we show that our query smoothing algorithm can also be applied to range-searchable encryption schemes and then prevents all recent plaintext recovery attacks.

Private learning of top-k, i.e., the k most frequent values also called heavy hitters, is a common industry scenario: Companies want to privately learn, e.g., frequently typed new words to improve suggestions on mobile devices, often used browser settings, telemetry data of frequent crashes, heavily shared articles, etc.

Directional data is an important class of data where the magnitudes of the data points are negligible. It naturally occurs in many real-world scenarios: For instance, geographic locations (approximately) lie on a sphere, and periodic data such as time of day, or day of week can be interpreted as points on a circle. Massive amounts of directional data are collected by location-based service platforms such as Google Maps or Foursquare, who depend on mobility data from users' smartphones or wearable devices to enable their analytics and marketing businesses. However, such data is often highly privacy-sensitive and hence demands measures to protect the privacy of the individuals whose data is collected and processed. Starting with the von Mises-Fisher distribution, we therefore propose and analyze two novel privacy mechanisms for directional data by combining directional statistics with differential privacy, which presents the current state-of-the-art for quantifying and limiting information disclosure about individuals. As we will see, our specialized privacy mechanisms achieve a better privacy-utility trade-off than ex post adaptions of established mechanisms to directional data.

Data confidentiality is an important requirement for clients when outsourcing databases to the cloud. Trusted execution environments, such as Intel SGX, offer an efficient solution to this confidentiality problem. However, existing TEE-based solutions are not optimized for column-oriented, in-memory databases and pose impractical memory requirements on the enclave. We present EncDBDB, a novel approach for client-controlled encryption of a column-oriented, in-memory databases allowing range searches using an enclave. EncDBDB offers nine encrypted dictionaries, which provide different security, performance, and storage efficiency tradeoffs for the data. It is especially suited for complex, read-oriented, analytic queries as present, e.g., in data warehouses. The computational overhead compared to plaintext processing is within a millisecond even for databases with millions of entries and the leakage is limited. Compressed encrypted data requires less space than a corresponding plaintext column. Furthermore, EncDBDB's enclave is very small reducing the potential for security-relevant implementation errors and side-channel leakages.

Watermarking algorithms have been introduced in the past years to protect deep learning models against unauthorized re-distribution. We investigate the robustness and reliability of state-of-the-art deep neural network watermarking schemes. We focus on backdoor-based watermarking and propose two simple yet effective attacks -- a black-box and a white-box -- that remove these watermarks without any labeled data from the ground truth. Our black-box attack steals the model and removes the watermark with only API access to the labels. Our white-box attack proposes an efficient watermark removal when the parameters of the marked model are accessible, and improves the time to steal a model up to twenty times over the time to train a model from scratch. We conclude that these watermarking algorithms are insufficient to defend against redistribution by a motivated attacker.

Outlier detection plays a significant role in various real world applications such as intrusion, malfunction, and fraud detection. Traditionally, outlier detection techniques are applied to find outliers in the context of the whole dataset. However, this practice neglects the data points, namely contextual outliers, that are not outliers in the whole dataset but in some specific neighborhoods. Contextual outliers are particularly important in data exploration and targeted anomaly explanation and diagnosis. In these scenarios, the data owner computes the following information: i) The attributes that contribute to the abnormality of an outlier (metric), ii) Contextual description of the outlier's neighborhoods (context), and iii) The utility score of the context, e.g. its strength in showing the outlier's significance, or in relation to a particular explanation for the outlier. However, revealing the outlier's context leaks information about the other individuals in the population as well, violating their privacy. We address the issue of population privacy violations in this paper. There are two main challenges in defining and applying privacy in contextual outlier release. In this setting, the data owner is required to release a valid context for the queried record, i.e. a context in which the record is an outlier. Hence, the first major challenge is that the privacy technique must preserve the validity of the context for each record. We propose techniques to protect the privacy of individuals through a relaxed notion of differential privacy to satisfy this requirement. The second major challenge is applying the proposed techniques efficiently, as they impose intensive computation to the base algorithm. To overcome this challenge, we propose a graph structure to map the contexts to, and introduce differentially private graph search algorithms as efficient solutions for the computation problem caused by differential privacy techniques.

Watermarking of deep neural networks (DNN) can enable their tracing once released by a data owner to an online platform. In this paper, we generalize white-box watermarking algorithms for DNNs, where the data owner needs white-box access to the model to extract the watermark. White-box watermarking algorithms have the advantage that they do not impact the accuracy of the watermarked model. We propose Robust whIte-box GAn watermarking (RIGA), a novel white-box watermarking algorithm that uses adversarial training. Our extensive experiments demonstrate that the proposed watermarking algorithm not only does not impact accuracy, but also significantly improves the covertness and robustness over the current state-of-art.

Differential privacy allows bounding the influence that training data records have on a machine learning model. To use differential privacy in machine learning, data scientists must choose privacy parameters (ϵ, δ ). Choosing meaningful privacy parameters is key, since models trained with weak privacy parameters might result in excessive privacy leakage, while strong privacy parameters might overly degrade model utility. However, privacy parameter values are difficult to choose for two main reasons. First, the theoretical upper bound on privacy loss (ϵ, δ) might be loose, depending on the chosen sensitivity and data distribution of practical datasets. Second, legal requirements and societal norms for anonymization often refer to individual identifiability, to which (ϵ, δ ) are only indirectly related. We transform (ϵ, δ ) to a bound on the Bayesian posterior belief of the adversary assumed by differential privacy concerning the presence of any record in the training dataset. The bound holds for multidimensional queries under composition, and we show that it can be tight in practice. Furthermore, we derive an identifiability bound, which relates the adversary assumed in differential privacy to previous work on membership inference adversaries. We formulate an implementation of this differential privacy adversary that allows data scientists to audit model training and compute empirical identifiability scores and empirical (ϵ, δ ).

Over-Threshold Multi-Party Private Set Intersection (OT-MP-PSI) is the problem where several parties, each holding a set of elements, want to know which elements appear in at least t sets, for a certain threshold t, without revealing any information about elements that do not meet this threshold. This problem has many practical applications, but current solutions require a number of expensive operations exponential in t and thus are impractical.

We focus on securely computing the ranks of sealed integers distributed among n parties. For example, we securely compute the largest or smallest integer, the median, or in general the kth-ranked integer. Such computations are a useful building block to securely implement a variety of sealed-bid auctions. Our objective is efficiency, specifically low interactivity between parties to support blockchains or other scenarios where multiple rounds are time-consuming. Hence, we dismiss powerful, yet highly-interactive MPC frameworks and propose BOREALIS, a special-purpose protocol for secure computation of ranks among integers. BOREALIS uses additively homomorphic encryption to implement core comparisons, but computes under distinct keys, chosen by each party to optimize the number of rounds. By carefully combining cryptographic primitives, such as ECC Elgamal encryption, encrypted comparisons, ciphertext blinding, secret sharing, and shuffling, BOREALIS sets up systems of multi-scalar equations which we efficiently prove with Groth-Sahai ZK proofs. Therewith, BOREALIS implements a multi-party computation of pairwise comparisons and rank zero-knowledge proofs secure against malicious adversaries. BOREALIS completes in at most 4 rounds which is constant in both bit length l of integers and the number of parties n. This is not only asymptotically optimal, but surpasses generic constant-round secure multi-party computation protocols, even those based on shared-key fully homomorphic encryption. Furthermore, our implementation shows that BOREALIS is very practical. Its main bottleneck, ZK proof computations, is small in practice. Even for a large number of parties (n=200) and high-precision integers (l=32), computation time of all proofs is less than a single Bitcoin block interval.

Order-preserving encryption (OPE) allows encrypting data, while still enabling efficient range queries on the encrypted data. Moreover, it does not require any change to the database management system, which makes OPE schemes very suitable for data outsourcing with threats from weak adversaries. However, all OPE schemes are necessarily symmetric limiting the use case to one client and one server. Imagine a scenario where a Data Owner (DO) outsources encrypted data to the Cloud Service Provider (CSP) and a Data Analyst (DA) wants to execute private range queries on this data. Then either the DO must reveal its encryption key or the DA must reveal the private queries. In this paper, we overcome this limitation by allowing the equivalent of a public-key OPE. We present a secure multiparty protocol that enables secure range queries for multiple users. In this scheme, the DA cooperates with the DO and the CSP in order to order-preserving encrypt the private range queries without revealing any other information to the parties. The basic idea of our scheme is to replace encryption with a secure, interactive protocol. In this protocol, we combine OPE based on binary search trees with homomorphic encryption and garbled circuits (GC) achieving security against passive adversaries with sublinear communication and computation complexity. We apply our construction to different OPE schemes including frequency-hiding OPE and OPE based on an efficiently searchable encrypted data structure which can withstand many of the popularized attacks on OPE. We implemented our scheme and observed that if the database size of the DO has 1 million entries it takes only about 0.3 s on average via a loopback interface (1.3 s via a LAN and 15.6 s via a WAN with about 200 ms round-trip time) to encrypt an input of the DA. Moreover, while the related work has an overhead of 10 to 100 seconds compared to a plaintext MySQL range query on a database with 10 million entries, our scheme has an overhead of only 360 milliseconds.

This work considers the trade-off between security and performance when revealing partial information about encrypted data computed on. The focus of our work is on information revealed through control flow side-channels when executing programs on encrypted data. We use quantitative information flow to measure security, running time to measure performance and program transformation techniques to alter the trade-off between the two. Combined with information flow policies, we perform a policy-aware security and performance trade-off (PASAPTO) analysis. We formalize the problem of PASAPTO analysis as an optimization problem, prove the NP-hardness of the corresponding decision problem and present two algorithms solving it heuristically. We implemented our algorithms and combined them with the Dataflow Authentication (DFAuth) approach for outsourcing sensitive computations. Our DFAuth Trade-off Analyzer (DFATA) takes Java Bytecode operating on plaintext data and an associated information flow policy as input. It outputs semantically equivalent program variants operating on encrypted data which are policy-compliant and approximately Pareto-optimal with respect to leakage and performance. We evaluated DFATA in a commercial cloud environment using Java programs, e.g., a decision tree program performing machine learning on medical data. The decision tree variant with the worst performance is 357% slower than the fastest variant. Leakage varies between 0% and 17% of the input.

File sharing applications using cloud storage are increasingly popular for personal and business use. Due to data protection concerns, end-to-end encryption is often a desired feature of these applications. Many attempts at designing cryptographic solutions fail to be adopted due to missing relevant features. We present SeGShare, a new architecture for end-to-end encrypted, group-based file sharing using trusted execution environments (TEE), e.g., Intel SGX. SeGShare is the first solution to protect the confidentiality and integrity of all data and management files; enforce immediate permission and membership revocations; support deduplication; and mitigate rollback attacks. Next to authentication, authorization and file system management, our implementation features an optimized TLS layer that enables high throughput and low latency. The encryption overhead of our implementation is extremely small in computation and storage resources. Our enclave code comprises less than 8500 lines of code enabling efficient mitigation of common pitfalls in deploying code to TEEs.

Private set intersection (PSI) allows two parties to compute the intersection of their data without revealing the data they possess that is outside of the intersection. However, in many cases of joint data analysis, the intersection is also sensitive. We define differentially private set intersection and we propose new protocols using (leveled) homomorphic encryption where the result is differentially private. Our circuit-based approach has an adaptability that allows us to achieve differential privacy, as well as to compute predicates over the intersection such as cardinality. Furthermore, our protocol produces differentially private output for set intersection and set intersection cardinality that is optimal in terms of communication and computation complexity. For a client set of size$m$and a server set of size$n$, where$m$is smaller than$n$, our communication complexity is$O(m)$while previous circuit-based protocols only achieve$O(n+m)$communication complexity. In addition to our asymptotic optimizations which include new analysis for using nested cuckoo hashing for PSI, we demonstrate the practicality of our protocol through an implementation that shows the feasibility of computing the differentially private intersection for large data sets containing millions of elements.

The prevalence of various (and increasingly large) datasets presents the challenging problem of discovering common entities dispersed across disparate datasets. Solutions to the private record linkage problem (PRL) aim to enable such explorations of datasets in a secure manner. A two-party PRL protocol allows two parties to determine for which entities they each possess a record (either an exact matching record or a fuzzy matching record) in their respective datasets - without revealing to one another information about any entities for which they do not both possess records. Although several solutions have been proposed to solve the PRL problem, no current solution offers a fully cryptographic security guarantee while maintaining both high accuracy of output and subquadratic runtime efficiency. To this end, we propose the first known efficient PRL protocol that runs in subquadratic time, provides high accuracy, and guarantees cryptographic security in the semi-honest security model.

Encryption can protect data in outsourced databases -- in the cloud -- while still enabling query processing over the encrypted data. However, the processing leaks information about the data specific to the type of query, e.g., aggregation queries. Aggregation over user-defined groups using SQL's GROUP BY clause is extensively used in data analytics, e.g., to calculate the total number of visitors each month or the average salary in each department. The information leaked, e.g., the access pattern to a group, may reveal the group's frequency enabling simple, yet detrimental leakage-abuse attacks. In this work we present SAGMA -- an encryption scheme for performing secure aggregation grouped by multiple attributes. The querier can choose any combination of one or multiple attributes in the GROUP BY clause among the set of all grouping attributes. The encryption scheme only stores semantically secure ciphertexts at the cloud and query processing hides the access pattern, i.e., the frequency of each group. We implemented our scheme and our evaluation results underpin its practical feasibility.

Abstract Encrypting data before sending it to the cloud protects it against attackers, but requires the cloud to compute on encrypted data. Trusted modules, such as SGX enclaves, promise to provide a secure environment in which data can be decrypted and then processed. However, vulnerabilities in the executed program, which becomes part of the trusted code base (TCB), give attackers ample opportunity to execute arbitrary code inside the enclave. This code can modify the dataflow of the program and leak secrets via SGX side-channels. Since any larger code base is rife with vulnerabilities, it is not a good idea to outsource entire programs to SGX enclaves. A secure alternative relying solely on cryptography would be fully homomorphic encryption. However, due to its high computational complexity it is unlikely to be adopted in the near future. Researchers have made several proposals for transforming programs to perform encrypted computations on less powerful encryption schemes. Yet current approaches do not support programs making control-flow decisions based on encrypted data. We introduce the concept of dataflow authentication (DFAuth) to enable such programs. DFAuth prevents an adversary from arbitrarily deviating from the dataflow of a program. Our technique hence offers protections against the side-channel attacks described above. We implemented DFAuth using a novel authenticated homomorphic encryption scheme, a Java bytecode-tobytecode compiler producing fully executable programs, and an SGX enclave running a small and program-independent TCB. We applied DFAuth to an existing neural network that performs machine learning on sensitive medical data. The transformation yields a neural network with encrypted weights, which can be evaluated on encrypted inputs in 0.86 s.

Abstract Secret sharing schemes are desirable across a variety of real-world settings due to the security and privacy properties they can provide, such as availability and separation of privilege. However, transitioning secret sharing schemes from theoretical research to practical use must account for gaps in achieving these properties that arise due to the realities of concrete implementations, threat models, and use cases. We present a formalization and analysis, using Ellison’s notion of ceremonies, that demonstrates how simple variations in use cases of secret sharing schemes result in the potential loss of some security properties, a result that cannot be derived from the analysis of the underlying cryptographic protocol alone. Our framework accounts for such variations in the design and analysis of secret sharing implementations by presenting a more detailed user-focused process and defining previously overlooked assumptions about user roles and actions within the scheme to support analysis when designing such ceremonies. We identify existing mechanisms that, when applied to an appropriate implementation, close the security gaps we identified. We present our implementation including these mechanisms and a corresponding security assessment using our framework.

Training deep neural networks is a computationally expensive task. Furthermore, models are often derived from proprietary datasets that have been carefully prepared and labelled. Hence, creators of deep learning models want to protect their models against intellectual property theft. However, this is not always possible, since the model may, e.g., be embedded in a mobile app for fast response times. As a countermeasure watermarks for deep neural networks have been developed that embed secret information into the model. This information can later be retrieved by the creator to prove ownership. Uchida et al. proposed the first such watermarking method. The advantage of their scheme is that it does not compromise the accuracy of the model prediction. However, in this paper we show that their technique modifies the statistical distribution of the model. Using this modification we can not only detect the presence of a watermark, but even derive its embedding length and use this information to remove the watermark by overwriting it. We show analytically that our detection algorithm follows consequentially from their embedding algorithm and propose a possible countermeasure. Our findings shall help to refine the definition of undetectability of watermarks for deep neural networks.

Performing joins over encrypted data is particularly challenging, since the query result or access pattern of 1 : n-joins reveals the frequency of each distinct element in the column. This frequency information is used in many easy, but very detrimental inference attacks. In this paper we present a different approach: Instead of implementing a stand-alone join operator that reveals the frequency of each element in the column, we show how to construct joins over encrypted data after selection operations have been applied. These joins only leak the fine granular access pattern and frequency of elements selected for the join. Our new fine-granularly secure joins use searchable encryption and key-policy attribute-based encryption and support dynamically adding and removing database rows. Their performance is practical and we present an implementation in MySQL.

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.

Data profiling is an important task to understand data semantics and is an essential pre-processing step in many tools. Due to privacy constraints, data is often partitioned into silos, with different access control. Discovering functional dependencies (FDs) usually requires access to all data partitions to find constraints that hold on the whole dataset. Simply applying general secure multi-party computation protocols incurs high computation and communication cost. This paper formulates the FD discovery problem in the secure multi-party scenario. We propose secure constructions for validating candidate FDs, and present efficient cryptographic protocols to discover FDs over distributed partitions. Experimental results show that solution is practically efficient over non-secure distributed FD discovery, and can significantly outperform general purpose multi-party computation frameworks. To the best of our knowledge, our work is the first one to tackle this problem.

Text mining and information retrieval techniques have been developed to assist us with analyzing, organizing and retrieving documents with the help of computers. In many cases, it is desirable that the authors of such documents remain anonymous: Search logs can reveal sensitive details about a user, critical articles or messages about a company or government might have severe or fatal consequences for a critic, and negative feedback in customer surveys might negatively impact business relations if they are identified. Simply removing personally identifying information from a document is, however, insufficient to protect the writer's identity: Given some reference texts of suspect authors, so-called authorship attribution methods can reidentfy the author from the text itself. One of the most prominent models to represent documents in many common text mining and information retrieval tasks is the vector space model where each document is represented as a vector, typically containing its term frequencies or related quantities. We therefore propose an automated text anonymization approach that produces synthetic term frequency vectors for the input documents that can be used in lieu of the original vectors. We evaluate our method on an exemplary text classification task and demonstrate that it only has a low impact on its accuracy. In contrast, we show that our method strongly affects authorship attribution techniques to the level that they become infeasible with a much stronger decline in accuracy. Other than previous authorship obfuscation methods, our approach is the first that fulfills differential privacy and hence comes with a provable plausible deniability guarantee.

In this paper we address the problem of outsourcing sensitive strings while still providing the functionality of substring searches. While security is one important aspect that requires careful system design, the practical application of the solution depends on feasible processing time and integration efforts into existing systems. That is, searchable symmetric encryption (SSE) allows queries on encrypted data but makes common indexing techniques used in database management systems for fast query processing impossible. As a result, the overhead for deploying such functional and secure encryption schemes into database systems while maintaining acceptable processing time requires carefully designed special purpose index structures. Such structures are not available on common database systems but require individual modifications depending on the deployed SSE scheme.

Software-based approaches for search over encrypted data are still either challenged by lack of proper, low-leakage encryption or slow performance. Existing hardware-based approaches do not scale well due to hardware limitations and software designs that are not specifically tailored to the hardware architecture, and are rarely well analyzed for their security (e.g. the impact of side channels). Additionally, existing hardware-based solutions often have a large code footprint in the trusted environment susceptible to software compromises. In this paper we present HardIDX: a hardware-based approach, leveraging Intel’s SGX, for search over encrypted data. It implements only the security critical core, i.e., the search functionality, in the trusted environment and resorts to untrusted software for the remainder. HardIDX is deployable as a highly performant encrypted database index: it is logarithmic in the size of the index and searches are performed within a few milliseconds rather than seconds. We formally model and prove the security of our scheme showing that its leakage is equivalent to the best known searchable encryption schemes. Our implementation has a very small code and memory footprint yet still scales to virtually unlimited search index sizes, i.e., size is limited only by the general – non-secure – hardware resources.

The rapid advances in technology can be witnessed in the emergence of cyber-physical systems that pertain to several domains of our society. In transportation, we see the emergence of self-driving vehicles that utilize a multitude of sensors and intelligent learning techniques to navigate autonomously. Such vehicles are complex cyber-physical systems that are mobile and due to their sensor and intrinsic intelligence are able to collect, analyze, and capitalize upon an unprecedented amount of fine-grained data, as well as collaborate in real time with multiple stakeholders. Although such rich data can play a key role in data-driven economies of scale, this raises questions with respect to privacy- and integrity-dependent scenarios. In this work, the feasibility of ensuring integrity, and hence safety, while preserving privacy in the emerging hyperconnected vehicle scenarios is discussed. An exemplary case study on real-time vehicle interactions pertaining to map updates exemplifies the combination of privacy-enhancing technologies with integrity-protecting mechanisms.

The objective of the 3rd ACM Workshop on Information Sharing and Collaborative Security is to advance the scientific foundations for sharing security-related data. Improving information sharing remains an important theme in the computer security community. A number of new sharing communities have been formed. Also, so called "threat intelligence" originating from open, commercial or governmental sources has by now become an important, commonly used tool for detecting and mitigating attacks in organizations. Security vendors are offering novel technologies for sharing, managing and consuming such data. The OASIS Technical Committee for Cyber Threat Intelligence (CTI) is creating a standard for structured sharing of information. This is the largest TC within OASIS attesting to the broad interest in the topic. As progress in real-life deployment of information sharing makes clear, the creation, analysis, sharing, and effective use of security data continues to raise intriguing technical problems. Addressing these problems will be critical for the ultimate success of sharing efforts and will benefit greatly from the diverse knowledge and techniques the scientific community brings. The 3rd ACM Workshop on Information Sharing and Collaborative Security (WISCS'16) brings together experts and practitioners from academia, industry, and government to present innovative research, case studies, and legal and policy issues. WISCS'16 is held in Vienna, Austria on October 24, 2016 in conjunction with the 23rd ACM Conference on Computer and Communications Security (ACM CCS 2016).

Order-preserving encryption allows encrypting data, while still enabling efficient range queries on the encrypted data. This makes its performance and functionality very suitable for data outsourcing in cloud computing scenarios, but the security of order-preserving is still debatable. We present a scheme that achieves a strictly stronger notion of security than any other scheme so far. The basic idea is to randomize the ciphertexts to hide the frequency of plaintexts. Still, the client storage size remains small, in our experiments up to 1/15 of the plaintext size. As a result, one can more securely outsource large data sets, since we can also show that our security increases with larger data sets.

Notwithstanding the latest buzzwords (grid, cloud, utility computing, SaaS, etc.), large-scale computing and cloud-like deployment are the fastest growing computing infrastructures today. How exactly they will look like tomorrow is still for the markets to decide, yet one thing has already been identified: clouds have new, untested deployment, associated adversarial models and vulnerabilities and hence a very different threat landscape. It is essential that our community becomes involved in shaping the future security of cloud computing. The CCSW workshop aims to bring together researchers and practitioners in all security and privacy aspects of cloud-centric and outsourced computing.

Proofs-of-Retrievability enables a client to store his data on a cloud server so that he executes an efficient auditing protocol to check that the server possesses all of his data in the future. During an audit, the server must maintain full knowledge of the client’s data to pass, even though only a few blocks of the data need to be accessed. Since the first work by Juels and Kaliski, many PoR schemes have been proposed and some of them can support dynamic updates. However, all the existing works that achieve public verifiability are built upon traditional public-key cryptosystems which imposes a relatively high computational burden on low-power clients (e.g., mobile devices). In this work we explore indistinguishability obfuscation for building a Proof-of-Retrievability scheme that provides public verification while the encryption is based on symmetric key primitives. The resulting scheme offers light-weight storing and proving at the expense of longer verification. This could be useful in apations where outsourcing files is usually done by low-power client and verifications can be done by well equipped machines (e.g., a third party server). We also show that the proposed scheme can support dynamic updates. At last, for better assessing our proposed scheme, we give a performance analysis of our scheme and a comparison with several other existing schemes which demonstrates that our scheme achieves better performance on the data owner side and the server side.

A data owner outsourcing the database of a multi user application wants to prevent information leaks caused by outside attackers exploiting software vulnerabilities or by curious personnel. Query processing over encrypted data solves this problem for a single user, but provides only limited functionality in the face of access restrictions for multiple users and keys. ENKI is a system for securely executing queries over sensitive, access restricted data on an outsourced database. It introduces an encryption based access control model and techniques for query execution over encrypted, access restricted data on the database with only a few cases requiring computations on the client. A prototype of ENKI supports all queries seen in three real world use cases and executes queries from TPC-C benchmark with a modest overhead compared to the single user mode.

Searchable (symmetric) encryption allows encryption while still enabling search for keywords. Its immediate application is cloud storage where a client outsources its files while the (cloud) service provider should search and selectively retrieve those. Searchable encryption is an active area of research and a number of schemes with different efficiency and security characteristics have been proposed in the literature. Any scheme for practical adoption should be efficient -- i.e. have sub-linear search time --, dynamic -- i.e. allow updates -- and semantically secure to the most possible extent. Unfortunately, efficient, dynamic searchable encryption schemes suffer from various drawbacks. Either they deteriorate from semantic security to the security of deterministic encryption under updates, they require to store information on the client and for deleted files and keywords or they have very large index sizes. All of this is a problem, since we can expect the majority of data to be later added or changed. Since these schemes are also less efficient than deterministic encryption, they are currently an unfavorable choice for encryption in the cloud. In this paper we present the first searchable encryption scheme whose updates leak no more information than the access pattern, that still has asymptotically optimal search time, linear, very small and asymptotically optimal index size and can be implemented without storage on the client (except the key). Our construction is based on the novel idea of learning the index for efficient access from the access pattern itself. Furthermore, we implement our system and show that it is highly efficient for cloud storage.

Customers of cloud service demand control over their data. Next to threats to intellectual property, legal requirements and risks, such as data protection compliance or the possibility of a subpoena of the cloud service provider, also pose restrictions. A commonly proposed and implemented solution is to encrypt the data on the client and retain the key at the client. In this tutorial we will review: - the available encryption methods, such deterministic, order-preserving, homomorphic, searchable (functional) encryption and secure multi-party computation, - possible attacks on currently deployed systems like dictionary and frequency attacks, - architectures integrating these solutions into SaaS and PaaS (DBaaS) applications.

Order-preserving encryption enables performing many classes of queries -- including range queries -- on encrypted databases. Popa et al. recently presented an ideal-secure order-preserving encryption (or encoding) scheme, but their cost of insertions (encryption) is very high. In this paper we present an also ideal-secure, but significantly more efficient order-preserving encryption scheme. Our scheme is inspired by Reed's referenced work on the average height of random binary search trees. We show that our scheme improves the average communication complexity from O(n log n) to O(n) under uniform distribution. Our scheme also integrates efficiently with adjustable encryption as used in CryptDB. In our experiments for database inserts we achieve a performance increase of up to 81% in LANs and 95% in WANs.

We are seeing a significant shift in the types and characteristics of computing devices that are commonly used. Today, more smartphones are sold than personal computers. An area of rapid growth are also cloud systems; and our everyday lives are invaded by sensors like smart meters and electronic tickets. The days when most computing resources were managed directly by a computer's operating system are over---data and computation is distributed, and devices are typically always connected via the Internet.

Recent advances in encrypted outsourced databases support the direct processing of queries on encrypted data. Depend- ing on functionality (i.e. operators) required in the queries the database has to use different encryption schemes with different security properties. Next to these functional re-quirements a security administrator may have to address security policies that may equally determine the used en-cryption schemes. We present an algorithm and tool set that determines an optimal balance between security and functionality as well as helps to identify and resolve possible conflicts. We test our solution on a database benchmark and business-driven security policies.

While performing pure e-business transactions such as purchasing software or music, customers can act anonymously supported by, e.g., anonymous communication protocols and anonymous payment protocols. However, it is hard to establish trust relations among anonymously acting business partners. Anonymous reputation systems have been proposed to mitigate this problem. Schiffner et al. recently proved that there is a conflict between anonymity and reputation and they established the non-existence of certain privacy-preserving reputation functions. In this paper we argue that this relationship is even more intricate. First, we present a reputation function that deanonymizes the user, yet provides strong anonymity (SA) according to their definitions. However, this reputation function has no utility, i.e., the submitted ratings have no influence on the resulting reputation values. Second, we show that a reputation function having utility requires the system to choose new independently at random selected pseudonyms (for all users it has utility for) on every new rating as a necessary condition to provide strong anonymity according to the aforementioned definition. Since some persistence of pseudonyms is favorable, we present a more secure, but also more usable definition for anonymous reputation systems that allows persistency yet guaranties k-anonymity. We further present a definition for rating secrecy based on a threshold. Finally, we propose a practical reputation function, for which we prove that it satisfies these definitions.

Zero-knowledge protocols are one of the fundamental concepts in modern cryptography and have countless applications. However, after more than 30 years from their introduction, there are only very few languages (essentially those with a group structure) for which we can construct zero-knowledge protocols that are efficient enough to be used in practice.

There are a number of domain-specific programming languages for secure computation. Out of those, the ones that are based on generic programming languages support mixing different protocol primitives and enable implementing a wider, possibly more efficient range of protocols. On the one hand, this may result in better protocol performance. On the other hand, this may lead to insecure protocols. In this paper we present a security type system that enables mixing protocol primitives in a generic programming language, but also ensures that well-typed programs are secure in the semi-honest model. Consequently, a compiled protocol must be secure. We show an extension of the L1 language with our security type system and evaluate the implementation of two protocols from the literature. This shows that our type system supports the provably secure implementation even of complex protocols.

Recent databases are implemented as in-memory column-stores. Adjustable encryption offers a solution to encrypted database processing in the cloud. We show that the two technologies play well together by providing an analysis and prototype results that demonstrate the impact of mechanisms at the database side (dictionaries and their compression) and cryptographic mechanisms at the adjustable encryption side (order-preserving, homomorphic, deterministic and probabilistic encryption).

In theory secure computation offers a solution for privacy in many collaborative applications. However, in practice poor efficiency of the protocols prevents their use. Hand-crafted protocols are more efficient than those implemented in compilers, but they require significantly more development effort in programming and verification. Recently, Kerschbaum introduced an automatic compiler optimization technique for secure computations that can make compilers as efficient as hand-crafted protocols. This optimization relies on the structure of the secure computation program. The programmer has to implement the program in such a way, such that the optimization can yield the optimal performance. In this paper we present an algorithm that rewrites the program -- most notably its expressions -- optimizing their efficiency in secure computation protocols. We give a heuristic for whole-program optimization and show the resulting performance gains using examples from the literature.

Security is still a major inhibitor of cloud computing. When companies are testing cloud applications, e.g. for storage or databases, they use generated data for fear of data loss. Modern encrypted databases where the cryptographic key remains at the client provide a solution to this problem. Recent results in cryptography, such order-preserving encryption, and database systems enable the practical use of these systems. We report on our pre-development efforts of implementing such an encrypted database in an in-memory, column store database. We highlight some unsolved research challenges: such as access control, infrequent queries and security vs. performance query optimization. Challenges to key management in multi-user environments remain largely unsolved. We give an overview of the architecture and performance benchmarks on our prototype which are very encouraging for practical adoption.

Benchmarking is the comparison of one company's key performance indicators (KPI) to the statistics of the same KPIs of its peer group. A KPI is a statistical quantity measuring the performance of a business process. Privacy by means of controlling access to data is of the utmost importance in benchmarking. Companies are reluctant to share their business performance data due to the risk of losing a competitive advantage or being embarrassed. We present a cryptographic protocol for securely computing benchmarks between multiple parties and describe the technical aspects of a proof of concept implementation of SAP's research prototype Global Benchmarking Service (GBS) on Microsoft's cloud technology Windows Azure.

Private set intersection enables two parties -- a client and a server -- to compute the intersection of their respective sets without disclosing anything else. It is a fundamental operation -- equivalent to a secure, distributed database join -- and has many applications particularly in privacy-preserving law enforcement. In this paper we present a novel protocol that has linear complexity, is secure in the malicious model without random oracles, is client set size-independent and efficient. Furthermore, the computation of the intersection can be outsourced to an oblivious service provider, as in secure cloud computing. We leverage a completely novel construction for computing the intersection using Bloom filter and homomorphic encryption. For outsourcing we require and introduce a new homomorphic encryption scheme which may be of independent interest.

Companies can optimize their supply chain if they exchange item-level data, i.e. item-specific data gathered with the help of Radio Frequency Identification or 2D bar codes. Data can either be distributed over the repositories of each company or stored in a central repository. The distributed approach requires "discovering" the repositories which contain data about the queried item. Thus, data access is slow. The central approach does not require discovery, but the data owner has to relinquish access control to the repository provider. Both approaches are not satisfactory. In this paper we present an encryption scheme for exchanging item-level data by storing it in a central repository. It allows the data owner to enforce access control on an item-level by managing the corresponding keys. Furthermore, data remains confidential even against the repository provider. Thus we eliminate the main problem of the central approach. We provide formal proofs that the proposed encryption scheme is secure. Then, we evaluate the encryption scheme with databases containing up to 50 million tuples. Results show that the encryption scheme is fast, scalable and that it can be parallelized very efficiently. Our encryption scheme thereby reconciles the conflict between security and performance in item-level data repositories.

In this demonstration we present a novel encryption scheme for enforcing access control in a Discovery Service. A Discovery Service is a piece of software that allows one to "discover" item-level data which is stored in data repositories of different companies. Such data can be gathered with the help of Radio Frequency Identification or 2D bar codes. Our software allows the data owner to enforce access control on an item-level by managing the corresponding keys. Data remains confidential even against the provider of the Discovery Service. We present three ways of querying data and evaluate them with databases containing up to 50 million tuples.

Interorganizational workflow systems play a fundamental role in business partnerships. We introduce and investigate the concept of workflow signatures. Not only can these signatures be used to ensure authenticity and protect integrity of workflow data, but also to prove the sequence and logical relationships, such as AND-join and AND-split, of a workflow. Hence, workflow signatures can be electronic evidence useful for auditing, that is proving compliance of business processes against some regulatory requirements. Furthermore, signing keys can be used to grant permissions to perform tasks. Since the signing keys are issued on-the-fly, authorization to execute a task within a workflow can be controlled and granted dynamically at runtime. In this paper, we propose a concrete workflow signature scheme, which is based on hierarchical identity-based cryptography, to meet security properties required by interorganizational workflows.

Companies can optimize their supply chain if they exchange item-level data, i.e. specific data about each item gathered with the help of Radio Frequency Identification or 2D bar codes. However, business critical information might be inferred from this data, e.g. strategic relations or best practices. Therefore, companies are reluctant to share item-level data. In this paper we discuss requirements for an encryption scheme for exchanging item-level data by storing it in a cloud-based data repository. We envision a system that allows the data owner to enforce access control on an item-level. And data should remain confidential even against the cloud service provider.

On the one hand, compilers for secure computation protocols, such as FairPlay or FairPlayMP, have significantly simplified the development of such protocols. On the other hand, optimized protocols with high performance for special problems demand manual development and security verification. The question considered in this paper is: Can we construct a compiler that produces optimized protocols? We present an optimization technique based on logic inference about what is known from input and output. Using the example of median computation we can show that our program analysis and rewriting technique translates a FairPlay program into an equivalent -- in functionality and security -- program that corresponds to the protocol by Aggarwal et al. Nevertheless our technique is general and can be applied to optimize a wide variety of secure computation protocols.

In this paper, we study methods for improving the utility and privacy of reputation scores for online auctions, such as used in eBay, so as to reduce the effectiveness of feedback extortion. The main idea behind our techniques is to escrow reputations scores until appropriate external events occur. Depending on the degree of utility and privacy needed, these external techniques could depend on the number and type of reputation scores collected. Moreover, if additional privacy protection is needed, then random sampling can be used with respect reputation scores in such a way that reputation aggregates remain useful, but individual reputation scores are probabilistically hidden from users. Finally, we show that if privacy is also desired with respect to the the reputation aggregator, then we can use zero-knowledge proofs for reputation comparisons.

Secure Computation (SC) enables secure distributed computation of arbitrary functions of private inputs. It has many useful applications, e.g. benchmarking or auctions. Several general protocols for SC have been proposed and recently been implemented in a number of compilers and frameworks. These compilers or frameworks implement one general SC protocol and then require the programmer to implement the function he wants the protocol to compute. Performance remains a challenge for this approach and it has been realized early on that special protocols for important problems can deliver superior performance. In this paper we propose a new intermediate language (L1) for optimizing SC compilers which enables efficient implementation of special protocols potentially mixing several general SC protocols. We show by three case studies - one for computation of the median, one for weighted average, one for division - that special protocols and mixed-protocol implementations in our language L1 can lead to superior performance. Moreover, we show that only a combined view on algorithm and cryptographic protocol can discover SCs with best run-time performance.

In composite web services one can only either hide the identities of the participants or provide end-to-end confidentiality via encryption. For a designer of inter-organizational business processes this implies that she either needs to reveal her suppliers or force her customers to reveal their information. In this paper we present a solution to the encrypted data modification problem and reconciliate this apparent conflict. Using a generic sender-transformer-recipient example scenario, we illustrate the steps required for applying XML transformations to encrypted data, present the cryptographic building blocks, and give an outlook on advantages and weaknesses of the proposed encryption scheme. The transformer is then able to offer composite services without itself learning the content of the messages.

There are a number of searchable encryption schemes that allow secure conjunctive keyword searches over encrypted data, but all of them assume that the position of the keywords is known. This is a pity, since in unstructured text, e.g. the body of an e-mail, this position is unknown and one has to construct O(mn) search tokens for n keywords in a text of length m. In this paper we present a searchable encryption scheme that allows conjunctive keyword searches without specifying the position requiring only one search token with constant ciphertext length. We prove the security of our scheme using the external Diffie-Hellman assumption in the random oracle model.

We consider large scale Publish/Subscribe systems deployed across multiple organizations. However, such cross organizational deployment is often hindered by firewalls and Network Address Translators (NATs). Several workarounds have been proposed to allow firewall and NAT traversal, e.g. VPN, connection reversal, relay routers. However, each traversal mechanism in turn leads to trade-offs with respect to implementation complexity, infrastructure overhead, latency, etc. We focus on the latency aspect in this work. We propose a cost-performance model that allows quantitative evaluation of the performance latency induced by the different firewall traversal mechanisms. The utility of the model is that for a given network configuration, it is able to provide a (close) approximation of the performance latencies based on simulation results, without actually having to deploy them in practice. This also allows selecting the best traversal mechanism for a given configuration. Finally, experimental results are given to show the validity of the proposed model.

Access to distributed databases containing tuples collected about mobile physical objects requires information about the objects' trajectories. Existing access control models cannot encode this information efficiently. This poses a policy management problem to administrators in real-world supply chains where companies want to protect their goods tracking data. In this paper we propose a new access control model as an extension to attribute-based access control that allows trajectory-based visibility policies. We prove the security properties of our novel authentication protocol for distributed systems that can supply the decision algorithm with the necessary reliable information using only standard passive RFID tags. As a result companies will be able to improve confidentiality protection and governance of their object tracking data and more trustingly engage in data sharing agreements.

Currently, companies are about to optimize their internal processes by monitoring items they handle with Radio Frequency Identification (RFID). However, there is a risk that sensitive information is disclosed when sharing RFID data with other companies. Therefore, companies are unwilling to share RFID data. At first glance, Secure Multi-Party Computation (SMC) might reconciliate data sharing with the privacy concerns. However, SMC requires the collaboration of all parties involved in a protocol. This prevents using SMC for many applications based on item-level RFID data collected in supply chains, since some parties may be competitors or have conflicting interests. We present protocols for securely and privately computing item-level metrics using only existing communication links (e.g., messages stored on RFID tags) and an oblivious third party. This enables optimizing the supply chain using novel item-level metrics without compromising sensitive information.

Social Network Analysis (SNA) is now a commonly used tool in criminal investigations, but evidence gathering and analysis is often restricted by data privacy laws. We consider the case where multiple investigators want to collaborate but do not yet have sufficient evidence that justifies a plaintext data exchange. We propose a practical solution that allows an investigator to expand his current view without actually exchanging sensitive private information. The investigator gets a partially anonymized view of the entire social network, while preserving his known view.

The growing use of RFID in supply chains brings along an indisputable added value from the business perspective, but raises a number of new interesting security challenges. One of them is the authentication of two participants of the supply chain that have possessed the same tagged item, but that have otherwise never communicated before. The situation is even more complex if we imagine that participants to the supply chain may be business competitors. We present a novel cryptographic scheme that solves this problem. In our solution, users exchange tags over the cycle of a supply chain and, if two entities have possessed the same tag, they agree on a secret common key they can use to protect their exchange of business sensitive information. No rogue user can be successful in a malicious authentication, because it would either be traceable or it would imply the loss of a secret key, which provides a strong incentive to keep the tag authentication information secret and protects the integrity of the supply chain. We provide game-based security proofs of our claims, without relying on the random oracle model.

Abstract Information sharing in supply chain management can dramatically improve the performance of the supply chain. Although many such problems can be modeled and efficiently solved using linear programming (LP), security requirements prevent their implementation in the traditional way. Companies are simply reluctant to exchange such sensitive information. Secure multi‐party computation can help by realizing protocols with guaranteed security. However, efficiency is a major concern. Parallel computing presents an opportunity to improve performance utilizing inherent parallel secure operations. This work focuses on practical approaches to privacy preserving parallel protocols for collaborative LP. First, it theoretically compares the approach of parallelizing a secure algorithm and securing a parallel algorithm. Their complexity being equal we implemented the simpler choice: parallelizing a secure algorithm. Different synchronization methods for the implementation are compared under different network conditions. Given the best implementation, the performance is almost independent of the network conditions, but parallelization, i.e. number of threads, needs to be adapted to such conditions. We present and evaluate an adaptive scheduling algorithm for the dynamic selection of the number of threads, such that it's not necessary to statically and up‐front determine the number for optimal speed‐up. The algorithm can even deal with varying network conditions. Copyright © 2009 John Wiley & Sons, Ltd.

Secure multiparty computation (SMC) protocols enable a group of mutually distrustful parties to perform a joint computation with private inputs. Novel e-commerce applications have emerged that could benefit from strong privacy protection, e.g., benchmarking, auctions, and collaborative supply chain management and planning. However, the uptake of SMC in these applications is still rare. We argue that this is due to poor performance, functionality, and scalability, as well as architectures that do not meet the needs of e-commerce applications. This paper explores SMC approaches and research directions, aiming at providing better support for e-commerce applications.

Benchmarking is the process of comparing one's own performance to the statistics of a group of competitors, named peer group. It is a common and important process in the business world for many important business metrics, called key performance indicators (KPI). Privacy is of the utmost importance, since these KPIs allow the inference of sensitive information. Therefore several secure multiparty computation (SMC) protocols for securely and privately computing statistics of KPIs have recently been developed. These protocols are the basic building block for a privacy-preserving benchmarking system, but in order to complete an enterprise system that offers a benchmarking service to its customers more problems need to be solved. This paper addresses two remaining problems: peer group formation and protocol orchestration. We first analyze how peer group participation impacts privacy and vice-versa. Given current network performance limitations we conclude that in order for KPIs to remain private one subscriber can participate in at most one peer group. Peer group formation is the process of forming sensible peer groups out of the set of subscribers. A sensible peer group is one that is useful for benchmarking, i.e. a group of similar companies, under the constraint that one subscriber can participate in at most one peer group. We characterize subscribers by a set of discrete criteria and therefore view the automatic peer group formation as a data clustering problem. A data clustering algorithm customized for automatic peer group formation is required to build clusters whose size does not fall below a minimum threshold. We present a high-performance modification of k-means clustering that takes the minimum cluster size as an additional parameter which might be of independent interest. In a simulation we evaluate its practical applicability to automatic peer group formation. Our final approach is the first automatic peer group formation algorithm for an enterprise benchmarking system. Polling-based protocol orchestration allows the subscribers to remain passive clients, i.e. require no inbound connection, e.g. through a company firewall. We show through simulation that such a polling-based orchestration can be expected to complete within one polling interval.

Systems of logical clocks are commonly found in distributed systems for establishing causality between events occurring in concurrent communicating processes. Vector clocks are a popular type of logical clocks which require processes to attach to each message a logical timestamp that contains information about the sender process's view of the state of the distributed computation at the time of message sending. Causality between two events can then be determined by comparing their two logical timestamps. However, by doing so, processes leak potentially sensitive information about the advancement of their computation and the computations performed by the processes they communicate with. The contribution presented in this paper is a protocol, based on secure computation techniques, which preserves the privacy of each process's local logical clock while being strictly equivalent to regular vector clocks.

We introduce the concept of using internal sensors to perform intrusion detection in computer systems. We show its practical feasibility and discuss its characteristics, related design and implementation issues. We introduce a classification of data collection mechanisms for intrusion detection sys tems. At a conceptual level, these mechanisms are classified as direct and indirect monitoring. At a practical level, direct monitoring can be implemented using external or internal sensors. Internal sensors provide advantages with respect to reliability, completeness, timeliness and volume of data, in addition to efficiency and resistance against attacks. We introduce an architecture called ESP as a framework for building intrusion detection systems based on internal sensors. We describe in detail a prototype implementation based on the ESP architecture and introduce the concept of embedded detectors as a mechanism for localized data reduction. Our implementation shows that it is possible to build both specific (specialized for a certain intrusion) and generic (able to detect different types of intrusions) detectors. Performance testing of the ESP implementation shows the impact that embedded detectors can have on a computer system. Detection testing shows that embedded detectors have the capability of detecting a significant percentage of new attacks.