| Summary: | 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 oneway functions and of functions with deterministic (uniform) time complexity 2O(n) and
non-deterministic circuit complexity 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 witnessindistinguishable proofs and commitment schemes [Barak, Ong and Vadhan, Crypto
2003].
|
|---|