# Thursday, November 9 at BU

Welcome to the first crypto day of this academic year. What’s in store: Coffee, lattices and much more!

**When:** ~~Friday, November 10 at MIT.~~ Thursday, November 9 at BU.

**Where: **Hariri Seminar Room, 111 Cummington Mall Room 180, Boston MA.

Attendance is free, as usual, but please register by filling in this rather short google form: https://goo.gl/forms/PkOmXELG8xPqwG812

**Organizers:** Ran Canetti, Yael Kalai, Ron Rothblum and Vinod Vaikuntanathan.

**Thanks:** NSF MACS Project for their generous support.

### Program:

9:30 – 10:00. | Coffee/Welcome |

10:00 – 11:00. |
Elette Boyle, IDC Herzliya
Can We Access a Database Both Locally and Privately? |

11:15 – 12:15. | Zvika Brakerski, WeizmannConstraint Hiding Constrained PRFs from LWE |

12:15 – 1:15. | Lunch (provided) |

1:15 – 2:15. | David Wu, StanfordQuasi-Optimal SNARGs via Linear Multi-Prover Interactive Proofs |

2:15 – 2:30. | Coffee Break |

2:30 – 3:30. | Daniel Wichs, NortheasternObfuscating Compute-and-Compare Programs under LWE |

### Abstracts:

**Speaker: Elette Boyle**

**Title: Can We Access a Database Both Locally and Privately?**

We consider the following strong variant of private information retrieval (PIR). There is a large database x that we want to make publicly available. To this end, we post an encoding X of x together with a short public key pk in a publicly accessible repository. The goal is to allow any client who comes along to retrieve a chosen bit x_i by reading a small number of bits from X, whose positions may be randomly chosen based on i and pk, such that even an adversary who can fully observe the access to X does not learn information about i.

Towards solving the above problem, we study a weaker secret key variant where the data is encoded and accessed by the same party. This primitive, that we call an oblivious locally decodable code (OLDC), is independently motivated by applications such as searchable symmetric encryption. We reduce the public-key variant of PIR to OLDC using an ideal form of obfuscation that can be instantiated heuristically with existing indistinguishability obfuscation candidates, or alternatively implemented with small and stateless tamper-proof hardware.

Finally, a central contribution of our work is the first proposal of an OLDC candidate. Our candidate is based on a secretly permuted Reed-Muller code. We analyze the security of this candidate against several natural attacks and leave its further study to future work.

Joint work with Yuval Ishai, Rafael Pass, and Mary Wootters.

**Speaker: Zvika Brakerski**

**Title: Constraint-Hiding Constrained PRFs from LWE**

We show how to construct a constraint-hiding constrained pseudorandom functions (CH-CPRF) based on the learning with errors assumption. We show two constructions using two different methods, which end up achieving similar features. Our constructions support arbitrary constraint functions (of a-priori bounded polynomial non-uniformity and depth), contrary to previous works that could only handle NC1 constraints. Similarly to previous works, our constructions do not protect against collusion (i.e. an adversary is only allowed to posses a single constrained key).

Technically, we extend the methodology of Brakerski and Vaikuntanathan (TCC 2015) that showed a duality between LWE-based attribute based encryption (ABE) and CPRF. If this duality extended to (weakly) attribute hiding ABE, then CH-CPRF would have followed. However this was not the case for previously known constructions of attribute hiding ABE. We show how to bridge this gap, and along the way present cleaner constructions of weakly attribute hiding ABE from LWE.

Joint work with Rotem Tsabary, Vinod Vaikuntanathan and Hoeteck Wee.

**Speaker: David Wu**

**Title: Quasi-Optimal SNARGs via Linear Multi-Prover Interactive Proofs**

Succinct non-interactive arguments (SNARGs) enable verifying NP computations with significantly less complexity than that required for classical NP verification. In this work, we focus on simultaneously minimizing the proof size and the prover complexity of SNARGs. Concretely, for a security parameter k, we measure the asymptotic cost of achieving soundness error 2^{-k} against provers of size 2^k. We say a SNARG is quasi-optimally succinct if its proof length is quasilinear in the security parameter, and that it is quasi-optimal, if moreover, its prover complexity is only polylogarithmically greater than the running time of the classical NP prover. These bounds are the best we could hope for assuming that NP does not have succinct proofs.

In this work, we give the first quasi-optimal SNARG for Boolean circuit satisfiability from a concrete cryptographic assumption. Our construction takes a two-step approach. The first is an information-theoretic construction of a quasi-optimal linear multi-prover interactive proof (linear MIP) for circuit satisfiability. Then, we describe a generic cryptographic compiler that transforms our quasi-optimal linear MIP into a quasi-optimal SNARG by relying on the notion of linear-only vector encryption over rings introduced by Boneh et al. (Eurocrypt 2017). Combining these two primitives yields the first quasi-optimal SNARG based on linear-only vector encryption.

Joint work with Dan Boneh, Yuval Ishai, and Amit Sahai.

**Speaker: Daniel Wichs**

**Title: Obfuscating Compute-and-Compare Programs under LWE**

We show how to obfuscate a large and expressive class of programs, which we call compute-and-compare programs, under the learning-with-errors (LWE) assumption. Each such program CC[f,y] is parametrized by an arbitrary polynomial-time computable function f along with a target value y and we define CCf,y to output 1 if f(x)=y. In other words, the program performs an arbitrary computation f and then compares its output against a target y. Our obfuscator satisfies distributional virtual-black-box security, which guarantees that the obfuscated program does not reveal any partial information about the function f or the target value y, as long as they are chosen from some distribution where y has sufficient pseudo-entropy given f. We also extend our result to multi-bit compute-and-compare programs which output a message z if f(x)=y.

Compute-and-compare programs are powerful enough to capture many interesting obfuscation tasks as special cases. This includes obfuscating conjunctions, and therefore we improve on the prior work of Brakerski et al. (ITCS ’16) which constructed a conjunction obfuscator under a non-standard “entropic” ring-LWE assumption, while here we obfuscate a significantly broader class of programs under standard LWE. We show that our obfuscator has several interesting applications such as upgrading attribute-based encryption to predicate encryption and witness encryption to indistinguishability obfuscation which is secure for all null circuits. Furthermore, we show that our obfuscator gives new circular-security counter-examples for public-key bit encryption and for unbounded length key cycles.

joint work with Giorgos Zirdelis.