Et veldig sterkt primitiv, med noen (teoretiske og upraktiske) foreslåtte konstruksjoner i nyere år, ("foreslått" fordi hvis jeg husker rett så er de basert på non-standard hard problems). > The road from a theoretical breakthrough to a practical protocol can be a long one, Barak said. “But you could imagine,” he said, “that maybe 50 years from now the crypto textbooks will basically say, ‘OK, here is a very simple construction of iO, and from that we’ll now derive all of the rest of crypto.’” Sitat hentet fra [Quanta-artikkel](https://www.quantamagazine.org/computer-scientists-achieve-crown-jewel-of-cryptography-20201110/). #### Implikasjoner Impliserer [[Deniable Encryption]]? > While the protocol is far from ready to be deployed in real-world applications, from a theoretical standpoint it provides an instant way to build an array of cryptographic tools that were previously out of reach. For instance, it enables the creation of “deniable” encryption, in which you can plausibly convince an attacker that you sent an entirely different message from the one you really sent, and “functional” encryption, in which you can give chosen users different levels of access to perform computations using your data. Trodde [[Deniable Encryption]] var umulig i standardmodellen ... kanskje konstruksjonen er i en idealisert modell, eller at de mener for polynome message spaces. > The new result should definitively silence the iO skeptics, Ishai said. “Now there will no longer be any doubts about the existence of indistinguishability obfuscation,” he said. “It seems like a happy end.” Optimistisk! Impliserer (så klart) også [[Offentlig-nøkkel kryptering]], samt [[Fully homomorphic encryption]] m.m.: > Over the years, computer scientists have shown that you can use iO as the basis for almost every cryptographic protocol you could imagine (except for black box obfuscation). That includes both classic cryptographic tasks like public key encryption (which is used in online transactions) and dazzling newcomers like fully homomorphic encryption, in which a cloud computer can compute on encrypted data without learning anything about it. #### Konstruksjonen til Jain/Lin/Sahai The breakthrough paper: - [Indistinguishability Obfuscation from Well-Founded Assumptions](https://eprint.iacr.org/2020/1003), av Jain, Lin, og Sahai. (NB: Claimer kun sub-exponential security.) Fra [Quanta](https://www.quantamagazine.org/computer-scientists-achieve-crown-jewel-of-cryptography-20201110/): > Since iO seemed to need degree-3 (multilinear) maps, but computer scientists only had secure constructions for degree-2 maps, what if there was something in between — a sort of degree-2.5 map? (...) To strike a balance between the power of higher-degree multilinear maps and the security of degree-2 maps, the machine is allowed to compute with polynomials of degree higher than 2, but there’s a restriction: The polynomial must be degree 2 on the hidden variables. ![[Pasted image 20240330121636.png]] > But to get from these less powerful multilinear maps to iO, the team needed one last ingredient: a new kind of pseudo-randomness generator, something that expands a string of random bits into a longer string that still looks random enough to fool computers. That’s what Jain, Lin and Sahai have figured out how to do in their new paper. Hvilke underlying assumptions? Fra [abstract til paperet](https://eprint.iacr.org/2020/1003): 1. Learning With Errors 2. Learning Parity With Noise 3. The existence of a Boolean Pseudo-random Generator 4. Symmetric eXternal Diffie-Hellman > The scheme’s security rests on four mathematical assumptions that have been widely used in other cryptographic contexts. And even the assumption that has been studied the least, called the “learning parity with noise” assumption, is related to a problem that has been studied since the 1950s. Men: Ikke kvantesikkert! (SXDH er vel knukket av [[Shors algoritme]].) > There is likely only one thing that could break the new scheme: a [quantum computer](https://www.quantamagazine.org/tag/quantum-computing), if a full-power one is ever built. One of the four assumptions is vulnerable to quantum attacks. ... men folk jobber med å fikse dette: > These versions of iO rest on less established security assumptions than the ones Jain, Lin and Sahai used, several researchers said. But it is possible, Barak said, that the two approaches could be combined in the coming years to create a version of iO that rests on standard security assumptions and also resists quantum attacks.