Yao’s Garbled Circuit (0): Introduction

Citation:

  1. “A Gentle Introduction to Yao’s Garbled Circuits” by Sophia Yakoubov
  2. UCLA CS 282A Notes by Rafail Ostrovsky, part 15

In this post we will discuss some of the very basics of Yao’s Garbled Circuit, preparing for the future posts.

Problem:

Consider two people Ginny and Evan. Ginny and Evan wish to figure out whether they should collaborate or not, but neither of them wants the other person to know his/her attitude.

Setup:

In other word, let Ginny holds a bit g and let Evan holds a bit e. The bit has value 1 if he/she agrees to collaborate, or has value 0 if he/she disagrees. They want to design a protocol such that both of them learn the value of g \wedge e at the end of protocol, but neither Ginny or Evan learns the other person’s bit during the protocol. In this scenario, we call Ginny the “garbler”, who is in charge of “garbled gate generation”. We call Evan the “evaluator“, who is in charge of “garbled gate evalution“.

Garbled Gate Generation (by Ginny):

The idea is to design a “garbled gate” and generalize it into garbled circuit. Garbling basically means to obfuscate boolean gate truth table. Ginny picks four random strings as “labels“, each corresponds to one of g = 0, 1 or e = 0, 1.

step 1: encryption

We pick a label from the g side and a label from the e side to form a label pair. Now we have four labels pairs, and together they represent the boolean truth table. Each label pair is used as input for a key derivation function H, the output H(label 1, lable 2) is a symmetric encryption key, and the key is used to encrypt the output of g \wedge e. Hence now the garbled outputs (ciphertexts) takes the form Enc(H(label 1, label 2), g \wedge e) after obfuscation.

step 2: permutation

Simply permute the garbled outputs, so that the garbled gate appears to have random order.

Garbled Gate Evaluation (by Evan):

Evan now needs to decrypt the ciphertext corresponding to the real values of g and e, so he needs to receive those two labels with the real values of g and e from Ginny. We call these two labels “label(g)” and “label(e)” respectively.

step 1: sending label(g)

Since Ginny knows g, she knows which label is label(g). Since labels are just random strings picked by Ginny, Evan is not able to learn anything about g from label(g) itself. So Ginny could just send her label(g) to Evan.

step 2: sending label(e)

Since Ginny doesn’t know e this time, she doesn’t know which label is label(g). She can’t send both labels corresponding to e to Evan, because then Evan can decrypt two ciphertexts. Evan can’t just ask for the one he wants, since he doesn’t want Ginny to learn the value of e. Hence they choose to use “oblivious transfer (OT)” to pass label(e).

From Gates to Circuits:

In reality, Ginny and Evan may wish to compute much more complicated functions using this protocol. In this case, Ginny will garble the entire function circuit, instead of a single gate. Now garbled gate becomes garbled circuit.

Yao’s Garbled Circuit (1): Yao’s Original Paper

Citation:

A. C. Yao, “How to generate and exchange secrets,” 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), Toronto, ON, Canada, 1986, pp. 162-167.
doi: 10.1109/SFCS.1986.25
keywords: {Polynomials;Probability distribution;Turing machines;Privacy;Knowledge transfer;History;Computer science;Cryptographic protocols;Cryptography;Circuits},
URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=4568207&isnumber=4568184

This post will clear the prerequisite for Garbled RAM, and we will summarize Yao’s Garbled Circuit directly from Yao’s original paper.

Oblivious RAM Done Right (1): Overview

Reading:

  1. UCLA CS 282A Notes

In this section, we will discuss some preliminaries for the study of Oblivious RAM (ORAM). We will clarify the definition of security of remote data storage problem, and provide some basic solutions to the problem.

1. Definition of Security (of Remote Data Storage)

Consider two companies A and B. A runs a cloud storage service, and B is considering to use this service. B would like to do so because leasing remote storage from A is much cheaper than buying machines and store data locally. However, B doesn’t trust A completely. B is afraid of the loss of privacy after uploading these data completely to A. In this scenario, we call company A “cloud” and company B “user. Here is how we define what is meant to be secure:

  1. Privacy: cloud is not able to read user’s data in clear.
  2. Mutation of data: cloud is not able to change user’s data.
  3. Loss of data: user is able to check if any data is lost or missing.
  4. Re-introduction of old data: user is able to check if any old data is introduced as new data by cloud at some later date.
  5. Invisible Access Pattern: If user performs a series of read/write operations, cloud is not able to the sequence of user’s operations.

If above criteria hold, we say this remote data stroage service is secure. Here is how we do to make them come true:

  1. Privacy: Encryption
  2. Mutation of data: Digital Signature Scheme
  3. Loss of data or re-introduction of old data: Hash functions and Merkle trees
  4. Invisible Access Pattern: ORAM

In the following blogs, we focus on 4, which is the study of ORAM. For a trivial solution, suppose user stores N piceces of data in the cloud, and cloud could pass all data back to user one by one in M separate times. User could uses local memory to hold them, perform read/write on relavant data, encrypt them again and pass them back to the cloud. This is the worst solution to solve this problem, and it has overhead O(N). Next, we present a solution with overhead O((logM)^4).

2. A Poly-log Solution:

Data Structure:

We refer user’s data as “words”. A word is a 2-tuple (i, w_{i}), where i is the location of data and w_{i} is the actual data at location i. Cloud creates arrays A_{i} with length 2^i, where 2 \leq i \leq, so the first array has length 4, second array has length 7, third array has length 16, and so on. Each array is called a “buffer“, and each entry of an array is called a “bucket“. Each bucket holds logM words. For each buffer A_{i}, user will use a secret seed and a pseudo-random function (PRF) to generate a hash function. These hash functions obfuscate the location of each piece of data, so cloud is not able to learn anything from the storing patten. The last buffer (also the longest) is called the “Storage Array”. It holds all N pieces of data that user uploaded at beginning.

Initialization:

Accesing Data (Read/Write):

Oblivious RAM Done Right (2): [GO96]

Reading:

  1. Software Protection and Simulation on Oblivious RAMs” by Rafail Ostrovsky

1. Introduction:

This paper starts from the problem of software protection, here we mean “protection against illegitimate duplication”, i.e. ensuring there is no efficient method for creating executable copies of the software. Purely software-based solution doesn’t exist, so hardware must involve. Our task is to minimize the participation of hardware, so that the solution is less expensive.

An existing solution is “software-hardware-package (SH-package)“, that is, selling a physically shielded CPU together with an encrypted program. An instruction cycle of such CPU will be fetching -> decrypting -> executing an instruction. Every ATM machine has such a protected chip.

However, above solution is not good enough, since it doesn’t hide the “access pattern“, i.e. the addresses of the memory cells accessed during the execution are not kept secret. The lack of such property may create trouble, e.g. an adversary could learn the loop structure of the program, which is important in certain scenario. If we come up with a solution that hides the access pattern, we consider it as secure. Informally, “hiding access pattern” means no PPT adversary can distinguish these two cases:

Case 1: The adversary is experimenting with the real CPU that runs the encrypted program.

Case 2: The adversary is experimenting with a fake CPU that runs dummy program, such as “while True do skip”. After the same number of steps as in case 1, the CPU writes exactly the same outputs as in case 1 into memory.

To protect software to such level of security, the cost is “speed”, called software protection overhead. Informally, software protection overhead means the number of steps the protected program makes for each each step of the program. Our task is to minimize this overhead.

2. Model and Definitions:

A machine is oblivious if the sequence in which it accesses memory locations is equivalent for any two inputs with the same running time.

3. Reducing Software Protection to Oblivious Simulation of RAMs:

4. Square Root Solution

5. Hierarchical Solution

6. Lower Bound

Theory of Computation

Readings:

  1. Algorithm Design” by Kleinberg and Tardos
  2. Introduction to the Theory of Computation” by Michael Sipser
  3. UCLA CS 282A Notes by Rafail Ostrovsky

You don’t have to memorize the precise definition for these computational models, since most of the time we won’t use details in their defitions to construct proofs. However, a poor understanding on these topics creates barriers when reading paper, so it is neccessary to at least know what they are talking about.

1. Turing Machine:

Turing machines mimic the function of a computer, but it uses an infinitely-long tape as memory, so it is rather an ideal model. Turing machines can read and write, and use a “read-write head” to point to a specific location on the tape to access the content of that location. For a brief introduction, please refer to this page.

2. Polynomial Time (P):

P class contains all decision problems that a deterministic single-tape Turing machine can solve in polynomial time。Generally speaking, P contains problems of time complexity O(n^k), k is a natrual number. We can assume a modern computer is able to solve a problem of class P, but note that this “easy-to-compute” impression comes from the difficulty of NP class. A problem of complexity O(n^1000000) is definitely not easy to solve.

3. Non-Deterministic Polynomial Time (NP):

NP class contains all problems that are polynomially verifiable。For example, given integers p and q, it is easy to verify whether x = p * q is a composite or not, simply by doing multiplication. However, if we are given an integer x and we are asked to find a factorization of x into p and q, this task can be very difficult to do. Let’s call this problem the “composite problem”, and we say composite problem is polynomially verifiable but not polynomially decidable, so it is of class NP, not P. Similarly, we can assume NP problems are unsolvable on modern computer, although some of them are easy to solve in special cases.

4. P versus NP:

From 2 and 3, we can define P and NP in the following way:

  1. P = the class of languages for which membership can be decided quickly (in polynomial time)
  2. NP = the class of languages for which membership can be verified quickly (in polynomial time)

If P equals NP, then all polynomially verifiable problems are polynomially decidable,As a result, one-way function doesn’t exist,and we are unable to build most of the modern cryptographic theory without the existence of one-way function. Hence P does not equal NP is a foundamental assumption that we make all the time.

5. NP-Completeness:

6. Randomized Algorithm:

7. Probabilistic Polynomial Time (PPT):

8. Randomized Polynomial Time (RP):

9. Bounded Probabilistic Polynomial Time (BPP):

10. Non-Uniform Polynomial Time (P/Poly):

11. Oracle Machines:

An oracle machine can be viewed as a Turing machine + a black box structure, called an oracle. An oracle can answer any decision problem in a single operation. The decision problem can be of any complexity class, even undecidable problem, so oracle machine is a rather ideal model.

12. Random-Access Machine (RAM):

RAM is a class of register machines, can be viewed as a counting machine + the ability of indirect addressing. RAM has registers labelled R1,R2,R3,R4 and etc,Each register stores an integer。RAM has a control unit, which contains a program. RAM uses a program counter (PC) points to and execute certain statement in the program。Here is a graph of the RAM structure.

13. Some notes:

  1. log function has a change of base formula, so any log function can be changed to another base by multiplying a constant。As a result,O(log n) can represent log function with any base, so we don’t need to specify what kind of base number we are working with, and replace everything with logn.