CryptoDB
Quasi-Linear Indistinguishability Obfuscation via Mathematical Proofs of Equivalence and Applications
| Authors: |
|
|---|---|
| Download: | |
| Conference: | EUROCRYPT 2025 |
| Abstract: | Indistinguishability obfuscation (iO) is a powerful crypto- graphic primitive and has been quoted as the “swiss army-knife of mod- ern cryptography”. Most prior works on iO focused on theoretical feasi- bility, and paid less attention to the efficiency of the constructions. As a result, all prior constructions stopped at achieving polynomial efficiency without worrying about how large the polynomial is. In fact, it has even been conjectured that a polynomial dependence on the input length is necessary. In this work, we show that if the two circuits to be obfuscated enjoy a succinct propositional logic proof of equivalence, then we can create obfuscated versions of these programs that are computationally indistin- guishable; and importantly, the resulting obfuscation’s efficiency is quasi- linear in the circuit size and proof size. We show that our quasi-linear iO construction also leads to new application. Specifically, we show how to achieve quasilinear efficiency for 1) iO for Turing Machines with un- bounded inputs, and 2) multi-input functional encryption, also assuming succinct proofs of equivalence. |
BibTeX
@inproceedings{eurocrypt-2025-35042,
title={Quasi-Linear Indistinguishability Obfuscation via Mathematical Proofs of Equivalence and Applications},
publisher={Springer-Verlag},
author={Chenxin Dai and Yaohua Ma and Elaine Shi},
year=2025
}