# Monthly Archives: April 2019

When: Friday, May 3, 2019.

Where: Northeastern University, ISEC Building (805 Columbus Ave) Room 655.

Organizers: Ran Canetti, Yael Kalai, Omer Paneth, Vinod Vaikuntanathan and Daniel Wichs.

Thanks: NSF MACS Project for their generous support.

### Program:

 9:30 – 10:00. Coffee/Breakfast 10:00 – 11:00. Benedikt Bünz, Stanford University Verifiable Delay Functions and Succinct Proofs in Groups of Unknown Order 11:15 – 12:15. Dakshita Khurana, Microsoft ResearchQuantum Advantage and Classical Cryptography 12:15 – 1:30. Lunch 1:30 – 2:30. Prabhanjan Ananth, MITSecure MPC with Honest Majority: Minimal Rounds and Efficiency Optimizations 3:00 – 4:00. Aloni Cohen, MITTowards Formalizing the GDPR Notion of Singling Out

### Abstracts:

Speaker: Benedikt Bünz, Stanford University
Title: Verifiable Delay Functions and Succinct Proofs in Groups of Unknown Order

We study the problem of building a verifiable delay function (VDF). A VDF requires a specified number of sequential steps to evaluate, yet produces a unique output that can be efficiently and publicly verified. VDFs have many applications in decentralized systems, including public randomness beacons, leader election in consensus protocols, and proofs of replication. We formalize the requirements for VDFs and present new candidate constructions that are the first to achieve an exponential gap between evaluation and verification time.

Further we survey new VDF constructions by Pietrzak and Wesolowski in groups of unknown order. Building on Wesolowski’s techniques we build succinct proofs in groups of unknown order. We build Sigma protocols that have good soundness in the challenge space and communication complexity independent of the witness. This circumvents a previous impossibility result. These proofs have applications to accumulators and vector commitments.

Speaker: Dakshita Khurana, Microsoft Research
Title: Quantum Advantage and Classical Cryptography

We demonstrate applications of quantum advantage to building new protocols for classical cryptography. In particular, we observe that in many applications, the oft-used technique of leveraging (time) complexity can be replaced with leveraging quantum advantage instead. In this talk, I will describe how this observation can be combined with additional techniques to obtain:
1. Non-interactive non-malleable commitments without setup in the plain model, under well-studied assumptions.
2. Two-message (privately verifiable) WI arguments based on the polynomial hardness of factoring and quantum polynomial hardness of LWE.

In the first case, I will begin by discussing how to build simple non-interactive non-malleable commitments for O (log log n) tags assuming the sub-exponential hardness of factoring or discrete log, and *quantum* sub-exponential hardness of LWE. Next, I will describe new combinatorial techniques to amplify the number of tags, assuming only the existence of NIWI (non-interactive witness indistinguishable) proofs. These techniques yield the first construction of non-interactive non-malleable commitments w.r.t. replacement for exponentially many tags in the plain model, based on well-studied assumptions.

I will also discuss how the second application (and some others) follow almost immediately from our observation on quantum advantage. This is based on joint work with Yael Tauman Kalai. The paper is available online at https://eccc.weizmann.ac.il/report/2018/203/.

Speaker: Prabhanjan Ananth, MIT
Title: Secure MPC with Honest Majority: Minimal Rounds and Efficiency Optimizations

We present two constructions of two-round secure multiparty computation protocols with honest majority:

– Our first construction satisfies statistical security with abort and can handle any functionality implementable in NC1. All the previous two-round protocols either required computational assumptions or had a weaker corruption threshold. Our construction employs both broadcast and point-to-point channels. We also show how to generically transform this protocol into one that only employs point-to-point channels while satisfying statistical security with selective abort property.

– Our second construction can securely compute any functionality implementable in P/poly and has per-party computation cost to be (|C|+n^2) poly(k)  with C being the circuit securely computed, n being the number of parties and k being the security parameter. It is based on one-way functions and satisfies semi-honest security. The per-party computation cost of all the previous protocols in this setting was |C| n^2 poly(k) or more. With an additional round, we can either upgrade to malicious security or achieve a protocol with total computation cost (|C|+n^2) poly(k).

Based on joint works with Arka Rai Choudhuri (JHU), Aarushi Goel (JHU) and Abhishek Jain (JHU).

Speaker: Aloni Cohen, MIT
Title: Towards Formalizing the GDPR Notion of Singling Out

There is a significant conceptual gap between legal and mathematical thinking around data privacy. The effect is uncertainty as to the which technical offerings adequately match expectations expressed in legal standards. The uncertainty is exacerbated by a litany of successful privacy attacks, demonstrating that traditional statistical disclosure limitation techniques often fall short of the sort of privacy envisioned by legal standards.

We define predicate singling out, a new type of privacy attack intended to capture the concept of singling out appearing in the General Data Protection Regulation (GDPR).

Informally, an adversary predicate singles out a dataset X using the output of a data release mechanism M(X) if it manages to a predicate p matching exactly one row in X with probability much better than a statistical baseline. A data release mechanism that precludes such attacks is secure against predicate singling out (PSO secure).

We argue that PSO security is a mathematical concept with legal consequences. Any data release mechanism that purports to “render anonymous” personal data under the GDPR must be secure against singling out, and hence must be PSO secure. We then analyze PSO security, showing that it fails to self-compose. Namely, a combination of $\omega(\log n)$ exact counts, each individually PSO secure, enables an attacker to predicate single out. In fact, the composition of just two PSO secure mechanisms can fail to provide PSO security.

Finally, we ask whether differential privacy and k-anonymity are PSO secure. Leveraging a connection to statistical generalization, we show that differential privacy implies PSO security. However, k-anonymity does not: there exists a simple and general predicate singling out attack under mild assumptions on the k-anonymizer and the data distribution.