## In this issue

1. [2024/1661] zkFFT: Extending Halo2 with Vector Commitments & More
2. [2024/1746] Secure and Privacy-preserving CBDC Offline Payments ...
3. [2024/1747] POMS : Proxy Offloading for Multicloud Storage with ...
4. [2024/1748] A Simple Method to Test the Zeros of Riemann Zeta ...
5. [2024/1749] Revisiting the “improving the security of multi- ...
6. [2024/1750] Robust Double Auctions for Resource Allocation
7. [2024/1751] Offline-Online Indifferentiability of Cryptographic ...
8. [2024/1752] DEEP Commitments and Their Applications
9. [2024/1753] HTCNN: High-Throughput Batch CNN Inference with ...
10. [2024/1754] PQNTRU: Acceleration of NTRU-based Schemes via ...
11. [2024/1755] Exponential sums in linear cryptanalysis
12. [2024/1756] $\mathsf{Graphiti}$: Secure Graph Computation Made ...
13. [2024/1757] On the Sample Complexity of Linear Code Equivalence ...
14. [2024/1758] A comprehensive analysis of Regev's quantum algorithm
15. [2024/1759] A Forgery Attack on a Code-based Signature Scheme
16. [2024/1760] Somewhat Homomorphic Encryption from Linear ...
17. [2024/1761] Resilience-Optimal Lightweight High-threshold ...
18. [2024/1762] Homomorphic Matrix Operations under Bicyclic Encoding
19. [2024/1763] Quantum Black-Box Separations: Succinct Non- ...
20. [2024/1764] Fully Homomorphic Encryption with Efficient Public ...
21. [2024/1765] Compact and Tightly Secure (Anonymous) IBE from ...
22. [2024/1766] Critical Round in Multi-Round Proofs: Compositions ...
23. [2024/1767] ECPM Cryptanalysis Resource Estimation
24. [2024/1768] Push-Button Verification for BitVM Implementations
25. [2024/1769] A Closer Look at Falcon
26. [2024/1770] Improved Attacks for SNOVA by Exploiting Stability ...
27. [2024/1771] PRIME: Differentially Private Distributed Mean ...
28. [2024/1772] Byte-wise equal property of ARADI
29. [2024/1773] Universal Adaptor Signatures from Blackbox Multi- ...
30. [2024/1774] PANTHER: Private Approximate Nearest Neighbor ...
31. [2024/1775] zkMarket : Privacy-preserving Digital Data Trade ...
32. [2024/1776] An efficient collision attack on Castryck-Decru- ...
33. [2024/1777] Masking Gaussian Elimination at Arbitrary Order, ...
34. [2024/1778] Construction of quadratic APN functions with ...
35. [2024/1779] Ciphertext-Policy ABE from Inner-Product FE
36. [2024/1780] ABE for Circuits with ...
37. [2024/1781] New results in Share Conversion, with applications ...
38. [2024/1782] The Battery Insertion Attack: Is Periodic Pseudo- ...
39. [2024/1783] PriSrv: Privacy-Enhanced and Highly Usable Service ...
40. [2024/1784] Fine-Grained Non-Interactive Key-Exchange without ...
41. [2024/1785] A General Quantum Duality for Representations of ...
42. [2024/1786] Black-Box Timed Commitments from Time-Lock Puzzles
43. [2024/1787] An Efficient and Secure Boolean Function Evaluation ...
44. [2024/1788] Advanced Transparency System
45. [2024/1789] Stealth and Beyond: Attribute-Driven Accountability ...
46. [2024/1790] Revisiting subgroup membership testing on pairing- ...
47. [2024/1791] Discrete gaussian sampling for BKZ-reduced basis
48. [2024/1792] Towards Explainable Side-Channel Leakage: Unveiling ...
49. [2024/1793] On the Jordan-Gauss graphs and new multivariate ...
50. [2024/1794] How Much Public Randomness Do Modern Consensus ...
51. [2024/1795] How Fast Does the Inverse Walk Approximate a Random ...
52. [2024/1796] Isogeny interpolation and the computation of ...
53. [2024/1797] FLock: Robust and Privacy-Preserving Federated ...
54. [2024/1798] Quantum One-Time Protection of any Randomized Algorithm
55. [2024/1799] Consensus Under Adversary Majority Done Right

## 2024/1661

* Title: zkFFT: Extending Halo2 with Vector Commitments & More
* Authors: Aram Jivanyan, Gohar Hovhannisyan, Hayk Hovhannisyan, Nerses Asaturyan
* [Permalink](https://eprint.iacr.org/2024/1661)
* [Download](https://eprint.iacr.org/2024/1661.pdf)

### Abstract

This paper introduces zkFFT, a novel zero-knowledge argument designed to efficiently generate proofs for FFT (Fast Fourier Transform) relations. Our approach enables the verification that one committed vector is the FFT of another, addressing an
efficiency need in general-purpose non-interactive zero-knowledge proof systems where the proof relation utilizes vector commitments inputs.

We present a concrete enhancement to the Halo2 proving system, demonstrating how zkFFT optimizes proofs in scenarios where the proof relation includes one or more vector commitments. Specifically, zkFFT incorporates streamlined logic within Halo2 and
similar systems, augmenting proof and verification complexity by only $O(\text{log}N)$, where $N$ is the vector size. This represents a substantial improvement over conventional approach, which often necessitates specific circuit extensions to validate
the integrity of vector commitments and their corresponding private values in the arithmetic framework of the proof relation. The proposed zkFFT method supports multiple vector commitments with only a logarithmic increase in extension costs, making it
highly scalable. This capability is pivotal for practical applications involving multiple pre-committed values within proof statements.

Apart from Halo2, our technique can be adapted to any other zero-knowledge proof system that relies on arithmetization, where each column is treated as an evaluation of a polynomial over a specified domain, computes this polynomial via FFT, and
subsequently commits to the resulting polynomial using a polynomial commitment scheme based on inner-product arguments. Along with efficient lookup and permutation arguments, zkFFT will streamline and significantly optimize the generation of zero-
knowledge proofs for arbitrary relations.

Beyond the applications in augmenting zero-knowledge proof systems, we believe that the formalized zkFFT argument can be of independent interest.



## 2024/1746

* Title: Secure and Privacy-preserving CBDC Offline Payments using a Secure Element
* Authors: Elli Androulaki, Angelo De Caro, Kaoutar El Khiyaoui, Romain Gay, Rebekah Mercer, Alessandro Sorniotti
* [Permalink](https://eprint.iacr.org/2024/1746)
* [Download](https://eprint.iacr.org/2024/1746.pdf)

### Abstract

Offline payments present an opportunity for central bank digital currency to address the lack of digital financial inclusion plaguing existing digital payment solutions. However, the design of secure offline payments is a complex undertaking; for example,
the lack of connectivity during the payments renders double spending attacks trivial. While the identification of double spenders and penal sanctions may curb attacks by individuals, they may not be sufficient against concerted efforts by states or well-
funded institutions. It is hence important to also rely on preventive measures that reduce the scale of such attacks. An example of such a measure is secure elements. These however are limited in compute and storage, making the design of solutions that
offer comparable privacy guarantees to those of physical cash challenging.
We address this with a protocol that offloads most of the payment computation to the user’s mobile device and restricts the computation on the secure element to deleting spent tokens, and generating a signature with a computation equivalent to that of
ECDSA. We claim that the use of mobile devices or enhanced smart card-based devices are required for secure consumer-to-consumer payments. To further harden the protocol, we enable the efficient identification of double spenders on the off-chance an
attacker successfully double spends. Finally, we prove its security in the ideal/real world paradigm, and evaluate its performance to demonstrate its practicality.



## 2024/1747

* Title: POMS : Proxy Offloading for Multicloud Storage with Keyword Search
* Authors: Adam Oumar Abdel-Rahman, Sofiane Azogagh, Zelma Aubin Birba, Arthur Tran Van
* [Permalink](https://eprint.iacr.org/2024/1747)
* [Download](https://eprint.iacr.org/2024/1747.pdf)

### Abstract

Cloud storage offers convenient data access and sharing, but security concerns remain. Existing secure cloud storage solutions often lack essential features like data integrity, multi-cloud support, user-friendly file sharing, and efficient search. This
paper proposes a novel secure cloud storage system that addresses these limitations. Our system uses distributed storage and attribute-based encryption to enhance data availability, access control, and user experience. It also enables private and
efficient file search and data retrievability verification. This approach overcomes the trade-offs present in prior work, offering a secure and user-friendly solution for cloud data management.



## 2024/1748

* Title: A Simple Method to Test the Zeros of Riemann Zeta Function
* Authors: Zhengjun Cao
* [Permalink](https://eprint.iacr.org/2024/1748)
* [Download](https://eprint.iacr.org/2024/1748.pdf)

### Abstract

The zeta function $\zeta(z)=\sum_{n=1}^{\infty} \frac{1}{n^z}$ is convergent only for $\text{Re}(z)>1$. The Riemann-Siegel function is $Z(t)=e^{i\vartheta(t)}\zeta(\frac{1}{2}+it)$. If $Z(t_1)$ and $Z(t_2)$ have opposite signs, $Z(t)$ vanishes between $
t_1$ and $t_2$, and $\zeta(z)$ has a zero on the critical line between $\frac{1}{2}+it_1$ and $\frac{1}{2}+it_2$. This method to test zeros is too hard to practice for newcomers. The eta function $\eta(z)=\sum_{n=1}^{\infty}\frac{(-1)^{n-1}}{n^z}$
is convergent for $\text{Re}(z)>0$, and $\eta(z)=\left(1-\frac{2}{2^z}\right)\zeta(z)$ for the critical strip $0<\text{Re}(z)<1$. So, $\eta(z)$ and the analytic continuation of $\zeta(z)$ have the same zeros in the critical strip, and the alternating
series can be directly used to test the zeros.



## 2024/1749

* Title: Revisiting the “improving the security of multi-party quantum key agreement with five- qubit Brown states”
* Authors: Yu-Yuan Chou, Hsien-Hung Liu, Jue-Sam Chou
* [Permalink](https://eprint.iacr.org/2024/1749)
* [Download](https://eprint.iacr.org/2024/1749.pdf)

### Abstract

In 2018 Cai et al. proposed a multi-party quantum key agreement with five-qubit Brown states. They confirmed the security of their proposed scheme. However, Elhadad, Ahmed, et al. found the scheme cannot resist the collusion attack launched by legal
participants. They suggested a modification and declared that their improved version is capable of resisting this type of attack. Nevertheless, after analysis, we found that the collusion attack still exists. Subsequently, we proposed a straightforward
modification to prevent the attack. After analysis, we conclude that our modification meets the required security and collusion attack requirements, which are very important in the quantum key agreement scheme.



## 2024/1750

* Title: Robust Double Auctions for Resource Allocation
* Authors: Arthur Lazzaretti, Charalampos Papamanthou, Ismael Hishon-Rezaizadeh * [Permalink](https://eprint.iacr.org/2024/1750)
* [Download](https://eprint.iacr.org/2024/1750.pdf)

### Abstract

In a zero-knowledge proof market, we have two sides. On one side, bidders with proofs of different sizes and some private value to have this proof computed. On the other side, we have distributors (also called sellers) which have compute available to
process the proofs by the bidders, and these distributors have a certain private cost to process these proofs (dependent on the size). More broadly, this setting applies to any online resource allocation where we have bidders who desire a certain amount
of a resource and distributors that can provide this resource. In this work, we study how to devise double auctions for this setting which are truthful for users, weak group strategy proof, weak budget balanced, computationally efficient, and achieve a
good approximation of the maximum welfare possible by the set of bids. We denote such auctions as $\textit{robust}$.



## 2024/1751

* Title: Offline-Online Indifferentiability of Cryptographic Systems
* Authors: Ashrujit Ghoshal, Ilan Komargodski, Gil Segev
* [Permalink](https://eprint.iacr.org/2024/1751)
* [Download](https://eprint.iacr.org/2024/1751.pdf)

### Abstract

The indifferentiability framework has become a standard methodology that enables us to study the security of cryptographic constructions in idealized models of computation. Unfortunately, while indifferentiability provides strong guarantees whenever the
security of a construction is captured by a ``single-stage'' security game, it may generally provide no meaningful guarantees when the security is captured by a ``multi-stage'' one. In particular, the indifferentiability framework does not capture
offline-online games, where the adversary can perform an extensive offline computation to later speed up the online phase. Such security games are extremely common, both in practice and in theory. Over the past decade, there has been numerous attempts to
meaningfully extend the indifferentiability framework to offline-online games, however, they all ultimately met with little success.

In this work, our contribution is threefold. First, we propose an extension of the classical indifferentiability framework, we refer to as *offline-online-indifferentiability*, that applies in the context of attackers with an expensive offline phase (
á la Ghoshal and Tessaro, CRYPTO '23). Second, we show that our notion lends itself to a natural and meaningful composition theorem for offline-online security games. Lastly, as our main technical contribution, we analyze the offline-online-
indifferentiability of two classical variants of the Merkle-Damg\aa rd hashing mechanism, one where the key is fed only to the first block in the chain and the other where the key is fed to each block in the chain. For both constructions, we prove a *
tight* bound on their offline-online-indifferentiability (i.e., an upper bound and an attack that matches it). Notably, our bound for the second variant shows that the construction satisfies *optimal* offline-online-indifferentiability.



## 2024/1752

* Title: DEEP Commitments and Their Applications
* Authors: Alan Szepieniec
* [Permalink](https://eprint.iacr.org/2024/1752)
* [Download](https://eprint.iacr.org/2024/1752.pdf)

### Abstract

This note studies a method of committing to a polynomial in a way that allows executions of low degree tests such as FRI to be batched and even deferred. In particular, it achieves (unlimited-depth) aggregation for STARKs.



## 2024/1753

* Title: HTCNN: High-Throughput Batch CNN Inference with Homomorphic Encryption for Edge Computing
* Authors: Zewen Ye, Tianshun Huang, Tianyu Wang, Yonggen Li, Chengxuan Wang, Ray C.C. Cheung, Kejie Huang
* [Permalink](https://eprint.iacr.org/2024/1753)
* [Download](https://eprint.iacr.org/2024/1753.pdf)

### Abstract

Homomorphic Encryption (HE) technology allows for processing encrypted data, breaking through data isolation barriers and providing a promising solution for privacy-preserving computation. The integration of HE technology into Convolutional Neural
Network (CNN) inference shows potential in addressing privacy issues in identity verification, medical imaging diagnosis, and various other applications. The CKKS HE algorithm stands out as a popular option for homomorphic CNN inference due to its
capability to handle real number computations. However, challenges such as computational delays and resource overhead present significant obstacles to the practical implementation of homomorphic CNN inference, largely due to the complex nature of HE
operations. In addition, current methods for speeding up homomorphic CNN inference primarily address individual images or large batches of input images, lacking a solution for efficiently processing a moderate number of input images with fast homomorphic
inference capabilities, which is more suitable for edge computing applications. In response to these challenges, we introduce a novel leveled homomorphic CNN inference scheme aimed at reducing latency and improving throughput using the CKKS scheme. Our
proposed inference strategy involves mapping multiple inputs to a set of ciphertext by exploiting the sliding window properties of convolutions to utilize CKKS's inherent Single-Instruction-Multiple-Data (SIMD) capability. To mitigate the delay
associated with homomorphic CNN inference, we introduce optimization techniques, including mask-weight merging, rotation multiplexing, stride convolution segmentation, and folding rotations. The efficacy of our homomorphic inference scheme is
demonstrated through evaluations carried out on the MNIST and CIFAR-10 datasets. Specifically, results from the MNIST dataset on a single CPU thread show that inference for 163 images can be completed in 10.4 seconds with an accuracy of 98.9%, which is a
6.9 times throughput improvement over state-of-the-art works. Comparative analysis with existing methodologies highlights the superior performance of our proposed inference scheme in terms of latency, throughput, communication overhead, and memory
utilization.



## 2024/1754

* Title: PQNTRU: Acceleration of NTRU-based Schemes via Customized Post-Quantum Processor
* Authors: Zewen Ye, Junhao Huang, Tianshun Huang, Yudan Bai, Jinze Li, Hao Zhang, Guangyan Li, Donglong Chen, Ray C.C. Cheung, Kejie Huang
* [Permalink](https://eprint.iacr.org/2024/1754)
* [Download](https://eprint.iacr.org/2024/1754.pdf)

### Abstract

Post-quantum cryptography (PQC) has rapidly evolved in response to the emergence of quantum computers, with the US National Institute of Standards and Technology (NIST) selecting four finalist algorithms for PQC standardization in 2022, including the
Falcon digital signature scheme. The latest round of digital signature schemes introduced Hawk, both based on the NTRU lattice, offering compact signatures, fast generation, and verification suitable for deployment on resource-constrained Internet-of-
Things (IoT) devices. Despite the popularity of Crystal-Dilithium and Crystal-Kyber, research on NTRU-based schemes has been limited due to their complex algorithms and operations. Falcon and Hawk's performance remains constrained by the lack of parallel
execution in crucial operations like the Number Theoretic Transform (NTT) and Fast Fourier Transform (FFT), with data dependency being a significant bottleneck. This paper enhances NTRU-based schemes Falcon and Hawk through hardware/software co-design on
a customized Single-Instruction-Multiple-Data (SIMD) processor, proposing new SIMD hardware units and instructions to expedite these schemes along with software optimizations to boost performance. Our NTT optimization includes a novel layer merging
technique for SIMD architecture to reduce memory accesses, and the use of modular algorithms (Signed Montgomery and Improved Plantard) targets various modulus data widths to enhance performance. We explore applying layer merging to accelerate fixed-point
FFT at the SIMD instruction level and devise a dual-issue parser to streamline assembly code organization to maximize dual-issue utilization. A System-on-chip (SoC) architecture is devised to improve the practical application of the processor in real-
world scenarios. Evaluation on 28 nm technology and FPGA platform shows that our design and optimizations can increase the performance of Hawk signature generation and verification by over 7 times.



## 2024/1755

* Title: Exponential sums in linear cryptanalysis
* Authors: Tim Beyne, Clémence Bouvier
* [Permalink](https://eprint.iacr.org/2024/1755)
* [Download](https://eprint.iacr.org/2024/1755.pdf)

### Abstract

It is shown how bounds on exponential sums derived from modern algebraic geometry, and l-adic cohomology specifically, can be used to upper bound the absolute correlations of linear approximations for cryptographic constructions of low algebraic degree.
This is illustrated by applying results of Deligne, Denef and Loeser, and Rojas-León, to obtain correlation bounds for a generalization of the Butterfly construction, three-round Feistel ciphers, and a generalization of the Flystel construction. For
each of these constructions, bounds obtained using other methods are significantly weaker. In the case of the Flystel construction, our bounds resolve a conjecture by the designers.
Correlation bounds of this type are relevant for the development of security arguments against linear cryptanalysis, especially in the weak-key setting or for primitives that do not involve a key. Since the methods used in this paper are applicable to
constructions defined over arbitrary finite fields, the results are also relevant for arithmetization-oriented primitives such as Anemoi, which uses S-boxes based on the Flystel construction.



## 2024/1756

* Title: $\mathsf{Graphiti}$: Secure Graph Computation Made More Scalable
* Authors: Nishat Koti, Varsha Bhat Kukkala, Arpita Patra, Bhavish Raj Gopal
* [Permalink](https://eprint.iacr.org/2024/1756)
* [Download](https://eprint.iacr.org/2024/1756.pdf)

### Abstract

Privacy-preserving graph analysis allows performing computations on graphs that store sensitive information while ensuring all the information about the topology of the graph, as well as data associated with the nodes and edges, remains hidden. The
current work addresses this problem by designing a highly scalable framework, $\mathsf{Graphiti}$, that allows securely realising any graph algorithm. $\mathsf{Graphiti}$ relies on the technique of secure multiparty computation (MPC) to design a generic
framework that improves over the state-of-the-art framework of GraphSC by Araki et al. (CCS'21). The key technical contribution is that $\mathsf{Graphiti}$ has round complexity independent of the graph size, which in turn allows attaining the desired
scalability. Specifically, this is achieved by (i) decoupling the $\mathsf{Scatter}$ primitive of GraphSC into separate operations of $\mathsf{Propagate}$ and $\mathsf{ApplyE}$, (ii) designing a novel constant-round approach to realise $\mathsf{Propagate}
$, as well as (iii) designing a novel constant-round approach to realise the $\mathsf{Gather}$ primitive of GraphSC by leveraging the linearity of the aggregation operation. We benchmark the performance of $\mathsf{Graphiti}$ for the application of
contact tracing via BFS for 10 hops and observe that it takes less than 2 minutes when computing over a graph of size $10^7$. Concretely it improves over the state-of-the-art up to a factor of $1034\times$ in online run time. Similar to GraphSC by Araki
et al., since $\mathsf{Graphiti}$ relies on a secure protocol for shuffle, we additionally design a shuffle protocol secure against a semi-honest adversary in the 2-party with a helper setting. Given the versatility of shuffle protocol, the designed
solution is of independent interest. Hence, we also benchmark the performance of the designed shuffle where we observe improvements of up to $1.83\times$ in online run time when considering an input vector of size $10^7$, in comparison to the state-of-
the-art in the considered setting.



## 2024/1757

* Title: On the Sample Complexity of Linear Code Equivalence for all Code Rates * Authors: Alessandro Budroni, Andrea Natale
* [Permalink](https://eprint.iacr.org/2024/1757)
* [Download](https://eprint.iacr.org/2024/1757.pdf)

### Abstract

In parallel with the standardization of lattice-based cryptosystems, the research community in Post-quantum Cryptography focused on non-lattice-based hard problems for constructing public-key cryptographic primitives. The Linear Code Equivalence (LCE)
Problem has gained attention regarding its practical applications and cryptanalysis.
Recent advancements, including the LESS signature scheme and its candidacy in the NIST standardization for additional signatures, supported LCE as a foundation for post-quantum cryptographic primitives. However, recent cryptanalytic results have revealed
vulnerabilities in LCE-based constructions when multiple related public keys are available for one specific code rate. In this work, we generalize the proposed attacks to cover all code rates. We show that the complexity of recovering the private key
from multiple public keys is significantly reduced for any code rate scenario. Thus, we advise against constructing specific cryptographic primitives using LCE.



## 2024/1758

* Title: A comprehensive analysis of Regev's quantum algorithm
* Authors: Razvan Barbulescu, Mugurel Barcau, Vicentiu Pasol
* [Permalink](https://eprint.iacr.org/2024/1758)
* [Download](https://eprint.iacr.org/2024/1758.pdf)

### Abstract

Public key cryptography can be based on integer factorization and
the discrete logarithm problem (DLP), applicable in multiplicative groups and elliptic curves. Regev’s recent quantum algorithm was initially designed for the
factorization and was later extended to the DLP in the multiplicative group.
In this article, we further extend the algorithm to address the DLP for elliptic
curves. Notably, based on celebrated conjectures in Number Theory, Regev’s algorithm is asymptotically faster than Shor’s algorithm for elliptic curves. Our analysis covers all cases where Regev’s algorithm can be applied. We examine the general framework of Regev’s algorithm and offer a geometric description of its parameters. This preliminary analysis enables us to certify the success of the algorithm on a particular instance before running it.
In the case of integer factorization, we demonstrate that there exists an in- finite family of RSA moduli for which the algorithm always fails. On the other hand, when the parameters align with the Gaussian heuristics, we prove that Regev’s algorithm succeeds. By noting that the algorithm naturally adapts
to the multidimensional DLP, we proved that it succeeds for a certain range
of parameters.



## 2024/1759

* Title: A Forgery Attack on a Code-based Signature Scheme
* Authors: Ali Babaei, Taraneh Eghlidos
* [Permalink](https://eprint.iacr.org/2024/1759)
* [Download](https://eprint.iacr.org/2024/1759.pdf)

### Abstract

With the advent of quantum computers, the security of cryptographic primitives, including digital signature schemes, has been compromised. To deal with this issue, some signature schemes have been introduced to resist against these computers. These
schemes are known as post-quantum signature schemes. One group of these schemes is based on the hard problems of coding theory, called code-based cryptographic schemes. Several code-based signature schemes are inspired by the McEliece encryption scheme
using three non-singular, parity-check, and permutation matrices as the only components of the private keys, and their product as the public key. In this paper, we focus on the analysis of a class of such signature schemes. For this purpose, we first
prove that the linear relationships between the columns of the parity-check/generator matrix appear in the public key matrix, and by exploiting this feature we perform a forgery attack on one of the signature schemes of this class as an evidence. The
complexity of this attack is of O(n^4).



## 2024/1760

* Title: Somewhat Homomorphic Encryption from Linear Homomorphism and Sparse LPN
* Authors: Henry Corrigan-Gibbs, Alexandra Henzinger, Yael Kalai, Vinod Vaikuntanathan
* [Permalink](https://eprint.iacr.org/2024/1760)
* [Download](https://eprint.iacr.org/2024/1760.pdf)

### Abstract

We construct somewhat homomorphic encryption schemes from the learning sparse parities with noise (sparse LPN) problem, along with an assumption that implies linearly homomorphic encryption (e.g., the decisional Diffie-Hellman or decisional composite
residuosity assumptions). Our resulting schemes support an a-priori bounded number of homomorphic operations: $O(\log \lambda/\log \log \lambda)$ multiplications followed by poly($\lambda$) additions, where $\lambda \in \mathbb{N}$ is a security
parameter. These schemes have compact ciphertexts: after homomorphic evaluation, the bit-length of each ciphertext is a fixed polynomial in the security parameter $\lambda$, independent of the number of homomorphic operations applied to it. This gives
the first somewhat homomorphic encryption schemes that can evaluate the class of bounded-degree polynomials with a bounded number of monomials without relying on lattice assumptions or bilinear maps.

Much like in the Gentry-Sahai-Waters fully homomorphic encryption scheme, ciphertexts in our scheme are matrices, homomorphic addition is matrix addition, and homomorphic multiplication is matrix multiplication. Moreover, when encrypting many messages at
once and performing many homomorphic evaluations at once, the bit-length of ciphertexts in some of our schemes (before and after homomorphic evaluation) can be arbitrarily close to the bit-length of the plaintexts. The main limitation of our schemes is
that they require a large evaluation key, whose size scales with the complexity of the homomorphic computation performed, though this key can be re-used across any polynomial number of encryptions and evaluations.



## 2024/1761

* Title: Resilience-Optimal Lightweight High-threshold Asynchronous Verifiable Secret Sharing
* Authors: Hao Cheng, Jiliang Li, Yizhong Liu, Yuan Lu, Weizhi Meng, Zhenfeng Zhang
* [Permalink](https://eprint.iacr.org/2024/1761)
* [Download](https://eprint.iacr.org/2024/1761.pdf)

### Abstract

Shoup and Smart (SS24) recently introduced a lightweight asynchronous verifiable secret sharing (AVSS) protocol with optimal resilience directly from cryptographic hash functions (JoC 2024), offering plausible quantum resilience and computational
efficiency. However, SS24 AVSS only achieves standard secrecy to keep the secret confidential against $n/3$ corrupted parties \textit{if no honest party publishes its share}. In contrast, from ``heavyweight'' public-key cryptography, one can realize so-
called \textit{high-threshold} asynchronous verifiable secret sharing (HAVSS), with a stronger \textit{high-threshold} secrecy to tolerate $n/3$ corrupted parties and additional leaked shares from $n/3$ honest parties. This raises the following question:
can we bridge the remaining gap to design an efficient HAVSS using only lightweight cryptography?

We answer the question in the affirmative by presenting a lightweight HAVSS with optimal resilience. When executing across $n$ parties to share a secret, it attains a worst-case communication complexity of $\Tilde{\bigO}(\lambda n^3)$ (where $\lambda$
is the cryptographic security parameter) and realizes high-threshold secrecy to tolerate a fully asynchronous adversary that can control $t= \lfloor \frac{n-1}{3} \rfloor$ malicious parties and also learn $t$ additional secret shares from some honest
parties.
The (worst-case) communication complexity of our lightweight HAVSS protocol matches that of SS24 AVSS---the state-of-the-art lightweight AVSS without high-threshold secrecy.
Notably, our design is a direct and concretely efficient reduction to hash functions in the random oracle model, without extra setup assumptions like CRS/PKI or heavy intermediate steps like hash-based zk-STARK.



## 2024/1762

* Title: Homomorphic Matrix Operations under Bicyclic Encoding
* Authors: Jingwei Chen, Linhan Yang, Wenyuan Wu, Yang Liu, Yong Feng
* [Permalink](https://eprint.iacr.org/2024/1762)
* [Download](https://eprint.iacr.org/2024/1762.pdf)

### Abstract


[continued in next message]

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