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 >>>

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 >>>

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 >>>