Papers tagged as Privacy
  1. Private Aggregation from Fewer Anonymous Messages 2020 DifferentialPrivacy Eurocrypt Privacy
    Badih Ghazi, Pasin Manurangsi, Rasmus Pagh, Ameya Velingker

    Consider the setup where $n$ parties are each given a number $x_i \in \mathbb{F}_q$ and the goal is to compute the sum $\sum_i x_i$ in a secure fashion and with as little communication as possible. We study this problem in the anonymized model of Ishai et al. (FOCS 2006) where each party may broadcast anonymous messages on an insecure channel.
    We present a new analysis of the one-round “split and mix” protocol of Ishai et al. In order to achieve the same security parameter, our analysis reduces the required number of messages by a $\Theta(\log n)$ multiplicative factor. We complement our positive result with lower bounds showing that the dependence of the number of messages on the domain size, the number of parties, and the security parameter is essentially tight.
    Using a reduction of Balle et al. (2019), our improved analysis of the protocol of Ishai et al. yields, in the same model, an $\left(\varepsilon, \delta\right)$-differentially private protocol for aggregation that, for any constant $\varepsilon > 0$ and any $\delta = \frac{1}{\mathrm{poly}(n)}$, incurs only a constant error and requires only a constant number of messages per party. Previously, such a protocol was known only for $\Omega(\log n)$ messages per party.

  2. Efficient Round-Optimal Blind Signatures in the Standard Model 2017 FinancialCryptography Privacy Signatures
    Essam Ghadafi

    Blind signatures are at the core of e-cash systems and have numerous other applications. In this work we construct efficient blind and partially blind signature schemes over bilinear groups in the standard model. Our schemes yield short signatures consisting of only a couple of elements from the shorter source group and have very short communication overhead consisting of 1 group element on the user side and 3 group elements on the signer side. At 80-bit security, our schemes yield signatures consisting of only 40 bytes which is 67% shorter than the most efficient existing scheme with the same security in the standard model. Verification in our schemes requires only a couple of pairings. Our schemes compare favorably in every efficiency measure to all existing counterparts offering the same security in the standard model. In fact, the efficiency of our signing protocol as well as the signature size compare favorably even to many existing schemes in the random oracle model. For instance, our signatures are shorter than those of Brands’ scheme which is at the heart of the U-Prove anonymous credential system used in practice. The unforgeability of our schemes is based on new intractability assumptions of a ``one-more’’ type which we show are intractable in the generic group model, whereas their blindness holds w.r.t.~malicious signing keys in the information-theoretic sense. We also give variants of our schemes for a vector of messages.

  3. A Practical Multivariate Blind Signature Scheme 2017 FinancialCryptography Multivariate Privacy Signatures
    Albrecht Petzoldt, Alan Szepieniec, Mohamed Saied Emam Mohamed

    Multivariate Cryptography is one of the main candidates for creating post-quantum cryptosystems. Especially in the area of digital signatures, there exist many practical and secure multivariate schemes. However, there is a lack of multivariate signature schemes with special properties such as blind, ring and group signatures. In this paper, we propose a generic technique to transform multivariate signature schemes into blind signature schemes and show the practicality of the construction on the example of Rainbow. The resulting scheme satisfies the usual blindness criterion and a one-more-unforgeability criterion adapted to MQ signatures, produces short blind signatures and is very efficient.

  4. Practically Efficient Secure Distributed Exponentiation Without Bit-Decomposition 2018 FinancialCryptography MPC Privacy
    Abdelrahaman Aly, Aysajan Abidin, and Svetla Nikova

    Bit-decomposition is a powerful tool which can be used to design constant round protocols for bit-oriented multiparty computation (MPC) problems, such as comparison and Hamming weight computation. However, protocols that involve bit-decomposition are expensive in terms of performance. In this paper, we introduce a set of protocols for distributed exponentiation without bit-decomposition. We improve upon the current state-of-the-art by Ning and Xu [1, 2], in terms of round and multiplicative complexity. We consider different cases where the inputs are either private or public and present privacy-preserving protocols for each case. Our protocols offer perfect security against passive and active adversaries and have constant multiplicative and round complexity, for any fixed number of parties. Furthermore, we showcase how these primitives can be used, for instance, to perform secure distributed decryption for some public key schemes, that are based on modular exponentiation.

  5. Faster Unbalanced Private Set Intersection 2018 FinancialCryptography Privacy PSI
    Amanda Cristina Davi Resende and Diego de Freitas Aranha

    Protocols for Private Set Intersection (PSI) are important cryptographic primitives that perform joint operations on datasets in a privacy-preserving way. They allow two parties to compute the intersection of their private sets without revealing any additional information beyond the intersection itself. Unfortunately, PSI implementations in the literature do not usually employ the best possible cryptographic implementation techniques. This results in protocols presenting computational and communication complexities that are prohibitive, particularly in the case when one of the participants is a low-powered device and there are bandwidth restrictions. This paper builds on modern cryptographic engineering techniques and proposes optimizations for a promising one-way PSI protocol based on public-key cryptography. For the case when one of the parties holds a set much smaller than the other (a realistic assumption in many scenarios) we show that our improvements and optimizations yield a protocol that outperforms the communication complexity and the run time of previous proposals by around one thousand times.

  6. Proof-of-Censorship: Enabling centralized censorship-resistant content providers 2018 Censorship FinancialCryptography Privacy
    Ian Martiny, Ian Miers, and Eric Wustrow

    Content providers often face legal or economic pressures to censor or remove objectionable or infringing content they host. While decentralized providers can enable censorship-resistant storage, centralized content providers remain popular for performance and usability reasons. But centralized content providers can always choose not to respond to requests for a specific file, making it difficult to prevent censorship. If it is not possible to prevent, is it possible to detect and punish censorship on a centralized service?

    A natural approach is to periodically audit the service provider by downloading the file. However, failure to download a file is not a proof of censorship. First, the provider could claim benign failure. Second, the proof is non-transferable: verifying censorship requires third parties to individually request the censored file. Moreover, a content provider may only selectively deny access to particular users or only for a short time frame. As such, checking by downloading does not work even for third parties who are online and willing to make queries.

    In this paper, we introduce proof of censorship, whereby a content provider cannot delete or otherwise selectively remove content from their service without creating transferable cryptographic proof of their misdeed. Even if the provider restores the file at a later date, the proof remains valid, allowing the reputation of a content provider’s commitment to censorship resistance to be based on the existence (or absence) of such proofs.

  7. A Universally Composable Framework for the Privacy of Email Ecosystems 2018 Asiacrypt Privacy UC
    Pyrros Chaidos and Olga Fourtounelli and Aggelos Kiayias and Thomas Zacharias

    Email communication is amongst the most prominent online activities, and as such, can put sensitive information at risk. It is thus of high importance that internet email applications are designed in a privacy-aware manner and analyzed under a rigorous threat model. The Snowden revelations (2013) suggest that such a model should feature a global adversary, in light of the observational tools available. Furthermore, the fact that protecting metadata can be of equal importance as protecting the communication context implies that end-to-end encryption may be necessary, but it is not sufficient.

    With this in mind, we utilize the Universal Composability framework [Canetti, 2001] to introduce an expressive cryptographic model for email ``ecosystems’’ that can formally and precisely capture various well-known privacy notions (unobservability, anonymity, unlinkability, etc.), by parameterizing the amount of leakage an ideal-world adversary (simulator) obtains from the email functionality.

    Equipped with our framework, we present and analyze the security of two email constructions that follow different directions in terms of the efficiency vs. privacy tradeoff. The first one achieves optimal security (only the online/offline mode of the users is leaked), but it is mainly of theoretical interest; the second one is based on parallel mixing [Golle and Juels, 2004] and is more practical, while it achieves anonymity with respect to users that have similar amount of sending and receiving activity.

  8. A Smart Contract for Boardroom Voting with Maximum Voter Privacy 2017 Blockchains FinancialCryptography Privacy SmartContracts
    Patrick McCorry, Siamak Shahandashti, Feng Hao

    We present the first implementation of a decentralised and self-tallying internet voting protocol with maximum voter privacy using the Blockchain. The Open Vote Network is suitable for boardroom elec- tions and is written as a smart contract for Ethereum. Unlike previously proposed Blockchain e-voting protocols, this is the first implementation that does not rely on any trusted authority to compute the tally or to protect the voter’s privacy. Instead, the Open Vote Network is a self- tallying protocol, and each voter is in control of the privacy of their own vote such that it can only be breached by a full collusion involving all other voters. The execution of the protocol is enforced using the consensus mechanism that also secures the Ethereum blockchain. We tested the implementation on Ethereum’s official test network to demonstrate its feasibility. Also, we provide a financial and computational breakdown of its execution cost.

  9. Quisquis: A New Design for Anonymous Cryptocurrencies 2019 Asiacrypt Blockchains Privacy
    Prastudy Fauzi, Sarah Meiklejohn, Rebekah Mercer and Claudio Orlandi

    Despite their usage of pseudonyms rather than persistent identifiers, most existing cryptocurrencies do not provide users with any meaningful levels of privacy. This has prompted the creation of privacy-enhanced cryptocurrencies such as Monero and Zcash, which are specifically designed to counteract the tracking analysis possible in currencies like Bitcoin. These cryptocurrencies, however, also suffer from some drawbacks: in both Monero and Zcash, the set of potential unspent coins is always growing, which means users cannot store a concise representation of the blockchain. Additionally, Zcash requires a common reference string and the fact that addresses are reused multiple times in Monero has led to attacks to its anonymity.

    In this paper we propose a new design for anonymous cryptocurrencies, Quisquis, that achieves provably secure notions of anonymity. Quisquis stores a relatively small amount of data, does not require trusted setup, and in Quisquis each address appears on the blockchain at most twice: once when it is generated as output of a transaction, and once when it is spent as input to a transaction. Our result is achieved by combining a DDH-based tool (that we call updatable keys) with efficient zero-knowledge arguments.

  10. Proof-of-Stake Protocols for Privacy-Aware Blockchains 2019 Blockchains Eurocrypt Privacy ProofOfStake
    Chaya Ganesh, Claudio Orlandi, and Daniel Tschudi

    Proof-of-stake (PoS) protocols are emerging as one of the most promising alternative to the wasteful proof-of-work (PoW) protocols for consensus in Blockchains (or distributed ledgers).

    However, current PoS protocols inherently disclose both the identity and the wealth of the stakeholders, and thus seem incompatible with privacy-preserving cryptocurrencies (such as ZCash, Monero, etc.).

    In this paper we initiate the formal study for PoS protocols with privacy properties. Our results include:

    • A (theoretical) feasibility result showing that it is possible to construct a general class of private PoS (PPoS) protocols; and to add privacy to a wide class of PoS protocols,

    • A privacy-preserving version of a popular PoS protocol, Ouroboros Praos.

    Towards our result, we define the notion of anonymous verifiable random function, which we believe is of independent interest.

  11. Faster Homomorphic Evaluation of Discrete Fourier Transforms 2017 FHE FinancialCryptography Privacy
    Anamaria Costache, Nigel P. Smart, Srinivas Vivek

    We present a methodology to achieve low latency homomorphic operations on approximations to complex numbers, by encoding a complex number as an evaluation of a polynomial at a root of unity. We then use this encoding to evaluate a Discrete Fourier Transform (DFT) on data which has been encrypted using a Somewhat Homomorphic Encryption (SHE) scheme, with up to three orders of magnitude improvement in latency over previous methods. We are also able to deal with much larger input sizes than previous methods. Due to the fact that the entire DFT algorithm is an algebraic operation over the underlying ring of the SHE scheme (for a suitably chosen ring), our method for the DFT utilizes exact arithmetic over the complex numbers, as opposed to approximations.

  12. SecGDB: Graph Encryption for Exact Shortest Distance Queries with Efficient Updates 2017 FinancialCryptography Privacy SearchableEncryption
    Qian Wang, Kui Ren, Minxin Du, Aziz Mohaisen

    In the era of big data, graph databases have become in-creasingly important for NoSQL technologies, and many systems (e.g.,online social networks, world-wide web and electrical grids, etc.) can be modeled as graphs for semantic queries. Meanwhile, with the advent of cloud computing, data owners are highly motivated to outsource and s-tore their massive potentially-sensitive graph data on remote untrusted servers in an encrypted form, expecting to retain the ability to query over the encrypted graphs.To allow e↵ective and private queries over encrypted data, the most well-studied class of structured encryption schemes are searchable symmetric encryption (SSE) designs, which encrypt search structures (e.g., inverted indexes based on keyword-file pairs) for retrieving data files of interestfrom remote servers. So far, however, the problem of graph data encryption that supports customized queries has received limited attention inthe literature. In this paper, we tackle the challenge of designing a Se-cure Graph DataBase encryption scheme (SecGDB) to encrypt graph structures and enforce private graph queries over the encrypted graph database. Specifically, our construction strategically makes use of e�cient additively homomorphic encryption and garbled circuits to support the shortest distance queries with optimal time and storage complexities. Toachieve better amortized time complexity over multiple queries, we further propose an auxiliary data structure called query historyand storeit on the remote server to act as a “caching” resource. Compared with the state-of-the-art solutions, our design returns exact shortest distancequery results instead of approximate ones and allows e�cient graph up-date queries over large-scale encrypted graphs. We prove that our construction is adaptively semantically-secure in the random oracle model and finally implement and evaluate it on various representative real-world datasets, showing that our approach is practically efficient in terms of both storage and computation.

  13. Real Hidden Identity-Based Signatures 2017 AnonymousCredentials FinancialCryptography Privacy
    Sherman S.M. Chow, Haibin Zhang, Tao Zhang

    Group signature allows members to issue signatures on be-half of the group anonymously in normal circumstances. When the need arises, an opening authority (OA) can open a signature and reveal its true signer. Yet, many constructions require not only the OA’s secret key but also a member database (cf. a public-key repository) in this opening.This “secret members list” put the anonymity of members at risk.To resolve this “anonymity catch-22” issue, Kiayias and Zhou proposed hidden identity-based signatures (Financial Crypt. 2007), where the opening just takes in the OA’s secret key and outputs the signer identity. The membership list can be hidden from the OA since there is no member-ship list whatsoever. However, their constructions suffer from efficiency problem.This paper aims to realize the vision of Kiayias and Zhou for real, that is,an efficient construction which achieves the distinctive feature of hidden identity-based signatures. Moreover, our construction is secure against concurrent attack, and easily extensible with linkability such that any double authentication can be publicly detected. Both features are especially desirable in Internet-based services which allow anonymous authentication with revocation to block any misbehaving user. We believe our work will improve the usability of group signature and its variant.

  14. SilentWhispers: Enforcing Security and Privacy in Decentralized Credit Networks 2017 Blockchains NDSS Privacy
    Giulio Malavolta, Pedro Moreno-Sanchez, Aniket Kate, and Matteo Maffei

    Credit networks model transitive trust (or credit) between users in a distributed environment and have recently seen a rapid increase of popularity due to their flexible design and robustness against intrusion. They serve today as a backbone of real-world IOweYou transaction settlement networks such as Ripple and Stellar, which are deployed by various banks worldwide, as well as several other systems, such as spam-resistant communication protocols and Sybil-tolerant social networks. Current solutions, however, raise serious privacy concerns, as the network topology as well as the credit value of the links are made public for apparent transparency purposes and any changes are logged. In payment scenarios, for instance, this means that all transactions have to be public and everybody knows who paid what to whom.

    In this work, we question the necessity of a privacy-invasive transaction ledger. In particular, we present SilentWhispers, the first distributed, privacy-preserving credit network that does not require any ledger to protect the integrity of transactions. Yet, SilentWhispers guarantees integrity and privacy of link values and transactions even in the presence of distrustful users and malicious neighbors, whose misbehavior in changing link values is detected and such users can be held accountable. We formalize these properties as ideal functionalities in the universal composability framework and present a secure realization based on a novel combination of secret-sharing-based multiparty computation and digital signature chains. SilentWhispers can handle network churn, and it is efficient as demonstrated with a prototype implementation evaluated using payments data extracted from the currently deployed Ripple payment system.

  15. Stormy: Statistics in Tor by Measuring Securely 2019 CCS MPC Privacy Tor
    Ryan Wails, Aaron Johnson, Daniel Starin, Arkady Yerukhimovich, and S. Dov Gordon

    Tor is a tool for Internet privacy with millions of daily users. The Tor system benefits in many ways from information gathered about the operation of its network. Measurements guide operators in diagnosing problems, direct the efforts of developers, educate users about the level of privacy they obtain, and inform policymakers about Tor’s impact. However, data collection and reporting can degrade user privacy, contradicting Tor’s goals. Existing approaches to measuring Tor have limited capabilities and security weaknesses. We present Stormy, a general-purpose, privacy-preserving measurement system that overcomes these limitations. Stormy uses secure multiparty computation (MPC) to compute any function of the observations made by Tor relays, while keeping those observations secret. Stormy makes use of existing efficient MPC protocols that are secure in the malicious model, and in addition it includes a novel input-sharing protocol that is secure, efficient, and fault tolerant. The protocol is non-interactive, which is consistent with how relays currently submit measurements, and it allows the relays to go offline after input submission, even while ensuring that an honest relay will not have its input excluded or modified. The input-sharing protocol is compatible with MPC protocols computing on authenticated values and may be of independent interest. We show how Stormy can be deployed in two realistic models: (1) run primarily by a small set of dedicated authorities, or (2) run decentralized across the relays in the Tor network. Stormy scales efficiently to Tor’s thousands of relays, tolerates network churn, and provides security depending only on either Tor’s existing trust assumption that at least one authority is honest (in the first model) or the existing assumption that a large fraction of relay bandwidth is honest (in the second model). We demonstrate how to use the system to compute two broadly-applicable statistics: the median of relay inputs and the cardinality of set-union across relays. We implement Stormy and experimentally evaluate system performance. When Stormy is run among authorities we can perform 151 median computations or 533 set-union cardinalities over 7,000 relay inputs in a single day. When run among the relays themselves, Stormy can perform 36 median computations or 134 set union cardinalities per day. Thus, both deployments enable non-trivial analytics to be securely computed in the Tor network.

  16. SAMPL: Scalable Auditability of Monitoring Processes using Public Ledgers 2019 Blockchains CCS Privacy
    Gaurav Panwar, Roopa Vishwanathan, Satyajayant Misra, and Austin Bos

    Organized surveillance, especially by governments poses a major challenge to individual privacy, due to the resources governments have at their disposal, and the possibility of overreach. Given the impact of invasive monitoring, in most democratic countries, government surveillance is, in theory, monitored and subject to public oversight to guard against violations. In practice, there is a difficult fine balance between safeguarding individual’s privacy rights and not diluting the efficacy of national security investigations, as exemplified by reports on government surveillance programs that have caused public controversy, and have been challenged by civil and privacy rights organizations. Surveillance is generally conducted through a mechanism where federal agencies obtain a warrant from a federal or state judge (e.g., the US FISA court, Supreme Court in Canada) to subpoena a company or service-provider (e.g., Google, Microsoft) for their customers’ data. The courts provide annual statistics on the requests (accepted, rejected), while the companies provide annual transparency reports for public auditing. However, in practice, the statistical information provided by the courts and companies is at a very high level, generic, is released after-the-fact, and is inadequate for auditing the operations. Often this is attributed to the lack of scalable mechanisms for reporting and transparent auditing. In this paper, we present SAMPL, a novel auditing framework which leverages cryptographic mechanisms, such as zero knowledge proofs, Pedersen commitments, Merkle trees, and public ledgers to create a scalable mechanism for auditing electronic surveillance processes involving multiple actors. SAMPL is the first framework that can identify the actors (e.g., agencies and companies) that violate the purview of the court orders. We experimentally demonstrate the scalability for SAMPL for handling concurrent monitoring processes without undermining their secrecy and auditability.

  17. Privacy Aspects and Subliminal Channels in Zcash 2019 Blockchains CCS Privacy
    Alex Biryukov, Daniel Feher, and Giuseppe Vitto

    In this paper we analyze two privacy and security issues for the privacy-oriented cryptocurrency Zcash. First we study shielded transactions and show ways to fingerprint user transactions, including active attacks. We introduce two new attacks which we call Danaan-gift attack and Dust attack. Following the recent Sapling update of Zcash protocol we study the interaction between the new and the old zk-SNARK protocols and the effects of their interaction on transaction privacy. In the second part of the paper we check for the presence of subliminal channels in the zk-SNARK protocol and in Pedersen Commitments. We show presence of efficient 70-bit channels which could be used for tagging of shielded transactions which would allow the attacker (malicious transaction verifier) to link transactions issued by a maliciously modified zk-SNARK prover, while would be indistinguishable from regular transactions for the honest verifier/user. We discuss countermeasures against both of these privacy issues.

  18. Omniring: Scaling Private Payments Without Trusted Setup 2019 Blockchains CCS Privacy
    Russell W. F. Lai, Viktoria Ronge, Tim Ruffing, Dominique Schröder, Sri Aravinda Krishnan Thyagarajan and Jiafan Wang

    Monero is the largest cryptocurrency with built-in cryptographic privacy features. The transactions are authenticated using spend proofs, which provide a certain level of anonymity by hiding the source accounts from which the funds are sent among a set (known as a ring) of other accounts. Due to its similarities to ring signatures, this core cryptographic component is called Ring Confidential Transactions (RingCT). Because of its practical relevance, several works attempt to analyze the security of RingCT. However, due to the complexity of RingCT they are either informal, miss fundamental functionalities, or introduce undesirable trusted setup assumptions. Regarding efficiency, Monero currently deploys a scheme in which the size of the spend proof is linear in the ring size. This limits the ring size to only a few accounts, which in turn limits the acquired anonymity significantly and facilitates de-anonymization attacks.

    As a solution to these problems, we present the first complete rigorous formalization of RingCT as a cryptographic primitive. We then propose a generic construction of RingCT and prove it secure in our formal security model. By instantiating our generic construction with new efficient zero-knowledge proofs we obtain Omniring, a fully-fledged RingCT scheme in the discrete logarithm setting that provides the highest concrete and asymptotic efficiency as of today. Omniring is the first RingCT scheme which 1) does not require a trusted setup or pairing-friendly elliptic curves, 2) has a proof size logarithmic in the size of the ring, and 3) allows to share the same ring between all source accounts in a transaction, thereby enabling significantly improved privacy level without sacrificing performance. Our zero-knowledge proofs rely on novel enhancements to the Bulletproofs framework (S&P 2018), which we believe are of independent interest.

  19. Membership Privacy for Fully Dynamic Group Signatures 2019 CCS Privacy Signatures
    Michael Backes, Lucjan Hanzlik and Jonas Schneider

    Group signatures present a trade-off between the traditional goals of digital signatures and the signer’s desire for privacy, allowing for the creation of unforgeable signatures in the name of a group which reveal nothing about the actual signer’s identity beyond their group membership. Considering the desired properties formally opens up a possibility space of different security goals under various assumptions on trust placed in the designated entities of any scheme. Many models differ in their consideration of the variability of group membership as well, yet a formal treatment of the privacy of group membership status is lacking in all models, thus far.

    We address this issue, starting from the vantage point of the comprehensive model due to Bootle et al. (ACNS’16), who prove that any scheme secure in their model is also secure in the previous models. Their model allows for fully dynamic management of group membership by segmenting the scheme’s lifetime into epochs during which group membership is static but between which users may join or leave the group.

    We extend the model of Bootle et al. by introducing formal notions of membership privacy. We then propose an efficient generic construction for a fully dynamic group signature scheme with membership privacy that is based on signatures with flexible public key (SFPK) and signatures on equivalence classes (SPSEQ). We instantiate the construction using a SFPK scheme based on the bilinear decisional Diffie-Hellman assumption and SPSEQ scheme by Fuchsbauer and Gay (PKC’18). The resulting scheme provides shorter signatures than existing schemes from standard assumption, while at the same time achieving stronger security guarantees.

  20. Delphi: A Cryptographic Inference Service for Neural Networks 2020 MachineLearning Privacy Usenix
    Pratyush Mishra, Ryan Lehmkuhl, Akshayaram Srinivasan, Wenting Zheng, and Raluca Ada Popa

    Many companies provide neural network prediction services to users for a wide range of applications. However, current prediction systems compromise one party’s privacy: either the user has to send sensitive inputs to the service provider for classification, or the service provider must store its proprietary neural networks on the user’s device. The former harms the personal privacy of the user, while the latter reveals the service provider’s proprietary model.

    We design, implement, and evaluate Delphi, a secure prediction system that allows two parties to run a neural network inference without revealing either party’s data. Delphi approaches the problem by simultaneously co-designing cryptography and machine learning. We first design a hybrid cryptographic protocol that improves upon the communication and computation costs over prior work. Second, we develop a planner that automatically generates neural network architecture configurations that navigate the performance-accuracy trade-offs of our hybrid protocol. Together, these techniques allow us to achieve a 22x improvement in prediction latency compared to the state-of-the-art prior work.

  21. Utility-Aware Synthesis of Differentially Private and Attack-Resilient Location Traces 2018 CCS DifferentialPrivacy Privacy
    Mehmet Emre Gursoy, Ling Liu, Stacey Truex, Lei Yu, and Wenqi Wei

    As mobile devices and location-based services become increasingly ubiquitous, the privacy of mobile users’ location traces continues to be a major concern. Traditional privacy solutions rely on perturbing each position in a user’s trace and replacing it with a fake location. However, recent studies have shown that such point-based perturbation of locations is susceptible to inference attacks and suffers from serious utility losses, because it disregards the moving trajectory and continuity in full location traces. In this paper, we argue that privacy-preserving synthesis of complete location traces can be an effective solution to this problem. We present AdaTrace, a scalable location trace synthesizer with three novel features: provable statistical privacy, deterministic attack resilience, and strong utility preservation. AdaTrace builds a generative model from a given set of real traces through a four-phase synthesis process consisting of feature extraction, synopsis learning, privacy and utility preserving noise injection, and generation of differentially private synthetic location traces. The output traces crafted by AdaTrace preserve utility-critical information existing in real traces, and are robust against known location trace attacks. We validate the effectiveness of AdaTrace by comparing it with three state of the art approaches (ngram, DPT, and SGLT) using real location trace datasets (Geolife and Taxi) as well as a simulated dataset of 50,000 vehicles in Oldenburg, Germany. AdaTrace offers up to 3-fold improvement in trajectory utility, and is orders of magnitude faster than previous work, while preserving differential privacy and attack resilience.

  22. ABY3 : A Mixed Protocol Framework for Machine Learning 2018 CCS MachineLearning MPC Privacy
    Payman Mohassel and Peter Rindal

    Abstract: Machine learning is widely used to produce models for a range of applications and is increasingly offered as a service by major technology companies. However, the required massive data collection raises privacy concerns during both training and prediction stages.

    In this paper, we design and implement a general framework for privacy-preserving machine learning and use it to obtain new solutions for training linear regression, logistic regression and neural network models. Our protocols are in a three-server model wherein data owners secret share their data among three servers who train and evaluate models on the joint data using three-party computation (3PC).

    Our main contribution is a new and complete framework (ABY3) for efficiently switching back and forth between arithmetic, binary, and Yao 3PC which is of independent interest. Many of the conversions are based on new techniques that are designed and optimized for the first time in this paper. We also propose new techniques for fixed-point multiplication of shared decimal values that extends beyond the three-party case, and customized protocols for evaluating piecewise polynomial functions. We design variants of each building block that is secure against {\em malicious adversaries} who deviate arbitrarily.

    We implement our system in C++. Our protocols are up to {\em four orders of magnitude} faster than the best prior work, hence significantly reducing the gap between privacy-preserving and plaintext training.

  23. Practical Accountability of Secret Processes 2018 Privacy Surveillance Usenix ZK zkSNARK
    Jonathan Frankle, Sunoo Park, Daniel Shaar, Shafi Goldwasser, and Daniel Weitzner

    The US federal court system is exploring ways to improve the accountability of electronic surveillance, an opaque process often involving cases sealed from public view and tech companies subject to gag orders against informing surveilled users. One judge has proposed publicly releasing some metadata about each case on a paper cover sheet as a way to balance the competing goals of (1) secrecy, so the target of an investigation does not discover and sabotage it, and (2) accountability, to assure the public that surveillance powers are not misused or abused.

    Inspired by the courts’ accountability challenge, we illustrate how accountability and secrecy are simultaneously achievable when modern cryptography is brought to bear. Our system improves configurability while preserving secrecy, offering new tradeoffs potentially more palatable to the risk-averse court system. Judges, law enforcement, and companies publish commitments to surveillance actions, argue in zero-knowledge that their behavior is consistent, and compute aggregate surveillance statistics by multi-party computation (MPC).

    We demonstrate that these primitives perform efficiently at the scale of the federal judiciary. To do so, we implement a hierarchical form of MPC that mirrors the hierarchy of the court system. We also develop statements in succinct zero-knowledge (SNARKs) whose specificity can be tuned to calibrate the amount of information released. All told, our proposal not only offers the court system a flexible range of options for enhancing accountability in the face of necessary secrecy, but also yields a general framework for accountability in a broader class of secret information processes.

  24. XONN: XNOR-based Oblivious Deep Neural Network Inference 2019 GarbledCircuits MachineLearning Privacy Usenix
    M. Sadegh Riazi, Mohammad Samragh, Hao Chen, Kim Laine, Kristin Lauter, and Farinaz Koushanfar

    Advancements in deep learning enable cloud servers to provide inference-as-a-service for clients. In this scenario, clients send their raw data to the server to run the deep learning model and send back the results. One standing challenge in this setting is to ensure the privacy of the clients’ sensitive data. Oblivious inference is the task of running the neural network on the client’s input without disclosing the input or the result to the server. This paper introduces XONN (pronounced /ZAn/), a novel end-to-end framework based on Yao’s Garbled Circuits (GC) protocol, that provides a paradigm shift in the conceptual and practical realization of oblivious inference. In XONN, the costly matrix-multiplication operations of the deep learning model are replaced with XNOR operations that are essentially free in GC. We further provide a novel algorithm that customizes the neural network such that the runtime of the GC protocol is minimized without sacrificing the inference accuracy.

    We design a user-friendly high-level API for XONN, allowing expression of the deep learning model architecture in an unprecedented level of abstraction. We further provide a compiler to translate the model description from high-level Python (i.e., Keras) to that of XONN. Extensive proof-of-concept evaluation on various neural network architectures demonstrates that XONN outperforms prior art such as Gazelle (USENIX Security’18) by up to 7×, MiniONN (ACM CCS’17) by 93×, and SecureML (IEEE S&P’17) by 37×. State-of-the-art frameworks require one round of interaction between the client and the server for each layer of the neural network, whereas, XONN requires a constant round of interactions for any number of layers in the model. XONN is first to perform oblivious inference on Fitnet architectures with up to 21 layers, suggesting a new level of scalability compared with state-of-the-art. Moreover, we evaluate XONN on four datasets to perform privacy-preserving medical diagnosis. The datasets include breast cancer, diabetes, liver disease, and Malaria.

  25. The Loopix Anonymity System 2017 Privacy Usenix
    Ania M. Piotrowska, Jamie Hayes, Tariq Elahi, Sebastian Meiser and George Danezis

    We present Loopix, a low-latency anonymous communication system that provides bi-directional ‘third-party’ sender and receiver anonymity and unobservability. Loopix leverages cover traffic and Poisson mixing—brief independent message delays—to provide anonymity and to achieve traffic analysis resistance against, including but not limited to, a global network adversary. Mixes and clients self-monitor and protect against active attacks via self-injected loops of traffic. The traffic loops also serve as cover traffic to provide stronger anonymity and a measure of sender and receiver unobservability. Loopix is instantiated as a network of Poisson mix nodes in a stratified topology with a low number of links, which serve to further concentrate cover traffic. Service providers mediate access in and out of the network to facilitate accounting and off-line message reception.

    We provide a theoretical analysis of the Poisson mixing strategy as well as an empirical evaluation of the anonymity provided by the protocol and a functional implementation that we analyze in terms of scalability by running it on AWS EC2. We show that mix nodes in Loopix can handle upwards of 300 messages per second, at a small delay overhead of less than 1.5ms on top of the delays introduced into messages to provide security. Overall message latency is on the order of seconds – which is relatively low for a mix-system. Furthermore, many mix nodes can be securely added to the stratified topology to scale throughput without sacrificing anonymity.