ECCC-Report TR15-187https://eccc.weizmann.ac.il/report/2015/187Comments and Revisions published for TR15-187en-usTue, 14 Feb 2017 05:55:56 +0200
Revision 1
| A Note on Perfect Correctness by Derandomization |
Nir Bitansky,
Vinod Vaikuntanathan
https://eccc.weizmann.ac.il/report/2015/187#revision1In 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].Tue, 14 Feb 2017 05:55:56 +0200https://eccc.weizmann.ac.il/report/2015/187#revision1
Paper TR15-187
| A Note on Perfect Correctness by Derandomization |
Nir Bitansky,
Vinod Vaikuntanathan
https://eccc.weizmann.ac.il/report/2015/187
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].Tue, 24 Nov 2015 20:52:44 +0200https://eccc.weizmann.ac.il/report/2015/187