International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Anna Lysyanskaya

Publications

Year
Venue
Title
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