## In this issue

1. [2024/752] More Embedded Curves for SNARK-Pairing-Friendly Curves
2. [2024/871] New Approaches for Estimating the Bias of ...
3. [2024/1238] Dynamic Collusion Functional Encryption and Multi- ...
4. [2024/1239] Efficient Differentially Private Set Intersection
5. [2024/1240] ARADI and LLAMA: Low-Latency Cryptography for ...
6. [2024/1241] PROF: Protected Order Flow in a Profit-Seeking World
7. [2024/1242] Beyond the Whitepaper: Where BFT Consensus ...
8. [2024/1243] Tailoring two-dimensional codes for structured ...
9. [2024/1244] A Note on ``Three-Factor Anonymous Authentication ...
10. [2024/1245] Garuda and Pari: Faster and Smaller SNARKs via ...
11. [2024/1246] MSMAC: Accelerating Multi-Scalar Multiplication for ...
12. [2024/1247] A Note on the Quasigroup Lai-Massey Structures
13. [2024/1248] A Not So Discrete Sampler: Power Analysis Attacks ...
14. [2024/1249] Koala: A Low-Latency Pseudorandom Function
15. [2024/1250] AutoHoG: Automating Homomorphic Gate Design for ...
16. [2024/1251] EMI Shielding for Use in Side-Channel Security: ...
17. [2024/1252] Legendre Sequences are Pseudorandom under the ...
18. [2024/1253] FELIX (XGCD for FALCON): FPGA-based Scalable and ...
19. [2024/1254] Non-Interactive Zero-Knowledge from LPN and MQ
20. [2024/1255] Compass: Encrypted Semantic Search with High Accuracy
21. [2024/1256] Concrete Analysis of Schnorr-type Signatures with ...
22. [2024/1257] Committing Wide Encryption Mode with Minimum ...
23. [2024/1258] Count Corruptions, Not Users: Improved Tightness ...
24. [2024/1259] Efficient (Non-)Membership Tree from ...
25. [2024/1260] zk-Promises: Making Zero-Knowledge Objects Accept ...
26. [2024/1261] A Key-Recovery Attack on a Leaky Seasign Variant
27. [2024/1262] Dilithium-Based Verifiable Timed Signature Scheme
28. [2024/1263] A Security Analysis of Two Classes of RSA-like ...
29. [2024/1264] Succinct Non-Subsequence Arguments
30. [2024/1265] Safe curves for elliptic-curve cryptography
31. [2024/1266] Information-Theoretic Topology-Hiding Broadcast: ...

## 2024/752

* Title: More Embedded Curves for SNARK-Pairing-Friendly Curves
* Authors: Aurore Guillevic
* [Permalink](https://eprint.iacr.org/2024/752)
* [Download](https://eprint.iacr.org/2024/752.pdf)

### Abstract

Embedded curves are elliptic curves defined over a prime field whose order (characteristic) is the prime subgroup order (the scalar field) of a pairing-friendly curve. Embedded curves have a large prime-order subgroup of cryptographic size but are not
pairing-friendly themselves. Sanso and El Housni published families of embedded curves for BLS pairing-friendly curves. Their families are parameterized by polynomials, like families of pairing-friendly curves are. However their work did not found
embedded families for KSS pairing-friendly curves. In this note we show how the problem of finding families of embedded curves is related to the problem of finding optimal formulas for $\G_1$ subgroup membership testing on the pairing-friendly curve side.
Then we apply Smith's technique and Dai, Lin, Zhao, and Zhou (DLZZ) criteria to obtain the formulas of embedded curves with KSS, and outline a generic algorithm for solving this problem in all cases. We provide two families of embedded curves of prime-
order for KSS18 that can form a plain cycle, and give examples of cryptographic size. We also give families of even-order $j=1728$ embedded curves for KSS16 with examples. We also suggest alternative embedded curves for BLS that have a seed of much lower
Hamming weight than Sanso et al.~and much higher 2-valuation for fast FFT. In particular we highlight BLS12 curves which have a prime-order embedded curve that form a plain cycle (no pairing), and a second (plain) embedded curve in Montgomery form. A
Brezing-Weng outer curve to have a pairing-friendly 2-chain is also possible like in the BLS12-377-BW6-761 construction. All curves have $j$-invariant 0 and an endomorphism for a faster arithmetic on the curve side.



## 2024/871

* Title: New Approaches for Estimating the Bias of Differential-Linear Distinguishers (Full Version)
* Authors: Ting Peng, Wentao Zhang, Jingsui Weng, Tianyou Ding
* [Permalink](https://eprint.iacr.org/2024/871)
* [Download](https://eprint.iacr.org/2024/871.pdf)

### Abstract

Differential-linear cryptanalysis was introduced by Langford and Hellman in 1994 and has been extensively studied since then. In 2019, Bar-On et al. presented the Differential-Linear Connectivity Table (DLCT), which connects the differential part and the
linear part, thus an attacked cipher is divided to 3 subciphers: the differential part, the DLCT part, and the linear part.
In this paper, we firstly present an accurate mathematical formula which establishes a relation between differential-linear and truncated differential cryptanalysis. Using the formula, the bias estimate of a differential-linear distinguisher can be
converted to the probability calculations of a series of truncated differentials. Then, we propose a novel and natural concept, the TDT, which can be used to accelerate the calculation of the probabilities of truncated differentials. Based on the formula
and the TDT, we propose two novel approaches for estimating the bias of a differential-linear distinguisher. We demonstrate the accuracy and efficiency of our new approaches by applying them to 5 symmetric-key primitives: Ascon, Serpent, KNOT, AES, and
CLEFIA. For Ascon and Serpent, we update the best known differential-linear distinguishers. For KNOT AES, and CLEFIA, for the first time we give the theoretical differential-linear biases for different rounds.



## 2024/1238

* Title: Dynamic Collusion Functional Encryption and Multi-Authority Attribute-Based Encryption
* Authors: Rachit Garg, Rishab Goyal, George Lu
* [Permalink](https://eprint.iacr.org/2024/1238)
* [Download](https://eprint.iacr.org/2024/1238.pdf)

### Abstract

Functional Encryption (FE) is a powerful notion of encryption which enables computations and partial message recovery of encrypted data. In FE, each decryption key is associated with a function $f$ such that decryption recovers the function evaluation $f(
m)$ from an encryption of $m$. Informally, security states that a user with access to function keys $\mathsf{sk}_{f_1}, \mathsf{sk}_{f_2}, \ldots$ (and so on) can only learn $f_1(m), f_2(m), \ldots$ (and so on) but nothing more about the message. The
system is said to be $q$-bounded collusion resistant if the security holds as long as an adversary gets access to at most $q = q(\lambda)$ decryption keys. In the last decade, numerous works have proposed many FE constructions from a wide array of
algebraic and general cryptographic assumptions, and proved their security in the bounded collusion model.

However, until very recently, all these works studied bounded collusion resistance in a "static model", where the collusion bound $q$ was a global system parameter. While the static collusion model led to great research progress in the community, it has
many major drawbacks. Very recently, Agrawal et al. (Crypto 2021) and Garg et al. (Eurocrypt 2022) independently introduced the "dynamic model" for bounded collusion resistance, where the collusion bound $q$ was a fluid parameter that was not globally
set but only chosen by each encryptor. The dynamic collusion model enabled harnessing the many virtues of the static collusion model, while avoiding its various drawbacks.

In this work, we give a simple and generic approach to upgrade any scheme from the static collusion model to the dynamic collusion model. Our result captures all existing results in the dynamic model in the form of a single unified framework, and also
gives new results as simple corollaries with a lot more potential in the future. An interesting artifact of our result is that it gives a generic way to match existing lower bounds in functional encryption.



## 2024/1239

* Title: Efficient Differentially Private Set Intersection
* Authors: Xinyu Peng, Yufei Wang, Weiran Liu, Liqiang Peng, Feng Han, Zhen Gu, Jianling Sun, Yuan Hong
* [Permalink](https://eprint.iacr.org/2024/1239)
* [Download](https://eprint.iacr.org/2024/1239.pdf)

### Abstract

Private Set Intersection (PSI) enables a sender and a receiver to jointly compute the intersection of their sets without disclosing other information about items not in the intersection. However, in many cases of joint data analysis, it is not just the
items outside the intersection that are sensitive but the items within it. To protect such sensitive information, prior work presents a Differentially Private version of PSI (DPSI) based on a circuit-PSI using Fully Homomorphic Encryption. However, their
concrete protocol is somewhat inefficient compared with the state-of-the-art (SOTA) circuit-PSI.

In this paper, we revisit the DPSI definition and formalize its ideal functionality. We identify the key desiderata required by PSI-related tools to construct DPSI and propose two frameworks to construct efficient DPSI protocols. The first one
generalizes the idea of existing DPSI, showing that any circuit-PSI can be used to construct DPSI. We obtain a more efficient DPSI protocol by plugging the SOTA circuit-PSI protocol in the framework. The second one helps to obtain a more efficient DPSI
protocol based on the multi-query Reverse Private Membership Test (mqRPMT) that was previously used to construct Private Set Operation (PSO). However, mqRPMT additionally leaks the intersection size to the sender. We bound such leakage using differential
privacy by padding random dummy items in input sets. We implement numerous constructions based on our frameworks. Experiments show that our protocols significantly outperform the existing DPSI construction, 2.5-22.6$\times$ more communication efficient
and up to 110.5-151.8$\times$ faster. Our work also shows a new use case for mqRPMT besides obtaining PSO.



## 2024/1240

* Title: ARADI and LLAMA: Low-Latency Cryptography for Memory Encryption
* Authors: Patricia Greene, Mark Motley, Bryan Weeks
* [Permalink](https://eprint.iacr.org/2024/1240)
* [Download](https://eprint.iacr.org/2024/1240.pdf)

### Abstract

In this paper, we describe a low-latency block cipher (ARADI) and authenticated encryption mode (LLAMA) intended to support memory encryption applications.



## 2024/1241

* Title: PROF: Protected Order Flow in a Profit-Seeking World
* Authors: Kushal Babel, Nerla Jean-Louis, Yan Ji, Ujval Misra, Mahimna Kelkar, Kosala Yapa Mudiyanselage, Andrew Miller, Ari Juels
* [Permalink](https://eprint.iacr.org/2024/1241)
* [Download](https://eprint.iacr.org/2024/1241.pdf)

### Abstract

Users of decentralized finance (DeFi) applications face significant risks from adversarial actions that manipulate the order of transactions to extract value from users. Such actions---an adversarial form of what is called maximal-extractable value (MEV)-
--impact both individual outcomes and the stability of the DeFi ecosystem. MEV exploitation, moreover, is being institutionalized through an architectural paradigm known Proposer-Builder Separation (PBS).

This work introduces a system called PROF (PRotected Order Flow) that is designed to limit harmful forms of MEV in existing PBS systems. PROF aims at this goal using two ideas. First, PROF imposes an ordering on a set ("bundle") of privately input
transactions and enforces that ordering all the way through to block production-preventing transaction-order manipulation. Second, PROF creates bundles whose inclusion is profitable to block producers, thereby ensuring that bundles see timely inclusion
in blocks.

PROF is backward-compatible, meaning that it works with existing and future PBS designs. PROF is also compatible with any desired algorithm for ordering transactions within a PROF bundle (e.g., first-come, first-serve, fee-based, etc.). It executes
efficiently, i.e., with low latency, and requires no additional trust assumptions among PBS entities. We quantitatively and qualitatively analyze PROF’s incentive structure, and its utility to users compared with existing solutions. We also report on
inclusion likelihood of PROF transactions, and concrete latency numbers through our end-to-end implementation.



## 2024/1242

* Title: Beyond the Whitepaper: Where BFT Consensus Protocols Meet Reality
* Authors: David Wong, Denis Kolegov, Ivan Mikushin
* [Permalink](https://eprint.iacr.org/2024/1242)
* [Download](https://eprint.iacr.org/2024/1242.pdf)

### Abstract

This paper presents a collection of lessons learned from analyzing the real-world security of various Byzantine Fault Tolerant (BFT) consensus protocol implementations. Drawing upon our experience as a team of security experts who have both developed and
audited BFT systems, including BA★, HotStuff variants, Paxos variants, and DAG-based algorithms like Narwhal and Bullshark, we identify and analyze a variety of security vulnerabilities discovered in the translation of theoretical protocols into real-
world code. Our analysis covers a range of issues, including subtle logic errors, concurrency bugs, cryptographic vulnerabilities, and mismatches between the theoretical model and the implementation. We provide detailed case studies illustrating these
vulnerabilities, discuss their potential impact, and propose mitigation strategies. This work aims to provide valuable insights for both designers and implementers of BFT consensus protocols, ultimately contributing to the development of more secure and
reliable distributed systems.



## 2024/1243

* Title: Tailoring two-dimensional codes for structured lattice-based KEMs and applications to Kyber
* Authors: Thales B. Paiva, Marcos A. Simplicio Jr, Syed Mahbub Hafiz, Bahattin Yildiz, Eduardo L. Cominetti
* [Permalink](https://eprint.iacr.org/2024/1243)
* [Download](https://eprint.iacr.org/2024/1243.pdf)

### Abstract

Kyber is a post-quantum lattice-based key encapsulation mechanism (KEM) selected by NIST for standardization as ML-KEM. The scheme is designed to ensure that the unintentional errors accumulated during decryption do not prevent the receiver to correctly
recover the encapsulated key. This is done by using a simple error-correction code independently applied to each bit of the message, for which it is possible to show that the decryption failure rate (DFR) is negligible. Although there have been other
proposals of more complex error-correction codes for Kyber, these have important limitations. Some proposals use independence assumptions on the noise distribution that do not hold. Others require significant changes in Kyber's core parameters, which
make them unpractical. In this work, we propose a family of 2-dimensional codes that can, in principle, be applied to any lattice-based scheme. Even though our 2D codes have a rather simple construction, they can be tailored for the specific noise
distribution observed for different Kyber parameters, and reduce Kyber's DFR by factors of $2^{4.8}$, $2^{5.4}$, and $2^{9.9}$, for security levels 1, 3, and 5, respectively, without requiring independence assumptions. Alternatively, the proposed codes
allow for up to $6\%$ ciphertext compression in Kyber Level 5 while maintaining the DFR lower than $2^{-160}$, which is the target value defined in Kyber's specification. Furthermore, we provide an efficient isochronous implementation of the encoding and
decoding procedures for our 2D codes. Compared with Kyber's reference implementation, the performance impact of the 2D codes in the decapsulation time is negligible (namely, between $0.08\%$ to $0.18\%$, depending on the security level).



## 2024/1244

* Title: A Note on ``Three-Factor Anonymous Authentication and Key Agreement Based on Fuzzy Biological Extraction for Industrial Internet of Things''
* Authors: Zhengjun Cao, Lihua Liu
* [Permalink](https://eprint.iacr.org/2024/1244)
* [Download](https://eprint.iacr.org/2024/1244.pdf)

### Abstract

We show that the key agreement scheme [IEEE Trans. Serv. Comput. 16(4): 3000-3013, 2023] fails to keep user anonymity, not as claimed. The scheme simply acknowledges that user anonymity is equivalent to preventing user's identity from being recovered.
But the true anonymity means that the adversary cannot attribute different sessions to target users. It relates to entity-distinguishable, not just identity-revealable. To the best of our knowledge, it is the first time to clarify the explicit
signification of user anonymity.



## 2024/1245

* Title: Garuda and Pari: Faster and Smaller SNARKs via Equifficient Polynomial Commitments
* Authors: Michel Dellepere, Pratyush Mishra, Alireza Shirzad
* [Permalink](https://eprint.iacr.org/2024/1245)
* [Download](https://eprint.iacr.org/2024/1245.pdf)

### Abstract

SNARKs are powerful cryptographic primitives that allow a prover to produce a succinct proof of a computation. Two key goals of SNARK research are to minimize the size of the proof and to minimize the time required to generate the proof. In this work, we
present new SNARK constructions that push the frontier on both of these goals.


Our first construction, Pari, is a SNARK that achieves the smallest proof size amongst *all* known SNARKs. Specifically, Pari achieves a proof size of just two group elements and two field elements, which, when instantiated with the BLS12-381 curve,
totals just 160 bytes, smaller than that of Groth16 [Groth, EUROCRYPT '16] and Polymath [Lipmaa, CRYPTO '24].

Our second construction, Garuda, is a SNARK that reduces proof generation time by supporting, for the first time, arbitrary "custom" gates and *free* linear gates. To demonstrate Garuda's performance, we implement and evaluate it, and show that it
provides significant prover-time savings compared to both the state-of-the-art SNARKs (Groth16 and HyperPlonk [EUROCRYPT '22])

Both constructions rely on a new cryptographic primitive: "equifficient" polynomial commitment schemes that enforce that committed polynomials have the same representation in particular bases. We provide both rigorous security definitions for this
primitive as well as efficient constructions for univariate and multilinear polynomials.



## 2024/1246

* Title: MSMAC: Accelerating Multi-Scalar Multiplication for Zero-Knowledge Proof
* Authors: Pengcheng Qiu, Guiming Wu, Tingqiang Chu, Changzheng Wei, Runzhou Luo, Ying Yan, Wei Wang, Hui Zhang
* [Permalink](https://eprint.iacr.org/2024/1246)
* [Download](https://eprint.iacr.org/2024/1246.pdf)

### Abstract

Multi-scalar multiplication (MSM) is the most computation-intensive part in proof generation of Zero-knowledge proof (ZKP). In this paper, we propose MSMAC, an FPGA accelerator for large-scale MSM. MSMAC adopts a specially designed Instruction Set
Architecture (ISA) for MSM and optimizes pipelined Point Addition Unit (PAU) with hybrid Karatsuba multiplier. Moreover, a runtime system is proposed to split MSM tasks with the optimal sub-task size and orchestrate execution of Processing Elements (PEs).
Experimental results show that MSMAC achieves up to 328× and 1.96× speedups compared to the state-of-the-art implementation on CPU (one core) and GPU, respectively, outperforming the state-of-the-art ASIC accelerator by 1.79×. On 4 FPGAs, MSMAC
performs 1,261× faster than a single CPU core.



## 2024/1247

* Title: A Note on the Quasigroup Lai-Massey Structures
* Authors: George Teseleanu
* [Permalink](https://eprint.iacr.org/2024/1247)
* [Download](https://eprint.iacr.org/2024/1247.pdf)

### Abstract

In our paper, we explore the consequences of replacing the commutative group operation used in Lai-Massey structures with a quasigroup operation.
We introduce four quasigroup versions of the Lai-Massey structure, and prove that for quasigroups isotopic with a group $\mathbb{G}$, the complexity of launching a differential attack against these variants of the Lai-Massey structure is equivalent to
attacking an alternative structure based on $\mathbb{G}$.
Then we provide the conditions needed for correct decryption, and further refine the resulting structure. The emerging structure is both intriguing and novel, and we hope that it will form the basis for future secure block ciphers based on non-
commutative groups. In the case of commutative groups, we show that the resulting structure reduces to the classical Lai-Massey structure.



## 2024/1248

* Title: A Not So Discrete Sampler: Power Analysis Attacks on HAWK signature scheme
* Authors: Morgane Guerreau, Mélissa Rossi
* [Permalink](https://eprint.iacr.org/2024/1248)
* [Download](https://eprint.iacr.org/2024/1248.pdf)

### Abstract

HAWK is a lattice-based signature scheme candidate to the fourth call of the NIST's Post-Quantum standardization campaign. Considered as a cousin of Falcon (one of the future NIST post-quantum standards) one can wonder whether HAWK shares the same
drawbacks as Falcon in terms of side-channel attacks. Indeed, Falcon signature algorithm and particularly its Gaussian sampler, has shown to be highly vulnerable to power-analysis attacks. Besides, efficiently protecting Falcon's signature algorithm
against these attacks seems a very challenging task.

This work presents the first power analysis leakage review on HAWK signature scheme: it extensively assesses the vulnerabilities of a central and sensitive brick of the scheme, the discrete Gaussian sampler. Knowing the output x of the sampler for a
given signature leads to linear information about the private key of the scheme.

This paper includes several demonstrations of simple power analysis attacks targeting this sample x with various attacker strengths, all of them performed on the reference implementation on a ChipWhisperer Lite with STM32F3 target (ARM Cortex M4). We
report being able to perform key recoveries with very low (to no) offline resources. As this reference implementation of HAWK is not claimed to be protected against side-channel attacks, the existence of such attacks is not surprising, but they still
concretely warn about the use of this unprotected signature on physical devices.

To go further, our study proposes a generic way of assessing the performance of a side-channel attack on x even when less information is recovered, in a setting where some protections are implemented or when the attacker has less measurement
possibilities. While it is easy to see that x is a sensitive value, quantifying the residual complexity of the key recovery with some knowledge about x (like the parity or the sign of some coefficients) is not straightforward as the underlying hardness
assumption is the newly introduced Module-LIP problem. We propose to adapt the existing methodology of leaky LWE estimation tools (Dachman-Soled et al. at Crypto 2020) to exploit the retrieved information and lower down the residual key recovery
complexity.

To finish, we propose an ad-hoc technique to lower down the leakage on the identified vulnerability points. These modifications prevent our attacks on our platform and come with essentially no cost in terms of performance. It could be seen as a temporary
solution and encourages more analysis on proven side-channel protection of HAWK like masking.



## 2024/1249

* Title: Koala: A Low-Latency Pseudorandom Function
* Authors: Parisa Amiri Eliasi, Yanis Belkheyar, Joan Daemen, Santosh Ghosh, Daniël Kuijsters, Alireza Mehrdad, Silvia Mella, Shahram Rasoolzadeh, Gilles Van Assche
* [Permalink](https://eprint.iacr.org/2024/1249)
* [Download](https://eprint.iacr.org/2024/1249.pdf)

### Abstract

This paper introduces the Koala PRF, which maps a variable-length sequence of $64$-bit input blocks to a single $257$-bit output block.
Its design focuses on achieving low latency in its implementation in ASIC.
To construct Koala, we instantiate the recently introduced Kirby construction with the Koala-P permutation and add an input encoding layer.

The Koala-P permutation is obtained as the $8$-fold iteration of a simple round function inspired by that of Subterranean.
Based on careful preliminary cryptanalysis, we made a variant of the Subterranean permutation by reordering and modifying it in a way that does not introduce any implementation overhead and enhances the cryptographic resistance of the resulting PRF.
Indeed, we demonstrate that Koala exhibits a high resistance against integral, cube, division property, and higher-order differential attacks.

Additionally, we compare the hardware implementation of Koala with the smallest latency with state-of-the-art low-latency PRF Orthros and Gleeok and the block cipher Prince in the same ASIC synthesis setup.
Our results show that Koala outperforms these primitives not only in terms of latency but also with respect to various other performance measures.



## 2024/1250

* Title: AutoHoG: Automating Homomorphic Gate Design for Large-Scale Logic Circuit Evaluation
* Authors: Zhenyu Guan, Ran Mao, Qianyun Zhang, Zhou Zhang, Zian Zhao, Song Bian
* [Permalink](https://eprint.iacr.org/2024/1250)
* [Download](https://eprint.iacr.org/2024/1250.pdf)

### Abstract

Recently, an emerging branch of research in the field of fully homomorphic encryption (FHE) attracts growing attention, where optimizations are carried out in developing fast and efficient homomorphic logic circuits. While existing works have pointed out
that compound homomorphic gates can be constructed without incurring significant computational overheads, the exact theory and mechanism of homomorphic gate design have not yet been explored. In this work, we propose AutoHoG, an automated procedure for
the generation of compound gates over FHE. We show that by formalizing the gate generation procedure, we can adopt a match-and-replace strategy to significantly improve the evaluation speed of logic circuits over FHE. In the experiment, we first show the
effectiveness of AutoHoG through a set of benchmark gates. We then apply AutoHoG to optimize common Boolean tasks, including adders, multipliers, the ISCAS’85 benchmark circuits, and the ISCAS’89 benchmark circuits. We show that for various circuit
benchmarks, we can achieve up to 5.7x reduction in computational latency when compared to the state-of-the-art implementations of logic circuits using conventional gates.



## 2024/1251

* Title: EMI Shielding for Use in Side-Channel Security: Analysis, Simulation and Measurements
* Authors: Daniel Dobkin, Edut Katz, David Popovtzer, Itamar Levi
* [Permalink](https://eprint.iacr.org/2024/1251)
* [Download](https://eprint.iacr.org/2024/1251.pdf)

### Abstract

Considering side-channel analysis (SCA) security for cryptographic devices, the mitigation of electromagnetic leakage and electromagnetic interference (EMI) between modules poses significant challenges. This paper presents a comprehensive review and deep
analysis of the utilization of EMI shielding materials, devised for reliability purposes and standards such as EMI/EMC, as a countermeasure to enhance EM-SCA security. We survey the current landscape of EMI-shields materials, including conductive
polymers, metal-foams, carbon-based materials, and meta-materials, evaluating their effectiveness in attenuating emissions and preventing information-leakage, a task done with security-centric metrics for such materials for the first time. Through a
systematic examination of existing literature, experimental studies and a construction of fully-simulatable EM environment in ANSYS-solver, we identify key factors influencing the performance of EMI-shield materials, such as shielding-effectiveness (SE),
bandwidth, thickness, and material properties, on security characteristics.
We devise a connection between SE and cryptographic-SNR, and we demonstrate from real hardware measurements how and in what conditions can such materials provide very high security levels. By synthesizing insights from multidisciplinary research
domains, this paper aims to provide valuable two-way benefit and guidance for researchers, engineers, and practitioners in the design and deployment of robust side-channel security measures leveraging EMI-shields, already in utilization devised by
reliability standards.



## 2024/1252

* Title: Legendre Sequences are Pseudorandom under the Quadratic-Residuosity Assumption
* Authors: Henry Corrigan-Gibbs, David J. Wu
* [Permalink](https://eprint.iacr.org/2024/1252)
* [Download](https://eprint.iacr.org/2024/1252.pdf)

### Abstract

The Legendre sequence of an integer $x$ modulo a prime $p$ with respect to offsets $\vec a = (a_1, \dots, a_\ell)$ is the string of Legendre symbols $(\frac{x+a_1}{p}), \dots, (\frac{x+a_\ell}{p})$. Under the quadratic-residuosity assumption, we show
that the function that maps the pair $(x,p)$ to the Legendre sequence of $x$ modulo $p$, with respect to public random offsets $\vec a$, is a pseudorandom generator. This answers an open question of Damgård (CRYPTO 1988), up to the choice of the offsets
$\vec a$.



## 2024/1253

* Title: FELIX (XGCD for FALCON): FPGA-based Scalable and Lightweight Accelerator for Large Integer Extended GCD
* Authors: Sam Coulon, Tianyou Bao, Jiafeng Xie
* [Permalink](https://eprint.iacr.org/2024/1253)
* [Download](https://eprint.iacr.org/2024/1253.pdf)

### Abstract

The Extended Greatest Common Divisor (XGCD) computation is a critical component in various cryptographic applications and algorithms, including both pre- and post-quantum cryptosystems. In addition to computing the greatest common divisor (GCD) of two
integers, the XGCD also produces Bezout coefficients $b_a$ and $b_b$ which satisfy $\mathrm{GCD}(a,b) = a\times b_a + b\times b_b$. In particular, computing the XGCD for large integers is of significant interest. Most recently, XGCD computation between 6,
479-bit integers is required for solving $N$-th degree Truncated polynomial Ring Unit (NTRU) trapdoors in Falcon, a National Institute of Standards and Technology (NIST)-selected Post-Quantum digital signature scheme. To this point, existing literature
has primarily focused on exploring software-based implementations for XGCD. The few existing high-performance hardware architectures require significant hardware resources and may not be desirable for practical usage, and the lightweight architectures
suffer from poor performance. To fill the research gap, this work proposes a novel FPGA-based scalablE and Lightweight accelerator for large Integer XGCD (FELIX). First, a new algorithm suitable for scalable and lightweight computation of XGCD is
proposed. Next, a hardware accelerator (FELIX) is presented, including both constant- and variable-time versions. Finally, a thorough evaluation is carried out to showcase the efficiency of the proposed FELIX. In certain configurations, FELIX involves 81%
less equivalent area-time product (eATP) than the state-of-the-art design for 1,024-bit integers, and achieves a 95% reduction in latency over the software for 6,479-bit integers (Falcon parameter set) with reasonable resource usage. Overall, the
proposed FELIX is highly efficient, scalable, lightweight, and suitable for very large integer computation, making it the first such XGCD accelerator in the literature (to the best of our knowledge).



## 2024/1254

* Title: Non-Interactive Zero-Knowledge from LPN and MQ
* Authors: Quang Dao, Aayush Jain, Zhengzhong Jin
* [Permalink](https://eprint.iacr.org/2024/1254)
* [Download](https://eprint.iacr.org/2024/1254.pdf)

### Abstract


[continued in next message]

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