## In this issue

1. [2023/1727] A Formal Treatment of Envelope Encryption
2. [2024/1586] WHIR: Reed–Solomon Proximity Testing with Super- ...
3. [2024/1879] Practical Zero-Knowledge PIOP for Public Key and ...
4. [2024/1880] Cryptography Experiments In Lean 4: SHA-3 ...
5. [2024/1881] THOR: Secure Transformer Inference with Homomorphic ...
6. [2024/1882] Single Trace Side-Channel Attack on the MPC-in-the- ...
7. [2024/1883] A Fault Analysis on SNOVA
8. [2024/1884] Age-aware Fairness in Blockchain Transaction ...
9. [2024/1885] Improved PIR Schemes using Matching Vectors and ...
10. [2024/1886] Impossibility Results for Post-Compromise Security ...
11. [2024/1887] Differential MITM attacks on SLIM and LBCIoT
12. [2024/1888] Chosen-Prefix Collisions on AES-like Hashing
13. [2024/1889] IO-Optimized Design-Time Configurable Negacyclic ...
14. [2024/1890] Efficient Modular Multiplication Hardware for ...
15. [2024/1891] Shifting our knowledge of MQ-Sign security
16. [2024/1892] A Comprehensive Survey on Hardware-Software co- ...
17. [2024/1893] High Speed High Assurance implementations of ...
18. [2024/1894] A non-comparison oblivious sort and its application ...
19. [2024/1895] A Tool for Fast and Secure LWE Parameter Selection: ...
20. [2024/1896] Shardora: Towards Scaling Blockchain Sharding via ...
21. [2024/1897] On Threshold Signatures from MPC-in-the-Head
22. [2024/1898] NTRU-based Bootstrapping for MK-FHEs without using ...
23. [2024/1899] Fast Multiplication and the PLWE-RLWE Equivalence ...
24. [2024/1900] Opening the Blackbox: Collision Attacks on Round- ...
25. [2024/1901] On the Insecurity of Bloom Filter-Based Private Set ...
26. [2024/1902] ZK-SNARKs for Ballot Validity: A Feasibility Study
27. [2024/1903] Trustworthy Approaches to RSA: Efficient ...
28. [2024/1904] An Open Source Ecosystem for Implementation ...
29. [2024/1905] OPL4GPT: An Application Space Exploration of ...
30. [2024/1906] On Efficient Computations of Koblitz Curves over ...
31. [2024/1907] Towards Optimal Garbled Circuits in the Standard Model
32. [2024/1908] Generalized Impossible Differential Attacks on ...
33. [2024/1909] NewtonPIR: Communication Efficient Single-Server PIR
34. [2024/1910] Stealth Software Trojan: Amplifying Hidden RF Side- ...
35. [2024/1911] Deletions and Dishonesty: Probabilistic Data ...

## 2023/1727

* Title: A Formal Treatment of Envelope Encryption
* Authors: Shoichi Hirose, Kazuhiko Minematsu
* [Permalink](https://eprint.iacr.org/2023/1727)
* [Download](https://eprint.iacr.org/2023/1727.pdf)

### Abstract

Envelope encryption is a method to encrypt data with two distinct keys in its basic form. Data is first encrypted with a data-encryption key, and then the data-encryption key is encrypted with a key-encryption key. Despite its deployment in major cloud
services, as far as we know, envelope encryption has not received any formal treatment. To address this issue, we first formalize the syntax and security requirements of envelope encryption in the symmetric-key setting. Then, we show that it can be
constructed by combining encryptment and authenticated encryption with associated data (AEAD). Encryptment is one-time AEAD satisfying that a small part of a ciphertext works as a commitment to the corresponding secret key, message, and associated data.
Finally, we show that the security of the generic construction is reduced to the security of the underlying encryptment and AEAD.



## 2024/1586

* Title: WHIR: Reed–Solomon Proximity Testing with Super-Fast Verification
* Authors: Gal Arnon, Alessandro Chiesa, Giacomo Fenzi, Eylon Yogev
* [Permalink](https://eprint.iacr.org/2024/1586)
* [Download](https://eprint.iacr.org/2024/1586.pdf)

### Abstract

We introduce WHIR, a new IOP of proximity that offers small query complexity and exceptionally fast verification time. The WHIR verifier typically runs in a few hundred microseconds, whereas other verifiers in the literature require several milliseconds (
if not much more). This significantly improves the state of the art in verifier time for hash-based SNARGs (and beyond).
Crucially, WHIR is an IOP of proximity for constrained Reed–Solomon codes, which can express a rich class of queries to multilinear polynomials and to univariate polynomials. In particular, WHIR serves as a direct replacement for protocols like FRI,
STIR, BaseFold, and others. Leveraging the rich queries supported by WHIR and a new compiler for multilinear polynomial IOPs, we obtain a highly efficient SNARG for generalized R1CS.
As a comparison point, our techniques also yield state-of-the-art constructions of hash-based (non-interactive) polynomial commitment schemes for both univariate and multivariate polynomials (since sumcheck queries naturally express polynomial
evaluations). For example, if we use WHIR to construct a polynomial commitment scheme for degree 222, with 100 bits of security, then the time to commit and open is 1.2 seconds, the sender communicates 63 KiB to the receiver, and the opening verification
time is 360 microseconds.



## 2024/1879

* Title: Practical Zero-Knowledge PIOP for Public Key and Ciphertext Generation in (Multi-Group) Homomorphic Encryption
* Authors: Intak Hwang, Hyeonbum Lee, Jinyeong Seo, Yongsoo Song
* [Permalink](https://eprint.iacr.org/2024/1879)
* [Download](https://eprint.iacr.org/2024/1879.pdf)

### Abstract

Homomorphic encryption (HE) is a foundational technology in privacy-enhancing cryptography, enabling non-interactive computation over encrypted data. Recently, generalized HE primitives designed for multi-party applications, such as multi-group HE (MGHE),
have gained significant research interest.
While constructing secure multi-party protocols from (MG)HE in the semi-honest model is straightforward, zero-knowledge techniques are essential for ensuring security against malicious adversaries.

In this work, we design practical proof systems for MGHE to guarantee the well-formedness of public keys and ciphertexts. Specifically, we develop and optimize a polynomial interactive oracle proof (PIOP) for MGHE, which can be compiled into zk-SNARKs
using a polynomial commitment scheme (PCS).

We compile our PIOP using a lattice-based PCS, and our implementation achieves a 5.5x reduction in proof size, a 70x speed-up in proof generation, and a 343x improvement in verification time compared to the previous state-of-the-art construction, PELTA (
ACM CCS 2023). Additionally, our PIOPs are modular, enabling the use of alternative PCSs to optimize other aspects, such as further reducing proof sizes.



## 2024/1880

* Title: Cryptography Experiments In Lean 4: SHA-3 Implementation
* Authors: Gérald Doussot
* [Permalink](https://eprint.iacr.org/2024/1880)
* [Download](https://eprint.iacr.org/2024/1880.pdf)

### Abstract

In this paper we explain how we implemented the Secure Hash Algorithm-3 (SHA-3) family of functions in Lean 4, a functional programming language and theorem prover. We describe how we used several Lean facilities including type classes, dependent types,
macros, and formal verification, and then refined the design to provide a simple one-shot and streaming API for hashing, and Extendable-output functions (XOFs), to reduce potential for misuse by users, and formally prove properties about the
implementation.



## 2024/1881

* Title: THOR: Secure Transformer Inference with Homomorphic Encryption
* Authors: Jungho Moon, Dongwoo Yoo, Xiaoqian Jiang, Miran Kim
* [Permalink](https://eprint.iacr.org/2024/1881)
* [Download](https://eprint.iacr.org/2024/1881.pdf)

### Abstract

As language models are increasingly deployed in cloud environments, privacy concerns have become a significant issue. To address this, we design THOR, a secure inference framework for transformer models on encrypted data. Specifically, we first propose
new fast matrix multiplication algorithms based on diagonal-major order encoding and extend them to parallel matrix computation through the compact ciphertext packing technique. Second, we design efficient protocols for secure computations of four non-
linear functions such as softmax, LayerNorm, GELU, and Tanh, by integrating advanced underlying approximation methods with tailored optimizations. Our matrix multiplication algorithms reduce the number of key-switching operations in the linear layers of
the attention block in the BERT-base model by up to 14.5x, compared to the state-of-the-art HE-based secure inference protocol (Park et al., Preprint). Combined with cryptographic optimizations, our experimental results demonstrate that THOR provides
secure inference for the BERT-base model with a latency of 10.43 minutes on a single GPU, while maintaining comparable inference accuracy on the MRPC dataset.



## 2024/1882

* Title: Single Trace Side-Channel Attack on the MPC-in-the-Head Framework
* Authors: Julie Godard, Nicolas Aragon, Philippe Gaborit, Antoine Loiseau, Julien Maillard
* [Permalink](https://eprint.iacr.org/2024/1882)
* [Download](https://eprint.iacr.org/2024/1882.pdf)

### Abstract

In this paper, we present the first single trace side-channel attack that targets the MPC-in-the-Head (MPCitH) framework based on threshold secret sharing, also known as Threshold Computation in the Head (TCitH) in its original version. This MPCitH
framework can be found in 5 of the 14 digital signatures schemes in the recent second round of the National Institute of Standards and Technology (NIST) call for digital signatures. In this work, we start by highlighting a side-channel vulnerability of
the TCitH framework and show an exploitation of it on the SDitH algorithm, which is part of this NIST call. Specifically, we exploit the leakage of a multiplication function in the Galois field to make predictions about intermediate values, and we use
the structure of the algorithm to combine information efficiently. This allows us to build an attack that is both the first Soft Analytical Side-Channel Attack (SASCA) targeting the MPCitH framework, as well as the first attack on SDitH. More
specifically, we build a SASCA based on Belief Propagation (BP) on the evaluation of polynomials in the signature using the threshold variant structure to reconstruct the secret key. We perform simulated attacks under the Hamming Weight (HW) leakage
model, enabling us to evaluate the resistance of the scheme against SASCA. We then perform our attacks in a real case scenario, more specifically on the STM32F407, and recover the secret key for all the security levels. We end this paper by discussing
the various shuffling countermeasures we could use to mitigate our attacks.



## 2024/1883

* Title: A Fault Analysis on SNOVA
* Authors: Gustavo Banegas, Ricardo Villanueva-Polanco
* [Permalink](https://eprint.iacr.org/2024/1883)
* [Download](https://eprint.iacr.org/2024/1883.pdf)

### Abstract

SNOVA is a post-quantum cryptographic signature scheme known for its efficiency and compact key sizes, making it a second-round candidate in the NIST post-quantum cryptography standardization process. This paper presents a comprehensive fault analysis of
SNOVA, focusing on both permanent and transient faults during signature generation. We introduce several fault injection strategies that exploit SNOVA's structure to recover partial or complete secret keys with limited faulty signatures. Our analysis
reveals that as few as $22$ to $68$ faulty signatures, depending on the security level, can suffice for key recovery. We propose a novel fault-assisted reconciliation attack, demonstrating its effectiveness in extracting the secret key space via solving
a quadratic polynomial system. Simulations show transient faults in key signature generation steps can significantly compromise SNOVA’s security. To address these vulnerabilities, we propose a lightweight countermeasure to reduce the success of fault
attacks without adding significant overhead. Our results highlight the importance of fault-resistant mechanisms in post-quantum cryptographic schemes like SNOVA to ensure robustness.



## 2024/1884

* Title: Age-aware Fairness in Blockchain Transaction Ordering for Reducing Tail Latency
* Authors: Yaakov Sokolik, Mohammad Nassar, Ori Rottenstriech
* [Permalink](https://eprint.iacr.org/2024/1884)
* [Download](https://eprint.iacr.org/2024/1884.pdf)

### Abstract

In blockchain networks, transaction latency is crucial for determining the quality of service (QoS). The latency of a transaction is measured as the time between its issuance and its inclusion in a block in the chain. A block proposer often prioritizes
transactions with higher fees or transactions from accounts it is associated with, to minimize their latencies. To maintain fairness among transactions, a block proposer is expected to select the included transactions randomly. The random selection might
cause some transactions to experience high latency following the variance in the time a transaction waits until it is selected. We suggest an alternative, age-aware approach towards fairness so that transaction priority is increased upon observing a
large waiting time. We explain that a challenge with this approach is that the age of a transaction is not absolute due to transaction propagation. Moreover, a node might present its transactions as older to obtain priority. We describe a new technique
to enforce a fair block selection while prioritizing transactions that observed high latency. The technique is based on various declaration schemes in which a node declares its pending transactions, providing the ability to validate transaction age. By
evaluating the solutions on Ethereum data and synthetic data of various scenarios, we demonstrate the advantages of the approach under realistic conditions and understand its potential impact to maintain fairness and reduce tail latency.



## 2024/1885

* Title: Improved PIR Schemes using Matching Vectors and Derivatives
* Authors: Fatemeh Ghasemi, Swastik Kopparty, Madhu Sudan
* [Permalink](https://eprint.iacr.org/2024/1885)
* [Download](https://eprint.iacr.org/2024/1885.pdf)

### Abstract

In this paper, we construct new t-server Private Information Retrieval (PIR) schemes with communication complexity subpolynomial in the previously best known, for all but finitely many t. Our results are
based on combining derivatives (in the spirit of Woodruff-Yekhanin) with the Matching Vector based PIRs of Yekhanin and Efremenko. Previously such a combination was achieved in an ingenious way by Dvir and Gopi, using polynomials and derivatives over
certain exotic rings, en route to their fundamental result giving the first 2-server PIR with subpolynomial communication.

Our improved PIRs are based on two ingredients:

• We develop a new and direct approach to combine derivatives with Matching Vector based PIRs.
This approach is much simpler than that of Dvir-Gopi: it works over the same field as the original PIRs, and only uses elementary properties of polynomials and derivatives.

• A key subproblem that arises in the above approach is a higher-order polynomial interpolation problem. We show how “sparse S-decoding polynomials”, a powerful tool from the original constructions of Matching Vector PIRs, can be used to solve this
higher-order polynomial interpolation problem using surprisingly few higer-order evaluations.

Using the known sparse S-decoding polynomials in combination with our
ideas leads to our improved PIRs. Notably, we get a 3-server PIR scheme with communication $2^{O^\sim( (\log n)^{1/3}) }$, improving upon the previously best known communication of $2^{O^\sim( \sqrt{\log n})}$ due to Efremenko.



## 2024/1886

* Title: Impossibility Results for Post-Compromise Security in Real-World Communication Systems
* Authors: Cas Cremers, Niklas Medinger, Aurora Naska
* [Permalink](https://eprint.iacr.org/2024/1886)
* [Download](https://eprint.iacr.org/2024/1886.pdf)

### Abstract

Modern secure communication systems, such as iMessage, WhatsApp, and Signal include intricate mechanisms that aim to achieve very strong security properties. These mechanisms typically involve continuously merging in new fresh secrets into the keying
material, which is used to encrypt messages during communications. In the literature, these mechanisms have been proven to achieve forms of Post Compromise Security (PCS): the ability to provide communication security even if the full state of a party
was compromised some time in the past. However, recent work has shown these proofs do not transfer to the end-user level, possibly because of usability concerns. This has raised the question of whether end-users can actually obtain PCS or not, and under
which conditions.

Here we show and formally prove that communication systems that need to be resilient against certain types of state loss (which can occur in practice) fundamentally cannot achieve full PCS for end-users. Whereas previous work showed that the Signal
messenger did not achieve this with its current session-management layer, we isolate the exact conditions that cause this failure, and why this cannot be simply solved in communication systems by implementing a different session-management layer or an
entirely different protocol. Moreover, we clarify the trade-off of the maximum number of sessions between two users (40 in Signal) in terms of failure-resilience versus security.

Our results have direct consequences for the design of future secure communication systems, and could motivate either the simplification of redundant mechanisms, or the improvement of session-management designs to provide better security trade-offs with
respect to state loss/failure tolerance.



## 2024/1887

* Title: Differential MITM attacks on SLIM and LBCIoT
* Authors: Peter Grochal, Martin Stanek
* [Permalink](https://eprint.iacr.org/2024/1887)
* [Download](https://eprint.iacr.org/2024/1887.pdf)

### Abstract

SLIM and LBCIoT are lightweight block ciphers proposed for IoT applications. We present differential meet-in-the-middle attacks on these ciphers and discuss several implementation variants and possible improvements of these attacks. Experimental
validation also shows some results that may be of independent interest in the cryptanalysis of other ciphers. Namely, the problems with low-probability differentials and the questionable accuracy of standard complexity estimates of using filters.



## 2024/1888

* Title: Chosen-Prefix Collisions on AES-like Hashing
* Authors: Shiyao Chen, Xiaoyang Dong, Jian Guo, Tianyu Zhang
* [Permalink](https://eprint.iacr.org/2024/1888)
* [Download](https://eprint.iacr.org/2024/1888.pdf)

### Abstract

Chosen-prefix collision (CPC) attack was first presented by Stevens, Lenstra and de Weger on MD5 at Eurocrypt 2007. A CPC attack finds a collision for any two chosen prefixes, which is a stronger variant of collision attack. CPCs are naturally harder to
construct but have larger practical impact than (identical-prefix) collisions, as seen from the series of previous works on MD5 by Stevens et al. and SHA-1 by Leurent and Peyrin. Despite its significance, the resistance of CPC attacks has not been
studied on AES-like hashing.
In this work, we explore CPC attacks on AES-like hashing following the framework practiced on MD5 and SHA-1. Instead of the message modification technique developed for MD-SHA family, we opt for related-key rebound attack to construct collisions for AES-
like hashing in view of its effectiveness. We also note that the CPC attack framework can be exploited to convert a specific class of one-block free-start collisions into two-block collisions, which sheds light on the importance of free-start collisions.
As a result, we present the first CPC attacks on reduced Whirlpool, Saturnin-hash and AES-MMO/MP in classic and quantum settings, and extend the collision attack on Saturnin-hash from 5 to 6 rounds in the classic setting. As an independent contribution,
we improve the memoryless algorithm of solving 3-round inbound phase by Hosoyamada and Sasaki at Eurocrpyt 2020, which leads to improved quantum attacks on Whirlpool. Notably, we find the first 6-round memoryless quantum collision attack on Whirlpool
better than generic CNS collision finding algorithm when exponential-size qRAM is not available but exponential-size classic memory is available.



## 2024/1889

* Title: IO-Optimized Design-Time Configurable Negacyclic Seven-Step NTT Architecture for FHE Applications
* Authors: Emre Koçer, Selim Kırbıyık, Tolun Tosun, Ersin Alaybeyoğlu, Erkay Savaş
* [Permalink](https://eprint.iacr.org/2024/1889)
* [Download](https://eprint.iacr.org/2024/1889.pdf)

### Abstract

FHE enables computations on encrypted data, making it essential for privacy-preserving applications. However, it involves computationally demanding tasks, such as polynomial multiplication, while NTT is the state-of-the-art solution to perform this task.
Most FHE schemes operate over the negacyclic ring of polynomials. We introduce a novel formulation of the hierarchical Four-Step NTT approach for the negacyclic ring, eliminating the need for pre- and post-processing steps found in the existing methods.
To accelerate NTT operations, the FPGAs offer flexible and powerful computing platforms. We propose an FPGA-based, parametric and fully pipelined architecture that implements the improved Seven-Step NTT algorithm (which builds upon the four-step). Our
design supports a wide range of parameters, including ring sizes up to $2^{16}$ and modulus sizes up to $64$-bit. We focus on achieving configurable throughput, as constrained by the bandwidth of HBM bandwidth, and aim to maximize throughput through an
IO parametric design on the Alveo U280 FPGA. The implementation results demonstrate a reduction in the area-time-product by $2.08\times$ and a speed-up of $10.32\times$ for a ring size of $2^{16}$ and a 32-bit width compared to the current state-of-the-
art designs.



## 2024/1890

* Title: Efficient Modular Multiplication Hardware for Number Theoretic Transform on FPGA
* Authors: Tolun Tosun, Selim Kırbıyık, Emre Koçer, Erkay Savaş, Ersin Alaybeyoğlu
* [Permalink](https://eprint.iacr.org/2024/1890)
* [Download](https://eprint.iacr.org/2024/1890.pdf)

### Abstract

In this paper, we present a comprehensive analysis of various modular multiplication methods for Number Theoretic Transform (NTT) on FPGA. NTT is a critical and time-intensive component of Fully Homomorphic Encryption (FHE) applications while modular
multiplication consumes a significant portion of the design resources in an NTT implementation. We study the existing modular reduction approaches from the literature, and implement particular methods on FPGA. Specifically Word-Level Montgomery (WLM))
for NTT friendly primes [1] and K2RED [2]. For improvements, we explore the trade-offs between the number of available primes in special forms and hardware cost of the reduction methods. We develop a DSP multiplication-optimized version of WLM, which we
call WLM-Mixed. We also introduce a subclass of Proth primes, referred to as Proth-l primes, characterized by a low and fixed signed Hamming Weight. This special class of primes allows us to design multiplication-free shift-add versions of K2RED and
naive Montgomery reduction [3], referred to as K2RED-Shift and Montgomery-Shift. We provide in-depth evaluations of these five reduction methods in an NTT architecture on FPGA. Our results indicate that WLM-Mixed is highly resource-efficient, utilizing
only 3 DSP multiplications for 64-bit coefficient moduli. On the other hand, K2RED-Shift and Montgomery-Shift offer DSP-free alternatives, which can be beneficial in specific scenarios



## 2024/1891

* Title: Shifting our knowledge of MQ-Sign security
* Authors: Lars Ran, Monika Trimoska
* [Permalink](https://eprint.iacr.org/2024/1891)
* [Download](https://eprint.iacr.org/2024/1891.pdf)

### Abstract

Unbalanced Oil and Vinegar (UOV) is one of the oldest, simplest, and most studied ad-hoc multivariate signature schemes. UOV signature schemes are attractive because they have very small signatures and fast verification. On the downside, they have large
public and secret keys. As a result, variations of the traditional UOV scheme are usually developed with the goal to reduce the key sizes. Seven variants of UOV were submitted to the additional call for digital signatures by NIST, prior to which, a
variant named MQ-Sign was submitted to the (South) Korean post-quantum cryptography competition (KpqC). MQ-Sign is currently competing in the second round of KpqC with two variants. One of the variants corresponds to the classic description of UOV with
certain implementation and parameter choices. In the other variant, called MQ-Sign-LR, a part of the central map is constructed from row shifts of a single matrix. This design makes for smaller secret keys, and in the case where the equivalent keys
optimization is used, it also leads to smaller public keys. However, we show in this work that the polynomial systems arising from an algebraic attack have a specific structure that can be exploited. Specifically, we are able to find preimages for $d$-
periodic targets under the public map with a probability of $63\%$ for all security levels. The complexity of finding these preimages, as well as the fraction of $d$-periodic target increases with $d$ and hence provides a trade-off. We show that for all
security levels one can choose $d=\frac{v}{2}$, for $v$ the number of vinegar variables, and reduce the security claim. Our experiments show practical running times for lower $d$ ranging from 0.06 seconds to 32 hours.



## 2024/1892

* Title: A Comprehensive Survey on Hardware-Software co-Protection against Invasive, Non-Invasive and Interactive Security Threats
* Authors: Md Habibur Rahman
* [Permalink](https://eprint.iacr.org/2024/1892)
* [Download](https://eprint.iacr.org/2024/1892.pdf)

### Abstract

In the face of escalating security threats in modern
computing systems, there is an urgent need for comprehensive
defense mechanisms that can effectively mitigate invasive, noninvasive and interactive security vulnerabilities in hardware
and software domains. Individually, hardware and software
weaknesses and probable remedies have been practiced but
protecting a combined system has not yet been discussed in
detail. This survey paper provides a comprehensive overview of
the emerging field of Hardware-Software co-Protection against
Invasive and Non-Invasive Security Threats. We systematically
review state-of-the-art research and developments in hardware
and software security techniques, focusing on their integration to
create synergistic defense mechanisms. The survey covers a wide
range of security threats, including physical attacks, side-channel
attacks, and malware exploits, and explores the diverse strategies
employed to counter them. Our survey meticulously examines the
landscape of security vulnerabilities, encompassing both physical
and software-based attack vectors, and explores the intricate
interplay between hardware and software defenses in mitigating
these threats. Furthermore, we discuss the challenges and opportunities associated with Hardware-Software co-Protection and
identify future research directions to advance the field. Through
this survey, we aim to provide researchers, practitioners, and
policymakers with valuable insights into the latest advancements
and best practices for defending against complex security threats
in modern computing environments.



## 2024/1893

* Title: High Speed High Assurance implementations of Multivariate Quadratic based Signatures
* Authors: Samyuktha M, Pallavi Borkar, Chester Rebeiro
* [Permalink](https://eprint.iacr.org/2024/1893)
* [Download](https://eprint.iacr.org/2024/1893.pdf)

### Abstract

In this poster, we present a Jasmin implementation of Mayo2, a multivariate quadratic(MQ) based signature scheme. Mayo overcomes the disadvantage of the Unbalanced oil and vinegar(UOV) scheme by whipping the UOV map to produce public keys of sizes
comparable to ML-DSA. Our Jasmin implementation of Mayo2 takes 930 μs for keygen, 3206 μs for sign, 480 μs for verify based on the average of 1,00,000 runs of the implementation on a 2.25GHz x86 64 processor with 256 GB RAM. To this end, we have a
multivariate quadratic based signature implementation that is amenable for verification of constant-time, correctness, proof of equivalence properties using Easycrypt. Subsequently, the results of this endeavor can be extended for other MQ based schemes
including UOV.



## 2024/1894

* Title: A non-comparison oblivious sort and its application to private k-NN
* Authors: Sofiane Azogagh, Marc-Olivier Killijian, Félix Larose-Gervais
* [Permalink](https://eprint.iacr.org/2024/1894)
* [Download](https://eprint.iacr.org/2024/1894.pdf)

### Abstract

This paper introduces a novel adaptation of counting sort that enables sorting of encrypted data using Fully Homomorphic Encryption (FHE). Our approach represents the first known sorting algorithm for encrypted data that does not rely on comparisons. The
implementation leverages some basic operations on TFHE's Look-Up-Tables (LUT). We have integrated these operations into RevoLUT, a comprehensive open-source library built upon tfhe-rs, which can be of independent interest for oblivious algorithms. We
demonstrate the effectiveness of our Blind Counting Sort algorithm by developing a top-$k$ selection algorithm and applying it to privacy-preserving $k$-Nearest Neighbors classification. This proves to be approximately 5x faster than current state-of-the-
art methods.



## 2024/1895

* Title: A Tool for Fast and Secure LWE Parameter Selection: the FHE case
* Authors: Beatrice Biasioli, Elena Kirshanova, Chiara Marcolla, Sergi Rovira
* [Permalink](https://eprint.iacr.org/2024/1895)
* [Download](https://eprint.iacr.org/2024/1895.pdf)

### Abstract

The field of fully homomorphic encryption (FHE) has seen many theoretical and computational advances in recent years, bringing the technology closer to practicality than ever before. For this reason, practitioners in related fields, such as machine
learning, are increasingly interested in using FHE to provide privacy to their applications.

Despite this progress, selecting secure and efficient parameters for FHE remains a complex and challenging task due to the intricate interdependencies between parameters. In this work, we address this issue by providing a rigorous theoretical foundation
for parameter selection for any LWE-based schemes, with a specific focus on FHE. Our approach starts with an in-depth analysis of lattice attacks on the LWE problem, deriving precise expressions for the most effective ones. Building on this, we introduce
closed-form formulas that establish the relationships among the LWE parameters.

In addition, we introduce a numerical method to enable the accurate selection of any configurable parameter to meet a desired security level.
Finally, we use our results to build a practical and efficient tool for researchers and practitioners deploying FHE in real-world applications, ensuring that our approach is both rigorous and accessible.



## 2024/1896

* Title: Shardora: Towards Scaling Blockchain Sharding via Unleashing Parallelism
* Authors: Yu Tao, Lu Zhou, Lei Xie, Dongming Zhang, Xinyu Lei, Fei Xu, Zhe Liu * [Permalink](https://eprint.iacr.org/2024/1896)
* [Download](https://eprint.iacr.org/2024/1896.pdf)

### Abstract


[continued in next message]

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