International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Anna Lysyanskaya

Publications

Year
Venue
Title
2022
CRYPTO
PI-Cut-Choo and Friends: Compact Blind Signatures via Parallel Instance Cut-and-Choose and More
Blind signature schemes are one of the best-studied tools for privacy-preserving authentication. Unfortunately, known constructions of provably secure blind signatures either rely on non-standard hardness assumptions, or require parameters that grow linearly with the number of concurrently issued signatures, or involve prohibitively inefficient general techniques such as general secure two-party computation. Recently, Katz, Loss and Rosenberg (ASIACRYPT'21) gave a technique that, for the security parameter n, transforms blind signature schemes secure for O(log n) concurrent executions of the blind signing protocol into ones that are secure for any poly(n) concurrent executions. This transform has two drawbacks that we eliminate in this paper: 1) the communication complexity of the resulting blind signing protocol grows linearly with the number of signing interactions; 2) the resulting schemes inherit a very loose security bound from the underlying scheme and, as a result, require impractical parameter sizes. In this work, we give an improved transform for obtaining a secure blind signing protocol tolerating any poly(n) concurrent executions from one that is secure for O(log n) concurrent executions. While preserving the advantages of the original transform, the communication complexity of our new transform only grows logarithmically with the number of interactions. Under the CDH and RSA assumptions, we improve on this generic transform in terms of concrete efficiency and give (1) a BLS-based blind signature scheme over a standard-sized group where signatures are of size roughly 3 KB and communication per signature is roughly 120 KB; and (2) an Okamoto-Guillou-Quisquater-based blind signature scheme with signatures and communication of roughly 9 KB and 8 KB, respectively.
2021
TCC
Cryptographic Shallots: A Formal Treatment of Repliable Onion Encryption 📺
Megumi Ando Anna Lysyanskaya
Onion routing is a popular, efficient, and scalable method for enabling anonymous communications. To send a message m to Bob via onion routing, Alice picks several intermediaries, wraps m in multiple layers of encryption --- a layer per intermediary --- and sends the resulting “onion” to the first intermediary. Each intermediary “peels off'”a layer of encryption and learns the identity of the next entity on the path and what to send along; finally Bob learns that he is the recipient and recovers the message m. Despite its wide use in the real world (e.g., Mixminion), the foundations of onion routing have not been thoroughly studied. In particular, although two-way communication is needed in most instances, such as anonymous Web browsing or anonymous access to a resource, until now no definitions or provably secure constructions have been given for two-way onion routing. Moreover, the security definitions that existed even for one-way onion routing were found to have significant flaws. In this paper, we (1) propose an ideal functionality for a repliable onion encryption scheme; (2) give a game-based definition for repliable onion encryption and show that it is sufficient to realize our ideal functionality; and finally (3), our main result is a construction of repliable onion encryption that satisfies our definitions.
2019
TCC
Fully Homomorphic NIZK and NIWI Proofs
In this work, we define and construct fully homomorphic non-interactive zero knowledge (FH-NIZK) and non-interactive witness-indistinguishable (FH-NIWI) proof systems.     We focus on the NP complete language L, where, for a boolean circuit C and a bit b, the pair $$(C,b)\in L$$ if there exists an input $$\mathbf {w}$$ such that $$C(\mathbf {w})=b$$. For this language, we call a non-interactive proof system fully homomorphic if, given instances $$(C_i,b_i)\in L$$ along with their proofs $$\varPi _i$$, for $$i\in \{1,\ldots ,k\}$$, and given any circuit $$D:\{0,1\}^k\rightarrow \{0,1\}$$, one can efficiently compute a proof $$\varPi $$ for $$(C^*,b)\in L$$, where $$C^*(\mathbf {w}^{(1)},\ldots ,\mathbf {w}^{(k)})=D(C_1(\mathbf {w}^{(1)}),\ldots ,C_k(\mathbf {w}^{(k)}))$$ and $$D(b_1,\ldots ,b_k)=b$$. The key security property is unlinkability: the resulting proof $$\varPi $$ is indistinguishable from a fresh proof of the same statement.     Our first result, under the Decision Linear Assumption (DLIN), is an FH-NIZK proof system for L in the common random string model. Our more surprising second result (under a new decisional assumption on groups with bilinear maps) is an FH-NIWI proof system that requires no setup.
2019
JOFC
Feasibility and Infeasibility of Secure Computation with Malicious PUFs
A recent line of work has explored the use of physically unclonable functions (PUFs) for secure computation, with the goals of (1) achieving universal composability without additional setup and/or (2) obtaining unconditional security (i.e., avoiding complexity-theoretic assumptions). Initial work assumed that all PUFs, even those created by an attacker, are honestly generated. Subsequently, researchers have investigated models in which an adversary can create malicious PUFs with arbitrary behavior. Researchers have considered both malicious PUFs that might be stateful , as well as malicious PUFs that can have arbitrary behavior but are guaranteed to be stateless . We settle the main open questions regarding secure computation in the malicious-PUF model: We prove that unconditionally secure oblivious transfer is impossible, even in the stand-alone setting, if the adversary can construct (malicious) stateful PUFs. We show that if the attacker is limited to creating (malicious) stateless PUFs, then universally composable two-party computation is possible, unconditionally.
2014
CRYPTO
2014
CRYPTO
2013
PKC
2013
TCC
2013
ASIACRYPT
2012
EUROCRYPT
2012
CRYPTO
2009
CRYPTO
2009
PKC
2008
TCC
2007
CRYPTO
2006
CRYPTO
2006
CRYPTO
2006
PKC
2005
CRYPTO
2005
EUROCRYPT
2005
EUROCRYPT
2005
TCC
2004
CRYPTO
2004
EUROCRYPT
2004
TCC
2002
CRYPTO
2002
CRYPTO
2001
ASIACRYPT
2001
ASIACRYPT
2001
CRYPTO
2001
EUROCRYPT
2000
EUROCRYPT

Program Committees

Crypto 2020
TCC 2018
Crypto 2018
Eurocrypt 2017
PKC 2015
Asiacrypt 2013
Eurocrypt 2011
TCC 2011
Asiacrypt 2010
Eurocrypt 2009
Crypto 2009
Eurocrypt 2008
Asiacrypt 2007
Eurocrypt 2007
PKC 2007
TCC 2005
PKC 2005
Eurocrypt 2004
Crypto 2003