[crypto] Fwd: CWG: 29 Nov schedule

[R. Hirschfeld]

-------- Original Message --------
Subject: CWG: 29 Nov schedule
Date: 2024-11-15 09:00
 From: "Guarise Vieira, Heloise" <h.guarise.vieira at tue.nl>
To:


Dear all,

Please find below the schedule for the next Crypto Working Group.
This meeting will be held on 29 November, in Utrecht, at the Kargadoor 
(Oudegracht 36).

Best regards,


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

--

[Image]

Heloise Vieira, PhD
Discrete Mathematics Cluster, Project Leader
Department of Mathematics and Computer Science
Phone number +31 (0)402474864

De Zaale, Eindhoven
05 MetaForum, MF 6.101