CryptoDB
Melissa Chase
Publications
Year
Venue
Title
2024
RWC
Invited talk: Key transparency: introduction, recent results, and open problems
★
Abstract
End-to-end encryption security guarantees crucially rely on the assumption that the user has the correct identity public key for the person they wish to communicate with. Traditionally, E2EE communication systems have required the user to perform cumbersome manual checks to verify these keys, e.g. by physically scanning QR codes, or by verbally reading a fingerprint. In practice, these verifications are rarely performed.
Key transparency, first introduced in CONIKS, allows much of this verification to be automated. Roughly, the communication service provider regularly publishes a commitment to the identity key directory; this commitment must be publicly and consistently visible to all users. Every key request is accompanied by a proof that the key is correct w.r.t. the committed directory. Finally, the user’s device regularly monitors the committed directory to ensure that the user’s key is correctly reflected.
This talk will present the motivation for key transparency and introduce the approach and intuition behind the constructions. It will then discuss some areas of active research and open problems.
2023
CRYPTO
Anonymous Tokens with Stronger Metadata Bit Hiding from Algebraic MACs
Abstract
On the one hand, the web needs to be secured from malicious activities such as bots or DoS attacks; on the other hand, such needs ideally should not justify services tracking people's activities on the web. Anonymous tokens provide a nice tradeoff between allowing an issuer to ensure that a user has been vetted and protecting the users' privacy. However, in some cases, whether or not a token is issued reveals a lot of information to an adversary about the strategies used to distinguish honest users from bots or attackers.
In this work, we focus on designing an anonymous token protocol between a client and an issuer (also a verifier) that enables the issuer to support its fraud detection mechanisms while preserving users' privacy. This is done by allowing the issuer to embed a hidden (from the client) metadata bit into the tokens. We first study an existing protocol from CRYPTO 2020 which is an extension of Privacy Pass from PoPETs 2018; that protocol aimed to provide support for a hidden metadata bit, but provided a somewhat restricted security notion. We demonstrate a new attack, showing that this is a weakness of the protocol, not just the definition. In particular, the metadata bit hiding is weak in the setting where the attacker can redeem some tokens and get feedback on whether the bit extraction succeeded.
We then revisit the formalism of anonymous tokens with private metadata bit, consider the more natural notion, and design a scheme which achieves it. In order to design this new secure protocol, we base our construction on algebraic MACs instead of PRFs. Our security definitions capture a realistic threat model where adversaries could, through direct feedback or side channels, learn the embedded bit when the token is redeemed. Finally, we compare our protocol with one of the CRYPTO 2020 protocols. We obtain 20% more efficient performance.
2021
TCC
Amortizing Rate-1 OT and Applications to PIR and PSI
📺
Abstract
Recent new constructions of rate-1 OT [D\"ottling, Garg, Ishai, Malavolta, Mour, and Ostrovsky, CRYPTO 2019] have brought this primitive under the spotlight and the techniques have led to new feasibility results for private-information retrieval, and homomorphic encryption for branching programs. The receiver communication of this construction consists of a quadratic (in the sender's input size) number of group elements for a single instance of rate-1 OT. Recently [Garg, Hajiabadi, Ostrovsky, TCC 2020] improved the receiver communication to a linear number of group elements for a single string-OT. However, most applications of rate-1 OT require executing it multiple times, resulting in large communication costs for the receiver.
In this work, we introduce a new technique for amortizing the cost of multiple rate-1 OTs. Specifically, based on standard pairing assumptions, we obtain a two-message rate-1 OT protocol for which the amortized cost per string-OT is asymptotically reduced to only four group elements. Our results lead to significant communication improvements in PSI and PIR, special cases of SFE for branching programs.
1. PIR: We obtain a rate-1 PIR scheme with client communication cost of $O(\lambda\cdot\log N)$ group elements for security parameter $\lambda$ and database size $N$. Notably, after a one-time setup (or one PIR instance), any following PIR instance only requires communication cost $O(\log N)$ number of group elements.
2. PSI with unbalanced inputs: We apply our techniques to private set intersection with unbalanced set sizes (where the receiver has a smaller set) and achieve receiver communication of $O((m+\lambda) \log N)$ group elements where $m, N$ are the sizes of the receiver and sender sets, respectively. Similarly, after a one-time setup (or one PSI instance), any following PSI instance only requires communication cost $O(m \cdot \log N)$ number of group elements. All previous sublinear-communication non-FHE based PSI protocols for the above unbalanced setting were also based on rate-1 OT, but incurred at least $O(\lambda^2 m \log N)$ group elements.
2021
RWC
The Signal Private Group System and Anonymous Credentials Supporting Efficient Verifiable Encryption
Abstract
We propose a talk based on a recent project to design and implement a new system to privately manage groups in the Signal messenger application. The system is in testing and is expected to be deployed by RWC 2021. There is an associated research paper, to appear at CCS 2020. (The first ten pages of that paper are attached, and an earlier version of the complete paper is online as ePrint 2019/1416). The talk will select content from the paper, implementation and deployment experience that are expected to be of interest to the RWC audience.
Paper abstract:
In this paper we present a system for maintaining a membership list of users in a group, designed for use in the Signal Messenger secure messaging app. The goal is to support {\em private groups} where membership information is readily available to all group members but hidden from the service provider or anyone outside the group. In the proposed solution, a central server stores the group membership in the form of encrypted entries. Members of the group authenticate to the server in a way that reveals only that they correspond to some encrypted entry, then read and write the encrypted entries.
Authentication in our design uses a primitive called a keyed-verification anonymous credential~(KVAC), and we construct a new KVAC scheme based on an algebraic MAC, instantiated in a group G of prime order. The benefit of the new KVAC is that attributes may be elements in G whereas previous schemes could only support attributes that were integers modulo the order of G. This enables us to encrypt group data using an efficient Elgamal-like encryption scheme, and to prove in
zero-knowledge that the encrypted data is certified by a credential. Because encryption, authentication, and the associated proofs of knowledge are all instantiated in G the system is efficient, even for large groups.
2020
CRYPTO
Private Set Intersection in the Internet Setting From Lightweight Oblivious PRF
📺
Abstract
We present a new protocol for two-party private set intersection (PSI) with semi-honest security in the plain model and one-sided malicious security in the random oracle model. Our protocol achieves a better balance between computation and communication than existing PSI protocols. Specifically, our protocol is the fastest in networks with moderate bandwidth (e.g., 30 - 100 Mbps). Considering the monetary cost (proposed by Pinkas et al. in CRYPTO 2019) to run the protocol on a cloud computing service, our protocol also compares favorably.
Underlying our PSI protocol is a new lightweight multi-point oblivious pesudorandom function (OPRF) protocol based on oblivious transfer (OT) extension. We believe this new protocol may be of independent interest.
2020
ASIACRYPT
Secret-Shared Shuffle
📺
Abstract
Generating additive secret shares of a shuffled dataset - such that neither party knows the order in which it is permuted - is a fundamental building block in many protocols, such as secure collaborative filtering, oblivious sorting, and secure function evaluation on set intersection. Traditional approaches to this problem either involve expensive public-key based crypto or using symmetric crypto on permutation networks. While public-key-based solutions are bandwidth efficient, they are computation-heavy. On the other hand, constructions based on permutation networks are communication-bound, especially when the dataset contains large elements, for e.g., feature vectors in an ML context.
We design a new 2-party protocol for this task of computing secret shares of shuffled data, which we refer to as secret-shared shuffle. Our protocol is secure against a static semi-honest adversary.
At the heart of our approach is a new primitive we define (which we call ``Share Translation'') that generates two sets of pseudorandom values ``correlated via the permutation''. This allows us to reduce the problem of shuffling the dataset to the problem of shuffling pseudorandom values, which enables optimizations both in computation and communication. We then design a Share Translation protocol based on oblivious transfer and puncturable PRFs.
Our final protocol for secret-shared shuffle uses lightweight operations like XOR and PRGs, and in particular doesn't use public-key operations besides the base OTs. As a result, our protocol is concretely more efficient than the existing solutions. In particular, we are two-three orders of magnitude faster than public-key-based approach and one order of magnitude faster compared to the best known symmetric-key approach when the elements are moderately large.
2019
CRYPTO
Reusable Non-Interactive Secure Computation
📺
Abstract
We consider the problem of Non-Interactive Two-Party Secure Computation (NISC), where Rachel wishes to publish an encryption of her input x, in such a way that any other party, who holds an input y, can send her a single message which conveys to her the value f(x, y), and nothing more. We demand security against malicious parties. While such protocols are easy to construct using garbled circuits and general non-interactive zero-knowledge proofs, this approach inherently makes a non-black-box use of the underlying cryptographic primitives and is infeasible in practice.Ishai et al. (Eurocrypt 2011) showed how to construct NISC protocols that only use parallel calls to an ideal oblivious transfer (OT) oracle, and additionally make only a black-box use of any pseudorandom generator. Combined with the efficient 2-message OT protocol of Peikert et al. (Crypto 2008), this leads to a practical approach to NISC that has been implemented in subsequent works. However, a major limitation of all known OT-based NISC protocols is that they are subject to selective failure attacks that allows a malicious sender to entirely compromise the security of the protocol when the receiver’s first message is reused.Motivated by the failure of the OT-based approach, we consider the problem of basing reusable NISC on parallel invocations of a standard arithmetic generalization of OT known as oblivious linear-function evaluation (OLE). We obtain the following results:We construct an information-theoretically secure reusable NISC protocol for arithmetic branching programs and general zero-knowledge functionalities in the OLE-hybrid model. Our zero-knowledge protocol only makes an absolute constant number of OLE calls per gate in an arithmetic circuit whose satisfiability is being proved. We also get reusable NISC in the OLE-hybrid model for general Boolean circuits using any one-way function.We complement this by a negative result, showing that reusable NISC is impossible to achieve in the OT-hybrid model. This provides a formal justification for the need to replace OT by OLE.We build a universally composable 2-message reusable OLE protocol in the CRS model that can be based on the security of Paillier encryption and requires only a constant number of modular exponentiations. This provides the first arithmetic analogue of the 2-message OT protocols of Peikert et al. (Crypto 2008).By combining our NISC protocol in the OLE-hybrid model and the 2-message OLE protocol, we get protocols with new attractive asymptotic and concrete efficiency features. In particular, we get the first (designated-verifier) NIZK protocols for NP where following a statement-independent preprocessing, both proving and verifying are entirely “non-cryptographic” and involve only a constant computational overhead. Furthermore, we get the first statistical designated-verifier NIZK argument for NP under an assumption related to factoring.
2016
CRYPTO
2016
ASIACRYPT
2016
JOFC
2012
ASIACRYPT
Service
- PKC 2025 Program committee
- RWC 2025 Program committee
- RWC 2024 Program committee
- RWC 2023 Program committee
- Crypto 2020 Program committee
- Eurocrypt 2019 Program committee
- Asiacrypt 2019 Program committee
- Eurocrypt 2018 Program committee
- Eurocrypt 2017 Program committee
- Crypto 2016 Program committee
- PKC 2016 Program committee
- TCC 2016 Program committee
- Crypto 2015 Program committee
- PKC 2015 Program committee
- Eurocrypt 2013 Program committee
- PKC 2011 Program committee
- TCC 2011 Program committee
- Crypto 2008 Program committee
Coauthors
- Masayuki Abe (2)
- Shashank Agrawal (2)
- Foteini Baldimtsi (1)
- Mira Belenkiy (2)
- Jan Camenisch (1)
- Nishanth Chandran (2)
- Melissa Chase (30)
- Bernardo David (2)
- Yevgeniy Dodis (1)
- F. Betül Durak (1)
- Georg Fuchsbauer (1)
- Chaya Ganesh (1)
- Sanjam Garg (1)
- Esha Ghosh (1)
- Mohammad Hajiabadi (1)
- Alexander Healy (1)
- Yuval Ishai (1)
- Seny Kamara (1)
- Markulf Kohlweiss (8)
- Daniel Kraschewski (1)
- Jialin Li (1)
- Tianren Liu (1)
- Feng-Hao Liu (1)
- Anna Lysyanskaya (8)
- Tal Malkin (1)
- Mary Maller (1)
- Sarah Meiklejohn (5)
- Peihan Miao (2)
- Payman Mohassel (1)
- Ryo Nishimaki (3)
- Miyako Ohkubo (2)
- Rafail Ostrovsky (2)
- Trevor Perrin (1)
- Oxana Poburinnaya (1)
- Leonid Reyzin (1)
- Hovav Shacham (1)
- Vinod Vaikuntanathan (2)
- Serge Vaudenay (1)
- Ivan Visconti (2)
- Keita Xagawa (1)
- Greg Zaverucha (1)