## 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
📺
Abstract

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.

2022

TCC

Poly Onions: Achieving Anonymity in the Presence of Churn
Abstract

Onion routing is a popular approach towards anonymous communication. Practical implementations are widely used (for example, Tor has millions of users daily), but are vulnerable to various traffic correlation attacks, and the theoretical foundations, despite recent progress, still lag behind.
In particular, all works that model onion routing protocols and prove their security only address a single run, where each party sends and receives a single message of fixed length, once. Moreover, they all assume a static network setting, where the parties are stable throughout the lifetime of the protocol. In contrast, real networks have a high rate of churn (nodes joining and exiting the network), real users want to send multiple messages, and realistic adversaries may observe multiple runs of the protocol.
We initiate a formal treatment of onion routing in a setting with multiple runs over a dynamic network with churn. We provide definitions of both security and anonymity in this setting, and constructions that satisfy them. In particular, we define a new cryptographic primitive called \emph{Poly Onions} and show that it can be used to realize our definitions.

2022

TCC

Universally Composable Sigma-protocols in the Global Random-Oracle Model
Abstract

Numerous cryptographic applications require efficient non-interactive zero-knowledge proofs of knowledge (NIZKPoK) as a building block. Typically they rely on the Fiat-Shamir heuristic to do so, as security in the random-oracle model is considered good enough in practice. However, there is a troubling disconnect between the stand-alone security of such a protocol and its security as part of a larger, more complex system where several protocols may be running at the same time. Provable security in the general universal composition model (GUC model) of Canetti et al. is the best guarantee that nothing will go wrong when a system is part of a larger whole, even when all parties share a common random oracle. In this paper, we prove the minimal necessary properties of generally universally composable (GUC) NIZKPoK in any global random-oracle model, and show how to achieve efficient and GUC NIZKPoK in both the restricted programmable and restricted observable (non-programmable) global random-oracle models.

2021

TCC

Cryptographic Shallots: A Formal Treatment of Repliable Onion Encryption
📺
Abstract

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
Abstract

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
Abstract

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

2001

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

#### Coauthors

- Prabhanjan Ananth (1)
- Megumi Ando (2)
- Foteini Baldimtsi (1)
- Mira Belenkiy (2)
- Jan Camenisch (8)
- Rutchathon Chairattana-Apirom (1)
- Melissa Chase (8)
- Miranda Christ (1)
- Dana Dachman-Soled (2)
- Apoorvaa Deshpande (1)
- Nils Fleischhacker (2)
- Rosario Gennaro (1)
- Lucjan Hanzlik (1)
- Alexander Healy (1)
- Susan Hohenberger (2)
- Stanislaw Jarecki (1)
- Yael Tauman Kalai (1)
- Jonathan Katz (2)
- Markulf Kohlweiss (5)
- Anja Lehmann (1)
- Moses Liskov (1)
- Feng-Hao Liu (1)
- Julian Loss (1)
- Tal Malkin (3)
- Sarah Meiklejohn (3)
- Mira Meyerovich (1)
- Silvio Micali (3)
- Gregory Neven (1)
- Chris Peikert (1)
- Tal Rabin (1)
- Leonid Reyzin (3)
- Leah Namisa Rosenbloom (1)
- Dominique Schröder (2)
- Hovav Shacham (2)
- Adam Smith (1)
- Nikos Triandopoulos (1)
- Benedikt Wagner (1)