International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Payman Mohassel

Affiliation: Visa Research, USA

Publications

Year
Venue
Title
2021
PKC
BETA: Biometric-Enabled Threshold Authentication 📺
In the past decades, user authentication has been dominated by server-side password-based solutions that rely on ``what users know". This approach is susceptible to breaches and phishing attacks, and poses usability challenges. As a result, the industry is gradually moving to biometric-based client-side solutions that do not store any secret information on servers. This shift necessitates the safe storage of biometric templates and private keys, which are used to generate tokens, on user devices. We propose a new generic framework called Biometric Enabled Threshold Authentication (BETA) to protect sensitive client-side information like biometric templates and cryptographic keys. Towards this, we formally introduce the notion of Fuzzy Threshold Tokenizer (FTT) where an initiator can use a ``close'' biometric measurement to generate an authentication token if at least t (the threshold) devices participate. We require that the devices only talk to the initiator, and not to each other, to capture the way user devices are connected in the real world. We use the universal composability (UC) framework to model the security properties of FTT, including the unforgeability of tokens and the privacy of the biometric values (template and measurement), under a malicious adversary. We construct three protocols that meet our definition. Our first two protocols are general feasibility results that work for any distance function, any threshold t and tolerate the maximal (i.e. t-1) amount of corruption. They are based on any two round UC-secure multi-party computation protocol in the standard model (with a CRS) and threshold fully homomorphic encryption, respectively. We show how to effectively use these primitives to build protocols in a constrained communication model with just four rounds of communication. For the third protocol, we consider inner-product based distance metrics (cosine similarity, Euclidean distance, etc.) specifically, motivated by the recent interest in its use for face recognition. We use Paillier encryption, efficient NIZKs for specific languages, and a simple garbled circuit to build an efficient protocol for the common case of n=3 devices with one compromised.
2021
PKC
Private Set Operations from Oblivious Switching 📺
Private set intersection reveals the intersection of two private sets, but many real-world applications require the parties to learn $\textit{only}$ partial information} about the intersection. In this paper, we introduce a new approach for computing arbitrary functions of the intersection, provided that it is safe to also reveal the cardinality of the intersection. In the most general case, our new protocol provides the participants with secret shares of the intersection, which can be fed into any generic 2PC protocol. Certain computations on the intersection can also be done even more directly and efficiently, avoiding this secret-sharing step. These cases include computing $\textit{only}$ the cardinality of the intersection, or the ``cardinality-sum'' application proposed in Ion $\textit{et al.}$ (ePrint 2017). Compared to the state-of-the-art protocol for computing on the intersection (Pinkas et al., Eurocrypt 2019), our protocol has about $2.5-3\times$ less communication and has faster running time on slower (50Mbps) networks. Our new techniques can also be used to privately compute the {\em union} of two sets as easily as computing the intersection. Our protocol concretely improves the leading private set union protocol (Kolesnikov et al., Asiacrypt 2020) by a factor of $2-2.5\times$, depending on the network speed. We then show how private set union can be used in a simple way to realize the ``Private-ID'' functionality suggested by Buddhavarapu et al.~(ePrint 2020). Our protocol is significantly faster than the prior Private-ID protocol, especially on fast networks. All of our protocols are in the two-party setting and are secure against semi-honest adversaries.
2018
CRYPTO
Non-Interactive Zero-Knowledge Proofs for Composite Statements 📺
Shashank Agrawal Chaya Ganesh Payman Mohassel
The two most common ways to design non-interactive zero-knowledge (NIZK) proofs are based on Sigma protocols and QAP-based SNARKs. The former is highly efficient for proving algebraic statements while the latter is superior for arithmetic representations.   Motivated by applications such as privacy-preserving credentials and privacy-preserving audits in cryptocurrencies, we study the design of NIZKs for composite statements that compose algebraic and arithmetic statements in arbitrary ways. Specifically, we provide a framework for proving statements that consist of ANDs, ORs and function compositions of a mix of algebraic and arithmetic components. This allows us to explore the full spectrum of trade-offs between proof size, prover cost, and CRS size/generation cost. This leads to proofs for statements of the form: knowledge of x such that $$SHA(g^x)=y$$SHA(gx)=y for some public y where the prover’s work is 500 times fewer exponentiations compared to a QAP-based SNARK at the cost of increasing the proof size to 2404 group and field elements. In application to anonymous credentials, our techniques result in 8 times fewer exponentiations for the prover at the cost of increasing the proof size to 298 elements.
2017
EUROCRYPT
2017
EUROCRYPT
2016
CRYPTO
2016
CRYPTO
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
TCC
2015
EUROCRYPT
2015
CRYPTO
2014
CRYPTO
2014
EUROCRYPT
2014
PKC
2014
EPRINT
2014
EPRINT
2014
ASIACRYPT
2013
PKC
2013
CRYPTO
2013
EUROCRYPT
2010
ASIACRYPT
2010
EUROCRYPT
2009
EPRINT
Communication-Efficient Private Protocols for Longest Common Subsequence
Matthew Franklin Mark Gondree Payman Mohassel
We design communication efficient two-party and multi-party protocols for the longest common subsequence (LCS) and related problems. Our protocols achieve privacy with respect to passive adversaries, under reasonable cryptographic assumptions. We benefit from the somewhat surprising interplay of an efficient block-retrieval PIR (Gentry-Ramzan, ICALP 2005) with the classic “four Russians” algorithmic design. This result is the first improvement to the communication complexity for this application over generic results (such as Yao’s garbled circuit protocol) and, as such, is interesting as a contribution to the theory of communication efficiency for secure two-party and multiparty applications.
2008
EUROCRYPT
2008
CRYPTO
2007
ASIACRYPT
2007
TCC
2007
EPRINT
Multi-Party Indirect Indexing and Applications
Matthew Franklin Mark Gondree Payman Mohassel
We develop a new multi-party generalization of Naor-Nissim indirect indexing, making it possible for many participants to simulate a RAM machine with only poly-logarithmic blow-up. Our most efficient instantiation (built from length-flexible additively homomorphic public key encryption) improves the communication complexity of secure multi-party computation for a number of problems in the literature. Underlying our approach is a new multi-party variant of oblivious transfer which may be of independent interest.
2006
PKC
2006
PKC
2006
EPRINT
Computational Soundness of Formal Indistinguishability and Static Equivalence
Gergei Bana Payman Mohassel Till Stegers
In the research of the relationship between the formal and the computational view of cryptography, a recent approach uses static equivalence from cryptographic pi calculi as a notion of formal indistinguishability. Previous work has shown that this yields the soundness of natural interpretations of some interesting equational theories, such as certain cryptographic operations and a theory of XOR. In this paper however, we argue that static equivalence is too coarse for sound interpretations of equational theories in general. We show some explicit examples how static equivalence fails to work in interesting cases. To fix this problem, we propose a notion of formal indistinguishability that is more flexible than static equivalence. We provide a general framework along with general theorems, and then discuss how this new notion works for the explicit examples where static equivalence failed to ensure soundness. We also improve the treatment by using ordered sorts in the formal view, and by allowing arbitrary probability distributions of the interpretations.
2006
EPRINT
Improved Efficiency for Private Stable Matching
Matthew Franklin Mark Gondree Payman Mohassel
At Financial Crypto 2006, Golle presented a novel framework for the privacy preserving computation of a stable matching (stable marriage). We show that the communication complexity of Golle's main protocol is substantially greater than what was claimed in that paper, in part due to surprising pathological behavior of Golle's variant of the Gale-Shapley stable matching algorithm. We also develop new protocols in Golle's basic framework with greatly reduced communication complexity.

Program Committees

PKC 2018
Crypto 2017
Crypto 2016
Crypto 2014
Eurocrypt 2014
Asiacrypt 2011
Asiacrypt 2010