Indistinguishability obfuscation was something that until recently scientists considered unfeasible. We have known of this concept since 1996, but it was only in 2001 that Boaz Barak of Harvard University proposed it, proving that it does exist. But it is only in 2020 that there is such a proposal that could work. Let’s take a look at it.

What is obfuscation?

It’s a security feature that helps you hide your data and what you do from the eyes of those who would want to do you harm in that regard. Very often, obfuscators are used by programmers who have their resulting code “mutilated” so that it is not readable to the human eye. For example, renaming classes to a string of Chinese characters – easy for a computer, but difficult for a human to read the code. For many years, it was thought that perfect obfuscation was an unattainable goal and something we would probably never achieve.

What is indistinguishability obfuscation?

This is where we finally get to cryptography. The defining property of this software obfuscation is that obfuscating any two programs that compute the same mathematical function will produce programs that are indistinguishable from each other. This is a concept that has long eluded implementation to the point where many people thought it was unfeasible, mainly due to its theoretical properties, where iO is the “best possible” obfuscation, meaning that anything that can be hidden by any obfuscation at all can be hidden by iO, and where iO can be used to construct almost the entire range of cryptographic primitives.

However, the designs were not secure and thus not fit for purpose. An iO construction with provable security was proposed by Garg et al. in 2013, but the assumption was later invalidated. This design was based on multilinear maps. Then in 2016, Jain, Lin and Sahai started to build iO based on the same principle. Initially, these were multilinear maps up to degree 30 and gradually the degrees were reduced to degree 3. However, even that was a lot for a safe iO. Eventually a compromise was made and a sort of grade 2.5 was created where not everything is covered.

Tip: You probably already have a digital identity, but how will it evolve?

Conclusion

We are still quite far from practicality, but it is quite possible that in a few years it will be a common study material in cryptography.

Source: quantamagazine.org