Welcome to the resource topic for 2024/1815
Title:
Succinct Randomized Encodings from Non-compact Functional Encryption, Faster and Simpler
Authors: Nir Bitansky, Rachit Garg
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. Such encodings are known to have powerful applications such as reducing communication in MPC, bootstrapping advanced encryption schemes, and constructing time-lock puzzles.
Until not long ago, the only known constructions were based on indistinguishability obfuscation, and in particular they 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 non-compact single-key functional encryption that satisfies a natural {\em efficiency preservation} property.
ePrint: https://eprint.iacr.org/2024/1815
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .