International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

A Note on Perfect Correctness by Derandomization

Authors:
Nir Bitansky
Vinod Vaikuntanathan
Download:
DOI: 10.1007/s00145-022-09428-0
Search ePrint
Search Google
Abstract: We show a general compiler that transforms a large class of erroneous cryptographic schemes (such as public-key encryption, indistinguishability obfuscation, and secure multiparty computation schemes) into perfectly correct ones. The transformation works for schemes that are correct on all inputs 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 2O(n) 2 O ( n ) and non-deterministic circuit complexity 2Ω(n) 2 Ω ( n ) . Our transformation complements previous results that showed how public-key encryption and indistinguishability obfuscation that err on a noticeable fraction of inputs can be turned into ones that for all inputs are often correct, showing that they can be made perfectly correct. The technique relies on the idea of “reverse randomization” [Naor, Crypto 1989] and on Nisan–Wigderson style derandomization, previously used in cryptography to remove interaction from witness-indistinguishable proofs and commitment schemes [Barak, Ong and Vadhan, Crypto 2003].
BibTeX
@article{jofc-2022-32791,
  title={A Note on Perfect Correctness by Derandomization},
  journal={Journal of Cryptology},
  publisher={Springer},
  volume={35},
  doi={10.1007/s00145-022-09428-0},
  author={Nir Bitansky and Vinod Vaikuntanathan},
  year=2022
}