[Busec] [charles-river-crypto-day] Charles River Crypto Day, Thursday Nov 9 @ BU

Ran Canetti canetti at bu.edu
Tue Oct 31 14:15:52 EDT 2017





Dear All:

Due to conflict with the event for Michael Cohen at MIT on Friday the 
10th, the Charles River Crypto Day has moved one day earlier to Thu Nov 
9th, this time at BU.

Schedule and abstracts are below, and also at 

As usual, the event is free but please help us plan by registering at 

(Please register again even if you registered for the Nov 10 event - 
this is a new list. Apologies again and thanks.)

Ran, Yael, Ron, Vinod, Daniel

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, Weizmann
*Constraint Hiding Constrained PRFs from LWE*
12:15 – 1:15. 	Lunch (provided)
1:15 – 2:15. 	David Wu, Stanford
*Quasi-Optimal SNARGs via Linear Multi-Prover Interactive Proofs
2:15 – 2:30. 	Coffee Break
2:30 – 3:30. 	Daniel Wichs, Northeastern
*Obfuscating Compute-and-Compare Programs under LWE*


*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 <https://bostoncryptoday.wordpress.com/x>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.

You received this message because you are subscribed to the Google Groups "Charles River Crypto Day" group.
To unsubscribe from this group and stop receiving emails from it, send an email to charles-river-crypto-day+unsubscribe at googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/charles-river-crypto-day/70ee981c-efae-1d73-7786-96e472fea3c6%40bu.edu.
For more options, visit https://groups.google.com/d/optout.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/busec/attachments/20171031/ff3da10c/attachment-0003.html>

More information about the Busec mailing list