Paper 2024/1815
Succinct Randomized Encodings from Laconic Function Evaluation, Faster and Simpler
Abstract
Succinct randomized encodings allow encoding the input $x$ of a time-$t$ uniform computation $M(x)$ in sub-linear time $o(t)$. The resulting encoding $\tilde{x}$ allows recovering the result of the computation $M(x)$, but hides any other information about $x$. These encodings have powerful applications, including time-lock puzzles, reducing communication in MPC, and bootstrapping advanced encryption schemes. Until not long ago, the only known constructions were based on indistinguishability obfuscation, and in particular were not based on standard post-quantum assumptions. In terms of efficiency, these constructions' encoding time is $\rm{polylog}(t)$, essentially the best one can hope for. Recently, a new construction was presented based on Circular Learning with Errors, an assumption similar to the one used in fully-homomorphic encryption schemes, and which is widely considered to be post-quantum resistant. However, the encoding efficiency significantly falls behind obfuscation-based scheme and is $\approx \sqrt{t} \cdot s$, where $s$ is the space of the computation. We construct, under the same assumption, succinct randomized encodings with encoding time $\approx t^{\varepsilon} \cdot s$ for arbitrarily small constant $\varepsilon<1$. Our construction is relatively simple, generic and relies on any laconic function evaluation scheme that satisfies a natural "efficiency preservation" property. Under sub-exponential assumptions, the encoding time can be further reduced to $\approx \sqrt{s}$, but at the account of a huge security loss. As a corollary, assuming also bounded-space languages that are worst-case hard-to-parallelize, we obtain time-lock puzzles with an arbitrary polynomial gap between encoding and decoding times.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- randomized encodingstime-lock puzzles
- Contact author(s)
-
nbitansky @ gmail com
rg5134 @ cims nyu edu - History
- 2025-01-27: revised
- 2024-11-06: received
- See all versions
- Short URL
- https://ia.cr/2024/1815
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1815, author = {Nir Bitansky and Rachit Garg}, title = {Succinct Randomized Encodings from Laconic Function Evaluation, Faster and Simpler}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1815}, year = {2024}, url = {https://eprint.iacr.org/2024/1815} }