Los Angeles Math Circle

6/2 -- High School I: Oblivious Transfer & Private Secure Computation (Amit Sahai)

Suppose an online bookstore has N books B1, ..., BN, and you want to buy a book, but you don't want the bookstore to know which book you're buying. In other words, you want be able to choose an integer i such that 0 < i < N+1, and you want to figure out a way that you can learn Bi, and yet the bookstore learns nothing about the integer i. This is called an Oblivious Transfer (OT). We will use modular arithmetic to construct OT, and see how to use OT to solve an even more general cryptographic problem called Private Secure Computation.