[digest] 2024 Week 38

## In this issue

1. [2023/795] Bit-Security Preserving Hardness Amplification
2. [2024/773] SQIPrime: A dimension 2 variant of SQISignHD with ...
3. [2024/876] Distributing Keys and Random Secrets with Constant ...
4. [2024/1438] Anamorphic Authenticated Key Exchange: Double Key ...
5. [2024/1439] Scabbard: An Exploratory Study on Hardware Aware ...
6. [2024/1440] Trojan Insertion versus Layout Defenses for Modern ...
7. [2024/1441] FlashSwift: A Configurable and More Efficient Range ...
8. [2024/1442] Design and Implementation of a Fast, Platform- ...
9. [2024/1443] 32-bit and 64-bit CDC-7-XPUF Implementation on a ...
10. [2024/1444] Attestation Proof of Association – provability that ....
11. [2024/1445] Another Walk for Monchi
12. [2024/1446] Updatable Private Set Intersection Revisited: ...
13. [2024/1447] Generic Differential Key Recovery Attacks and Beyond
14. [2024/1448] Randomness in Private Sequential Stateless Protocols
15. [2024/1449] Marian: An Open Source RISC-V Processor with Zvk ...
16. [2024/1450] TentLogiX: 5-bit Chaos-Driven S-Boxes for ...
17. [2024/1451] Traffic-aware Merkle Trees for Shortening ...
18. [2024/1452] On the Complexity of Cryptographic Groups and ...
19. [2024/1453] Breaking and Repairing SQIsign2D-East
20. [2024/1454] Interval Key-Encapsulation Mechanism
21. [2024/1455] Threshold PAKE with Security against Compromise of ...
22. [2024/1456] Crooked Indifferentiability of the Feistel Construction
23. [2024/1457] A Combined Design of 4-PLL-TRNG and 64-bit ...
24. [2024/1458] Providing Integrity for Authenticated Encryption in ...
25. [2024/1459] Verifiable Oblivious Pseudorandom Functions from ...
26. [2024/1460] PPSA: Polynomial Private Stream Aggregation for ...
27. [2024/1461] Detecting and Correcting Computationally Bounded ...
28. [2024/1462] Efficient Fuzzy Private Set Intersection from Fuzzy ...
29. [2024/1463] Asynchronous Verifiable Secret Sharing with Elastic ...
30. [2024/1464] SoK: Descriptive Statistics Under Local ...
31. [2024/1465] Linear approximations of the Flystel construction
32. [2024/1466] Dishonest Majority Constant-Round MPC with Linear ...
33. [2024/1467] P2C2T: Preserving the Privacy of Cross-Chain Transfer
34. [2024/1468] Dense and smooth lattices in any genus
35. [2024/1469] Password-Protected Threshold Signatures
36. [2024/1470] Quantum Pseudorandom Scramblers
37. [2024/1471] Communication Efficient Secure and Private Multi- ...
38. [2024/1472] Isogeny-Based Secure Voting Systems for Large-Scale ...
39. [2024/1473] A Note on Low-Communication Secure Multiparty ...
40. [2024/1474] Mystrium: Wide Block Encryption Efficient on Entry- ...
41. [2024/1475] On the Spinor Genus and the Distinguishing Lattice ...
42. [2024/1476] The Concrete Security of Two-Party Computation: ...
43. [2024/1477] Signature-based Witness Encryption with Compact ...
44. [2024/1478] Mind the Bad Norms: Revisiting Compressed Oracle- ...

## 2023/795

* Title: Bit-Security Preserving Hardness Amplification
* Authors: Shun Watanabe, Kenji Yasunaga
* [Permalink](https://eprint.iacr.org/2023/795)
* [Download](https://eprint.iacr.org/2023/795.pdf)

### Abstract

Hardness amplification is one of the important reduction techniques in cryptography, and it has been extensively studied in the literature. The standard XOR lemma known in the literature evaluates the hardness in terms of the probability of correct prediction; the hardness is amplified from mildly hard (close to $1$) to very hard $1/2 + \varepsilon$ by inducing $\varepsilon^2$ multiplicative decrease of the circuit size. Translating such a statement in terms of the bit-security framework introduced by Micciancio-Walter (EUROCRYPT 2018) and Watanabe-Yasunaga (ASIACRYPT 2021), it may cause a bit-security loss of $\log(1/\varepsilon)$. To resolve this issue, we derive a new variant of the XOR lemma in terms of the R\'enyi advantage, which directly characterizes the bit security. In the course of proving this result, we prove a new variant of the hardcore lemma in terms of the conditional squared advantage; our proof uses a boosting algorithm that may output the $\bot$ symbol in addition to $0$ and $1$, which may be of independent interest.



## 2024/773

* Title: SQIPrime: A dimension 2 variant of SQISignHD with non-smooth challenge isogenies
* Authors: Max Duparc, Tako Boris Fouotsa
* [Permalink](https://eprint.iacr.org/2024/773)
* [Download](https://eprint.iacr.org/2024/773.pdf)

### Abstract

We introduce SQIPrime, a post-quantum digital signature scheme based on the Deuring correspondence and Kani's Lemma.
Compared to its predecessors that are SQISign and especially SQISignHD, SQIPrime further expands the use of high dimensional isogenies, already in use in the verification in SQISignHD, to all its subroutines.
In doing so, it no longer relies on smooth degree isogenies (of dimension 1). Intriguingly, this includes  the challenge isogeny which is also a non-smooth degree isogeny, but has an accessible kernel. The fact that the isogenies do not have rational kernel allows to fit more rational power 2 torsion points which are necessary when computing and representing the response isogeny.
SQIPrime operates with prime numbers of the form $p = 2^\alpha f-1$.

We describe two variants of SQIPrime. SQIPrime4D which incorporates the novelties described above and uses dimension 4 isogenies to represent the response isogeny. The runtime of higher dimensional isogeny computation is exponential in the dimension, hence the smaller the dimension the better for efficiency.. The second variant, SQIPrime2D,  solely uses dimension 2 isogenies. This is achieved by setting the degree of the secret isogeny to be equal to that of the challenge isogeny and  further exploiting Kani's Lemma. SQIPrime2D is more efficient compared to SQIPrime4D and to SQISignHD, at the cost of being comparatively less compact, but still very compact compared to non isogeny based post-quantum signatures.



## 2024/876

* Title: Distributing Keys and Random Secrets with Constant Complexity
* Authors: Benny Applebaum, Benny Pinkas
* [Permalink](https://eprint.iacr.org/2024/876)
* [Download](https://eprint.iacr.org/2024/876.pdf)

### Abstract

In the *Distributed Secret Sharing Generation* (DSG) problem $n$ parties wish to obliviously sample a secret-sharing of a random value $s$ taken from some finite field, without letting any of the parties learn $s$. *Distributed Key Generation* (DKG) is a closely related variant of the problem in which, in addition to their private shares, the parties also generate a public ``commitment'' $g^s$ to the secret. Both DSG and DKG are central primitives in the domain of secure multiparty computation and threshold cryptography.

In this paper, we study the communication complexity of DSG and DKG. Motivated by large-scale cryptocurrency and blockchain applications, we ask whether it is possible to obtain protocols in which the communication per party is a constant that does not grow with the number of parties. We answer this question to the affirmative in a model where broadcast communication is implemented via a public bulletin board (e.g., a ledger). Specifically, we present a constant-round DSG/DKG protocol in which the number of bits that each party sends/receives from the public bulletin board is a constant that depends only on the security parameter and the field size but does not grow with the number of parties $n$. In contrast, in all existing solutions at least some of the parties send $\Omega(n)$ bits.

Our protocol works in the near-threshold setting. Given arbitrary privacy/correctness parameters $0<\tau_p<\tau_c<1$, the protocol tolerates up to $\tau_p n$ actively corrupted parties and delivers shares of a random secret according to some $\tau_p n$-private $\tau_c n$-correct secret sharing scheme, such that the adversary cannot bias the secret or learn anything about it. The protocol is based on non-interactive zero-knowledge proofs, non-interactive commitments and a novel secret-sharing scheme with special robustness properties that is based on Low-Density Parity-Check codes. As a secondary contribution, we extend the formal MPC-based treatment of DKG/DSG, and study new aspects of Affine Secret Sharing Schemes.



## 2024/1438

* Title: Anamorphic Authenticated Key Exchange: Double Key Distribution under Surveillance
* Authors: Weihao Wang, Shuai Han, Shengli Liu
* [Permalink](https://eprint.iacr.org/2024/1438)
* [Download](https://eprint.iacr.org/2024/1438.pdf)

### Abstract

Anamorphic encryptions and anamorphic signatures assume a double key pre-shared between two parties so as to enable the transmission of covert messages. How to securely and efficiently distribute a double key under the dictator's surveillance is a central problem for anamorphic cryptography, especially when the users are forced to surrender their long-term secret keys or even the randomness used in the algorithms to the dictator.

In this paper, we propose Anamorphic Authentication Key Exchange (AM-AKE) to solve the problem. Similar to anamorphic encryption, AM-AKE contains a set of anamorphic algorithms besides the normal algorithms. With the help of the anamorphic algorithms in AM-AKE, the initiator and the responder are able to exchange not only a session key but also a double key. We define robustness and security notions for AM-AKE, and also prove some impossibility results on plain AM-AKE whose anamorphic key generation algorithm only outputs a key-pair. To bypass the impossibility results, we work on two sides.

-- On the one side, for plain AM-AKE, the securities have to be relaxed to resist only passive attacks from the dictator. Under this setting, we propose a generic construction of two-pass plain AM-AKE from a two-pass AKE with partially randomness-recoverable algorithms.

-- On the other side, we consider (non-plain) AM-AKE whose key generation algorithm also outputs an auxiliary trapdoor besides the key-pairs. We ask new properties from AKE: its key generation algorithm has secret extractability and other algorithms have separability. Based on such a two-pass AKE, we propose a generic construction of two-pass (non-plain) AM-AKE. The resulting AM-AKE enjoys not only robustness but also the strong security against any dictator knowing both users' secret keys and even the internal randomness of the AKE algorithms and implementing active attacks.

Finally, we present concrete AM-AKE schemes from the popular SIG+KEM paradigm and three-KEM paradigm for constructing AKE.



## 2024/1439

* Title: Scabbard: An Exploratory Study on Hardware Aware Design Choices of Learning with Rounding-based Key Encapsulation Mechanisms
* Authors: Suparna Kundu, Quinten Norga, Angshuman Karmakar, Shreya Gangopadhyay, Jose Maria Bermudo Mera, Ingrid Verbauwhede
* [Permalink](https://eprint.iacr.org/2024/1439)
* [Download](https://eprint.iacr.org/2024/1439.pdf)

### Abstract

Recently, the construction of cryptographic schemes based on hard lattice problems has gained immense popularity. Apart from being quantum resistant, lattice-based cryptography allows a wide range of variations in the underlying hard problem. As cryptographic schemes can work in different environments under different operational constraints such as memory footprint, silicon area, efficiency, power requirement, etc., such variations in the underlying hard problem are very useful for designers to construct different cryptographic schemes. In this work, we explore various design choices of lattice-based cryptography and their impact on performance in the real world. In particular, we propose a suite of key-encapsulation mechanisms based on the learning with rounding problem with a focus on improving different performance aspects of lattice-based cryptography. Our suite consists of three schemes. Our first scheme is Florete, which is designed for efficiency. The second scheme is Espada, which is aimed at improving parallelization, flexibility, and memory footprint. The last scheme is Sable, which can be considered an improved version in terms of key sizes and parameters of the Saber key-encapsulation mechanism, one of the finalists in the National Institute of Standards and Technology's post-quantum standardization procedure. In this work, we have described our design rationale behind each scheme.
Further, to demonstrate the justification of our design decisions, we have provided software and hardware implementations. Our results show Florete is faster than most state-of-the-art KEMs on software platforms. For example, the key-generation algorithm of high-security version Florete outperforms the National Institute of Standards and Technology's standard Kyber by $47\%$, the Federal Office for Information Security's standard Frodo by $99\%$, and Saber by $57\%$ on the ARM Cortex-M4 platform. Similarly, in hardware, Florete outperforms Frodo and NTRU Prime for all KEM operations. The scheme Espada requires less memory and area than the implementation of most state-of-the-art schemes. For example, the encapsulation algorithm of high-security version Espada uses $30\%$ less stack memory than Kyber, $57\%$ less stack memory than Frodo, and $67\%$ less stack memory than Saber on the ARM Cortex-M4 platform. The implementations of Sable maintain a trade-off between Florete and Espada regarding software performance and memory requirements. Sable outperforms Saber at least by $6\%$ and Frodo by $99\%$. Through an efficient polynomial multiplier design, which exploits the small secret size, Sable outperforms most state-of-the-art KEMs, including Saber, Frodo, and NTRU Prime. The implementations of Sable that use number theoretic transform-based polynomial multiplication (SableNTT) surpass all the state-of-the-art schemes in performance, which are optimized for speed on the Cortext M4 platform. The performance benefit of SableNTT against Kyber lies in between $7-29\%$, $2-13\%$ for Saber, and around $99\%$ for Frodo.



## 2024/1440

* Title: Trojan Insertion versus Layout Defenses for Modern ICs: Red-versus-Blue Teaming in a Competitive Community Effort
* Authors: Johann Knechtel, Mohammad Eslami, Peng Zou, Min Wei, Xingyu Tong, Binggang Qiu, Zhijie Cai, Guohao Chen, Benchao Zhu, Jiawei Li, Jun Yu, Jianli Chen, Chun-Wei Chiu, Min-Feng Hsieh, Chia-Hsiu Ou, Ting-Chi Wang, Bangqi Fu, Qijing Wang, Yang Sun, Qin Luo, Anthony W. H. Lau, Fangzhou Wang, Evangeline F. Y. Young, Shunyang Bi, Guangxin Guo, Haonan Wu, Zhengguang Tang, Hailong You, Cong Li, Ramesh Karri, Ozgur Sinanoglu, Samuel Pagliarini
* [Permalink](https://eprint.iacr.org/2024/1440)
* [Download](https://eprint.iacr.org/2024/1440.pdf)

### Abstract

Hardware Trojans (HTs) are a longstanding threat to secure computation. Among different threat models, it is the fabrication-time insertion of additional malicious logic directly into the layout of integrated circuits (ICs) that constitutes the most versatile, yet challenging scenario, for both attackers and defenders.

Here, we present a large-scale, first-of-its-kind community effort through red-versus-blue teaming that thoroughly explores this threat. Four independently competing blue teams of 23 IC designers in total had to analyze and fix vulnerabilities of representative IC layouts, whereas a red team of 3 experts in hardware security and IC design continuously pushed the boundaries of these defense efforts through different HTs and novel insertion techniques. Importantly, we find that, despite the blue teams’ commendable efforts, even highly-optimized layouts retained at least some exploitable vulnerabilities.

Our effort follows a real-world setting for a modern 7nm technology node and industry-grade tooling for IC design, all embedded into a fully-automated and extensible benchmarking framework. To ensure the relevance of this work, strict rules that adhere to real-world requirements for IC design and manufacturing were postulated by the organizers. For example, not a single violation for timing and design-rule checks were allowed for defense techniques. Besides, in an advancement over prior art, neither red nor blue teams were allowed to use any so-called fillers and spares for trivial attack or defense approaches.

Finally, we release all methods and artifacts: the representative IC layouts and HTs, the devised attack and defense techniques, the evaluation metrics and setup, the technology setup and commercial-grade reference flow for IC design, the encompassing benchmarking framework, and all best results. This full release enables the community to continue exploring this important challenge for hardware security, in particular to focus on the urgent need for further advancements in defense strategies.



## 2024/1441

* Title: FlashSwift: A Configurable and More Efficient Range Proof With Transparent Setup
* Authors: Nan Wang, Dongxi Liu
* [Permalink](https://eprint.iacr.org/2024/1441)
* [Download](https://eprint.iacr.org/2024/1441.pdf)

### Abstract

Bit-decomposition-based zero-knowledge range proofs in the discrete logarithm (DLOG) setting with a transparent setup, e.g., Bulletproof (IEEE S\&P \textquotesingle 18), Flashproof (ASIACRYPT \textquotesingle 22), and SwiftRange (IEEE S\&P \textquotesingle 24), have garnered widespread popularity across various privacy-enhancing applications. These proofs aim to prove that a committed value falls within the non-negative range $[0, 2^N-1]$ without revealing it, where $N$ represents the bit length of the range. Despite their prevalence, the current implementations still suffer from suboptimal performance. Some exhibit reduced communication costs at the expense of increased computational costs while others experience the opposite. Presently, users are compelled to utilize these proofs in scenarios demanding stringent requirements for both communication and computation efficiency.

In this paper, we introduce, FlashSwift, a stronger DLOG-based logarithmic-sized alternative. It stands out for its greater shortness and significantly enhanced computational efficiency compared with the cutting-edge logarithmic-sized ones for the most common ranges where $N \leq 64$. It is developed by integrating the techniques from Flashproof and SwiftRange without using a trusted setup. The substantial efficiency gains stem from our dedicated efforts in overcoming the inherent incompatibility barrier between the two techniques. Specifically, when $N=64$, our proof achieves the same size as Bulletproof and exhibits 1.1$\times$ communication efficiency of SwiftRange. More importantly, compared with the two, it achieves $2.3\times$ and $1.65\times$ proving efficiency, and $3.2\times$ and $1.7\times$ verification efficiency, respectively. At the time of writing, our proof also creates two new records of the smallest proof sizes, 289 bytes and 417 bytes, for 8-bit and 16-bit ranges among all the bit-decomposition-based ones without requiring trusted setups. Moreover, to the best of our knowledge, it is the first {\em configurable} range proof that is adaptable to various scenarios with different specifications, where the configurability allows to trade off communication efficiency for computational efficiency. In addition, we offer a bonus feature: FlashSwift supports the aggregation of multiple single proofs for efficiency improvement. Finally, we provide comprehensive performance benchmarks against the state-of-the-art ones to demonstrate its practicality.



## 2024/1442

* Title: Design and Implementation of a Fast, Platform-Adaptive, AIS-20/31 Compliant PLL-Based True Random Number Generator on a Zynq 7020 SoC FPGA
* Authors: Oğuz Yayla, Yunus Emre Yılmaz
* [Permalink](https://eprint.iacr.org/2024/1442)
* [Download](https://eprint.iacr.org/2024/1442.pdf)

### Abstract

Phase-locked loops (PLLs) integrated within field-programmable gate arrays (FPGAs) or System-on-Chip FPGAs (SoCs) represent a promising approach for generating random numbers. Their widespread deployment, isolated functionality within these devices, and robust entropy, as demonstrated in prior studies, position PLL-based true random number generators (PLL-TRNGs) as highly viable solutions for this purpose. This study explicitly examines PLL-TRNG implementations using the ZC702 Rev1.1 evaluation board featuring the Zynq 7020 SoC from Xilinx, utilizing a configuration involving three such boards for experimental validation. Parameters governing the PLL-TRNG are optimized using a backtracking algorithm. Additionally, a novel methodology is proposed to enhance the rate of random data bit generation while preserving entropy characteristics. Performance metrics are rigorously evaluated against the criteria set by the German Federal Office for Information Security (BSI) AIS-20/31 Tests, accompanied by detailed descriptions of the implementation process.



## 2024/1443

* Title: 32-bit and 64-bit CDC-7-XPUF Implementation on a Zynq-7020 SoC
* Authors: Oğuz Yayla, Yunus Emre Yılmaz
* [Permalink](https://eprint.iacr.org/2024/1443)
* [Download](https://eprint.iacr.org/2024/1443.pdf)

### Abstract

Physically (Physical) Unclonable Functions (PUFs) are basic and useful primitives in designing cryptographic systems. PUFs are designed to facilitate device authentication, secure boot and firmware integrity, and secure communications. To achieve these objectives, PUFs must exhibit both consistent repeatability and instance-specific randomness. The Arbiter PUF, recognized as the first silicon PUF, is capable of generating a substantial number of secret keys instantaneously based on the input, all while maintaining a lightweight design. This advantageous characteristic makes it particularly well-suited for device authentication in applications with constrained resources, especially for Internet-of-Things (IoT) devices. Despite these advantages, arbiter PUFs are vulnerable to machine learning attacks. Hence, those arbiter PUF designs are improved to achieve increased resistance against such attacks. In this work, a machine-learning-resistant 32-bit and 64-bit component-differentially challenged XOR Arbiter PUF (CDC-XPUF) is implemented based on a design found in the literature. The system is implemented using the ZC702 Rev1.1 Evaluation Board, which features the Xilinx Zynq 7020 SoC, and utilizes a configuration involving three boards for experimental validation. The 32-bit and 64-bit 7-stream CDC-7-XPUFs are evaluated using PUF metrics in the literature, and the utilization ratio of both implementations is also presented. These improvements aim to increase resilience against machine learning attacks while maintaining usefulness and efficiency for IoT applications.



## 2024/1444

* Title: Attestation Proof of Association – provability that attestation keys are bound to the same hardware and person
* Authors: Eric Verheul
* [Permalink](https://eprint.iacr.org/2024/1444)
* [Download](https://eprint.iacr.org/2024/1444.pdf)

### Abstract

We propose a wallet provider issued attestation called Wallet Trust Evidence (WTE) and three related specific instructions for the European Digital Identity (EUDI) Wallet cryptographic hardware, most notably the generation of a Proof of Association (PoA). These allow the EUDI Wallet providing verifiable assurance to third parties (issuers, relying parties) that attestation private keys are not only bound to conformant cryptographic hardware but also that they are bound to the same such hardware. This allows the EUDI Wallet meeting eIDAS Level of Assurance ``high'' as well as operating in a privacy friendly manner. The instructions specified in this document cater for convenient implementation in all envisioned EUDI Wallet architectures including those based on a GlobalPlatform based Secure Element such as an eID-card or an embedded SIM (eSIM). By their simplicity, the three instructions also allow for convenient Common Criteria certification. This document is a further refinement and cryptographic concretization of the WTE/PoA logic specified in the wallet Architecture and Reference Framework (ARF), which is based on the EPIC-09 result developed in a cooperation between the NI-Scy consortium and the eIDAS expert group. However, the present draft document is meant for discussion only and not approved by the NI-Scy consortium, the eIDAS expert group or Dutch government.



## 2024/1445

* Title: Another Walk for Monchi
* Authors: Riccardo Taiello, Emre Tosun, Alberto Ibarrondo, Hervé Chabanne, Melek Önen
* [Permalink](https://eprint.iacr.org/2024/1445)
* [Download](https://eprint.iacr.org/2024/1445.pdf)

### Abstract

Monchi is a new protocol aimed at privacy-preserving biometric identification.. It begins with scores computation in the encrypted domain thanks to homomorphic encryption and ends with comparisons of these scores to a given threshold with function secret sharing. We here study the integration in that context of scores computation techniques recently introduced by Bassit et al. that eliminate homomorphic multiplications by replacing them by lookup tables. First, we extend this lookup tables biometric recognition solution by adding the use of function secret sharing for the final comparison of scores. Then, we introduce a two-party computation of the scores with lookup tables which fits nicely together with the function secret sharing scores comparison. Our solutions accommodate well with the flight boarding use case introduced by Monchi.



## 2024/1446

* Title: Updatable Private Set Intersection Revisited: Extended Functionalities, Deletion, and Worst-Case Complexity
* Authors: Saikrishna Badrinarayanan, Peihan Miao, Xinyi Shi, Max Tromanhauser, Ruida Zeng
* [Permalink](https://eprint.iacr.org/2024/1446)
* [Download](https://eprint.iacr.org/2024/1446.pdf)

### Abstract

Private set intersection (PSI) allows two mutually distrusting parties each holding a private set of elements, to learn the intersection of their sets without revealing anything beyond the intersection. Recent work (Badrinarayanan et al., PoPETS'22) initiates the study of updatable PSI (UPSI), which allows the two parties to compute PSI on a regular basis with sets that constantly get updated, where both the computation and communication complexity only grow with the size of the small updates and not the large entire sets. However, there are several limitations of their presented protocols. First, they can only be used to compute the plain PSI functionality and do not support extended functionalities such as PSI-Cardinality and PSI-Sum. Second, they only allow parties to add new elements to their existing set and do not support arbitrary deletion of elements.  Finally, their addition-only protocols either require both parties to learn the output or only achieve low complexity in an amortized sense and incur linear worst-case complexity.

In this work, we address all the above limitations. In particular, we study UPSI with semi-honest security in both the addition-only and addition-deletion settings. We present new protocols for both settings that support plain PSI as well as extended functionalities including PSI-Cardinality and PSI-Sum, achieving one-sided output (which implies two-sided output). In the addition-only setting, we also present a protocol for a more general functionality Circuit-PSI that outputs secret shares of the intersection. All of our protocols have worst-case computation and communication complexity that only grow with the set updates instead of the entire sets (except for a polylogarithmic factor). We implement our new UPSI protocols and compare with the state-of-the-art protocols for PSI and extended functionalities. Our protocols compare favorably when the total set sizes are sufficiently large, the new updates are sufficiently small, or in networks with low bandwidth.



## 2024/1447

* Title: Generic Differential Key Recovery Attacks and Beyond
* Authors: Ling Song, Huimin Liu, Qianqian Yang, Yincen Chen, Lei Hu, Jian Weng
* [Permalink](https://eprint.iacr.org/2024/1447)
* [Download](https://eprint.iacr.org/2024/1447.pdf)

### Abstract

At Asiacrypt 2022, a holistic key guessing strategy was proposed to yield the most efficient key recovery for the rectangle attack. Recently, at Crypto 2023,  a new cryptanalysis technique--the differential meet-in-the-middle (MITM) attack--was introduced. Inspired by these two previous works, we present three generic key recovery attacks in this paper. First, we extend the holistic key guessing strategy from the rectangle to the differential attack, proposing the generic classical differential attack (GCDA). Next, we combine the holistic key guessing strategy with the differential MITM attack, resulting in the generalized differential MITM attack (GDMA). Finally, we apply the MITM technique to the rectangle attack, creating the generic rectangle MITM attack (GRMA). In terms of applications, we improve 12/13-round attacks on AES-256. For 12-round AES-256, by using the GDMA, we reduce the time complexity by a factor of $2^{62}$; by employing the GCDA, we reduce both the time and memory complexities by factors of $2^{61}$ and $2^{56}$, respectively. For 13-round AES-256, we present a new differential attack with data and time complexities of $2^{89}$ and $2^{240}$, where the data complexity is $2^{37}$ times lower than previously published results. These are currently the best attacks on AES-256 using only two related keys. For KATAN-32, we increase the number of rounds covered by the differential attack from 115 to 151 in the single-key setting using the basic differential MITM attack (BDMA) and GDMA. Furthermore, we achieve the first 38-round rectangle attack on SKINNYe-64-256 by using the GRMA.



## 2024/1448

* Title: Randomness in Private Sequential Stateless Protocols
* Authors: Hari Krishnan P. Anilkumar, Varun Narayanan, Manoj Prabhakaran, Vinod M. Prabhakaran
* [Permalink](https://eprint.iacr.org/2024/1448)
* [Download](https://eprint.iacr.org/2024/1448.pdf)

### Abstract

A significant body of work in information-theoretic cryptography has been devoted to the fundamental problem of understanding the power of randomness in private computation. This has included both in-depth study of the randomness complexity of specific functions (e.g., Couteau and Ros ́en, ASIACRYPT 2022, gives an upper bound of 6 for n-party $\mathsf{AND}$), and results for broad classes of functions (e.g., Kushilevitz et al. STOC 1996, gives an $O(1)$ upper bound for all functions with linear-sized circuits). In this work, we make further progress on both fronts by studying randomness complexity in a new simple model of secure computation called Private Sequential Stateless (PSS) model.
We show that functions with $O(1)$ randomness complexity in the PSS model are exactly those with constant-width branching programs, restricting to “speak-constant-times” protocols and to “read-constant-times” branching programs.
Towards this our main construction is a novel PSS protocol for “strongly regular branching programs” (SRBP). As we show, any constant-width branching program can be converted to a constant-width SRBP, yielding one side of our characterization. The converse direction uses ideas from Kushilevitz et al. to translate randomness to communication.
Our protocols are concretely efficient, has a simple structure, covers the broad class of functions with small-width, read-once (or read-a-few-times) branching programs, and hence may be of practical interest when 1-privacy is considered adequate. Also, as a consequence of our general result for SRBPs, we obtain an improvement over the protocol of Couteau and Ros ́en for $\mathsf{AND}$ in certain cases — not in terms of the number of bits of randomness, but in terms of a simpler protocol structure (sequential, stateless).



## 2024/1449

* Title: Marian: An Open Source RISC-V Processor with Zvk Vector Cryptography Extensions
* Authors: Thomas Szymkowiak, Endrit Isufi, Markku-Juhani Saarinen
* [Permalink](https://eprint.iacr.org/2024/1449)
* [Download](https://eprint.iacr.org/2024/1449.pdf)

### Abstract

The RISC-V Vector Cryptography Extensions (Zvk) were ratified in 2023 and integrated into the main ISA manuals in 2024. These extensions support high-speed symmetric cryptography (AES, SHA2, SM3, SM4) operating on the vector register file and offer significant performance improvements over scalar cryptography extensions (Zk) due to data parallelism. As a ratified extension, Zvk is supported by compiler toolchains and is already being integrated into popular cryptographic middleware such as OpenSSL. We report on Marian, the first open-source hardware implementation of a vector processor with the Zvk extensions.. The design is based on the PULP ``Ara'' vector unit, which itself is an extension of the popular CVA6 processor. The implementation is in SystemVerilog and has been tested using Virtex Ultrascale+ FPGA prototyping, with a planned tapeout targeting a 22nm process node. We offer an analysis of the architectural requirements that vector cryptography imposes on a processor, as well as the initial estimates of performance and area for our implementation.



## 2024/1450

* Title: TentLogiX: 5-bit Chaos-Driven S-Boxes for Lightweight Cryptographic Systems
* Authors: Maha Allouzi, Arefeh Rahaei
* [Permalink](https://eprint.iacr.org/2024/1450)
* [Download](https://eprint.iacr.org/2024/1450.pdf)

### Abstract

Cryptography is a crucial method for ensuring the security of communication and data transfers across networks. While it excels on devices with abundant resources, such as PCs, servers, and smartphones, it may encounter challenges when applied to resource-constrained Internet of Things (IoT) devices like Radio Frequency Identification (RFID) tags and sensors. To address this issue, a demand arises for a lightweight variant of cryptography known as lightweight cryptography (LWC).
In developing any cryptographic algorithm, the substitution box (S-box) is a fundamental component, providing nonlinear functionality between inputs and outputs. Researchers have TentLogiX diverse S-box designs tailored for various applications, but only a few manage to balance the trade-offs among cost, performance, and security, particularly in the context of resource-constrained IoT devices.
This paper delves into the realm of S-boxes employed in popular LWC algorithms, categorizing them by their input–output bit sizes and elucidating their strengths and limitations. The focus then shifts to a novel 5-bit S-box design, utilizing chaotic mapping theory to introduce a randomized behavior.
Subsequently, the paper proposed TentLogiX a 5-bit S-box, constructed based on compound chaotic system, tent-logistic systems, which has better chaotic performance and wider sequences and explores its security robustness through various cryptanalysis techniques, including bijective analysis, nonlinearity assessment, linearity evaluation, and differential cryptanalysis. The paper concludes by presenting a thorough comparison that underscores the superiority of the TentLogiX 5-bit S-box over its 5-bit counterparts.



## 2024/1451

* Title: Traffic-aware Merkle Trees for Shortening Blockchain Transaction Proofs
* Authors: Avi Mizrahi, Noam Koren, Ori Rottenstreich, Yuval Cassuto
* [Permalink](https://eprint.iacr.org/2024/1451)
* [Download](https://eprint.iacr.org/2024/1451.pdf)

### Abstract

Merkle trees play a crucial role in blockchain networks in organizing network state. They allow proving a particular value of an entry in the state to a node that maintains only the root of the Merkle trees, a hash-based signature computed over the data in a hierarchical manner. Verification of particular state entries is crucial in reaching a consensus on the execution of a block where state information is required in the processing of its transactions. For instance, a payment transaction should be based on the balance of the two involved accounts. The proof length affects the network communication and is typically logarithmic in the state size. In this paper, we take advantage of typical transaction characteristics for better organizing Merkle trees to improve blockchain network performance. We focus on the common transaction processing where Merkle proofs are jointly provided for multiple accounts. We first provide lower bounds for the communication cost that are based on the distribution of accounts involved in the transactions. We then describe algorithms that consider traffic patterns for significantly reducing it. The algorithms are inspired by various coding methods such as Huffman coding, partition and weight balancing. We also generalize our approach towards the encoding of smart contract transactions that involve an arbitrary number of accounts. Likewise, we rely on real blockchain data to show the savings allowed by our approach. The experimental evaluation is based on transactions from the Ethereum network and demonstrates cost reduction for both payment transactions and smart contract transactions.



## 2024/1452

* Title: On the Complexity of Cryptographic Groups and Generic Group Models
* Authors: Cong Zhang, Keyu Ji, Taiyu Wang, Bingsheng Zhang, Hong-Sheng Zhou, Xin Wang, Kui Ren
* [Permalink](https://eprint.iacr.org/2024/1452)
* [Download](https://eprint.iacr.org/2024/1452.pdf)

### Abstract

Ever since the seminal work of Diffie and Hellman, cryptographic (cyclic) groups have served as a fundamental building block for constructing cryptographic schemes and protocols. The security of these constructions can often be based on the hardness of (cyclic) group-based computational assumptions. Then, the generic group model (GGM) has been studied as an idealized model (Shoup, EuroCrypt 1997), which justifies the hardness of many (cyclic) group-based assumptions and shows the limits of some group-based cryptosystems. We stress that, the importance of the length of group encoding, either in a concrete group-based construction or assumption, or in the GGM, has not been studied.

In this work, we initiate a systematic study on the complexity of cryptographic groups and generic group models, varying in different lengths of group encodings, and demonstrate evidences that ``the length matters''. More concretely, we have the following results:

-- We show that there is no black-box/relativizing reduction from the CDH-secure groups (i.e., over such groups, the computational Diffie-Hellman assumption holds) with shorter encodings, to the CDH-secure groups with longer encodings, within the same security parameter. More specifically, given any arbitrary longer CDH-secure group, it is impossible to generically shorten the group encoding and obtain a shorter CDH-secure group within the same group order. 

-- We show that there is a strict hierarchy of the GGMs with different lengths of encodings. That is, in the framework of indifferentiability, the shorter GGM is strictly stronger than the longer ones, even in the presence of computationally bounded adversaries.



## 2024/1453

* Title: Breaking and Repairing SQIsign2D-East
* Authors: Wouter Castryck, Mingjie Chen, Riccardo Invernizzi, Gioella Lorenzon, Frederik Vercauteren
* [Permalink](https://eprint.iacr.org/2024/1453)
* [Download](https://eprint.iacr.org/2024/1453.pdf)

### Abstract

We present a key recovery attack on SQIsign2D-East that reduces its security level from $\lambda$ to $\lambda/2$.  We exploit the fact that each signature leaks a Legendre symbol modulo the secret degree of the private key isogeny.  About $\lambda/2$ signatures are enough for these Legendre symbols to fully determine the secret degree, which can then be recovered by exhaustive search over a set of size $O(2^{\lambda/2})$. Once the degree is known, the private key isogeny itself can be found, again by exhaustive search, in time $\tilde{O}(2^{\lambda/2})$.

We also present a new version of the protocol which does not leak any such information about the private key and show that our modified protocol is more efficient than the original one.  Finally, we give a security analysis as well as a new proof of security.



## 2024/1454

* Title: Interval Key-Encapsulation Mechanism
* Authors: Alexander Bienstock, Yevgeniy Dodis, Paul Rösler, Daniel Wichs
* [Permalink](https://eprint.iacr.org/2024/1454)
* [Download](https://eprint.iacr.org/2024/1454.pdf)

### Abstract

Forward-Secure Key-Encapsulation Mechanism (FS-KEM; Canetti et al. Eurocrypt 2003) allows Alice to encapsulate a key $k$ to Bob for some time $t$ such that Bob can decapsulate it at any time $t'\leq t$. Crucially, a corruption of Bob's secret key after time $t$ does not reveal $k$.

In this work, we generalize and extend this idea by also taking Post-Compromise Security (PCS) into account and call it Interval Key-Encapsulation Mechanism (IKEM). Thus, we do not only protect confidentiality of previous keys against future corruptions but also confidentiality of future keys against past corruptions. For this, Bob can regularly renew his secret key and inform others about the corresponding public key. IKEM enables Bob to decapsulate keys sent to him over an interval of time extending into the past, in case senders have not obtained his latest public key; forward security only needs to hold with respect to keys encapsulated before this interval. This basic IKEM variant can be instantiated based on standard KEM, which we prove to be optimal in terms of assumptions as well as ciphertext and key sizes.

We also extend this notion of IKEM for settings in which Bob decapsulates (much) later than Alice encapsulates (e.g., in high-latency or segmented networks): if a third user Charlie forwards Alice's ciphertext to Bob and, additionally, knows a recently renewed public key of Bob's, Charlie could re-encrypt the ciphertext for better PCS. We call this extended notion IKEMR. Our first IKEMR construction based on trapdoor permutations has (almost) constant sized ciphertexts in the number of re-encryptions; and our second IKEMR construction based on FS-PKE has constant sized public keys in the interval size.

Finally, to bypass our lower bound on the IKEM(R) secret key size, which must be linear in the interval size, we develop a new Interval RAM primitive with which Bob only stores a constant sized part of his secret key locally, while outsourcing the rest to a (possibly adversarial) server.

For all our constructions, we achieve security against active adversaries. For this, we obtain new insights on Replayable CCA security for KEM-type primitives, which might be of independent interest.



## 2024/1455

* Title: Threshold PAKE with Security against Compromise of all Servers
* Authors: Yanqi Gu, Stanislaw Jarecki, Pawel Kedzior, Phillip Nazarian, Jiayu Xu
* [Permalink](https://eprint.iacr.org/2024/1455)
* [Download](https://eprint.iacr.org/2024/1455.pdf)

### Abstract

We revisit the notion of threshold Password-Authenticated Key Exchange (tPAKE), and we extend it to augmented tPAKE (atPAKE), which protects password information even in the case all servers are compromised, except for allowing an (inevitable) offline dictionary attack.  Compared to prior notions of tPAKE this is analogous to replacing symmetric PAKE, where the server stores the user's password, with an augmented (or asymmetric) PAKE, like OPAQUE [JKX18], where the server stores a password hash, which can be used only as a target in an offline dictionary search for the password.  An atPAKE scheme also strictly improves on the security of an aPAKE, by secret-sharing the password hash among a set of servers. Indeed, our atPAKE protocol is a natural realization of threshold OPAQUE.

We formalize atPAKE in the framework of Universal Composability (UC), and show practical ways to realize it.  All our schemes are generic compositions which interface to any aPAKE used as a sub-protocol, making them easier to adopt.. Our main scheme relies on threshold Oblivious Pseudorandom Function (tOPRF), and our independent contribution fixes a flaw in the UC tOPRF notion of [JKKX17] and upgrades the tOPRF scheme therein to achieve the fixed definition while preserving its minimal cost and round complexity.  The technique we use enforces implicit agreement on arbitrary context information within threshold computation, and it is of general interest.



## 2024/1456

* Title: Crooked Indifferentiability of the Feistel Construction
* Authors: Alexander Russell, Qiang Tang, Jiadong Zhu
* [Permalink](https://eprint.iacr.org/2024/1456)
* [Download](https://eprint.iacr.org/2024/1456.pdf)

### Abstract

The Feistel construction is a fundamental technique for building pseudorandom permutations and block ciphers. This paper shows that a simple adaptation of the construction is resistant, even to algorithm substitution attacks---that is, adversarial subversion---of the component round functions. Specifically, we establish that a Feistel-based construction with more than $337n/\log(1/\epsilon)$ rounds can transform a subverted random function---which disagrees with the original one at a small fraction (denoted by $\epsilon$) of inputs---into an object that is \emph{crooked-indifferentiable} from a random permutation, even if the adversary is aware of all the randomness used in the transformation. Here, $n$ denotes the length of both the input and output of the round functions that underlie the Feistel cipher.  We also provide a lower bound showing that the construction cannot use fewer than $2n/\log(1/\epsilon)$ rounds to achieve crooked-indifferentiable security.



## 2024/1457

* Title: A Combined Design of 4-PLL-TRNG and 64-bit CDC-7-XPUF on a Zynq-7020 SoC
* Authors: Oğuz Yayla, Yunus Emre Yılmaz
* [Permalink](https://eprint.iacr.org/2024/1457)
* [Download](https://eprint.iacr.org/2024/1457.pdf)

### Abstract

True Random Number Generators (TRNGs) and Physically Unclonable Functions (PUFs) are critical hardware primitives for cryptographic systems, providing randomness and device-specific security. TRNGs require complete randomness, while PUFs rely on consistent, device-unique responses. In this work, both primitives are implemented on a System-on-Chip Field-Programmable Gate Array (SoC FPGA), leveraging the integrated Phase-Locked Loops (PLLs) for robust entropy generation in PLLbased TRNGs. A novel backtracking parameter selection algorithm for the TRNG implementation is employed, alongside a methodology to boost data generation rates without compromising entropy. The design is rigorously evaluated using the German BSI AIS-20/31 standards. For the PUF implementation, the Arbiter PUF, known for its lightweight design and key generation, is enhanced to resist machine learning attacks by implementing a 32-bit and a 64-bit component-differentially challenged XOR Arbiter PUF (CDC-XPUF). These designs are tested using standard PUF metrics, including uniformity, correctness, and uniqueness. Finally, a combined 4-PLL-TRNG and 64-bit CDC-XPUF design is introduced and evaluated for its suitability in Internet-of-Things (IoT) systems, demonstrating strong performance in both TRNG and PUF tests. The tests are conducted on the Xilinx Zynq 7020 SoC using a ZC702 evaluation board, confirming the effectiveness of this integrated approach for secure, low-resource applications like IoT.



## 2024/1458

* Title: Providing Integrity for Authenticated Encryption in the Presence of Joint Faults and Leakage
* Authors: Francesco Berti, Itamar Levi
* [Permalink](https://eprint.iacr.org/2024/1458)
* [Download](https://eprint.iacr.org/2024/1458.pdf)

### Abstract

Passive (leakage exploitation) and active (fault injection) physical attacks pose a significant threat to cryptographic schemes. Although leakage-resistant cryptography is well studied, there is little work on mode-level security in the presence of joint faults and leakage exploiting adversaries. In this paper, we focus on integrity for authenticated encryption (AE).
First, we point out that there is an inherent attack in the fault-resilience model presented at ToSC 2023. This shows how fragile the freshness condition of a forgery is when faults are injected into either the tag-generation or the encryption algorithm. Therefore, we provide new integrity definitions for AE in the presence of leakage and faults, and we follow the atomic model, in which the scheme is divided into atoms (or components, e.g. a call to a block cipher) and allows the adversary to inject a fault only into the inputs of an atom. We envision this model as a first step for leveled implementations in the faults context, the granularity of atoms can be made finer or coarser (for example, instead of considering a call to a block cipher, we can consider atoms to be rounds of the block cipher). We hold the underlying belief that it would be easier to protect smaller blocks than a full scheme. The proposed model is very flexible and allows us to understand where to apply faults countermeasures (in some very interesting cases this model can reduce faults inside atoms to faults on their outputs, as we discuss).
We then show that an AE-scheme using a single call to a highly leakage-protected (and thus very expensive) component, CONCRETE (presented at Africacrypt 2019), maintains integrity in the presence of leakage in both encryption and decryption, and faults only in decryption.On the other hand, a single fault in encryption is enough to forge. Therefore, we first introduce a weaker definition (which restricts the meaning of freshness), weak integrity, which CONCRETE achieves even if the adversary can introduce faults in the encryption queries (with some restrictions on the number and type of faults). Finally, we provide a variant, CONCRETE2, which is slightly more computationally expensive, but still uses a single call to a strongly protected component that provides integrity in the presence of leakage and faults.



## 2024/1459

* Title: Verifiable Oblivious Pseudorandom Functions from Lattices: Practical-ish and Thresholdisable
* Authors: Martin R. Albrecht, Kamil Doruk Gur
* [Permalink](https://eprint.iacr.org/2024/1459)
* [Download](https://eprint.iacr.org/2024/1459.pdf)

### Abstract

We revisit the lattice-based verifiable oblivious PRF construction from PKC'21 and remove or mitigate its central three sources of inefficiency. First, applying Rényi divergence arguments, we eliminate one superpolynomial factor from the ciphertext modulus \(q\), allowing us to reduce the overall bandwidth consumed by RLWE samples by about a factor of four. This necessitates us introducing intermediate unpredictability notions to argue PRF security of the final output in the Random Oracle model. Second, we remove the reliance on the \(\mathsf{1D-SIS}\) assumption, which reduces another superpolynomial factor, albeit to a factor that is still superpolynomial. Third, by applying the state-of-the-art in zero-knowledge proofs for lattice statements, we achieve a reduction in bandwidth of several orders of magnitude for this material.
  Finally, we give a \(t\)-out-of-\(n\) threshold variant of the VOPRF for constant \(t\) and with trusted setup, based on a \(n\)-out-of-\(n\) distributed variant of the VOPRF (and without trusted setup).



## 2024/1460

* Title: PPSA: Polynomial Private Stream Aggregation for Time-Series Data Analysis
* Authors: Antonia Januszewicz, Daniela Medrano Gutierrez, Nirajan Koirala, Jiachen Zhao, Jonathan Takeshita, Jaewoo Lee, Taeho Jung
* [Permalink](https://eprint.iacr.org/2024/1460)
* [Download](https://eprint.iacr.org/2024/1460.pdf)

### Abstract

Modern data analytics requires computing functions on streams of data points from many users that are challenging to calculate, due to both the high scale and nontrivial nature of the computation at hand. The need for data privacy complicates this matter further, as general-purpose privacy-enhancing technologies face limitations in at least scalability or utility. Existing work has attempted to improve this by designing purpose-built protocols for the use case of Private Stream Aggregation; however, prior work lacks the ability to compute more general aggregative functions without the assumption of trusted parties or hardware.

In this work, we present PPSA, a protocol that performs Private Polynomial Stream Aggregation, allowing the private computation of any polynomial function on user data streams even in the presence of an untrusted aggregator. Unlike previous state-of-the-art approaches, PPSA enables secure aggregation beyond simple summations without relying on trusted hardware; it utilizes only tools from cryptography and differential privacy. Our experiments show that PPSA has low latency during the encryption and aggregation processes with an encryption latency of 10.5 ms and aggregation latency of 21.6 ms for 1000 users, which are up to 138$\times$ faster than the state-of-the-art prior work.



## 2024/1461

* Title: Detecting and Correcting Computationally Bounded  Errors: A Simple Construction Under Minimal Assumptions
* Authors: Jad Silbak, Daniel Wichs
* [Permalink](https://eprint.iacr.org/2024/1461)
* [Download](https://eprint.iacr.org/2024/1461.pdf)

### Abstract

We study error detection and error correction in a computationally bounded world, where errors are introduced by an arbitrary polynomial time adversarial channel. We consider codes where the encoding procedure uses random coins and define two distinct variants: (1) in randomized codes, fresh randomness is chosen during each encoding operation and is unknown a priori, while (2) in self-seeded codes, the randomness of the encoding procedure is fixed once upfront and is known to the adversary. In both cases, the randomness need not be known to the decoding procedure, and there is no trusted common setup between the encoder and decoder. The encoding  and decoding algorithms are efficient and run in some fixed polynomial time, independent of the run time of the adversary. 

The parameters of standard codes for worst-case (inefficient) errors are limited by the Singleton bound:  for rate $R$ it is not possible to detect more than a $1-R$ fraction of errors,  or uniquely correct more than a $(1-R)/2$ fraction of errors, and efficient codes matching this bound exist for sufficiently large alphabets. In the computationally bounded setting, we show that going beyond the Singleton bound implies one-way functions in the case of randomized codes and collision-resistant hash functions in the case of self-seeded codes. We construct randomized and self-seeded codes under these respective minimal assumptions with essentially optimal parameters over a constant-sized alphabet:

- Detection: the codes have a rate $R \approx 1$ while detecting a $\rho \approx 1$ fraction of errors.
- Correction: for any $\rho <  1/2$, the codes uniquely correct a $\rho$ fraction of errors with rate $R \approx 1-\rho$.

Codes for computationally bounded errors were studied in several prior works starting with Lipton (STACS '94), but all such works either: (a) need some trusted common setup (e.g., public-key infrastructure, common reference string) between the encoder and decoder, or (b) only handle channels whose complexity is a prior bounded below that of the code.



## 2024/1462

* Title: Efficient Fuzzy Private Set Intersection from Fuzzy Mapping
* Authors: Ying Gao, Lin Qi, Xiang Liu, Yuanchao Luo, Longxin Wang
* [Permalink](https://eprint.iacr.org/2024/1462)
* [Download](https://eprint.iacr.org/2024/1462.pdf)

### Abstract

Private set intersection (PSI) allows Sender holding a set \(X\) and Receiver holding a set \(Y\) to compute only the intersection \(X\cap Y\) for Receiver. We focus on a variant of PSI, called fuzzy PSI (FPSI), where Receiver only gets points in \(X\) that are at a distance not greater than a threshold from some points in \(Y\).

Most current FPSI approaches first pick out pairs of points that are potentially close and then determine whether the distance of each selected pair is indeed small enough to yield FPSI result. Their complexity bottlenecks stem from the excessive number of point pairs selected by the first picking process. Regarding this process, we consider a more general notion, called fuzzy mapping (Fmap), which can map each point of two parties to a set of identifiers, with closely located points having a same identifier, which forms the selected point pairs.

We initiate the formal study on Fmap and show novel Fmap instances for Hamming and \(L_\infty\) distances to reduce the number of selected pairs. We demonstrate the powerful capability of Fmap with some superior properties in constructing FPSI variants and provide a generic construction from Fmap to FPSI.

Our new Fmap instances lead to the fastest semi-honest secure FPSI protocols in high-dimensional space to date, for both Hamming and general \(L_{\mathsf p\in [1, \infty]}\) distances. For Hamming distance, our protocol is the first one that achieves strict linear complexity with input sizes. For \(L_{\mathsf p\in [1, \infty]}\) distance, our protocol is the first one that achieves linear complexity with input sizes, dimension, and threshold.



## 2024/1463

* Title: Asynchronous Verifiable Secret Sharing with Elastic Thresholds and Distributed Key Generation
* Authors: Junming Li, Zhi Lu, Renfei Shen, Yuanqing Feng, Songfeng Lu
* [Permalink](https://eprint.iacr.org/2024/1463)
* [Download](https://eprint.iacr.org/2024/1463.pdf)

### Abstract

Distributed Key Generation (DKG) is a technique that enables the generation of threshold cryptography keys among a set of mutually untrusting nodes. DKG generates keys for a range of decentralized applications such as threshold signatures, multiparty computation, and Byzantine consensus. Over the past five years, research on DKG has focused on optimizing network communication protocols to improve overall system efficiency by reducing communication complexity.. However, SOTA asynchronous distributed key generation (ADKG) schemes (e.g., Kokoris-Kogias ADKG, CCS 2020 and Das ADKG, S\&P 2022, and others) only support recovery thresholds of either $f$ or $2f$, where $f$ is the maximum number of malicious nodes. This paper proposes an asynchronous verifiable secret sharing protocol featuring an elastic threshold, where $t \in [f,n-f-1]$ and $n \ge 3f+1$ is the total number of parties. Our protocol enables a dealer to share up to $t+1$ secrets with a total communication cost of O($\lambda n^3$), where $\lambda$ is the security parameter, and the protocol relies on the hardness of the $q$-SDH problem. We further modified the Schnorr protocol to enable simultaneous commitments to multiple secrets, which we refer to $m$-Schnorr.



## 2024/1464

* Title: SoK: Descriptive Statistics Under Local Differential Privacy
* Authors: René Raab, Pascal Berrang, Paul Gerhart, Dominique Schröder
* [Permalink](https://eprint.iacr.org/2024/1464)
* [Download](https://eprint.iacr.org/2024/1464.pdf)

### Abstract

Local Differential Privacy (LDP) provides a formal guarantee of privacy that enables the collection and analysis of sensitive data without revealing any individual's data. While LDP methods have been extensively studied, there is a lack of a systematic and empirical comparison of LDP methods for descriptive statistics. In this paper, we first provide a systematization of LDP methods for descriptive statistics, comparing their properties and requirements. We demonstrate that several mean estimation methods based on sampling from a Bernoulli distribution are equivalent in the one-dimensional case and introduce methods for variance estimation. We then empirically compare methods for mean, variance, and frequency estimation. Finally, we provide recommendations for the use of LDP methods for descriptive statistics and discuss their limitations and open questions.



## 2024/1465

* Title: Linear approximations of the Flystel construction
* Authors: Tim Beyne, Clémence Bouvier
* [Permalink](https://eprint.iacr.org/2024/1465)
* [Download](https://eprint.iacr.org/2024/1465.pdf)

### Abstract

Using a purity theorem for exponential sums due to Rojas-Léon, we upper bound the absolute correlations of linear approximations of the Flystel construction used in Anemoi. This resolves open problem 7.1 in [Bouvier, 2023].



## 2024/1466

* Title: Dishonest Majority Constant-Round MPC with Linear Communication from DDH
* Authors: Vipul Goyal, Junru Li, Ankit Kumar Misra, Rafail Ostrovsky, Yifan Song, Chenkai Weng
* [Permalink](https://eprint.iacr.org/2024/1466)
* [Download](https://eprint.iacr.org/2024/1466.pdf)

### Abstract

In this work, we study constant round multiparty computation (MPC) for Boolean circuits against a fully malicious adversary who may control up to $n-1$ out of $n$ parties. Without relying on fully homomorphic encryption (FHE), the best-known results in this setting are achieved by Wang et al. (CCS 2017) and Hazay et al. (ASIACRYPT 2017) based on garbled circuits, which require a quadratic communication in the number of parties $O(|C|\cdot n^2)$. In contrast, for non-constant round MPC, the recent result by Rachuri and Scholl (CRYPTO 2022) has achieved linear communication $O(|C|\cdot n)$.

    In this work, we present the first concretely efficient constant round MPC protocol in this setting with linear communication in the number of parties $O(|C|\cdot n)$. Our construction can be based on any public-key encryption scheme that is linearly homomorphic for public keys. Our work gives a concrete instantiation from a variant of the El-Gamal Encryption Scheme assuming the DDH assumption. The analysis shows that when the computational security parameter $\lambda=128$ and statistical security parameter $\kappa=80$, our protocol achieves a smaller communication than Wang et al. (CCS 2017) when there are $16$ parties for AES circuit and $8$ parties for general Boolean circuits (where we assume that the numbers of AND gates and XOR gates are the same). When comparing with the recent work by Beck et al. (CCS 2023) that achieves constant communication complexity $O(|C|)$ in the strong honest majority setting ($t<(1/2-\epsilon)n$ where $\epsilon$ is a constant), our protocol is better as long as $n<3500$ (when $t=n/4$ for their work).



## 2024/1467

* Title: P2C2T: Preserving the Privacy of Cross-Chain Transfer
* Authors: Panpan Han, Zheng Yan, Laurence T. Yang, Elisa Bertino
* [Permalink](https://eprint.iacr.org/2024/1467)
* [Download](https://eprint.iacr.org/2024/1467.pdf)

### Abstract

Blockchain-enabled digital currency systems have typically operated in isolation, lacking necessary mechanisms for seamless interconnection. Consequently, transferring assets across distinct currency systems remains a complex challenge, with existing schemes often falling short in ensuring security, privacy, and practicality. This paper proposes P2C2T -- a privacy-preserving cross-chain transfer scheme. It is the first scheme to address atomicity, unlinkability, indistinguishability, non-collateralization, and required functionalities across diverse currency systems. P2C2T is based on \textit{threshold anonymous atomic locks} (TA$^2$L), also proposed by us, serving as the cornerstone for guaranteeing atomic cross-chain transfer while obscuring the payment relationships between users. By combining TA$^2$L with \textit{verifiable timed discrete logarithm} schemes, P2C2T renders cross-chain transactions indistinguishable from regular intra-chain ones. Notably, P2C2T eliminates the collateralization of senders and imposes minimal requirements on underlying blockchains, specifically on the ability to verify signatures. We substantiate the security of TA$^2$L based on a proposed cryptographic notion called \textit{threshold blind conditional signatures} and demonstrate the security of P2C2T through necessary proofs. Additionally, we compare the performance of P2C2T with an existing scheme that has properties closest to P2C2T. The comparison reveals that P2C2T reduces overhead by at least $85.488\%$ in terms of running time, communication cost, and storage cost when completing a cross-chain transfer. We further conduct cross-chain transfers and intra-chain payments using the Bitcoin testnet and Litecoin testnet to illustrate the privacy and practicality of P2C2T.



## 2024/1468

* Title: Dense and smooth lattices in any genus
* Authors: Wessel van Woerden
* [Permalink](https://eprint.iacr.org/2024/1468)
* [Download](https://eprint.iacr.org/2024/1468.pdf)

### Abstract

The Lattice Isomorphism Problem (LIP) was recently introduced as a new hardness assumption for post-quantum cryptography.
The strongest known efficiently computable invariant for LIP is the genus of a lattice.
To instantiate LIP-based schemes one often requires the existence of a lattice that (1) lies in some fixed genus, and (2) has some good geometric properties such as a high packing density or small smoothness parameter.

In this work we show that such lattices exist. In particular, building upon classical results by Siegel (1935), we show that essentially any genus contains a lattice with a close to optimal packing density, smoothing parameter and covering radius.
We present both how to efficiently compute concrete existence bounds for any genus, and asymptotically tight bounds under weak conditions on the genus.



## 2024/1469

* Title: Password-Protected Threshold Signatures
* Authors: Stefan Dziembowski, Stanislaw Jarecki, Paweł Kędzior, Hugo Krawczyk, Chan Nam Ngo, Jiayu Xu
* [Permalink](https://eprint.iacr.org/2024/1469)
* [Download](https://eprint.iacr.org/2024/1469.pdf)

### Abstract

We witness an increase in applications like cryptocurrency wallets, which involve users issuing signatures using private keys. To protect these keys from loss or compromise, users commonly outsource them to a custodial server. This creates a new point of failure, because compromise of such a server leaks the user’s key, and if user authentication is implemented with a password then this password becomes open to an offline dictionary attack (ODA). A better solution is to secret-share the key among a set of servers, possibly including user’s own device(s), and implement password authentication and signature computation using threshold cryptography.

We propose a notion of augmented password protected threshold signature scheme (aptSIG) which captures the best possible security level for this setting. Using standard threshold cryptography techniques, i.e. threshold password authentication and threshold signatures, one can guarantee that compromising up to t out of n servers reveals no information on either the key or the password. However, we extend this with a novel property, namely that compromising even all n servers also does not leak any information, except via an unavoidable ODA attack, which reveals the key (and the password) only if the attacker guesses the password.

We define aptSIG in the Universally Composable (UC) framework and show that it can be constructed very efficiently, using a black-box composition of any UC threshold signature and a UC augmented Password-Protected Secret Sharing (aPPSS), which we define as an extension of prior notion of PPSS.  As concrete instantiations we obtain secure aptSIG schemes for ECDSA and BLS signatures with very small overhead over the respective threshold signature.

Finally, we note that both the notion and our generic solution for augmented password-protected threshold signatures can be generalized to password-protecting MPC for any keyed functions.



## 2024/1470

* Title: Quantum Pseudorandom Scramblers
* Authors: Chuhan Lu, Minglong Qin, Fang Song, Penghui Yao, Mingnan Zhao
* [Permalink](https://eprint.iacr.org/2024/1470)
* [Download](https://eprint.iacr.org/2024/1470.pdf)

### Abstract

Quantum pseudorandom state generators (PRSGs) have stimulated exciting developments in recent years. A PRSG, on a fixed initial (e.g., all-zero) state, produces an output state that is computationally indistinguishable from a Haar random state. However, pseudorandomness of the output state is not guaranteed on other initial states. In fact, known PRSG constructions provably fail on some initial states.

In this work, we propose and construct quantum Pseudorandom State Scramblers (PRSSs), which can produce a pseudorandom state on an arbitrary initial state.. In the information-theoretical setting, we obtain a scrambler which maps an arbitrary initial state to a distribution of quantum states that is close to Haar random in total variation distance. As a result, our scrambler exhibits a dispersing property. Loosely, it can span an ɛ-net of the state space.. This significantly strengthens what standard PRSGs can induce, as they may only concentrate on a small region of the state space provided that average output state approximates a Haar random state.

Our PRSS construction develops a parallel extension of the famous Kac's walk, and we show that it mixes exponentially faster than the standard Kac's walk. This constitutes the core of our proof. We also describe a few applications of PRSSs. While our PRSS construction assumes a post-quantum one-way function, PRSSs are potentially a weaker primitive and can be separated from one-way functions in a relativized world similar to standard PRSGs.



## 2024/1471

* Title: Communication Efficient Secure and Private Multi-Party Deep Learning
* Authors: Sankha Das, Sayak Ray Chowdhury, Nishanth Chandran, Divya Gupta, Satya Lokam, Rahul Sharma
* [Permalink](https://eprint.iacr.org/2024/1471)
* [Download](https://eprint.iacr.org/2024/1471.pdf)

### Abstract

Distributed training that enables multiple parties to jointly train
a model on their respective datasets is a promising approach to
address the challenges of large volumes of diverse data for training
modern machine learning models. However, this approach immedi-
ately raises security and privacy concerns; both about each party
wishing to protect its data from other parties during training and
preventing leakage of private information from the model after
training through various inference attacks. In this paper, we ad-
dress both these concerns simultaneously by designing efficient
Differentially Private, secure Multiparty Computation (DP-MPC)
protocols for jointly training a model on data distributed among
multiple parties. Our DP-MPC protocol in the two-party setting
is 56-794× more communication-efficient and 16-182× faster than
previous such protocols. Conceptually, our work simplifies and
improves on previous attempts to combine techniques from secure
multiparty computation and differential privacy, especially in the
context of ML training.



## 2024/1472

* Title: Isogeny-Based Secure Voting Systems for Large-Scale Elections
* Authors: Mohammed El Baraka, Siham Ezzouak
* [Permalink](https://eprint.iacr.org/2024/1472)
* [Download](https://eprint.iacr.org/2024/1472.pdf)

### Abstract

This article presents an in-depth study of isogeny-based cryptographic methods for the development of secure and scalable electronic voting systems. We address critical challenges such as voter privacy, vote integrity, and resistance to quantum attacks. Our work introduces novel cryptographic protocols leveraging isogenies, establishing a robust framework for post-quantum secure electronic voting. We provide detailed mathematical foundations, protocol designs, and security proofs, demonstrating the efficacy and scalability of our proposed system in large-scale elections.



## 2024/1473

* Title: A Note on Low-Communication Secure Multiparty Computation via Circuit Depth-Reduction
* Authors: Pierre Charbit, Geoffroy Couteau, Pierre Meyer, Reza Naserasr
* [Permalink](https://eprint.iacr.org/2024/1473)
* [Download](https://eprint.iacr.org/2024/1473.pdf)

### Abstract

We consider the graph-theoretic problem of removing (few) nodes from a directed acyclic graph in order to reduce its depth. While this problem is intractable in the general case, we provide a variety of algorithms in the case where the graph is that of a circuit of fan-in (at most) two, and explore applications of these algorithms to secure multiparty computation with low communication. Over the past few years, a paradigm for low-communication secure multiparty computation has found success based on decomposing a circuit into low-depth ``chunks''. This approach was however previously limited to circuits with a ``layered'' structure. Our graph-theoretic approach extends this paradigm to all circuits. In particular, we obtain the following contributions:

1) Fractionally linear-communication MPC in the correlated randomness model: We provide an $N$-party protocol for computing an $n$-input, $m$-output $\mathsf{F}$-arithmetic circuit with $s$ internal gates (over any basis of binary gates) with communication complexity $(\frac{2}{3}s + n + m)\cdot N\cdot\log |\mathsf{F}|$, which can be improved to $((1+\epsilon)\cdot\frac{2}{5}s+n+m)\cdot N\cdot\log |\mathsf{F}|$ (at the cost of increasing the computational overhead from a small constant factor to a large one). Previously, comparable protocols either used more than $s\cdot N\cdot \log |\mathsf{F}|$ bits of communication, required super-polynomial computation, were restricted to layered circuits, or tolerated a sub-optimal corruption threshold.

2) Sublinear-Communication MPC:
Assuming the existence of $N$-party Homomorphic Secret Sharing for logarithmic depth circuits (respectively doubly logarithmic depth circuits), we show there exists sublinear-communication secure $N$-party computation for \emph{all} $\log^{1+o(1)}$-depth (resp.~$(\log\log)^{1+o(1)}$-depth) circuits. Previously, this result was limited to $(\mathcal{O}(\log))$-depth (resp.~$(\mathcal{O}(\log\log))$-depth) circuits, or to circuits with a specific structure (e.g. layered).

3) The 1-out-of-M-OT complexity of MPC:
We introduce the `` 1-out-of-M-OT complexity of MPC'' of a function $f$, denoted $C_M(f)$, as the number of oracle calls required to securely compute $f$ in the  1-out-of-M-OT hybrid model. We establish the following upper bound: for every $M\geq 2$, $C_N(f) \leq (1+g(M))\cdot \frac{2 |f|}{5}$, where $g(M)$ is an explicit vanishing function.

We also obtain additional contributions to reducing the amount of bootstrapping for fully homomorphic encryption, and to other types of sublinear-communication MPC protocols such as those based on correlated symmetric private information retrieval.



## 2024/1474

* Title: Mystrium: Wide Block Encryption Efficient on Entry-Level Processors
* Authors: Parisa Amiri Eliasi, Koustabh Ghosh, Joan Daemen
* [Permalink](https://eprint.iacr.org/2024/1474)
* [Download](https://eprint.iacr.org/2024/1474.pdf)

### Abstract

We present a tweakable wide block cipher called Mystrium and show it as the fastest such primitive on low-end processors that lack dedicated AES or other cryptographic instructions, such as ARM Cortex-A7.
Mystrium is based on the provably secure double-decker mode, that requires a doubly extendable cryptographic keyed (deck) function and a universal hash function.
We build a new deck function called Xymmer that for its compression part uses Multimixer-128, the fastest universal hash for such processors, and for its expansion part uses a newly designed permutation, $\mathcal{G}_{512}$.
Deck functions can also be used in modes to build encryption, authenticated encryption, and authentication schemes, and hence, Xymmer is of independent interest.
The current state-of-the-art wide tweakable block cipher Adiantum-XChaCha12-AES encrypts 4096-byte messages at 11.5 cycles per byte on ARM Cortex-A7, while for Mystrium it is 6.8 cycles per byte while having a higher claimed security.



## 2024/1475

* Title: On the Spinor Genus and the Distinguishing Lattice Isomorphism Problem
* Authors: Cong Ling, Jingbo Liu, Andrew Mendelsohn
* [Permalink](https://eprint.iacr.org/2024/1475)
* [Download](https://eprint.iacr.org/2024/1475.pdf)

### Abstract

This paper addresses the spinor genus, a previously unrecognized classification of quadratic forms in the context of cryptography, related to the lattice isomorphism problem (LIP). The spinor genus lies between the genus and equivalence class, thus refining the concept of genus. We present algorithms to determine whether two quadratic forms belong to the same spinor genus. If they do not, it provides a negative answer to the distinguishing variant of LIP. However, these algorithms have very high complexity, and we show that the proportion of genera splitting into multiple spinor genera is vanishing (assuming rank $n \geq 3$). For the special case of anisotropic integral binary forms ($n = 2$) over number fields with class number 1, we offer an efficient quantum algorithm to test if two forms lie in the same spinor genus. Our algorithm does not apply to the HAWK protocol, which uses integral binary Hermitian forms over number fields with class number greater than 1.



## 2024/1476

* Title: The Concrete Security of Two-Party Computation: Simple Definitions, and Tight Proofs for PSI and OPRFs
* Authors: Mihir Bellare, Rishabh Ranjan, Doreen Riepel, Ali Aldakheel
* [Permalink](https://eprint.iacr.org/2024/1476)
* [Download](https://eprint.iacr.org/2024/1476.pdf)

### Abstract

This paper initiates a concrete-security treatment of two-party secure computation. The first step is to propose, as target, a simple, indistinguishability-based definition that we call InI. This could be considered a poor choice if it were weaker than standard simulation-based definitions, but it is not; we show that for functionalities satisfying a condition called invertibility, that we define and show is met by functionalities of practical interest like PSI and its variants, the two definitions are equivalent. Based on this, we move forward to study the concrete security of a canonical OPRF-based construction of PSI, giving a tight proof of InI security of the constructed PSI protocol based on the security of the OPRF. This leads us to the concrete security of OPRFs, where we show how different DH-style assumptions on the underlying group yield proofs of different degrees of tightness, including some that are tight, for the well-known and efficient 2H-DH OPRF, and thus for the corresponding DH PSI protocol. We then give a new PSI protocol, called salted-DH PSI, that is as efficient as DH-PSI, yet enjoys tighter proofs.



## 2024/1477

* Title: Signature-based Witness Encryption with Compact Ciphertext
* Authors: Gennaro Avitabile, Nico Döttling, Bernardo Magri, Christos Sakkas, Stella Wohnig
* [Permalink](https://eprint.iacr.org/2024/1477)
* [Download](https://eprint.iacr.org/2024/1477.pdf)

### Abstract

Signature-based witness encryption (SWE) is a recently proposed notion that allows to encrypt a message with respect to a tag $T$ and a set of signature verification keys. The resulting ciphertext can only be decrypted by a party who holds at least $k$ different valid signatures w.r.t. $T$ and $k$ different verification keys out of the $n$ keys specified at encryption time. Natural applications of this primitive involve distributed settings (e.g., blockchains), where multiple parties sign predictable messages, such as polling or randomness beacons. However, known SWE schemes without trusted setup have ciphertexts that scale linearly in the number of verification keys. This quickly becomes a major bottleneck as the system gets more distributed and the number of parties increases.
   
    Towards showing the feasibility of SWE with ciphertext size sub-linear in the number of keys, we give a construction based on indistinguishability obfuscation (iO) for Turing machines and strongly puncturable signatures (SPS).



## 2024/1478

* Title: Mind the Bad Norms: Revisiting Compressed Oracle-based Quantum Indistinguishability Proofs
* Authors: Ritam Bhaumik, Benoît Cogliati, Jordan Ethan, Ashwin Jha
* [Permalink](https://eprint.iacr.org/2024/1478)
* [Download](https://eprint.iacr.org/2024/1478.pdf)

### Abstract

In this work, we revisit the Hosoyamada-Iwata (HI) proof for the quantum CPA security of the 4-round Luby-Rackoff construction and identify a gap that appears to undermine the security proof. We emphasize that this is not an attack, and the construction may still achieve the claimed security level. However, this gap raises concerns about the feasibility of establishing a formal security proof for the 4-round Luby-Rackoff construction. In fact, the issue persists even if the number of rounds is increased arbitrarily. On a positive note, we restore the security of the 4-round Luby-Rackoff construction in the non-adaptive setting, achieving security up to $2^{n/6}$ superposition queries. Furthermore, we establish the quantum CPA security of the 4-round MistyR and 5-round MistyL constructions, up to $2^{n/5}$ and $2^{n/7}$ superposition queries, respectively, where $n$ denotes the size of the underlying permutation.