## In this issue

1. [2023/559] Weakening Assumptions for Publicly-Verifiable Deletion
2. [2023/1389] Cuckoo Commitments: Registration-Based Encryption ...
3. [2023/1537] DEFEND: Towards Verifiable Delay Functions from ...
4. [2023/1590] Single trace HQC shared key recovery with SASCA
5. [2023/1591] One-way Functions and Hardness of (Probabilistic) ...
6. [2023/1592] Analysis of one semi-quantum-honest key agreement ...
7. [2023/1593] Multi-Party Homomorphic Secret Sharing and ...
8. [2023/1594] Secure Noise Sampling for DP in MPC with Finite ...
9. [2023/1595] CDLS: Proving Knowledge of Committed Discrete ...
10. [2023/1596] A Black Box Attack Using Side Channel Analysis and ...
11. [2023/1597] Computational FHE Circuit Privacy for Free
12. [2023/1598] Lightweight but Not Easy: Side-channel Analysis of ...
13. [2023/1599] Boomy: Batch Opening Of Multivariate polYnomial ...
14. [2023/1600] Compress: Reducing Area and Latency of Masked ...
15. [2023/1601] The Uber-Knowledge Assumption: A Bridge to the AGM
16. [2023/1602] A one-query lower bound for unitary synthesis and ...
17. [2023/1603] Breaking Parallel ROS: Implication for Isogeny and ...
18. [2023/1604] Manifold Learning Side-Channel Attacks against ...
19. [2023/1605] Three Party Secure Computation with Friends and Foes
20. [2023/1606] Efficient Lattice-based Sublinear Arguments for ...
21. [2023/1607] Crust: Verifiable And Efficient Private Information ...
22. [2023/1608] Can Alice and Bob Guarantee Output to Carol?
23. [2023/1609] How to Prove Statements Obliviously?
24. [2023/1610] An Efficient ZK Compiler from SIMD Circuits to ...
25. [2023/1611] Power circuits: a new arithmetization for GKR- ...
26. [2023/1612] Mitigating MEV via Multiparty Delay Encryption
27. [2023/1613] Toothpicks: More Efficient Fork-Free Two-Round ...
28. [2023/1614] New proof systems and an OPRF from CSIDH
29. [2023/1615] Order vs. Chaos: A Language Model Approach for ...
30. [2023/1616] DeVoS: Deniable Yet Verifiable Vote Updating
31. [2023/1617] Designing Efficient and Flexible NTT Accelerators
32. [2023/1618] Improved algorithms for finding fixed-degree ...
33. [2023/1619] Encode and Permute that Database! Single-Server ...
34. [2023/1620] Commitments from Quantum One-Wayness
35. [2023/1621] Withdrawable Signature: How to Call off a Signature
36. [2023/1622] Max Attestation Matters: Making Honest Parties Lose ...
37. [2023/1623] Concrete Analysis of Quantum Lattice Enumeration
38. [2023/1624] On the (Not So) Surprising Impact of Multi-Path ...
39. [2023/1625] SPA-GPT: General Pulse Tailor for Simple Power ...
40. [2023/1626] Et tu, Brute? SCA Assisted CCA using Valid ...
41. [2023/1627] Defeating Low-Cost Countermeasures against Side- ...

## 2023/559

* Title: Weakening Assumptions for Publicly-Verifiable Deletion
* Authors: James Bartusek, Dakshita Khurana, Giulio Malavolta, Alexander Poremba, Michael Walter
* [Permalink](https://eprint.iacr.org/2023/559)
* [Download](https://eprint.iacr.org/2023/559.pdf)

### Abstract

We develop a simple compiler that generically adds publicly-verifiable deletion to a variety of cryptosystems. Our compiler only makes use of one-way functions (or one-way state generators, if we allow the public verification key to be quantum). Previously, similar compilers either relied on the use of indistinguishability obfuscation (Bartusek et. al., ePrint:2023/265) or almost-regular one-way functions (Bartusek, Khurana and Poremba, arXiv:2303.08676).

## 2023/1389

* Title: Cuckoo Commitments: Registration-Based Encryption and Key-Value Map Commitments for Large Spaces
* Authors: Dario Fiore, Dimitris Kolonelos, Paola de Perthuis
* [Permalink](https://eprint.iacr.org/2023/1389)
* [Download](https://eprint.iacr.org/2023/1389.pdf)

### Abstract

Registration-Based Encryption (RBE) [Garg et al. TCC'18] is a public-key encryption mechanism in which users generate their own public and secret keys, and register their public keys with a central authority called the key curator.
Similarly to Identity-Based Encryption (IBE), in RBE users can encrypt by only knowing the public parameters and the public identity of the recipient. Unlike IBE, though, RBE does not suffer the key escrow problem — one of the main obstacles of IBE's adoption in practice — since the key curator holds no secret.

In this work, we put forward a new methodology to construct RBE schemes that support large users identities (i.e., arbitrary strings). Our main result is the first efficient pairing-based RBE for large identities.
Prior to our work, the most efficient RBE is that of [Glaeser et al. ePrint'22] which only supports small identities. The only known RBE schemes with large identities are realized either through expensive non-black-box techniques (ciphertexts of 3.6 TB for 1000 users), or via a specialized lattice-based construction [Döttling et al. Eurocrypt'23] (ciphertexts of 2.4 GB), or through the more complex notion of Registered Attribute-Based Encryption [Hohenberger et al. Eurocrypt’23]. By unlocking the use of pairings for RBE with large identity space, we enable a further improvement of three orders of magnitude, as our ciphertexts for a system with 1000 users are 1.7 MB.

The core technique of our approach is a novel use of cuckoo hashing in cryptography that can be of independent interest. We give two main applications. The first one is the aforementioned RBE methodology, where we use cuckoo hashing to compile an RBE with small identities into one for large identities. The second one is a way to convert any vector commitment scheme into a key-value map commitment. For instance, this leads to the first algebraic pairing-based key-value map commitments.

## 2023/1537

* Title: DEFEND: Towards Verifiable Delay Functions from Endomorphism Rings
* Authors: Knud Ahrens, Jens Zumbrägel
* [Permalink](https://eprint.iacr.org/2023/1537)
* [Download](https://eprint.iacr.org/2023/1537.pdf)

### Abstract

We present a verifiable delay function based on isogenies of supersingular elliptic curves, using Deuring correspondence and computation of endomorphism rings for the delay. For each input x a verifiable delay function has a unique output y and takes a predefined time to evaluate, even with parallel computing. Additionally, it generates a proof by which the output can efficiently be verified. In our approach the input is a path in the 2-isogeny graph and the output is the maximal order isomorphic to the endomorphism ring of the curve at the end of that path. This approach is presumably quantum-secure, does not require a trusted setup or special primes and the verification is independent from the delay. It works completely within the isogeny setting and the computation of the proof causes no overhead. The efficient sampling of challenges however remains an open problem.

## 2023/1590

* Title: Single trace HQC shared key recovery with SASCA
* Authors: Guillaume Goy, Julien Maillard, Philippe Gaborit, Antoine Loiseau
* [Permalink](https://eprint.iacr.org/2023/1590)
* [Download](https://eprint.iacr.org/2023/1590.pdf)

### Abstract

This paper presents practicable single trace attacks against the Hamming Quasi-Cyclic (HQC) Key Encapsulation Mechanism. These attacks are the first Soft Analytical Side-Channel Attacks (SASCA) against code-based cryptography. We mount SASCA based on Belief Propagation (BP) on several steps of HQC's decapsulation process. Firstly, we target the Reed-Solomon (RS) decoder involved in the HQC publicly known code. We perform simulated attacks under Hamming weight leakage model, and reach excellent accuracies (superior to $0.9$) up to a high noise level ($\sigma = 3$), thanks to a re-decoding strategy. In a real case attack scenario, on a STM32F407, this attack leads to a perfect success rate. Secondly, we conduct an analogous attack against the RS encoder used during the re-encryption step required by the Fujisaki-Okamoto-like transform. Both in simulation and practical instances, results are satisfactory and this attack represents a threat to the security of HQC. Finally, we analyze the strength of countermeasures based on masking and shuffling strategies. In line with previous SASCA literature targeting Kyber, we show that masking HQC is a limited countermeasure against BP attacks, as well as shuffling countermeasures adapted from Kyber. We evaluate the ``full shuffling'' strategy which thwarts our attack by introducing sufficient combinatorial complexity. Eventually, we highlight the difficulty of protecting the current RS encoder with a shuffling strategy. A possible countermeasure would be to consider another encoding algorithm for the scheme to support a full shuffling. Since the encoding subroutine is only a small part of the implementation, it would come at a small cost.

## 2023/1591

* Title: One-way Functions and Hardness of (Probabilistic) Time-Bounded Kolmogorov Complexity w.r.t. Samplable Distributions
* Authors: Yanyi Liu, Rafael Pass
* [Permalink](https://eprint.iacr.org/2023/1591)
* [Download](https://eprint.iacr.org/2023/1591.pdf)

### Abstract

Consider the recently introduced notion of \emph{probabilistic
time-bounded Kolmogorov Complexity}, pK^t (Goldberg et al,
CCC'22), and let MpK^tP denote the language of pairs (x,k) such that pK^t(x) \leq k.
We show the equivalence of the following:
- MpK^{poly}P is (mildly) hard-on-average w.r.t. \emph{any} samplable
distribution D;
- MpK^{poly}P is (mildly) hard-on-average w.r.t. the
\emph{uniform} distribution;
- Existence of one-way functions.
As far as we know, this yields the first natural class of problems where
hardness with respect to any samplable distribution is equivalent
to hardness with respect to the uniform distribution.