[digest] 2024 Week 15

## In this issue

1. [2023/1531] Towards Practical Transciphering for FHE with Setup ...
2. [2024/537] Confidential and Verifiable Machine Learning ...
3. [2024/538] A comment on "Comparing the MOV and FR reductions ...
4. [2024/539] Supersingular Hashing using Lattès Maps
5. [2024/540] Lattice-Based Timed Cryptography
6. [2024/541] Dual Support Decomposition in the Head: Shorter ...
7. [2024/542] Breaking Bicoptor from S$\&$P 2023 Based on ...
8. [2024/543] A Note on the Common Haar State Model
9. [2024/544] A post-quantum Distributed OPRF from the Legendre PRF
10. [2024/545] Optimal Asynchronous Byzantine Consensus with Fair ...

## 2023/1531

* Title: Towards Practical Transciphering for FHE with Setup Independent of the Plaintext Space
* Authors: Pierrick Méaux, Jeongeun Park, Hilder V. L. Pereira
* [Permalink](https://eprint.iacr.org/2023/1531)
* [Download](https://eprint.iacr.org/2023/1531.pdf)

### Abstract

Fully Homomorphic Encryption (FHE) is a powerful tool to achieve non-interactive privacy preserving protocols with optimal computation/communication complexity. However, the main disadvantage is that the actual communication cost (bandwidth) is high due to the large size of FHE ciphertexts. As a solution, a technique called transciphering (also known as Hybrid Homomorphic Encryption) was introduced to achieve almost optimal bandwidth for such protocols. However, all of existing works require clients to fix a  precision for the messages or a mathematical structure for the message space beforehand. It results in unwanted constraints on the plaintext size or underlying structure of FHE based applications.

In this article, we introduce a new approach for transciphering which does not require fixed message precision decided by the client, for the first time. In more detail, a client uses any kind of FHE-friendly symmetric cipher  for $\{0,1\}$ to send its input data encrypted bit-by-bit, then the server can choose a precision $p$ depending on the application and homomorphically transforms the encrypted bits into FHE ciphertexts encrypting integers in $\mathbb{Z}_p$. To illustrate our new technique, we evaluate a transciphering using FiLIP cipher and adapt the most practical homomorphic evaluation technique [CCS'22] to keep the practical latency.  As a result, our proof-of-concept implementation for $p$ from $2^2$ to $2^8$ takes only from $13$ ms to $137$ ms.



## 2024/537

* Title: Confidential and Verifiable Machine Learning Delegations on the Cloud
* Authors: Wenxuan Wu, Soamar Homsi, Yupeng Zhang
* [Permalink](https://eprint.iacr.org/2024/537)
* [Download](https://eprint.iacr.org/2024/537.pdf)

### Abstract

With the growing adoption of cloud computing, the ability to store data and delegate computations to powerful and affordable cloud servers have become advantageous for both companies and individual users. However, the security of cloud computing has emerged as a significant concern. Particularly, Cloud Service Providers (CSPs) cannot assure data confidentiality and computations integrity in mission-critical applications. In this paper, we propose a confidential and verifiable delegation scheme that advances and overcomes major performance limitations of existing Secure Multiparty Computation (MPC) and Zero Knowledge Proof (ZKP). Secret-shared Data and delegated computations to multiple cloud servers remain completely confidential as long as there is at least one honest MPC server. Moreover, results are guaranteed to be valid even if all the participating servers are malicious. Specifically, we design an efficient protocol based on interactive proofs, such that most of the computations generating the proof can be done locally on each server. In addition, we propose a special protocol for matrix multiplication where the overhead of generating the proof is asymptotically smaller than the time to evaluate the result in MPC. Experimental evaluation demonstrates that our scheme significantly outperforms prior work, with the online prover time being 1-2 orders of magnitude faster. Notably, in the matrix multiplication protocol, only a minimal 2% of the total time is spent on the proof generation. Furthermore, we conducted tests on machine learning inference tasks. We executed the protocol for a fully-connected neural network with 3 layers on the MNIST dataset and it takes 2.6 seconds to compute the inference in MPC and generate the proof, 88× faster than prior work. We also tested the convolutional neural network of Lenet with 2 convolution layers and 3 dense layers and the running time is less than 300 seconds across three servers.



## 2024/538

* Title: A comment on "Comparing the MOV and FR reductions in elliptic curve cryptography" from EUROCRYPT'99
* Authors: Qiping Lin, Fengmei Liu
* [Permalink](https://eprint.iacr.org/2024/538)
* [Download](https://eprint.iacr.org/2024/538.pdf)

### Abstract

In general the discrete logarithm problem is a hard problem in the elliptic curve cryptography, and the best known solving algorithm have exponential running time. But there exists a class of curves, i.e. supersingular elliptic curves, whose discrete logarithm problem has a subexponential solving algorithm called the MOV attack. In 1999, the cost of the MOV reduction is still computationally expensive due to the power of computers. We analysis the cost of the MOV reduction and the discrete logarithm problem of the curves in \cite{HSSI99} using Magma with an ordinary computer.



## 2024/539

* Title: Supersingular Hashing using Lattès Maps
* Authors: Daniel Larsson
* [Permalink](https://eprint.iacr.org/2024/539)
* [Download](https://eprint.iacr.org/2024/539.pdf)

### Abstract

In this note we propose a variant (with four sub-variants) of the Charles--Goren--Lauter (CGL) hash function using Lattès maps over finite fields. These maps define dynamical systems on the projective line. The underlying idea is that these maps ``hide'' the $j$-invariants in each step in the isogeny chain, similar to the Merkle--Damgård construction. This might circumvent the problem concerning the knowledge of the starting (or ending) curve's endomorphism ring, which is known to create collisions in the CGL hash function.   

Let us, already in the abstract, preface this note by remarking that we have not done any explicit computer experiments and benchmarks (apart from a small test on the speed of computing the orbits), nor do we make any security claims. Part of the reason for this is the author's lack of competence in complexity theory and evaluation of security claims. Instead this note is only meant as a presentation of the main idea, the hope being that someone more competent will find it interesting enough to pursue further.



## 2024/540

* Title: Lattice-Based Timed Cryptography
* Authors: Russell W. F. Lai, Giulio Malavolta
* [Permalink](https://eprint.iacr.org/2024/540)
* [Download](https://eprint.iacr.org/2024/540.pdf)

### Abstract

Timed cryptography studies primitives that retain their security only for a predetermined amount of time, such as proofs of sequential work and time-lock puzzles. This feature has proven to be useful in a large number of practical applications, e.g. randomness generation, sealed-bid auctions, and fair multi-party computation. However, the current state of affairs in timed cryptography is unsatisfactory: Virtually all efficient constructions rely on a single sequentiality assumption, namely that repeated squaring in unknown order groups cannot be parallelised. This is a single point of failure in the classical setting and is even false against quantum adversaries.

In this work we put forward a new sequentiality assumption, which essentially says that a repeated application of the standard lattice-based hash function cannot be parallelised. We provide concrete evidence of the validity of this assumption and perform some initial cryptanalysis. We also propose a new template to construct proofs of sequential work, based on lattice techniques.



## 2024/541

* Title: Dual Support Decomposition in the Head: Shorter Signatures from Rank SD and MinRank
* Authors: Loïc Bidoux, Thibauld Feneuil, Philippe Gaborit, Romaric Neveu, Matthieu Rivain
* [Permalink](https://eprint.iacr.org/2024/541)
* [Download](https://eprint.iacr.org/2024/541.pdf)

### Abstract

The MPC-in-the-Head (MPCitH) paradigm is widely used for building post-quantum signature schemes, as it provides a versatile way to design proofs of knowledge based on hard problems. Over the years, the MPCitH landscape has changed significantly, with the most recent improvement coming from VOLE-in-the-Head (VOLEitH) and Threshold-Computation-in-the-Head (TCitH).

   While a straightforward application of these frameworks already improve the existing MPCitH-based signatures, we show in this work that we can adapt the arithmetic constraints representing the underlying security assumptions (here called the modeling) to achieve smaller sizes using these new techniques.
More precisely, we explore existing modelings for the rank syndrome decoding (RSD) and MinRank problems and we introduce a new modeling, named dual support decomposition, which achieves better sizes with the VOLEitH and TCitH frameworks by minimizing the size of the witnesses. 
While this modeling is naturally more efficient than the other ones for a large set of parameters, we show that it is possible to go even further and explore new areas of parameters. With these new modeling and parameters, we obtain low-size witnesses which drastically reduces the size of the ``arithmetic part'' of the signature.
   
    We apply our new modeling to both TCitH and VOLEitH frameworks and compare our results to RYDE, MiRitH, and MIRA signature schemes. We obtain signature sizes below 4 kB for 128 bits of security with N=256 parties (a.k.a. leaves in the GGM trees) and going as low as $\approx$ 3.5 kB with N=2048, for both RSD and MinRank. This represents an improvement of more than 1.5 kB compared to the original submissions to the 2023 NIST call for additional signatures. We also note that recent techniques optimizing the sizes of GGM trees are applicable to our schemes and further reduce the signature sizes by a few hundred bytes, bringing them arround 3 kB (for 128 bits of security with N=2048).



## 2024/542

* Title: Breaking Bicoptor from S$\&$P 2023 Based on Practical Secret Recovery Attack
* Authors: Jun Xu, Zhiwei Li, Lei Hu
* [Permalink](https://eprint.iacr.org/2024/542)
* [Download](https://eprint.iacr.org/2024/542.pdf)

### Abstract

At S$\&$P 2023, a family of secure three-party computing protocols called Bicoptor was mainly proposed by Huawei Technology in China, which is used to compute non-linear functions in privacy preserving machine learning. In these protocols, two parties $P_0, P_1$ respectively hold the corresponding shares of the secret, while a third party $P_2$ acts as an assistant. The authors claimed that neither party in the Bicoptor can independently compromise the confidentiality of the input, intermediate, or output. In this paper, we point out that this claim is incorrect. The assistant $P_2$ can recover the secret in the DReLU protocol, which is the basis of Bicoptor. The restoration of its secret will result in the security of the remaining protocols in Bicoptor being compromised. Specifically, we provide two secret recovery attacks regarding the DReLU protocol. The first attack method belongs to a clever enumeration method, which is mainly due to the derivation of the modular equation about the secret and its share. The key of the second attack lies in solving the small integer root problem of a modular equation, as the lattices involved are only 3 or 4 dimensions, the LLL algorithm can effectively work. For the system settings selected by Bicoptor, our experiment shows that the desired secret in the DReLU protocol can be restored within one second on a personal computer.. Therefore, when using cryptographic protocols in the field of privacy preserving machine learning, it is not only important to pay attention to design overhead, but also to be particularly careful of potential security threats.



## 2024/543

* Title: A Note on the Common Haar State Model
* Authors: Prabhanjan Ananth, Aditya Gulati, Yao-Ting Lin
* [Permalink](https://eprint.iacr.org/2024/543)
* [Download](https://eprint.iacr.org/2024/543.pdf)

### Abstract

Common random string model is a popular model in classical cryptography with many constructions proposed in this model. We study a quantum analogue of this model called the common Haar state model, which was also studied in an independent work by Chen, Coladangelo and Sattath (arXiv 2024). In this model, every party in the cryptographic system receives many copies of one or more i.i..d Haar states.

Our main result is the construction of a statistically secure PRSG with: (a) the output length of the PRSG is strictly larger than the key size, (b) the security holds even if the adversary receives $O\left(\frac{\lambda}{(\log(\lambda))^{1.01}} \right)$ copies of the pseudorandom state. We show the optimality of our construction by showing a matching lower bound. Our construction is simple and its analysis uses elementary techniques.



## 2024/544

* Title: A post-quantum Distributed OPRF from the Legendre PRF
* Authors: Novak Kaluderovic, Nan Cheng, Katerina Mitrokotsa
* [Permalink](https://eprint.iacr.org/2024/544)
* [Download](https://eprint.iacr.org/2024/544.pdf)

### Abstract

A distributed OPRF allows a client to evaluate a pseudorandom function on an input chosen by the client using a distributed key shared among multiple servers. This primitive ensures that the servers learn nothing about the input nor the output, and the client learns nothing about the key.
We present a post-quantum OPRF in a distributed server setting, which can be computed in a single round of communication between a client and the servers.
The only server-to-server communication occurs during a precomputation phase.
The algorithm is based on the Legendre PRF which can be computed from a single MPC multiplication among the servers.
To this end we propose two MPC approaches to evaluate the Legendre PRF based on replicated and optimised secret sharing, respectively. Furthermore, we propose two methods that allows us to perform MPC multiplication in an efficient way that are of independent interest.
By employing the latter, we are able to evaluate the Legendre OPRF in a fashion that is quantum secure, verifiable and secure against malicious adversaries under a threshold assumption, as well as computable in a single round of interaction.
To the best of our knowledge, our proposed  distributed OPRFs are the first post-quantum secure offering such properties.
We also provide an implementation of our protocols, and benchmark it against existing OPRF constructions.



## 2024/545

* Title: Optimal Asynchronous Byzantine Consensus with Fair Separability
* Authors: Vincent Gramoli, Zhenliang Lu, Qiang Tang, Pouriya Zarbafian
* [Permalink](https://eprint.iacr.org/2024/545)
* [Download](https://eprint.iacr.org/2024/545.pdf)

### Abstract

Despite ensuring both consistency and liveness, state machine replication protocols remain vulnerable to adversaries who manipulate the transaction order. To address this, researchers have proposed order-fairness techniques that rely either on building dependency graphs between transactions, or on assigning sequence numbers to transactions. Existing protocols that handle dependency graphs suffer from sub-optimal performance, resilience, or security.
On the other hand, Pompe (OSDI '20) introduced the novel ordering notion of ordering linearizability that uses sequence numbers. However, Pompe's ordering only applies to committed transactions, opening the door to order-fairness violation when there are network delays, and vulnerability to performance downgrade when there are Byzantine attackers. A stronger notion, fair separability, was introduced to require ordering on all observed transactions. However, no implementation of fair separability exists.

In this paper, we introduce a protocol for state machine replication with fair separability ($\mathsf{SMRFS}$); moreover, our protocol has communication complexity $\mathcal{O}(n\ell+\lambda n^2)$, where $n$ is the number of processes, $\ell$ is the input (transaction) size, and $\lambda$ is the security parameter. This is optimal when $\ell\geq \lambda n$, while previous works have cubic communication. To the best of our knowledge, $\mathsf{SMRFS}$ is the first protocol to achieve fair separability, and the first implementation of fair ordering that has optimal communication complexity and optimal Byzantine resilience.