10:45h
Asymptotics and Improvements of Sieving for Codes
Simona Etinski
Abstract: A recent work by Guo, Johansson, and Nguyen (Eprint'23) proposes a promising adaptation of Sieving techniques from lattices to codes, in particular, by claiming concrete cryptanalytic improvements on various schemes. The core of their algorithm reduces to a Near Neighbor Search (NNS) problem, for which they devise an ad-hoc approach. This work aims for a better theoretical understanding of this approach. First, we provide an asymptotic analysis not present in the original paper. Second, we propose a more systematic use of well-established NNS machinery, known as Locality Sensitive Hashing and Filtering (LSH/F). LSH/F is an approach that has been applied very successfully in the case of sieving over lattices. We thus establish the first baseline for the sieving approach with a decoding complexity of $2^0.117n$ for the conventional worst parameters (full distance decoding, where complexity is maximized over all code rates). Our cumulative improvements eventually enable us to lower the hardest parameter decoding complexity for SievingISD algorithms to $2^0.101n$. This approach outperforms the BJMM algorithm (Eurocrypt'12) but falls behind the most advanced conventional ISD approach by Both and May (PQCrypto'18). As for lattices, we found the Random-Spherical-Code-Product (RPC) to give the best asymptotic complexity. Moreover, we also consider an alternative that seems specific to the Hamming Sphere, which we believe could be of practical interest as it plausibly hides less sub-exponential overheads than RPC.

11:30h - coffee break
11:45h
Finding and using unique substructures in tensor graphs with an application to MEDS and ALTEQ
Lars Ran

The Tensor Isomorphism problem is a hardness assumption that is gaining popularity in the cryptographic community in recent years. Two of the schemes in NISTs additional call for signatures, MEDS and ALTEQ, are based on this problem, and multiple new algorithms for solving the problem have been proposed.

In this talk we improve upon one of these algorithms by taking a specific invariant into account. We will look at the tensor graph associated with a tensor and show that in roughly 1/q of the cases this graph has a unique triangle. Furthermore, we can find this triangle algebraically. Finding this triangle on both sides leads to a 3-point collision, greatly improving complexity results.

12:30h - lunch
14:00h
Private Join and Compute in the Real World
Tianxin Tang
Private Join and Compute (PJC), recently proposed by Google, is a two-party protocol for various use-cases, including ad conversion (Asiacrypt 2021). It
generalizes their deployed private set intersection sum (PSI-SUM) protocol (EuroS&P 2020). PJC allows two parties, each holding a key-value database, to privately evaluate the inner product of values whose keys lie in the intersection. While the functionality output is not typically considered in the
security model of the MPC literature, it may pose real-world privacy risks, thus raising concerns about deploying protocols like PJC.
In this talk, I will discuss our findings from analyzing the risks associated with the PJC functionality output. We consider an adversary that is a participating party of PJC and describe four practical attacks that break the other party's input privacy. These attacks can recover both membership of keys
in the intersection and their associated values. Our attacks demonstrate privacy threats associated with deployment and highlight the need to include functionality output as part of the MPC security model.

14:45h - coffee break
15:00h
Pairing-Free Blind Signatures from Standard Assumptions in the ROM
Julia Kastner

The paper is joint work with Michael Reichle and Ky Nguyen.

Blind Signatures are a useful primitive for privacy preserving applications such as electronic payments, e-voting, anonymous credentials, and more. However, existing practical blind signature schemes based on standard assumptions require either pairings or lattices. We present the first practical construction of a round-optimal blind signature in the random oracle model based on standard assumptions without resorting to pairings or lattices. In particular, our construction is secure under the strong RSA assumption and DDH (in pairing-free groups). For our construction, we provide a NIZK-friendly signature based on strong RSA, and efficiently instantiate a variant of Fischlin's generic framework (CRYPTO'06). Our Blind Signature scheme has signatures of size 4.28 KB and communication cost 10.98 KB. On the way, we develop techniques that might be of independent interest. In particular, we provide efficient \emph{relaxed} range-proofs for large ranges with subversion zero-knowledge and compact commitments to elements of arbitrary groups.

15:45h end of activities