The second GTACS of the year will be at IDC Herzliya, Mon, Mar 5th, 2018
at the Efi Arazi School of Computer Science.
Registration and breaks will be in the M.Sc. lab of the Computer Science/Communications building (there will be signs once you reach the building). The seminars will be held in room C.109 (also on the first floor of the CS building).
PROGRAM
09:30-10:00 Coffee & Registration
10:00-11:00 Benny Pinkas, Circuit-based Private Set Intersection
11:00-11:15 Coffee break
11:15-12:15 Lisa Kohl, On Tightly Secure Non-Interactive Key Exchange
12:15-13:30 Lunch
13:30-14:30 Eyal Ronen, How to (not) share a password: Privacy preserving protocols for finding heavy hitters with adversarial behavior
14:30-14:45 Coffee break
14:45-15:45 Nir Bitansky, Multi-Collision Resistance: A Paradigm for Keyless Hash Functions
ABSTRACTS
Benny Pinkas, Bar Ilan University
Circuit-based Private Set Intersection
Abstract:
While there has been a lot of progress in designing efficient custom protocols for computing Private Set Intersection (PSI), there has been less research on using generic Multi-Party Computation (MPC) protocols for this task. However, there are many variants of the set intersection functionality that are not addressed by the existing custom PSI solutions and are easy to compute with generic MPC protocols (e.g., comparing the cardinality of the intersection with a threshold or measuring ad conversion rates).
Generic PSI protocols evaluate circuits which compute the intersection. For sets of size n, the best known circuit constructions compute O(nlogn/loglogn) comparisons. We propose two new circuit-based protocols for computing generic variants of the intersection. The first construction uses an almost linear number of comparisons and is based on new variants of Cuckoo hashing in two dimensions. The second construction has a linear overhead and is based on obliviously computing programmable pseudo-random functions. For both protocols we analyze both the asymptotic overhead, and the concrete efficiency. We experimentally show that the run-time is concretely better than that of existing constructions.
Lisa Kohl, Karlsruhe Insitute of Technology (KIT)
On Tightly Secure Non-Interactive Key Exchange
Abstract:
We consider the reduction loss of security reductions for non-interactive key exchange (NIKE) schemes. Currently, no tightly secure NIKE schemes exist, and in fact Bader et al. (EUROCRYPT 2016) provide a lower bound (of O(n^2), where n is the number of parties an adversary interacts with) on the reduction loss for a large class of NIKE schemes.
We offer two results: the first "somewhat tight" NIKE scheme (with a reduction loss of n/2) that circumvents the lower bound of Bader et al., but is of course still far from tightly secure. Second, we provide a generalization of Bader et al.'s lower bound to a larger class of NIKE schemes (that also covers our NIKE scheme), with an adapted lower bound of n/2 on the reduction loss. Hence, in that sense, the reduction for our NIKE scheme is optimal.
This is joint work with Julia Hesse and Dennis Hofheinz.
Eyal Ronen, Weizmann Institute of Science
Abstract:
Bad choices of passwords were and are a pervasive problem. Most password alternatives (such as two-factor authentication) may increase cost and arguably hurt the usability of the system. This is of special significance for low cost IoT devices.
Users choosing weak passwords do not only compromise themselves, but the whole ecosystem. For example, common and default passwords in IoT devices were exploited by hackers to create botnets and mount severe attacks on large Internet services, such as the Mirai botnet DDoS attack.
We present a method to help protect the Internet from such large scale attacks. We enable a server to identify popular passwords (heavy hitters), and publish a list of over-popular passwords that must be avoided. This filter ensures that no single password can be used to comprise a large percentage of the users. The list is dynamic and can be changed as new users are added or when current users change their passwords. We apply maliciously secure two-party computation and differential privacy to protect the users' password privacy. Our solution does not require extra hardware or cost, and is transparent to the user.
Our private heavy hitters construction is secure even against a malicious coalition of devices which tries to manipulate the protocol in order to hide the popularity of some password that the attacker is exploiting. Moreover it ensures differential privacy under continues observation of the blacklist as it changes over time. We implemented and analyze the performance of a proof-of-concept.
Our construction can also be used in other settings to privately learn heavy hitters in the presence of an active malicious adversary. For example, learning the most popular sites accessed by the TOR network.
Joint work with Moni Naor and Benny Pinkas.
Nir Bitansky, Tel-Aviv University
Multi-Collision Resistance: A Paradigm for Keyless Hash Functions
Abstract:
We introduce a new notion of multi-collision resistance for keyless hash functions. This is a natural relaxation of collision resistance where it is hard to find multiple inputs with the same hash in the following sense. The number of colliding inputs that a polynomial-time non-uniform adversary can find is not much larger than its advice. We discuss potential candidates for this notion and study its applications.
Assuming the existence of such hash functions, we construct a 3-message zero knowledge argument (with a negligible soundness error) against arbitrary polynomial-size non-uniform adversaries, a long standing open problem. We also improve the round complexity in several other central applications, including a 3-message succinct argument of knowledge for NP, a 4-message epsilon-zero-knowledge proof, and a 5-message public-coin zero-knowledge argument. Our techniques can also be applied in the keyed setting, where we match the round complexity of known protocols while relaxing the underlying assumption from (keyed) collision-resistance to (keyed) multi-collision resistance.
The core technical contribution behind our results is a domain extension transformation from multi-collision-resistant hash functions for a fixed input length to ones with an arbitrary input length and a local opening property. The transformation is based on a combination of classical domain extension techniques, together with new information-theoretic tools. In particular, we define and construct a new variant of list-recoverable codes, which may be of independent interest.
Joint work with Yael Kalai and Omer Paneth