**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Person# Divesh Aggarwal

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related units

Loading

Courses taught by this person

Loading

Related research domains

Loading

Related publications

Loading

People doing similar research

Loading

Courses taught by this person

People doing similar research (58)

No results

Related publications (7)

Loading

Loading

Loading

Related research domains (2)

In communications and information processing, code is a system of rules to convert information—such as a letter, word, sound, image, or gesture—into another form, sometimes shortened or secret, for c

Malleability is a property of some cryptographic algorithms. An encryption algorithm is "malleable" if it is possible to transform a ciphertext into another ciphertext which decrypts to a related plai

Related units (2)

The study of seeded randomness extractors is a major line of research in theoretical computer science. The goal is to construct deterministic algorithms which can take a weak random source x with min-entropy k and a uniformly random seed Y of length d, and outputs a string of length close to k that is close to uniform and independent of Y. Dodis and Wichs [DW09] introduced a generalization of randomness extractors called non-malleable extractors (nmExt) where nmExt(X, Y) is close to uniform and independent of Y and nmExt(X, f(Y)) for any function f with no fixed points. We relax the notion of a non-malleable extractor and introduce what we call an affine-malleable extractor (AmExt : Fn x Fd -> F) where AmExt(X, Y ) is close to uniform and independent of Y and has some limited dependence of AmExt(X, f(Y )) - that conditioned on Y , (AmExt(X, Y ), AmExt(X, f(Y ))) is epsilon-close to (U, A U + B) where U is uniformly distributed in F and A, B is an element of F are random variables independent of U. We show that the inner-product function (,) : FnxFn -> F is an affine-malleable extractor for min-entropy k = n/2 + Omega(log(1/epsilon)). Moreover, under a plausible conjecture in additive combinatorics (called the Spectrum Doubling Conjecture), we show that this holds for k = Omega(log n log(1/epsilon)). As a modest justification of the conjecture, we show that a weaker version of the conjecture is implied by the widely believed Polynomial Freiman-Ruzsa conjecture. We also study the classical problem of privacy amplification, where two parties Alice and Bob share a weak secret X of min-entropy k, and wish to agree on secret key R of length m over a public communication channel completely controlled by a computationally unbounded attacker Eve. The main application of non-malleable extractors and their many variants has been in constructing secure privacy amplification protocols. We show that affine-malleable extractors along with affine-evasive sets can also be used to construct efficient privacy amplification protocols. This gives a much simpler protocol for min-entropy k = n/2 + Omega(log(1/epsilon)), and additionally, under the Spectrum Doubling Conjecture, achieves near optimal parameters and achieves additional security properties like source privacy that have been the focus of some recent results in privacy amplification.

The unique shortest vector problem on a rational lattice is the problem of finding the shortest non-zero vector under the promise that it is unique (up to multiplication by -1). We give several incremental improvements on the known hardness of the unique shortest vector problem (uSVP) using standard techniques. This includes a deterministic reduction from the shortest vector problem to the uSVP, the NP-hardness of uSVP on (1 + 1/poly(n))-unique lattices, and a proof that the decision version of uSVP defined by Cai [4] is in co-NP for n(1/4)-unique lattices. (C) 2016 Published by Elsevier B.V.

,

Non-malleable codes are a generalization of classical error-correcting codes where the act of "corrupting" a codeword is replaced by a "tampering" adversary. Non-malleable codes guarantee that the message contained in the tampered codeword is either the original message m, or a completely unrelated one. In the common split-state model, the codeword consists of multiple blocks (or states) and each block is tampered with independently. The central goal in the split-state model is to construct high rate non-malleable codes against all functions with only two states (which are necessary). Following a series of long and impressive line of work, constant rate, two-state, non-malleable codes against all functions were recently achieved by Aggarwal et al. [2]. Though constant, the rate of all known constructions in the split state model is very far from optimal (even with more than two states). In this work, we consider the question of improving the rate of splitstate non-malleable codes. In the "information theoretic" setting, it is not possible to go beyond rate 1/2. We therefore focus on the standard computational setting. In this setting, each tampering function is required to be efficiently computable, and the message in the tampered codeword is required to be either the original message m or a "computationally" independent one. In this setting, assuming only the existence of one-way functions, we present a compiler which converts any poor rate, two-state, (sufficiently strong) non-malleable code into a rate-1, two-state, computational non-malleable code. These parameters are asymptotically optimal. Furthermore, for the qualitative optimality of our result, we generalize the result of Cheraghchi and Guruswami [10] to show that the existence of one-way functions is necessary to achieve rate > 1/2 for such codes. Our compiler requires a stronger form of non-malleability, called augmented non-malleability. This notion requires a stronger simulation guarantee for non-malleable codes and simplifies their modular usage in cryptographic settings where composition occurs. Unfortunately, this form of non-malleability is neither straightforward nor generally guaranteed by known results. Nevertheless, we prove this stronger form of non-malleability for the two-state construction of Aggarwal et al. [3]. This result is of independent interest.