# Monthly Archives: April 2018

When: Friday, April 20 at MSR.

Where:  Microsoft New England Research and Development Center
One Memorial Drive, Cambridge MA 02142.

Organizers: Ran Canetti, Yael Kalai, Ron Rothblum (emeritus), Vinod Vaikuntanathan and Daniel Wichs.

Thanks: NSF MACS Project for their generous support.

### Program:

 9:30 – 10:00. Coffee/Welcome 10:00 – 11:00. Brent Waters, UT Austin Collusion Resistant Traitor Tracing from Learning with Errors 11:15 – 12:15. Mor Weiss, Northeastern Private Anonymous Data Access 12:15 – 1:30. Lunch 1:30 – 2:30. Tianren Liu, MIT Breaking the Circuit-Size Barrier for General Secret Sharing 2:45 – 3:45. Ron Rothblum, MIT + Northeastern Efficient Batch Verification for UP

### Abstracts:

Speaker:  Brent Waters, UT Austin
Title:  Collusion Resistant Traitor Tracing from Learning with Errors

Abstract: In this work we provide a traitor tracing construction with ciphertexts that grow polynomially in log(n) where n is the number of users and prove it secure under the Learning with Errors (LWE) assumption. This is the first traitor tracing scheme with such parameters provably secure from a standard assumption. In addition to achieving new traitor tracing results, we believe our techniques push forward the broader area of computing on encrypted data under standard assumptions. Notably, traitor tracing is substantially different problem from other cryptography primitives that have seen recent progress in LWE solutions.

We achieve our results by first conceiving a novel approach to building traitor tracing that starts with a new form of Functional Encryption that we call Mixed FE. In a Mixed FE system the encryption algorithm is bimodal and works with either a public key or master secret key. Ciphertexts encrypted using the public key can only encrypt one type of functionality. On the other hand the secret key encryption can be used to encode many different types of programs, but is only secure as long as the attacker sees a bounded number of such ciphertexts.

We first show how to combine Mixed FE with Attribute-Based Encryption to achieve traitor tracing. Second we build Mixed FE systems for polynomial sized branching programs (which corresponds to the complexity class logspace) by relying on the polynomial hardness of the LWE assumption with super-polynomial modulus-to-noise ratio.

Joint work with Rishab Goyal and Venkata Koppula

Speaker: Mor Weiss, Northeastern
Title:  Private Anonymous Data Access

Abstract: We consider a scenario where a server holds a huge database that it wants to make accessible to a large group of clients. After an initial setup phase, clients should be able to read arbitrary locations in the database while maintaining privacy (the server does not learn which locations are being read) and anonymity (the server does not learn which client is performing each read). This should hold even if the server colludes with a subset of the clients. Moreover, the run-time of both the server and the client during each read operation should be low, ideally only polylogarithmic in the size of the database and the number of clients. We call this notion Private Anonymous Data Access (PANDA).

PANDA simultaneously combines aspects of Private Information Retrieval (PIR) and Oblivious RAM (ORAM). PIR has no initial setup, and allows anybody to privately and anonymously access a public database, but the server’s run-time is linear in the data size. On the other hand, ORAM achieves poly-logarithmic server run-time, but requires an initial setup after which only a single client with a secret key can access the database. The goal of PANDA is to get the best of both worlds: allow many clients to privately and anonymously access the database as in PIR, while having an efficient server as in ORAM.

In this work, we construct bounded-collusion PANDA schemes, where the efficiency scales linearly with a bound on the number of corrupted clients that can collude with the server, but is otherwise poly-logarithmic in the data size and the total number of clients. Our solution relies on standard assumptions, namely the existence of fully homomorphic encryption, and combines techniques from both PIR and ORAM. We also extend PANDA to settings where clients can write to the database.

Joint work with Ariel Hamlin, Rafail Ostrovsky,  and Daniel Wichs

Speaker: Tianren Liu, MIT
Title:  Breaking the Circuit-Size Barrier for General Secret Sharing

Abstract: We study secret sharing schemes for general (non-threshold) access structures. A general secret sharing scheme for $n$ parties is associated to a monotone function $F:{0,1}^n\to{0,1}$. In such a scheme, a dealer distributes shares of a secret $s$ among $n$ parties. Any subset of parties $T \subseteq [n]$ should be able to put together their shares and reconstruct the secret $s$ if $F(T)=1$, and should have no information about $s$ if $F(T)=0$. One of the major long-standing questions in information-theoretic cryptography is to minimize the (total) size of the shares in a secret-sharing scheme for arbitrary monotone functions $F$.

There is a large gap between lower and upper bounds for secret sharing. The best known scheme for general $F$ has shares of size $2^{n-o(n)}$, but the best lower bound is $\Omega(n^2/\log n)$. Indeed, the exponential share size is a direct result of the fact that in all known secret-sharing schemes, the share size grows with the size of a circuit (or formula, or monotone span program) for $F$. Indeed, several researchers have suggested the existence of a {\em representation size barrier} which implies that the right answer is closer to the upper bound, namely, $2^{n-o(n)}$.

In this work, we overcome this barrier by constructing a secret sharing scheme for any access structure with shares of size $2^{0.994n}$ and a linear secret sharing scheme for any access structure with shares of size $2^{0.999n}$.  Our construction builds on our recent works that construct better protocols for the conditional disclosure of secrets (CDS) problem.

Joint work with Vinod Vaikuntanathan

Speaker:  Ron Rothblum, MIT + Northeastern
Title:  Efficient Batch Verification for UP

Abstract: We construct an interactive proof for verifying the correctness of any k UP statements (i.e., NP statements that have a unique witness). Our proof-system has a constant number of rounds of interaction and has communication complexity is $k^\delta \cdot poly(m)$, where $\delta>0$ is an arbitrarily small constant, m is the length of a single witness and the $poly$ term refers to a fixed polynomial that only depends on the language and not on $\delta$. The (honest) prover strategy can be implemented in polynomial-time given access to the k (unique) witnesses.

Since communication grows sub-linearly with k, for large values of k this proof-system is much more efficient than the naive solution in which the prover simply sends the k witnesses.

Joint work with Omer Reingold and Guy Rothblum