CWI Cryptology Group

Abstract: We present Mosaic, a modular cryptographic framework for Private Fuzzy Heavy Hitters Detection, a new problem introduced and formalized in this work. In this problem, a service provider aims to identify the most frequent items (i.e., heavy hitters) in private client data without learning any individual client's data. Motivated by real-world applications where inputs are inherently noisy, we consider fuzzy heavy hitters that are close to a sufficiently large number of client data points under a chosen distance metric. Mosaic operates in the setting with two non-colluding servers and supports both the known-dictionary setting (where candidate fuzzy heavy hitters are fixed in advance) and the unknown-dictionary setting (where popular items must be discovered). The framework proceeds in two phases: during the upload phase, each client shares an encoding of their input with each server; in the fuzzy matching phase, the servers jointly identify fuzzy heavy hitters without learning any additional information about individual client's data. In the upload phase, Mosaic introduces a new cryptographic primitive called Property-Based Function Secret Sharing (PB-FSS), which relaxes the standard notion of FSS (Boyle et al., Eurocrypt 2015) in that the outputs of the FSS evaluations satisfy a certain property, rather than forming exact additive secret shares of the function output. We present a suite of new PB-FSS constructions for the L_inf and L_p distance metrics from lightweight cryptographic techniques.Furthermore, we introduce new methods to prevent malicious client behavior by detecting malformed PB-FSS shares. In the fuzzy matching phase, Mosaic presents two approaches, one involving only the two servers, and one involving an additional trusted dealer to improve efficiency. All parties are assumed to be semi-honest during the fuzzy matching phase. Finally, we implement Mosaic and evaluate it using real-world trace data from a ride-sharing service. In one scenario, Mosaic servers discovered over a thousand of the most popular ride start locations among 21 thousand users within 30-90 seconds. On the user side, the protocol requires only lightweight computation (as low as 0.14 millisecond) and communication (as low as 9 KB).

Abstract: We initiate the study of basing the hardness of hinted ISIS problems (i.e. with trapdoor information, or ‘hints’) on the previously conjectured space-time hardness of lattice problems without hints. We present two main results. 1. If there exists an efficient algorithm for hinted ISIS that outputs solutions a constant factor longer than the hints, then there exists a single-exponential time and polynomial memory zero-centred spherical Gaussian sampler solving hinted SIS with norm a constant factor shorter than the hints. 2. Assume the existence of a chain of algorithms for hinted ISIS each taking as input Gaussian hints whose norms decrease by a constant factor at each step in the chain, then there exists a single-exponential time and polynomial memory algorithm for SIS with norm a quasilinear factor from optimal. The existence of such hinted ISIS solvers implies single-exponential time and polynomial memory algorithms for worst-case lattice problems, contradicting a conjecture by Lombardi and Vaikuntanathan (CRYPTO’20) and all known algorithms. This suggests that hinted ISIS is hard. Apart from advancing our understanding of hinted lattice problems, an immediate consequence is that signing the same message twice in GPV-style [Gentry–Peikert–Vaikuntanathan, STOC’08] schemes (without salting or derandomisation) likely does not compromise unforgeability. Also, cryptanalytic attempts on the One-More-ISIS problem [Agrawal–Kirshanova–Stehlé-Yadav, CCS’22] likely will need to overcome the conjectured space-time hardness of lattices.

Abstract: In this talk, we will discuss new algorithms for the Shortest Vector Problem, including one running in time 2^{n/2} and others that break the 2^n barrier. We focus on the two algorithms that exploit a spectral property of the periodic Gaussian function F: for a shortest vector v, the gradient (or Hessian) of F at cv, for a small scalar c, is approximately proportional to v (or vv^t, respectively). If time permits, I will also discuss my (or our) role and the role of AI in this research journey, which may, in fact, be the more interesting part of the talk in the current era. The abstract of this talk is generated by human, and modified by AI, and then modified again by human. The presenter taks full responsibility for the content of this talk.