TCC 2012: Day 2 AM

On Tuesday morning, there were three sessions about leakage resilience, hash functions, and differential privacy.

The first talk presented a way to compile a circuit such that the result is leakage resilient in the bounded independent model. In this model, the memory is split into parts, and as many bits as a given fraction of the key length can be leaked from only some parts in a certain period. The compiler creates a two-party protocol that computes the circuit, where every player and a communication resource are assigned a part of the memory. In every step of the protocol, leakage can occur from one player and the communication resource. It is also assumed that there is a leakage-free source that gives correlated bits to the players. Every wire in the circuit is represented by one random bit string for each player such that the inner product of the two strings is the bit on the wire. The leakage-free source is used to generate these two strings. If the first bit of string of the first player is always 1, the negation can be computed by flipping the first bit in the string of the second player. For an AND gate, the players can locally compute the multiplication of all n^2 combination of bits of their strings. The inner product of the results then is the AND of the input bits. However, the output strings are not random and too long. Running a randomization, publicly computing the inner product of the excess string, and then negating if the result is 1 brings the strings back to the desired form.

The second and the third talk of the leakage resilience session covered leakage resilience amplification by repetition and the universal composability with leakage resilience, respectively.

The first talk in the hash function session discussed Feistel networks with random oracles. For someone not familiar with hash functions, it was interesting to see that the security does continuously increase with the number of rounds but, instead, there is a minimal number of rounds to achieve certain a certain security definition. The topic of the second talk was a hash function based on a blockciphers with a connection to discrete geometry.

The final session of the morning was on differential privacy. This concept tries to ensure that the answer to database queries do not give away sensitive information about an individual entry. A possible way to solve the problem is to add noise to the answers. In the first talk of the session, lower bounds on this noise were presented. Another way to achieve differential privacy covered in the last talk. A sanitizer keeps a local approximation to the database that is empty in the beginning. For every query, the sanitizer queries the real database in a noisy way and its local approximation. If the two answers are close enough, the answer of the approximation is returned, and otherwise, the approximation is updated and the noisy answer of the real database is returned. After some approximation updates, the approximation is close enough, and from then on, all queries will be based on the approximation. If the noise used earlier was big enough, no query will reveal sensitive data. This technique of approximation a database is called iterative database construction.