On March 22nd, the Friday before Easter week in Denmark, we will hold the fourth NordiCrypt meetup at DTU in Kongens Lyngby in Building 116, Auditorium 82. We will start at 10:30 am, so you can arrive from Aarhus (or Sweden) on the same day.
To attend the workshop, you can take buses 150S or 15E from Nørreport to Rævehøjvej/DTU station, from where building 116 is only a 5-10min walk away.
Alternatively, you can take the A or E S-Tog from København H or Nørreport until Lyngby Station, and take the 300S bus from there.
11:00 Felix Engelmann (Lund University): Updatable Privacy-Preserving Blueprints
Privacy-preserving blueprints enable users to create escrows using the auditor's public key. An escrow encrypts the evaluation of a function P(t,x) , where is a secret input used to generate the auditor's key and x is the user's private input to escrow generation. Nothing but P(t,x) is revealed even to a fully corrupted auditor. The original definition and construction (Kohlweiss et al., EUROCRYPT'23) only support the evaluation of functions on an input provided by a single user. We address this limitation by introducing updatable privacy-preserving blueprint schemes (UPPB), which enhance the original notion with the ability for multiple parties to non-interactively update the private value x in a blueprint. Moreover, a UPPB scheme allows for verifying that a blueprint is the result of a sequence of valid updates while revealing nothing else.
We present uBlu, an efficient instantiation of UPPB for computing a comparison between private user values and a private threshold t set by the auditor, where the current value x is the cumulative sum of private inputs, which enables applications such as privacy-preserving anti-money laundering and location tracking. Additionally, we show the feasibility of the notion generically for all value update functions and (binary) predicates from FHE and NIZKs. Our main technical contribution is a technique to keep the size of primary blueprint components independent of the number of updates and reasonable for practical applications. This is achieved by elegantly extending an algebraic NIZK by Couteau and Hartmann (CRYPTO'20) with an update function and making it compatible with our additive updates. This result is of independent interest and may find additional applications thanks to the concise size of our proofs.
11:25 Rahul Bangalore Satish (ITU): Garbling gadgets and it's applications to oblivious garbling
Garbling schemes are one of the most fundamental objects in cryptography and have been studied extensively due to their broad applicability. The state-of-the-art is a construction in which XOR gates are free and AND gates require $3\kappa/2+\cO(1)$ bits per gate, due to Rosulek and Roy (CRYPTO'21). An important technique in their garbling is slicing, which partitions the labels into two equal-length slices. In this paper, we explore the feasibility of the slicing technique for garbling schemes beyond the results introduced by Rosulek and Roy, demonstrating both its potential and its limitations.
In particular, we extend this technique to demonstrate the garbling of certain higher fan-in gadgets, and then use this to show that it is possible to garble 2-input AND gates at a cost of $4\kappa/3 +\cO(1)$ bits. We then give a separation result showing that sliced garbling cannot be used to garble higher fan-in gadgets of degree $\geq 3$ when restricted to making queries that are linear functions of the input labels to the random oracle. We further demonstrate the usefulness of our techniques in the context of oblivious garbling, a newly introduced concept for capturing circuit hiding from the garbler. The complexity of our construction is superior to that of universal circuits, and grows linearly with circuit size.
13:00 Mustafa Khairallah (Lund): Cryptanalysis of TNT: a new chapter in the LRW paradigm
Liskov, Rivest, and Wagner laid the theoretical foundations for tweakable block ciphers (TBC). In a seminal paper, they proposed two (up to) birthday-bound secure design strategies --- LRW1 and LRW2 --- to convert any block cipher into a TBC. Several of the follow-up works consider cascading LRW-type TBCs to construct beyond-the-birthday bound (BBB) secure TBCs. Landecker et al. demonstrated that just a two-round cascading of LRW2 can already give BBB security. Bao et al. undertook a similar exercise in the context of LRW1 with TNT --- a three-round cascading of LRW1 --- that has been shown to achieve BBB security as well. In this talk, we present a CCA distinguisher on TNT that achieves a non-negligible advantage with O(2^{n/2}) queries, directly contradicting the security claims made by the designers. We discuss the cryptanalysis process, a scalable advantage calculation, and experimental verifications that further support our claim.
As part of the work, we also reinforce the birthday-bound security of TNT and show that it is also true for its single-key variant. Furthering on to a more positive note, we show that adding just one more block cipher call, referred to as 4-LRW1, does not just reestablish the BBB security, but also amplifies it up to 2^{3n/4} queries. As a side-effect of this endeavour, we propose a new abstraction of the cascaded LRW-design philosophy, referred to as the LRW+ paradigm, comprising two block cipher calls sandwiched between a pair of tweakable universal hashes. This helps us to provide a modular-proof approach covering all cascaded LRW constructions with at least 2 rounds, including 4-LRW1, and its more established relative, the well-known CLRW2, or more aptly, 2-LRW2.
13:25 Pierre Meyer (AU): tbd
tbd
13:50 Christian Majenz (DTU): SDitH in the QROM
Since the seminal work of Ishai, Kushilevitz, Ostrovsky and Sahai, the MPCitH technique has enjoyed increasing popularity, especially due to the fact that it can be used to construct post-quantum-secure digital signature schemes. For the NIST digital signature “onramp”, a number of candidates have been submitted using various one-way functions at their core, including one based on the Syndrome Decoding in the Head (SDitH) proposal by Feneuil, Joux and Rivain. In this talk, I will describe the SDitH scheme, giving enough detail to gain an intuitive understanding of the structure and security of 5-round identification (ID) scheme used, and how the need for 5 rounds arises. Subsequently, I will describe how the scheme is compressed to 3 rounds by Fiat-Shamir-transforming (FS) the first round trip in the quantum-accessible random oracle model (QROM), to allow application of an existing tight QROM reduction to obtain extractability of the (fully) FS transformed scheme from generalized special soundness. To round of the talk, I will give a teaser of ongoing work generalizing the round compression technique to a large class of ID schemes, that should include the one underlying FAEST and a number of other MPCitH schemes.
14:50 Arup Mondal (ITU): Accountability for Threshold Decryption
Keeping decrypting parties accountable in public key encryption is notoriously hard since the secret key owner can decrypt any arbitrary ciphertext. Threshold encryption aims at solving this issue by distributing the power to decrypt among a set of parties, who must interact via a decryption protocol. However, such parties can employ cryptographic tools such as Multiparty Computation (MPC) to decrypt arbitrary ciphertexts without being detected. We introduce the notion of (threshold) encryption with Self-Incriminating Proofs, where parties must produce a self-incriminating proof of decryption when decrypting every ciphertext. In the standard public key encryption case, the adversary could simply destroy these proofs, so we strengthen our notion to guarantee that the proofs are published when decryption succeeds. This creates a decryption audit trail, which is useful in scenarios where decryption power is held by a single trusted party (e.g., a Trusted Execution Environment) who must be kept accountable. In the threshold case, we ensure that at least one of the parties who execute the decryption protocol will learn a self-incriminating proof, even if they employ advanced tools such as MPC. The fact that a party learns the proof and may leak it at any moment acts as a deterrent for parties who do not wish to be identified as malicious decryptors (e.g. a commercial operator of a service based on threshold encryption). We investigate the (im)possibility and applications of our notions while providing matching constructions under appropriate assumptions. In the threshold case, we build on recent results on Individual Cryptography (CRYPTO 2023).
15:15 Fabrizio Sisinni (DTU): Provable security against decryption failure attacks from LWE
Through several improvements in the last years we are getting tighter bound for the Fujisaki-Okamoto (FO) transform both in the Random Oracle Model and in the Quantum Random Oracle Model. In a recent work, Hövelmanns, Hülsing and Majenz introduced a new security proof for the FO transform in the quantum-accessible random oracle model (QROM) used in post-quantum key encapsulation mechanisms. While having a smaller security loss due to ecryption failures present in many constructions, it requires two new security properties of the underlying public-key encryption scheme (PKE).
We describe one of these property, called Find Non-Generically Failing Plaintexts (FFP-NG). We show how to recover information from an LWE sample by adding an extra error to it. We do so by describing a security reduction from the LWE problem to the FFP-NG security of the PVW scheme. For the reduction we use a variant of the PVW scheme in which all errors are discrete Gaussian distributed. To analyse the probability distributions we encounter during the proof, we use the framework introduced by Genise, Micciancio, Peikert and Walter. This framework allows us to describe all the results about convolutions of discrete Gaussians by using simple linear algebra.
15:40 Jens Groth (Nexus): Memory checking in zkVMs
In zkVMs based on folding, instances and witnesses pertaining to correct instruction execution are continuously compressed together to create more compact instances and witnesses. While instruction execution is a local operation, memory accesses may reference data created many instruction cycles earlier. This talk will present techniques to verify memory accesses in the context of folding and incrementally verifiable execution.
We booked tables at Restaurant Vespa in central Copenhagen. The restaurant is directly next to the Marmorkirken metro stop.
The dinner has a fixed menu and includes drinks such as wine and beer as well, at a fixed price of 545 DKK per person. We will inform the restaurant if you have dietary restrictions (vegetarian and vegan options are offered).