Welcome to the resource topic for 2015/1130
Title:
A Note on Perfect Correctness by Derandomization
Authors: Nir Bitansky, Vinod Vaikuntanathan
Abstract:In this note, we show how to transform a large class of erroneous cryptographic schemes into perfectly correct ones. The transformation works for schemes that are correct on every input with probability noticeably larger than half, and are secure under parallel repetition. We assume the existence of one-way functions and of functions with deterministic (uniform) time complexity 2^{O(n)} and non-deterministic circuit complexity 2^{\Omega(n)}. The transformation complements previous results showing that public-key encryption and indistinguishability obfuscation that err on a noticeable fraction of inputs can be turned into ones that are often correct {\em for all inputs}. The technique relies on the idea of ``reverse randomization’’ [Naor, Crypto 1989] and on Nisan-Wigderson style derandomization, which was previously used in cryptography to obtain non-interactive witness-indistinguishable proofs and commitment schemes [Barak, Ong and Vadhan, Crypto 2003].
ePrint: https://eprint.iacr.org/2015/1130
Talk: https://www.youtube.com/watch?v=klnJ2r73dGI
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 .