Abstract
The first part of this lecture investigated the use of direct-access memory in secure computing, in order to go further than the Boolean or arithmetic circuit-based computing models used in previous lectures. The Oblivious RAM(ORAM) model enables a secure processor to access an external RAM without the data exchanged or the RAM access patterns revealing anything about the computation performed by the processor. We presented the first realization of this concept: the "square-root ORAM" algorithmby Goldreich and Ostrovsky (1996). We then considered the case where memory access addresses are generated by a homomorphically evaluated circuit. Lin, Mook and Wichs (2023) applied their "DEPIR" (Doubly-Efficient Private Information Retrieval) approach to this scenario, in which the memory, represented by a multidimensional array, is first encrypted with a weakly homomorphic algebraic encryption (contents and addresses), then represented relatively compactly and with polylogarithmic time accesses using the fast polynomial factorization technique of Kedlaya and Umans (2008).
The second part of the lecture was devoted to program obfuscation: how to make the code of a program incomprehensible to the point where it provides no additional information to that obtained by executing the program. Insecure obfuscation techniques are frequently used to facilitate reverse engineering and software piracy. Much more ambitiously, a cryptographic-quality obfuscation such as indistinguishability obfuscation(IO, Barak et al, 2001) would easily realize almost all known cryptographic primitives, from public-key encryption to homomorphic encryption and much more. We have tried to explain the extreme difficulty of realizing an indistinguishable obfuscator, with several proposals using multilinear forms proving unsafe, and only one proposal (Jain, Lin and Sahai, 2021) still holding out.
