## IACR News

Here you can see all recent updates to the IACR webpage. These updates are also available:

#### 09 February 2024

###### Patrick Struck, Maximiliane Weishäupl

ePrint Report###### Haoqian Zhang, Michelle Yeo, Vero Estrada-Galinanes, Bryan Ford

ePrint Report###### Yanxue Jia, Varun Madathil, Aniket Kate

ePrint ReportHomeRun stands out by providing unlinkability across multiple requests for the same recipient's address. Moreover, it does not impose a limit on the number of pertinent messages that can be received by a recipient, which thwarts ``message balance exhaustion'' attacks and enhances system usability. HomeRun also empowers servers to regularly delete the retrieved messages and the associated auxiliary data, which mitigates the constantly increasing computation costs and storage costs incurred by servers. Remarkably, none of the existing solutions offer all of these features collectively. Finally, thanks to its judicious use of highly efficient cryptographic building blocks, HomeRun is highly performant: Specifically, the total runtime of servers in HomeRun is $3830 \times$ less than that in the work by Liu et al. (CRYPTO '22) based on fully-homomorphic encryption, and at least $1459 \times$ less than that in the design by Madathil et al. (USENIX Security '22) based on two semi-honest and non-colluding servers, using a single thread in a WAN setting.

###### Anna-Maurin Graner, Björn Kriepke, Lucas Krompholz, Gohar M. Kyureghyan

ePrint Report###### Daniel Dobkin, Nimrod Cever, Itamar Levi

ePrint Report###### Alexandre Belling, Azam Soleimanian, Bogdan Ursu

ePrint ReportVortex is a list polynomial commitment, obtained through a modification of Ligero (CCS 2017), inspired by the schemes of Brakedown (Crypto 2023), batch-FRI (FOCS 2020), and RedShift (CCS 2022). Concerning one application of Vortex, for a witness of size $N$, the messages between the prover and the verifier are of size $O(N^{1/2})$. Vortex is a core component of the SNARK used by the prover of Linea (Consensys). This paper provides a complete security analysis for Vortex. We use a general compiler to build an Argument of Knowledge (AoK) by combining our list polynomial commitment and a polynomial-IOP (PIOP).

The approach is similar to combining a PIOP with a polynomial commitment scheme and has a soundness loss only linear in the list size. This overcomes a previous limitation in the standard compiler from a generic PIOP and a list polynomial commitment scheme to an interactive argument of knowledge, which suffers from a soundness loss of $\mathcal{O}(|L|^r)$ (where $|L|$ is the list size and $r$ is the number of interactions between the prover and the verifier in the PIOP).

###### Rafael del Pino, Shuichi Katsumata, Mary Maller, Fabrice Mouhartem, Thomas Prest, Markku-Juhani Saarinen

ePrint ReportWe present the first efficient lattice-based threshold signatures with signature size 13 KiB and communication cost 40 KiB per user, supporting a threshold size as large as 1024 signers. We provide an accompanying high performance implementation. The security of the scheme is based on the same assumptions as Dilithium, a signature recently selected by NIST for standardisation which, as far as we know, cannot easily be made threshold efficiently.

All operations used during signing are due to symmetric primitives and simple lattice operations; in particular our scheme does not need heavy tools such as threshold fully homomorphic encryption or homomorphic trapdoor commitments as in prior constructions. The key technical idea is to use one-time additive masks to mitigate the leakage of the partial signing keys through partial signatures.

###### Balthazar Bauer, Georg Fuchsbauer

ePrint ReportThe original EQS construction (J.Crypto'19) is only proven in the generic group model, while the first construction from standard assumptions (PKC'18) only yields security guarantees insufficient for most applications. Two works (AC'19, PKC'22) propose applicable schemes which assume the existence of a common reference string for the anonymity notion. Their unforgeability is argued via a security proof from standard (or non-interactive) assumptions.

In this work we show that their security proof is flawed and explain the subtle issue.

###### Minghui Xu, Jiahao Zhang, Hechuan Guo, Xiuzhen Cheng, Dongxiao Yu, Qin Hu, Yijun Li, Yipu Wu

ePrint Report###### Dongwon Lee, Seonhong Min, Yongsoo Song

ePrint ReportThis paper introduces a new bootstrapping framework for the Fan-Vercuteren (FV) scheme, called the functional bootstrapping, providing more generic and advanced functionality than the ordinary bootstrapping method. More specifically, the functional bootstrapping allows us to evaluate an arbitrary function while removing the error of an input ciphertext. Therefore, we achieve better depth consumption and computational complexity as the evaluation of a circuit can be integrated as part of the functional bootstrapping procedure. In particular, our approach extends the functionality of FV since it is even applicable to functions between different plaintext spaces.

At the heart of our functional bootstrapping framework is a novel homomorphic Look-Up Table (LUT) evaluation method where we represent any LUT using only the operations supported by the FV scheme. Finally, we provide a proof-of-concept implementation and present benchmarks. In concrete examples, such as delta and sign functions, our functional bootstrapping takes about 46.5s or 171.4s for 9-bit or 13-bit plaintext modulus, respectively.

###### Aya Fukami, Richard Buurke, Zeno Geradts

ePrint Report###### Pedro Branco, Russell W. F. Lai, Monosij Maitra, Giulio Malavolta, Ahmadreza Rahimi, Ivy K. Y. Woo

ePrint ReportIn this work, we propose a new model for traitor-tracing systems where, instead of having a key authority, users could generate and register their own public keys. The public parameters are computed by aggregating all user public keys. Crucially, the aggregation process is \emph{public}, thus eliminating the need of any trusted authority. We present two new traitor-tracing systems in this model based on bilinear pairings. Our first scheme is proven adaptively secure in the generic group model. This scheme features a transparent setup, ciphertexts consisting of $6\sqrt{L}+4$ group elements, and a public tracing algorithm. Our second scheme supports a bounded collusion of traitors and is proven selectively secure in the standard model. Our main technical ingredients are new registered functional encryption (RFE) schemes for quadratic and linear functions which, prior to this work, were known only from indistinguishability obfuscation. To substantiate the practicality of our approach, we evaluate the performance a proof of concept implementation. For a group of $L = 1024$ users, encryption and decryption take roughly 50ms and 4ms, respectively, whereas a ciphertext is of size 6.7KB.

###### Dung Bui, Geoffroy Couteau, Pierre Meyer, Alain Passelègue, Mahshid Riahinia

ePrint Report#### 06 February 2024

###### Engineering Department, Horizen Labs, Remote

Job PostingWe are looking for a talented and motivated engineer who will contribute to building the cryptographic infrastructure of our Web 3.0-enabled blockchain ecosystem. You will be involved in the design and implementation of blockchain scaling solutions, primarily based on zero-knowledge cryptography, with the aim of dramatically reducing the costs that blockchain operators incur when deploying their products. Our international team works in a stimulating and innovative environment, where technical expertise and experience contribute to the development of cutting-edge blockchain technology. You will be joining a small, deeply driven team of highly technical minds in a culture of openness, pragmatism, and ownership of challenging problems that span software engineering, systems design, cryptography, and computing.

**What You’ll Own**

- Design and implementation of blockchain-based cryptographic solutions leveraging modern cryptography (ZK, MPC, FHE).
- Assume technical responsibility of novel systems while identifying areas for innovative research and development.
- Writing reusable, testable, and efficient code with a focus on best practices and security.
- Help shape the future of the company where you will be intimately involved in the strategic decision making process and immediately see the impact of your contributions.
- Attend conferences and find opportunities in the on-chain ecosystem.

**Closing date for applications:**

**Contact:** People & Talent Team -
recruiting@horizenlabs.io

**More information:** https://boards.greenhouse.io/horizenlabs/jobs/5075393004

###### Qiaohan Chu, Li Lin, Chen Qian, Jie Chen

ePrint Report###### Panos Kampanakis, Will Childs-Klein

ePrint Report###### Quang Dao, Aayush Jain

ePrint ReportIn this work, we propose a new code-based assumption: Dense-Sparse LPN, that falls in the complexity class $\mathcal{BPP}^{\mathcal{SZK}}$ and is conjectured to be secure against subexponential time adversaries. Our assumption is a variant of LPN that is inspired by McEliece's cryptosystem and random $k\mbox{-}$XOR in average-case complexity. Roughly, the assumption states that \[(\mathbf{T}\, \mathbf{M}, \mathbf{s} \,\mathbf{T}\, \mathbf{M} + \mathbf{e}) \quad \text{is indistinguishable from}\quad (\mathbf{T} \,\mathbf{M}, \mathbf{u}),\] for a random (dense) matrix $\mathbf{T}$, random sparse matrix $\mathbf{M}$, and sparse noise vector $\mathbf{e}$ drawn from the Bernoulli distribution with inverse polynomial noise probability.

We leverage our assumption to build lossy trapdoor functions (Peikert-Waters STOC 08). This gives the first post-quantum alternative to the lattice-based construction in the original paper. Lossy trapdoor functions, being a fundamental cryptographic tool, are known to enable a broad spectrum of both lossy and non-lossy cryptographic primitives; our construction thus implies these primitives in a generic manner. In particular, we achieve collision-resistant hash functions with plausible subexponential security, improving over a prior construction from LPN with noise rate $\frac{\log^2 n}{n}$ that is only quasi-polynomially secure.

###### Randy Kuang

ePrint Report###### Helger Lipmaa, Roberto Parisella, Janno Siim

ePrint Report###### Zeyu Liu, Yunhao Wang

ePrint ReportIn this work, we inspect the BGV/BFV bootstrapping procedure from a different angle. We provide a generalized bootstrapping definition that relaxes the correctness requirement of regular bootstrapping, allowing constructions that support only certain kinds of circuits with arbitrary depth. In addition, our definition captures a form of functional bootstrapping. In other words, the output encrypts a function evaluation of the input instead of the input itself. Under this new definition, we provide a bootstrapping procedure supporting different types of functions. Our construction is 1-2 orders of magnitude faster than the state-of-the-art BGV/BFV bootstrapping algorithms, depending on the evaluated function. Of independent interest, we show that our technique can be used to improve the batched FHEW/TFHE bootstrapping construction introduced by Liu and Wang (Asiacrypt 2023). Our optimization provides a speed-up of 6x in latency and 3x in throughput for batched binary gate bootstrapping and a plaintext-space-dependent speed-up for batched functional bootstrapping with plaintext space smaller than $\mathbb{Z}_{512}$.