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

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in EUROCRYPT 2017
Keywords
DerandomizationPublic-Key EncryptionIndistinguishability ObfuscationCorrectness
Contact author(s)
nbitansky @ gmail com
History
2017-02-14: revised
2015-11-26: received
See all versions
Short URL
https://ia.cr/2015/1130
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1130,
      author = {Nir Bitansky and Vinod Vaikuntanathan},
      title = {A Note on Perfect Correctness by Derandomization},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1130},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1130}},
      url = {https://eprint.iacr.org/2015/1130}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.