## CryptoDB

### Divesh Aggarwal

#### Publications

**Year**

**Venue**

**Title**

2021

EUROCRYPT

A 2^{n/2}-Time Algorithm for \sqrt{n}-SVP and \sqrt{n}-Hermite SVP, and an Improved Time-Approximation Tradeoff for (H)SVP
Abstract

We show a 2^{n/2+o(n)}-time algorithm that, given as input a basis of a lattice $\lat \subset \R^n$, finds a (non-zero) vector in whose length is at most $\widetilde{O}(\sqrt{n})\cdot \min\{\lambda_1(\lat), \det(\lat)^{1/n}\}$, where $\lambda_1(\lat)$ is the length of a shortest non-zero lattice vector and $\det(\lat)$ is the lattice determinant. Minkowski showed that $\lambda_1(\lat) \leq \sqrt{n} \det(\lat)^{1/n}$ and that there exist lattices with $\lambda_1(\lat) \geq \Omega(\sqrt{n}) \cdot \det(\lat)^{1/n}$, so that our algorithm finds vectors that are as short as possible relative to the determinant (up to a polylogarithmic factor).
The main technical contribution behind this result is new analysis of (a simpler variant of) a 2^{n/2 + o(n)}-time algorithm from [ADRS15], which was only previously known to solve less useful problems. To achieve this, we rely crucially on the ``reverse Minkowski theorem'' (conjectured by Dadush [DR16] and proven by [RS17]), which can be thought of as a partial converse to the fact that $\lambda_1(\lat) \leq \sqrt{n} \det(\lat)^{1/n}$.
Previously, the fastest known algorithm for finding such a vector was the 2^{0.802n + o(n)}-time algorithm due to [LWXZ11], which actually found a non-zero lattice vector with length $O(1) \cdot \lambda_1(\lat)$. Though we do not show how to find lattice vectors with this length in time $2^{n/2+o(n)}$, we do show that our algorithm suffices for the most important application of such algorithms: basis reduction. In particular, we show a modified version of Gama and Nguyen's slide-reduction algorithm [GN08], which can be combined with the algorithm above to improve the time-length tradeoff for shortest-vector algorithms in nearly all regimes---including the regimes relevant to cryptography.

2020

EUROCRYPT

How to Extract Useful Randomness from Unreliable Sources
📺
Abstract

For more than 30 years, cryptographers have been looking for public sources of uniform randomness in order to use them as a set-up to run appealing cryptographic protocols without relying on trusted third parties. Unfortunately, nowadays it is fair to assess that assuming the existence of physical phenomena producing public uniform randomness is far from reality.
It is known that uniform randomness cannot be extracted from a single weak source. A well-studied way to overcome this is to consider several independent weak sources. However, this means we must trust the various sampling processes of weak randomness from physical processes.
Motivated by the above state of affairs, this work considers a set-up where players can access multiple {\em potential} sources of weak randomness, several of which may be jointly corrupted by a computationally unbounded adversary. We introduce {\em SHELA} (Somewhere Honest Entropic Look Ahead) sources to model this situation.
We show that there is no hope of extracting uniform randomness from a {\em SHELA} source. Instead, we focus on the task of {\em Somewhere-Extraction} (i.e., outputting several candidate strings, some of which are uniformly distributed -- yet we do not know which). We give explicit constructions of {\em Somewhere-Extractors} for {\em SHELA} sources with good parameters.
Then, we present applications of the above somewhere-extractor where the public uniform randomness can be replaced by the output of such extraction from corruptible sources, greatly outperforming trivial solutions. The output of somewhere-extraction is also useful in other settings, such as a suitable source of random coins for many randomized algorithms.
In another front, we comprehensively study the problem of {\em Somewhere-Extraction} from a {\em weak} source, resulting in a series of bounds. Our bounds highlight the fact that, in most regimes of parameters (including those relevant for applications), {\em SHELA} sources significantly outperform {\em weak} sources of comparable parameters both when it comes to the process of {\em Somewhere-Extraction}, or in the task of amplification of success probability in randomized algorithms. Moreover, the low quality of somewhere-extraction from weak sources excludes its use in various efficient applications.

2020

CRYPTO

Slide Reduction, Revisited—Filling the Gaps in SVP Approximation
📺
Abstract

We show how to generalize Gama and Nguyen's slide reduction algorithm [STOC '08] for solving the approximate Shortest Vector Problem over lattices (SVP) to allow for arbitrary block sizes, rather than just block sizes that divide the rank n of the lattice. This leads to significantly better running times for most approximation factors. We accomplish this by combining slide reduction with the DBKZ algorithm of Micciancio and Walter [Eurocrypt '16].
We also show a different algorithm that works when the block size is quite large---at least half the total rank. This yields the first non-trivial algorithm for sublinear approximation factors.
Together with some additional optimizations, these results yield significantly faster provably correct algorithms for \delta-approximate SVP for all approximation factors n^{1/2+\eps} \leq \delta \leq n^{O(1)}, which is the regime most relevant for cryptography. For the specific values of \delta = n^{1-\eps} and \delta = n^{2-\eps}, we improve the exponent in the running time by a factor of 2 and a factor of 1.5 respectively.

2019

EUROCRYPT

Continuous Non-Malleable Codes in the 8-Split-State Model
📺
Abstract

Non-malleable codes (NMCs), introduced by Dziembowski, Pietrzak and Wichs [20], provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. NMCs have emerged as a fundamental object at the intersection of coding theory and cryptography. In particular, progress in the study of non-malleable codes and the related notion of non-malleable extractors has led to new insights and progress on even more fundamental problems like the construction of multi-source randomness extractors. A large body of the recent work has focused on various constructions of non-malleable codes in the split-state model. Many variants of NMCs have been introduced in the literature, e.g., strong NMCs, super strong NMCs and continuous NMCs. The most general, and hence also the most useful notion among these is that of continuous non-malleable codes, that allows for continuous tampering by the adversary. We present the first efficient information-theoretically secure continuously non-malleable code in the constant split-state model. We believe that our main technical result could be of independent interest and some of the ideas could in future be used to make progress on other related questions.

2019

EUROCRYPT

A Quantum-Proof Non-malleable Extractor
📺
Abstract

In privacy amplification, two mutually trusted parties aim to amplify the secrecy of an initial shared secret X in order to establish a shared private key K by exchanging messages over an insecure communication channel. If the channel is authenticated the task can be solved in a single round of communication using a strong randomness extractor; choosing a quantum-proof extractor allows one to establish security against quantum adversaries.In the case that the channel is not authenticated, this simple solution is no longer secure. Nevertheless, Dodis and Wichs (STOC’09) showed that the problem can be solved in two rounds of communication using a non-malleable extractor, a stronger pseudo-random construction than a strong extractor.We give the first construction of a non-malleable extractor that is secure against quantum adversaries. The extractor is based on a construction by Li (FOCS’12), and is able to extract from source of min-entropy rates larger than 1 / 2. Combining this construction with a quantum-proof variant of the reduction of Dodis and Wichs, due to Cohen and Vidick (unpublished) we obtain the first privacy amplification protocol secure against active quantum adversaries.

2019

CRYPTO

Stronger Leakage-Resilient and Non-Malleable Secret Sharing Schemes for General Access Structures
📺
Abstract

In this work we present a collection of compilers that take secret sharing schemes for an arbitrary access structure as input and produce either leakage-resilient or non-malleable secret sharing schemes for the same access structure. A leakage-resilient secret sharing scheme hides the secret from an adversary, who has access to an unqualified set of shares, even if the adversary additionally obtains some size-bounded leakage from all other secret shares. A non-malleable secret sharing scheme guarantees that a secret that is reconstructed from a set of tampered shares is either equal to the original secret or completely unrelated. To the best of our knowledge we present the first generic compiler for leakage-resilient secret sharing for general access structures. In the case of non-malleable secret sharing, we strengthen previous definitions, provide separations between them, and construct a non-malleable secret sharing scheme for general access structures that fulfills the strongest definition with respect to independent share tampering functions. More precisely, our scheme is secure against concurrent tampering: The adversary is allowed to (non-adaptively) tamper the shares multiple times, and in each tampering attempt can freely choose the qualified set of shares to be used by the reconstruction algorithm to reconstruct the tampered secret. This is a strong analogue of the multiple-tampering setting for split-state non-malleable codes and extractors.We show how to use leakage-resilient and non-malleable secret sharing schemes to construct leakage-resilient and non-malleable threshold signatures. Classical threshold signatures allow to distribute the secret key of a signature scheme among a set of parties, such that certain qualified subsets can sign messages. We construct threshold signature schemes that remain secure even if an adversary leaks from or tampers with all secret shares.

2018

CRYPTO

A New Public-Key Cryptosystem via Mersenne Numbers
📺
Abstract

In this work, we propose a new public-key cryptosystem whose security is based on the computational intractability of the following problem: Given a Mersenne number
$$p = 2^n - 1$$
p=2n-1, where n is a prime, a positive integer h, and two n-bit integers T, R, decide whether their exist n-bit integers F, G each of Hamming weight less than h such that
$$T = F\cdot R + G$$
T=F·R+G modulo p.

2011

ASIACRYPT

2008

EPRINT

FACTORING IS EQUIVALENT TO GENERIC RSA
Abstract

We show that a generic ring algorithm for breaking RSA in
$\mathbb{Z}_N$ can be converted into an algorithm for factoring the
corresponding RSA-modulus $N$. Our results imply that any attempt at
breaking RSA without factoring $N$ will be non-generic and hence
will have to manipulate the particular bit-representation of the
input in $\mathbb{Z}_N$. This provides new evidence that breaking
RSA may be equivalent to factoring the modulus.

2008

EPRINT

Breaking RSA Generically is Equivalent to Factoring
Abstract

We show that a generic ring algorithm for breaking RSA in
$\mathbb{Z}_N$ can be converted into an algorithm for factoring the
corresponding RSA-modulus $N$. Our results imply that any attempt at
breaking RSA without factoring $N$ will be non-generic and hence
will have to manipulate the particular bit-representation of the
input in $\mathbb{Z}_N$. This provides new evidence that breaking RSA may be equivalent to factoring the modulus.

#### Program Committees

- Eurocrypt 2020
- TCC 2018

#### Coauthors

- Shashank Agrawal (2)
- Kai-Min Chung (1)
- Ivan Damgård (1)
- Yevgeniy Dodis (1)
- Nico Döttling (1)
- Stefan Dziembowski (1)
- Alexander Golovnev (1)
- Divya Gupta (2)
- Zahra Jafargholi (1)
- Antoine Joux (1)
- Tomasz Kazana (3)
- Zeyong Li (1)
- Jianwei Li (1)
- Han-Hsuan Lin (1)
- Hemanta K. Maji (2)
- Ueli Maurer (4)
- Eric Miles (1)
- Phong Q. Nguyen (1)
- Jesper Buus Nielsen (2)
- Maciej Obremski (6)
- Omkant Pandey (2)
- Manoj Prabhakaran (2)
- Anupam Prakash (1)
- Erick Purwanto (2)
- Leonid Reyzin (1)
- João Ribeiro (2)
- Miklos Santha (1)
- Mark Simkin (1)
- Luisa Siniscalchi (1)
- Noah Stephens-Davidowitz (2)
- Thomas Vidick (1)
- Ivan Visconti (1)