## In this issue

1. [2024/761] Lattice-based Broadcast Authenticated Searchable ...
2. [2024/763] Incorporating SIS Problem into Luby-Rackoff Cipher
3. [2024/775] Spec-o-Scope: Cache Probing at Cache Speed
4. [2024/1575] Efficiently-Thresholdizable Batched Identity Based ...
5. [2024/1718] Drifting Towards Better Error Probabilities in ...
6. [2024/1719] Compact Pseudorandom Functional Encryption from ...
7. [2024/1720] Pseudorandom Multi-Input Functional Encryption and ...
8. [2024/1721] An Efficient Noncommutative NTRU from Semidirect ...
9. [2024/1722] Revisiting Fermat's Factorization Method
10. [2024/1723] Proving the Security of the Extended Summation- ...
11. [2024/1724] Straight-Line Knowledge Extraction for Multi-Round ...
12. [2024/1725] PISA: Privacy-Preserving Smart Parking
13. [2024/1726] Certified Randomness implies Secure Classical ...
14. [2024/1727] (Quantum) Indifferentiability and Pre-Computation
15. [2024/1728] On Key Substitution Attacks against Aggregate ...
16. [2024/1729] cuTraNTT: A Novel Transposed Number Theoretic ...
17. [2024/1730] Secure and Efficient Outsourced Matrix ...
18. [2024/1731] Arc: Accumulation for Reed--Solomon Codes
19. [2024/1732] Radical 2-isogenies and cryptographic hash ...
20. [2024/1733] One Time Pad and the Short Key Dream
21. [2024/1734] Optimizing Message Range and Ciphertext Storage in ...
22. [2024/1735] The Mysteries of LRA: Roots and Progresses in Side- ...
23. [2024/1736] A graph-theoretic approach to analyzing decoding ...
24. [2024/1737] Embedded Curves and Embedded Families for SNARK- ...
25. [2024/1738] More Efficient Isogeny Proofs of Knowledge via ...
26. [2024/1739] Provably Robust Watermarks for Open-Source Language ...
27. [2024/1740] OpenNTT: An Automated Toolchain for Compiling High- ...
28. [2024/1741] The Learning Stabilizers with Noise problem
29. [2024/1742] Pseudorandom Obfuscation and Applications
30. [2024/1743] The Window Heuristic: Automating Differential Trail ...
31. [2024/1744] PEARL-SCALLOP: Parameter Extension Applicable in ...
32. [2024/1745] Pseudorandomness in the (Inverseless) Haar Random ...

## 2024/761

* Title: Lattice-based Broadcast Authenticated Searchable Encryption for Cloud Storage
* Authors: Yibo Cao, Shiyuan Xu, Xiu-Bo Chen, Gang Xu, Siu-Ming Yiu, Zongpeng Li
* [Permalink](https://eprint.iacr.org/2024/761)
* [Download](https://eprint.iacr.org/2024/761.pdf)

### Abstract

For security issue, data in cloud is encrypted. Searching encrypted data (without decryption) is a practical and important problem. Public key authenticated encryption with keyword search (PAEKS) enables the retrieval of encrypted data, while resisting
the insider keyword guessing attacks (IKGAs). Most PAEKS schemes only work with single-receiver model, exhibiting very limited applicability. To address this concern, there have been researches on broadcast authenticated encryption with keyword search (
BAEKS) to achieve multi-receiver ciphertext search. But to our best knowledge, existing BAEKS schemes are not quantum resistant. In this paper, we propose lattice-based BAEKS, the first post-quantum broadcast authenticated encryption with keyword search
in multi-receiver model. In particular, we leverage several lattice sampling algorithms and rejection sampling technique to construct our BAEKS scheme. We also incorporate the minimal cover set technique and lattice basis extension algorithm to construct
an enhanced version, namely FS-BAEKS, which addresses the secret key leakage problem. We give a rigorous security analysis of our schemes. For the efficiency of BAEKS and Test algorithms in our BAEKS scheme, the computational overheads are at least 2x
and 89x faster than the state-of-the-art schemes respectively, which is practical for cloud storage systems.



## 2024/763

* Title: Incorporating SIS Problem into Luby-Rackoff Cipher
* Authors: Yu Morishima, Masahiro Kaminaga
* [Permalink](https://eprint.iacr.org/2024/763)
* [Download](https://eprint.iacr.org/2024/763.pdf)

### Abstract

With the rise of quantum computing, the security of traditional cryptographic systems, especially those vulnerable to quantum attacks, is under threat. While public key cryptography has been widely studied in post-quantum security, symmetric-key
cryptography has received less attention. This paper explores using the Ajtai-Micciancio hash function, based on the Short Integer Solution (SIS) problem, as a pseudorandom function in the Luby-Rackoff cipher. Since lattice-based problems like SIS are
believed to resist quantum algorithms, this approach provides the potential for a quantum-resistant block cipher. We also propose a novel statistical method based on the Generalized Extreme Value distribution to evaluate the number of secure rounds and
resistance to differential cryptanalysis.



## 2024/775

* Title: Spec-o-Scope: Cache Probing at Cache Speed
* Authors: Gal Horowitz, Eyal Ronen, Yuval Yarom
* [Permalink](https://eprint.iacr.org/2024/775)
* [Download](https://eprint.iacr.org/2024/775.pdf)

### Abstract

Over the last two decades, microarchitectural side channels have been the focus of a large body of research on the development of new attack techniques, exploiting them to attack various classes of targets and designing mitigations. One line of work
focuses on increasing the speed of the attacks, achieving higher levels of temporal resolution that can allow attackers to learn finer-grained information. The most recent addition to this line of work is Prime+Scope [CCS '21], which only requires a
single access to the L1 cache to confirm the absence of victim activity in a cache set. While significantly faster than prior attacks, Prime+Scope is still an order of magnitude slower than cache access. In this work, we set out to close this gap.

We draw on techniques from research into microarchitectural weird gates, software constructs that exploit transient execution to perform arbitrary computation on cache state. We design the Spec-o-Scope gate, a new weird gate that performs 10 cache probes
in quick succession, and forms the basis for our eponymous attack. Our Spec-o-Scope attack achieves an order of magnitude improvement in temporal resolution compared to the previous state-of-the-art of Prime+Scope, reducing the measurement time from ~70
cycles to only 5 --- only one cycle more than an L1 cache access. We experimentally verify that our attack can detect timing differences in a 5 cycle resolution. Finally, using our Spec-o-Scope attack, we show the first microarchitectural side-channel
attack on an unmodified AES S-box-based implementation, which uses generic CPU features and does not require manipulation of the operating system's scheduler.



## 2024/1575

* Title: Efficiently-Thresholdizable Batched Identity Based Encryption, with Applications
* Authors: Amit Agarwal, Rex Fernando, Benny Pinkas
* [Permalink](https://eprint.iacr.org/2024/1575)
* [Download](https://eprint.iacr.org/2024/1575.pdf)

### Abstract

We propose a new cryptographic primitive called "batched identity-based encryption" (Batched IBE) and its thresholdized version. The new primitive allows encrypting messages with specific identities and batch labels, where the latter can represent, for
example, a block number on a blockchain. Given an arbitrary subset of identities for a particular batch, our primitive enables efficient issuance of a single decryption key that can be used to decrypt all ciphertexts having identities that are included
in the subset while preserving the privacy of all ciphertexts having identities that are excluded from the subset. At the heart of our construction is a new technique that enables public aggregation (i.e. without knowledge of any secrets) of any subset
of identities, into a succinct digest. This digest is used to derive, via a master secret key, a single succinct decryption key for all the identities that were digested in this batch. In a threshold system, where the master key is distributed as secret
shares among multiple authorities, our method significantly reduces the communication (and in some cases, computation) overhead for the authorities. It achieves this by making their costs for key issuance independent of the batch size.

We present a concrete instantiation of a Batched IBE scheme based on the KZG polynomial commitment scheme by Kate et al. (Asiacrypt'10) and a modified form of the BLS signature scheme by Boneh et al. (Asiacrypt'01). The construction is proven secure in
the generic group model (GGM).

In a blockchain setting, the new construction can be used for achieving mempool privacy by encrypting transactions to a block, opening only the transactions included in a given block and hiding the transactions that are not included in it. With the
thresholdized version, multiple authorities (validators) can collaboratively manage the decryption process. Other possible applications include scalable support via blockchain for fairness of dishonest majority MPC, and conditional batched threshold
decryption that can be used for implementing secure Dutch auctions and privacy preserving options trading.



## 2024/1718

* Title: Drifting Towards Better Error Probabilities in Fully Homomorphic Encryption Schemes
* Authors: Olivier Bernard, Marc Joye, Nigel P. Smart, Michael Walter
* [Permalink](https://eprint.iacr.org/2024/1718)
* [Download](https://eprint.iacr.org/2024/1718.pdf)

### Abstract

There are two security notions for FHE schemes the traditional notion of IND-CPA, and a more stringent notion of IND-CPA$^D$. The notions are equivalent if the FHE schemes are perfectly correct, however for schemes with negligible failure probability
the FHE parameters needed to obtain IND-CPA$^D$ security can be much larger than those needed to obtain IND-CPA security. This paper uses the notion of ciphertext drift in order to understand the practical difference between IND-CPA and IND-CPA$^D$
security in schemes such as FHEW, TFHE and FINAL. This notion allows us to define a modulus switching operation (the main culprit for the difference in parameters) such that one does not require adapting IND-CPA cryptographic parameters to meet the IND-
CPA$^D$ security level. Further, the extra cost incurred by the new techniques has no noticeable performance impact in practical applications. The paper also formally defines a stronger version for IND-CPA$^D$ security called sIND-CPA$^D$, which is
proved to be strictly separated from the IND-CPA$^D$ notion. Criterion for turning an IND-CPA$^D$ secure public-key encryption into an sIND-CPA$^D$ one is also provided.



## 2024/1719

* Title: Compact Pseudorandom Functional Encryption from Evasive LWE
* Authors: Shweta Agrawal, Simran Kumari, Shota Yamada
* [Permalink](https://eprint.iacr.org/2024/1719)
* [Download](https://eprint.iacr.org/2024/1719.pdf)

### Abstract

We provide the first construction of compact Functional Encryption (FE) for pseudorandom functionalities from the evasive LWE and LWE assumptions. Intuitively, a pseudorandom functionality means that the output of the circuit is indistinguishable from
uniform for every input seen by the adversary. This yields the first compact FE for a nontrivial class of functions which does not rely on pairings.

We demonstrate the power of our new tool by using it to achieve optimal parameters for both key-policy and ciphertext-policy Attribute Based Encryption (ABE) schemes for circuits of unbounded depth, from just the LWE and evasive LWE assumptions. This
improves prior work along the twin axes of assumptions and performance. In more detail, this allows to: (i) replace the assumption of circular evasive LWE used in the work of Hseih, Lin and Luo (FOCS 2023) by plain evasive LWE, (ii) remove the need for
the circular tensor LWE assumption in the work of Agrawal, Kumari and Yamada (CRYPTO, 2024), (iii) improve parameters obtained by both aforementioned works to achieve asymptotic optimality.

Previously, optimal parameters for ABE schemes were only achieved using compact FE for P (Jain, Lin and Luo, Eurocrypt 2023) – we show that compact FE for a much weaker class (albeit with incomparable security) suffices. Thus we obtain the first
optimal ABE schemes for unbounded depth circuits which can be conjectured post-quantum secure. Along the way, we define and construct a new primitive which we term laconic pseudorandom obfuscation from the same assumptions – this may be of independent
interest.



## 2024/1720

* Title: Pseudorandom Multi-Input Functional Encryption and Applications
* Authors: Shweta Agrawal, Simran Kumari, Shota Yamada
* [Permalink](https://eprint.iacr.org/2024/1720)
* [Download](https://eprint.iacr.org/2024/1720.pdf)

### Abstract

We construct the first multi-input functional encryption (MIFE) and indistinguishability obfuscation (iO) schemes for pseudorandom functionalities, where the output of the functionality is pseudorandom for every input seen by the adversary. Our MIFE
scheme relies on LWE and evasive LWE (Wee, Eurocrypt 2022 and Tsabary, Crypto 2022) for constant arity functions, and a strengthening of evasive LWE for polynomial arity. Thus, we obtain the first MIFE and iO schemes for a nontrivial functionality from
conjectured post-quantum assumptions.

Along the way, we identify subtle issues in the proof of witness encryption from evasive LWE by prior work and believe that a similar strengthening of evasive LWE should also be required for their proof, for the same reasons as ours. We demonstrate the
power of our new tools via the following applications:

1. Multi Input Predicate Encryption for Constant Arity. Assuming evasive LWE and LWE, we construct a multi-input predicate encryption scheme (MIPE) for P, supporting constant arity. The only prior work to support MIPE for P with constant arity by Agrawal
et al. (Crypto, 2023) relies on a strengthening of Tensor LWE in addition to LWE and evasive LWE.

2. Multi Input Predicate Encryption for Polynomial Arity. Assuming a stronger variant of evasive LWE and LWE, we construct MIPE for P for polynomial arity. MIPE for polynomial arity supporting P was not known before, to the best of our knowledge.

3. Two Party ID Based Key Exchange. Assuming a stronger variant of evasive LWE and LWE, along with Decision Bilinear Diffie-Hellman, we provide the first two-party ID based Non-Interactive Key Exchange (ID-NIKE) scheme in the standard model. This leads
to the first ID-NIKE in the standard model without using multilinear maps or indistinguishability obfuscation.

4. Instantiating the Random Oracle. We use our pseudorandom iO to instantiate the random oracle in several applications that previously used iO (Hohenberger, Sahai and Waters, Eurocrypt 2014) such as full-domain hash signature based on trapdoor
permutations and more.

Our tools of MIFE and iO for pseudorandom functionalities appear quite powerful and yield extremely simple constructions when used in applications. We believe they provide a new pathway for basing “extreme” cryptography, which has so far required
full fledged iO, on the presumably weaker evasive LWE in the post quantum regime.



## 2024/1721

* Title: An Efficient Noncommutative NTRU from Semidirect Product
* Authors: Vikas Kumar, Ali Raya, Aditi Kar Gangopadhyay, Sugata Gangopadhyay, Md Tarique Hussain
* [Permalink](https://eprint.iacr.org/2024/1721)
* [Download](https://eprint.iacr.org/2024/1721.pdf)

### Abstract

NTRU is one of the most extensively studied lattice-based schemes. Its flexible design has inspired different proposals constructed over different rings, with some aiming to enhance security and others focusing on improving performance. The literature
has introduced a line of noncommutative NTRU-like designs that claim to offer greater resistance to existing attacks. However, most of these proposals are either theoretical or fall short in terms of time and memory requirements when compared to standard
NTRU. To our knowledge, DiTRU (Africacrypt 2024) is the first noncommutative analog of NTRU provided as a complete package. Although DiTRU is practical, it operates at two times slower than NTRU with no decryption failure. Additionally, key generation,
encryption, and decryption are 1.2, 1.7, and 1.7 times slower, respectively, with negligible decryption failure. In this work, we introduce a noncommutative version of NTRU that offers comparable performance and key sizes to NTRU while improving upon
DiTRU. Our cryptosystem is based on the GR-NTRU framework, utilizing the group ring of a semidirect product of cyclic groups over the ring of Eisenstein integers. This design allows for an efficient construction with key generation speeds approximately
two (three) times faster than NTRU (DiTRU). Further, the proposed scheme provides roughly a speed-up by a factor of 1.2 (2) while encrypting/decrypting messages of the same length over NTRU (DiTRU). We provide a reference implementation in C for the
proposed cryptosystem to prove our claims.



## 2024/1722

* Title: Revisiting Fermat's Factorization Method
* Authors: Gajraj Kuldeep, Rune Hylsberg Jacobsen
* [Permalink](https://eprint.iacr.org/2024/1722)
* [Download](https://eprint.iacr.org/2024/1722.pdf)

### Abstract

This paper addresses the problem of factoring composite numbers by introducing a novel approach to represent their prime divisors. We develop a method to efficiently identify smaller divisors based on the difference between the primes involved in forming
the composite number. Building on these insights, we propose an algorithm that significantly reduces the computational complexity of factoring, requiring half as many iterations as traditional quadratic residue-based methods. The presented algorithm
offers a more efficient solution for factoring composite numbers, with potential applications in fields such as cryptography and computational number theory.



## 2024/1723

* Title: Proving the Security of the Extended Summation-Truncation Hybrid
* Authors: Avijit Dutta, Eik List
* [Permalink](https://eprint.iacr.org/2024/1723)
* [Download](https://eprint.iacr.org/2024/1723.pdf)

### Abstract

Since designing a dedicated secure symmetric PRF is difficult, various works studied optimally secure PRFs from the sum of independent permutations (SoP).
At CRYPTO'20, Gunsing and Mennink proposed the Summation-Truncation Hybrid (STH).
While based on SoP, STH releases additional $a \leq n$ bits of the permutation calls and sums $n-a$ bits of them.
Thus, it produces $n+a$ bits at $O(n-a/2)$-bit PRF security.
Both SoP or STH can be used directly in encryption schemes or MACs in place of permutation calls for higher security.
However, simply replacing every call as in GCM-SIV$r$ would demand more calls.

For encryption schemes, Iwata's XORP scheme is long known to provide a better trade-off between efficiency and security. It extends SoP to variable-length-outputs by using $r+1$ calls to a block cipher where the output of one call is added to each of the
other $r$ outputs.
A similar extension can be conducted for STH that we call XTH, the XORP-Truncation Hybrid.
Such an extension was already suggested in the final discussion by Gunsing and Mennink, but left as an open problem. This work fills the gap by formalizing and proving the security of XTH.
For a rate of $r/(r+1)$ as in XORP, we show $O(n-a/2-1.5\log(r))$-bit security for XTH.



## 2024/1724

* Title: Straight-Line Knowledge Extraction for Multi-Round Protocols
* Authors: Lior Rotem, Stefano Tessaro
* [Permalink](https://eprint.iacr.org/2024/1724)
* [Download](https://eprint.iacr.org/2024/1724.pdf)

### Abstract

The Fiat-Shamir (FS) transform is the standard approach to compiling interactive proofs into non-interactive ones. However, the fact that knowledge extraction typically requires rewinding limits its applicability without having to rely on further
heuristic conjectures. A better alternative is a transform that guarantees straight-line knowledge extraction. Two such transforms were given by Pass (CRYPTO '03) and Fischlin (CRYPTO '05), respectively, with the latter giving the most practical
parameters. Pass's approach, which is based on cut-and-choose, was also adapted by Unruh (EUROCRYPT '12, '14, '15) to the quantum setting, where rewinding poses a different set of challenges. All of these transforms are tailored at the case of three-
round Sigma protocols, and do not apply to a number of popular paradigms for building succinct proofs (e.g., those based on folding or sumcheck) which rely on multi-round protocols.

This work initiates the study of transforms with straight-line knowledge extraction for multi-round protocols. We give two transforms, which can be thought of as multi-round analogues of those by Fischlin and Pass. Our first transform leads to more
efficient proofs, but its usage applies to a smaller class of protocols than the latter one. Our second transform also admits a proof of security in the Quantum Random Oracle Model (QROM), making it the first transform for multi-round protocols which
does not incur the super-polynomial security loss affecting the existing QROM analysis of the FS transform (Don et al., CRYPTO '20).



## 2024/1725

* Title: PISA: Privacy-Preserving Smart Parking
* Authors: Sayon Duttagupta, Dave Singelée
* [Permalink](https://eprint.iacr.org/2024/1725)
* [Download](https://eprint.iacr.org/2024/1725.pdf)

### Abstract

In recent years, urban areas have experienced a rapid increase in vehicle numbers, while the availability of parking spaces has remained largely static, leading to a significant shortage of parking spots. This shortage creates considerable inconvenience
for drivers and contributes to traffic congestion. A viable solution is the temporary use of private parking spaces by homeowners during their absence, providing a means to alleviate the parking problem and generate additional income for the owners.
However, current systems for sharing parking spaces often neglect security and privacy concerns, exposing users to potential risks.
This paper presents PISA, a novel Privacy-Preserving Smart Parking scheme designed to address these issues through a cryptographically secure protocol. PISA enables the anonymous sharing of parking spots and allows vehicle owners to park without
revealing any personal identifiers. Our primary contributions include the development of a comprehensive bi-directional anonymity framework that ensures neither party can identify the other, and the use of formal verification methods to substantiate the
soundness and reliability of our security measures. Unlike existing solutions, which often lack a security focus, fail to provide formal validation, or are computationally intensive, PISA is designed to be both secure and efficient.



## 2024/1726

* Title: Certified Randomness implies Secure Classical Position-Verification
* Authors: Omar Amer, Kaushik Chakraborty, David Cui, Fatih Kaleoglu, Charles Lim, Minzhao Liu, Marco Pistoia
* [Permalink](https://eprint.iacr.org/2024/1726)
* [Download](https://eprint.iacr.org/2024/1726.pdf)

### Abstract

Liu et al. (ITCS22) initiated the study of designing a secure position verification protocol based on a specific proof of quantumness protocol and classical communication. In this paper, we study this interesting topic further and answer some of the open
questions that are left in that paper. We provide a new generic compiler that can convert any single round proof of quantumness-based certified randomness protocol to a secure classical communication-based position verification scheme. Later, we extend
our compiler to different kinds of multi-round proof of quantumness-based certified randomness protocols. Moreover, we instantiate our compiler with a random circuit sampling (RCS)-based certified randomness protocol proposed by Aaronson and Hung (STOC
23). RCS-based techniques are within reach of today's NISQ devices; therefore, our design overcomes the limitation of the Liu et al. protocol that would require a fault-tolerant quantum computer to realize. Moreover, this is one of the first
cryptographic applications of RCS-based techniques other than certified randomness.



## 2024/1727

* Title: (Quantum) Indifferentiability and Pre-Computation
* Authors: Joseph Carolan, Alexander Poremba, Mark Zhandry
* [Permalink](https://eprint.iacr.org/2024/1727)
* [Download](https://eprint.iacr.org/2024/1727.pdf)

### Abstract

Indifferentiability is a popular cryptographic paradigm for analyzing the security of ideal objects---both in a classical as well as in a quantum world. It is typically stated in the form of a composable and simulation-based definition, and captures what
it means for a construction (e.g., a cryptographic hash function) to be ``as good as'' an ideal object (e.g., a random oracle). Despite its strength, indifferentiability is not known to offer security against pre-processin} attacks in which the adversary
gains access to (classical or quantum) advice that is relevant to the particular construction. In this work, we show that indifferentiability is (generically) insufficient for capturing pre-computation. To accommodate this shortcoming, we propose a
strengthening of indifferentiability which is not only composable but also takes arbitrary pre-computation into account. As an application, we show that the one-round sponge is indifferentiable (with pre-computation) from a random oracle. This yields the
first (and tight) classical/quantum space-time trade-off for one-round sponge inversion.



## 2024/1728

* Title: On Key Substitution Attacks against Aggregate Signatures and Multi-Signatures
* Authors: Yuuki Fujita, Yusuke Sakai, Kyosuke Yamashita, Goichiro Hanaoka
* [Permalink](https://eprint.iacr.org/2024/1728)
* [Download](https://eprint.iacr.org/2024/1728.pdf)

### Abstract

When we use signature schemes in practice, we sometimes should consider security beyond unforgeability.
This paper considers security against key substitution attacks of multi-signer signatures (i.e., aggregate signatures and multi-signatures).
Intuitively, this security property ensures that a malicious party cannot claim the ownership of a signature that is created by an honest signer.
We investigate security against key substitution attacks of a wide range of aggregate signature schemes and multi-signature schemes: the Boneh-Gentry-Lynn-Shacham aggregate signature scheme, the sequential aggregate signature scheme by Lysyanskaya et al.,
the multi-signature scheme by Bellare and Neven, MuSig2, and the ordered multi-signature scheme by Boldyreva et al.
Furthermore, if the scheme does not provide security against key substitution attacks, then we modify the scheme to become secure against the attacks.



## 2024/1729

* Title: cuTraNTT: A Novel Transposed Number Theoretic Transform Targeting Low Latency Homomorphic Encryption for IoT Applications
* Authors: Supriya Adhikary, Wai Kong Lee, Angshuman Karmakar, Yongwoo Lee, Seong Oun Hwang, Ramachandra Achar
* [Permalink](https://eprint.iacr.org/2024/1729)
* [Download](https://eprint.iacr.org/2024/1729.pdf)

### Abstract

Large polynomial multiplication is one of the computational bottlenecks in fully homomorphic encryption implementations. Usually, these multiplications are implemented using the number-theoretic transformation to speed up the computation. State-of-the-
art GPU-based implementation of fully homomorphic encryption computes the number theoretic transformation in two different kernels, due to the necessary synchronization between GPU blocks to ensure correctness in computation. This can be a serious
limitation in embedded systems that only have constrained computational resources to support the time-consuming homomorphic encryption. In this paper, we proposed a series of techniques to improve the performance of number theoretic transform targeting
homomorphic encryption on a GPU device. Firstly, we proposed to arrange the polynomials in a transposed manner and skip the last two levels of radix-4 number theoretic transformation, allowing us to completely
avoid the block synchronization in NTT implementation. This technique improved the performance of homomorphic encryption by 1.37× and 1.34× on RTX 4060 and Jetson Orin Nano respectively, compared to the conventional approach that uses full NTT without
skipping any levels. However, such an approach also introduces extra overhead in the subsequent point-wise multiplication, which slows down the homomorphic multiplication. To reduce this negative impact, a fast 16 × 16 point-wise
multiplication implementation was proposed, which relies on the heavily optimized Toom-Cook 4-way algorithm. Experimental results show that our proposed homomorphic multiplication can achieve similar latency compared to Jung et al. and Yang et al., which
are the best results to date. This shows that the proposed cuTraNTT is able to reduce the latency of homomorphic encryption without sacrificing the performance in homomorphic multiplication.



## 2024/1730

* Title: Secure and Efficient Outsourced Matrix Multiplication with Homomorphic Encryption
* Authors: Aikata Aikata, Sujoy Sinha Roy
* [Permalink](https://eprint.iacr.org/2024/1730)
* [Download](https://eprint.iacr.org/2024/1730.pdf)

### Abstract

Fully Homomorphic Encryption (FHE) is a promising privacy-enhancing technique that enables secure and private data processing on untrusted servers, such as privacy-preserving neural network (NN) evaluations. However, its practical application presents
significant challenges. Limitations in how data is stored within homomorphic ciphertexts and restrictions on the types of operations that can be performed create computational bottlenecks. As a result, a growing body of research focuses on optimizing
existing evaluation techniques for efficient execution in the homomorphic domain.

One key operation in this space is matrix multiplication, which forms the foundation of most neural networks. Several studies have even proposed new FHE schemes specifically to accelerate this operation. The optimization of matrix multiplication is also
the primary goal of our work. We leverage the Single Instruction Multiple Data (SIMD) capabilities of FHE to increase data packing and significantly reduce the KeySwitch operation count— an expensive low-level routine in homomorphic encryption. By
minimizing KeySwitching, we surpass current state-of-the-art solutions, requiring only a minimal multiplicative depth of two.

The best-known complexity for matrix multiplication at this depth is $\mathcal{O}(d)$ for matrices of size $d\times d$. Remarkably, even the leading techniques that require a multiplicative depth of three still incur a KeySwitch complexity of $\mathcal{
O}(d)$. In contrast, our method reduces this complexity to $\mathcal{O}(\log{d})$ while maintaining the same level of data packing. Our solution broadly applies to all FHE schemes supporting Single Instruction Multiple Data (SIMD) operations.
We further generalize the technique in two directions: allowing arbitrary packing availability and extending it to rectangular matrices. This versatile approach offers significant improvements in matrix multiplication performance and enables faster
evaluation of privacy-preserving neural network applications.



## 2024/1731

* Title: Arc: Accumulation for Reed--Solomon Codes
* Authors: Benedikt Bünz, Pratyush Mishra, Wilson Nguyen, William Wang
* [Permalink](https://eprint.iacr.org/2024/1731)
* [Download](https://eprint.iacr.org/2024/1731.pdf)

### Abstract


[continued in next message]

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