Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR15-187 | 14th February 2017 05:55

#### A Note on Perfect Correctness by Derandomization

Revision #1
Authors: Nir Bitansky, Vinod Vaikuntanathan
Accepted on: 14th February 2017 05:55
Downloads: 597
Keywords:

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

### Paper:

TR15-187 | 24th November 2015 03:14

#### A Note on Perfect Correctness by Derandomization

TR15-187
Authors: Nir Bitansky, Vinod Vaikuntanathan
Publication: 24th November 2015 20:52
Downloads: 1514
Keywords:

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

ISSN 1433-8092 | Imprint