8
$\begingroup$

I hear there's a recent advance in Indistinguishability Obfuscation, aka , with emphasis on Aayush Jain, Huijia Li and Amit Sahai Indistinguishability Obfuscation from Well-Founded Assumptions (eprint and arXiv, August 2020).

For the applied cryptographer inexperienced in Indistinguishability Obfuscation, what's the big picture? What concrete problem does this aim to solve, preferably with orders of magnitude of the data and work required?

Improve this question
$\endgroup$
7
  • $\begingroup$ @kelalaka: what linked answer? All answers in the linked question are old. $\endgroup$
    – fgrieu ♦
    Commented Nov 10, 2020 at 18:36
  • $\begingroup$ The usage requirements don't change much. The first answer gives a need for the sofware developer. and the floor cat's answer, too. $\endgroup$
    – kelalaka
    Commented Nov 10, 2020 at 18:41
  • 1
    $\begingroup$ @Nic: ideally I'd like both! But I'd want at least to know what it can do, perhaps with an example of a concrete class of algorithms that it can obfuscate. $\endgroup$
    – fgrieu ♦
    Commented Nov 10, 2020 at 22:15
  • 1
    $\begingroup$ As the title suggests, the construction in the Jain-Li-Sahai paper is the first that is based on "standard" long-studied assumptions. The paper was a culmination of a long series of works that aimed at achieving this. $\endgroup$
    – ckamath
    Commented Nov 11, 2020 at 8:40
  • 1
    $\begingroup$ "So the advance would be mostly about the confidence we can have in the security, not in the kind or size of problems that can be addressed." Yes I suppose: the goal here is full-blown obfuscation (i.e., for all circuits) from standard assumptions. We already knew how to do obfuscation for some simpler tasks (e.g., point functions) from "standard" assumptions, but it is not clear if these functions have any useful applications. But we should wait for someone more knowledgeable in the area to verify this. $\endgroup$
    – ckamath
    Commented Nov 11, 2020 at 9:23

1 Answer 1

Reset to default
3
$\begingroup$

Indistinguishability obfuscation allows programs to run while they remain encrypted, including their internal data structures. This allows for a lot of things; just one example is programs can generate their own signing key so any computational process that we currently rely on a central authority for (e.g. verified software builds) we can now entrust to a computer program.

However, the recent advance is purely theoretical and we are still a long way away from implementing efficient IO. Wikipedia » Indistinguishability obfuscation:

There have been attempts to implement and benchmark IO candidates. For example, as of 2017, an obfuscation of the function $x_1 ∧ x_2 ∧ ⋯ ∧ x_{32}$ at a security level of 80 bits took 23.5 minutes to produce and measured 11.6 GB, with an evaluation time of 77 ms. Additionally, an obfuscation of the Advanced Encryption Standard encryption circuit at a security level of 128 bits would measure 18 PB and have an evaluation time of about 272 years.

Pellet--Mary, Alice (26 May 2020). "Co6GC: Program Obfuscation | COSIC". www.esat.kuleuven.be. Archived from the original on 11 November 2020. Retrieved 22 August 2021.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.