Instructor: Daniele Micciancio (UCSD)

Introduction

Public key encryption is among the most important (and commonly used) tools in cryptography, and it allows two parties (traditionally called Alice and Bob) to communicate privately over an open communication channel, i.e., in the presence of an eavesdropper (Eve). An encryption scheme consists of a collection of algorithms (KeyGen,Enc,Dec) which are used as follows:

1. Alice generates a public/secret key pair (pk,sk) ⟵ KeyGen(t) and provides the public (encryption) key pk to Bob
2. Bob, on input a message m, applies the encryption function to compute a ciphertext c ⟵ Enc(pk,m), and sends it to Alice
3. Alice uses the decryption algorithm and secret key to recover the original message m = Dec(sk,c)

The scheme should satisfy the natural correctness condition

Dec(sk,Enc(pk,m)) = m

i.e., encrypting a message, and decrypting the resulting ciphertext should produce the original message. Notice how this formula only specifies a correctness requirement, and says nothing about security. Formalizing appropriate notions of security (for encryption and many other tasks of theoretical or practical interest), and designing and analyzing algorithms that provably satisfy the desired security properties (typically under some commonly accepted complexity assumption) is one of the most important achievements of modern cryptography, and an active research area to the present day. We will review formal security definitions for public key encryption shortly, but for now, let's keep the discussion informal.

In this course, we will study a number of advanced cryptographic problems/primitives that go well beyond the problem of securely communicating a message m, and combine the secrecy properties of encryption with some form of computation. We will be primarily concerned with the following three problems:

• Fully Homomorphic Encryption (FHE): This extends encryption scheme (KeyGen,Enc,Dec) with an evaluation algorithm Eval that allows to compute on ciphertexts without decrypting them, and, in fact, without even knowing the decryption key. Technically, an FHE scheme should satisfy the following correctness requirement

  Dec(sk,Eval(pk,f,Enc(pk,m))) = f(m)

  where f is some function (or program) to be evaluated on the message m. Notice how the result of applying the evaluation function Eval(pk,f,c) on a ciphertext c ⟵ Enc(pk,m)) produces a result still in encrypted form. So, while the evaluation function can be publicly applied to the ciphertext, the secret key is required to recoved the result of the evaluation.

• Functional Encryption (FE): Just like FHE, functional encryption also allows to perform computations on encrypted messages. The difference is that computation is performed during decryption, using a special (function dependent) decryption key fk=FunGen(sk,f) satisfying the following correctness requirement:

  Dec(FunGen(sk,f),Enc(pk,m)) = f(m)

  On the security front, the functional decryption key fk=FunGen(sk,f) should not allow to obtain any information about the message m other than the result of the computation f(m), enabling applications with fine-grained access control on encrypted messages.

• Program Obfuscation (Ob): This time the goal is to keep the program f secret, and still allow to run it on any (unencrypted) input. A program obfuscation scheme is a compiler that on input the decryption of a function f, outputs a functionally equivalent program Ob(f) such that

  [Ob(f)](m) = f(m)

  for any program input m. Notice how no message encryption takes place, and no cryptographic keys are involved. Still, as we will see, program ofbuscation is closely related to certain types of (functional) encryption.

The study of these advanced cryptographic primitives (and their many variants) has been one of the hottest research areas in cryptography during the last several years, and it is a very active research area, with many open problems of both theoretical and potentially practical interest. The study of FHE has reached a fairly mature stage, with the first candidate solutions to it proposed in 2009, and with current research mostly focused on finding more efficient schemes. Functional encryption and Obfuscation are still to a large extent unsolved problems. A candidate general solution to these problems was proposed in 2013, but subsequently broken, and for some versions of the security definitions impossibility results have been known for a while. But, in the process, a number of theoretical results have been obtained, relating different forms of functional encryption to each other, and establishing links between functional encryption, obfuscation and FHΕ. So, while building a provably secure functional encryption or obfuscation scheme based on a standard, widely accepted assumption is still an open problem, there is hope that a solution will soon emerge. Functional encryption and obfuscation can also be related to a number of simpler (still quite powerful) cryptographic primitives, like identity based encryption, attribute based encryption, witness encryption, and more. One of the main goals of this course is to explore the relation between all these different primitives, and the solution to some of the more specialized problems which can be seen as special cases of functional encryption.

Prerequisites/Background

This course assume both a reasonable level of mathematical maturity, and good familiarity with the definitional framework of modern cryptography, and related proof techniques, as typically covered in (or implied by) a graduate level introductory cryptography course like UCSD CSE207: Modern Cryptography, including:

• basic knowledge of various areas of mathematics and computer science, like probability theory, abstract algebra, linear algebra, theory of computation, algorithms, etc.
• the mathematical security definition of the most basic cryptographic primitives, like pseudorandom generators, pseudorandom functions, hash functions, secret and public key encryption, digital signatures,
• some form of the simulation paradigm, as employed for example in the definition of semantic security for encryption, zero-knowledge proof systems, or secure multiparty computation
• common cryptographic proof techniques, like the hybrid method for the analysis of security games
• some examples of computationally hard problems used in cryptography (like RSA, DLOG or lattice problems) and related constructions of simple cryptographic primitives

We will briefly review many of the basic cryptographic definitions as we need/use them. So, if you are unfamiliar with one or two of the above cryptographic primitives, you should not worry too much about it. But we will only have the time to present the formal definitions very briefly, without going through the standard set of examples and excercises that are required to build a strong intuition about them. So, if you lack most of the background outlined above, you will likely have trouble making sense of the definitions, or will only get a superficial understanding, not enough to make the most of this class. In such a case, it is recommended that you first take a more introductory course on modern cryptography.