Cryptology ePrint Archive: Report 2015/1130

A Note on Perfect Correctness by Derandomization

Nir Bitansky and 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].

Category / Keywords: foundations / Derandomization, Public-Key Encryption, Indistinguishability Obfuscation, Correctness

Original Publication (with minor differences): IACR-EUROCRYPT-2017

Date: received 23 Nov 2015, last revised 13 Feb 2017

Contact author: nbitansky at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20170214:041059 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]