All reports by Author Dakshita Khurana:

__
TR18-203
| 1st December 2018
__

Yael Kalai, Dakshita Khurana#### Non-Interactive Non-Malleability from Quantum Supremacy

__
TR18-009
| 9th January 2018
__

Saikrishna Badrinarayanan, Yael Kalai, Dakshita Khurana, Amit Sahai, Daniel Wichs#### Non-Interactive Delegation for Low-Space Non-Deterministic Computation

__
TR17-100
| 7th June 2017
__

Dakshita Khurana, Amit Sahai#### How to Achieve Non-Malleability in One or Two Rounds

Yael Kalai, Dakshita Khurana

We construct non-interactive non-malleable commitments with respect to replacement, without setup in the plain model, under well-studied assumptions.

First, we construct non-interactive non-malleable commitments with respect to commitment for $\epsilon \log \log n$ tags for a small constant $\epsilon>0$, under the following assumptions:

- Sub-exponential hardness of factoring or discrete ... more >>>

Saikrishna Badrinarayanan, Yael Kalai, Dakshita Khurana, Amit Sahai, Daniel Wichs

We construct a delegation scheme for verifying non-deterministic computations, with complexity proportional only to the non-deterministic space of the computation. Specifi cally, letting $n$ denote the input length, we construct a delegation scheme for any language veri fiable in non-deterministic time and space $(T(n);S(n))$ with communication complexity $poly(S(n))$, verifi er ... more >>>

Dakshita Khurana, Amit Sahai

Despite over 25 years of research on non-malleable commitments in the plain model, their round complexity has remained open. The goal of achieving non-malleable commitment protocols with only one or two rounds has been especially elusive. Pass (TCC 2013, CC 2016) captured this difficulty by proving important impossibility results regarding ... more >>>