## 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


[continued in next message]

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)