# Arithmetisation of the Floor Function and Its Applications to Homomorphic Cryptography

Pierre-Augustin Berthet, Cédric Tavernier

<figure><img src="image_1.png" /></figure>

## To cite this version:

Pierre-Augustin Berthet, Cédric Tavernier. Arithmetisation of the Floor Function and Its Applications to Homomorphic Cryptography. 2025. hal-05064442

HAL Id: hal-05064442

https://hal.science/hal-05064442v1

Preprint submitted on 12 May 2025

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Arithmetisation of the Floor Function and Its Applications to Homomorphic Cryptography<sup>a</sup>

Pierre-Augustin Berthet<sup>1,2</sup> and Cédric Tavernier<sup>1</sup>

<sup>1</sup> Hensoldt France SAS, Plaisir, France,
{pierre-augustin.berthet,cedric.tavernier}@hensoldt.net

<sup>2</sup> LTCI, Télécom Paris, Institut Polytechnique de Paris, Palaiseau, France,
berthet@telecom-paris.fr

**Keywords:** Floor Function · Arithmetisation · Homomorphism · Cryptography · Abstract

## Introduction

Cryptography has historically been based on integer arithmetic. Thus, there was no need to investigate functions related to real numbers or analysis, such as the fractional part or the floor function. The floor function has several applications in modern cryptography. For example, it is used in the FALCON post-quantum signature [4]. Although our method can- not beat its reference floor function, it has an application in side-channel resilience, where arithmetisation is a valid strategy to apply generic countermeasures like masking. Another application is an indirect consequence of the progress made on Fully Homomorphic Encryp- tion (FHE). Although most of the most widely used FHEs work with integers, one of them, CKKS [2], allows one to work with real numbers. Some examples of applications are Artificial Intelligence (AI) and Machine Learning (ML), which can use the floor function for normal- isation or discretization. Indeed, a client and a company can be in the following situation. The client owns some data he does not want to reveal. The company owns an ML model she doesn't want to share. In that configuration, FHE can be used to perform the model computa- tions without any of them revealing their sensitive data. In order to do this, we have to ensure that all the operations can be arithmetised to use FHE. Thus, when the ML model requires the floor function to be used, our arithmetised version enables its computation under FHE.

## Contributions

In this work we propose a new methodology to compute the floor function with only addi- tions, scalar multiplications, and multiplications.

To do so, we introduce the concepts of absolute and relative precision. We show that with a bounded relative precision, one can add a bias to the result to obtain absolute precision. This will help to "build" the result of the floor function one decimal of precision at a time.

To achieve this bounded relative precision, we use Fourier series. Our main contribution is to use a partial series of a few terms and recompute this partial series with the new result. This drastically accelerates the convergence.

Finally, the last step is to arithmetise the computation of the sinus function necessary for the Fourier series. We use Bhaskara I and trigonometry formulae.

## 1 Floor function

The floor function is defined as follows:

**Definition 1.1.** ∀x ∈ R, the floor function of x, denoted by ⌊x⌋, returns the highest integer z such as z ≤ x.
The floor function can be approximated using a Fourier series:

$$ \forall x \in \mathbb{R} \sim \mathbb{Z}, \lfloor x \rfloor = x - \frac{1}{2} + \frac{1}{\pi} \sum_{k=1}^{n} \frac{\sin(2\pi k x)}{k}, \text{ with } n \to \infty \quad (1) $$

However, due to its discontinuities, Equation 1 suffers from the Gibbs phenomenon [1], and its convergence speed at the points of discontinuity is very slow. It cannot be used as a means to compute the floor function in a reasonable time.

# 2 Arithmetisation

## 2.1 Overall idea

If we can calculate the floor function of $x$ with one decimal of precision with a positive error, we can then multiply the result by 10 and then apply our calculation again to the new value. We denote by $f(x, k)$ the approximation of $\lfloor x \rfloor$ with a precision of $k$ decimals and a positive error. We have the following proposition:

**Proposition 2.1.** Let $x \in \mathbb{R}$. Let $y = 10 \times f(x, 1)$. Then $f(y, 1)/10 \approx f(x, 2)$.

To compute the floor function, we thus need an approximation accurate enough to provide us with one decimal of precision with a positive error. We can then "build" the floor function for any precision we want.

## 2.2 Absolute and relative precisions

Ensuring a positive error is sometimes not possible, especially when using Fourier series for approximation. Thus, we introduce the notions of absolute and bounded relative precision.

**Definition 2.1.** An approximation $f(x)$ is said to have an absolute precision of $k$ decimals if $f(x) = \lfloor x \rfloor + \epsilon$ with $\epsilon = \alpha \times 10^{-k}$, $\alpha \in [0, 1)$.

**Definition 2.2.** An approximation $f(x)$ is said to have a relative precision bounded by $\omega$ of $k$ decimals if $f(x) = \lfloor x \rfloor + \epsilon$ with $\epsilon = \alpha \times 10^{-k}$, $\alpha \in (-\omega, \omega)$.

If $\omega = 1$, then Definition 2.2 corresponds to the classical definition of precision with $k$ decimals. However, the most interesting case is when $\omega = 0.5$: If $\alpha \in (-0.5, 0.5)$, then if $\alpha' = \alpha + 0.5$, we have $\alpha' \in (0, 1)$.

We do not need absolute precision as we can obtain it by biasing the result of an approximation with bounded relative precision. Bounded relative precision is always possible.

## 2.3 Fourier series with restarts

As stated in the first section, there is a Fourier series which approximates the floor function, described in Equation 1. The most problematic inputs are the values close to the discontinuity points where the series does not converge very fast. Although there are some methods in analysis to avoid the Gibbs phenomenon altogether, such as the Cesàro summations and the Fejér kernel, we propose a different approach: Fourier series with "restarts".

First, we rewrite Equation 1 as a function that converges towards $\lfloor x \rfloor + \frac{1}{2}$ when $n \to \infty$:

$$ f(x, n) = x + \frac{1}{\pi} \sum_{k=1}^{n} \frac{\sin(2\pi k x)}{k} \quad (2) $$

As the sine is $2\pi$-periodic, we can study our method on $x \in (0; 1)$ and generalise the result to $x \in \mathbb{R}$. Let $n = 3$. We use Figure 1 to support our explanation. We study the composition of $f(x, 3)$ with itself. This composition is what we call a restart.

A trivial stability point is $x = f(x, 3)$. This is achieved only in $x = 0.5$. As for convergence, if $x \in (0.1; 0.9)$, $0.4 < f(x, 3) < 0.6$. Also, for $x \in (0.4; 0.6)$, $0.45 < f(x, 3) < 0.55$. This implies that, as soon as a composition lands in $(0.1; 0.9)$, we are guaranteed that it
<figure><img src="image_3.png" /><figcaption>Figure 1: $f(x, 3)$ for $x \in (0; 1)$ in blue, with $y = x$ in black, $y = 0.4$ in dashed red and $y = 0.6$ in dashed green</figcaption></figure>

will converge toward the interval $(0.45; 0.55)$ in two compositions and will remain in that interval if further compositions are performed.

For $x \in (0; 0.1)$, $x < f(x, 3) < 0.6$ and $f(x, 3)$ is monotonically increasing. Thus, composing the function with itself starting from $x \in (0; 0.1)$ will always increase the value until it reaches the $(0.1, 0.9)$ interval. For $x \in (0.9; 1)$, $f(x, 3)$ also increases monotonically, but $0.4 < f(x, 3) < x$. Thus, composing the function with itself starting from $x \in (0.9; 1)$ will always decrease the value until it reaches the $(0.1, 0.9)$ interval.

Once the composition step of our method is performed, we simply retrieve the missing $-\frac{1}{2}$ to have the integer part with a relative precision of one decimal bounded by $\alpha = 0.5$. To have absolute precision, we simply retrieve $-\frac{1}{2} + \alpha \times 10^{-1} = -0.45$ instead of $-\frac{1}{2}$.

**Example** Let $x = 1 \times 10^{-20}$. Using the Fourier series described in Equation 1, we heuristically estimated that $2.5 \times 10^{13}$ terms are required to have one zero of absolute precision. With our method, we need 24 restarts with $n = 3$, which is equivalent to 72 terms.

## 2.4 Sinus arithmetisation

To arithmetize the sinus, we use the Bhaskara I's formula[3]:

$$sin(x) \approx \frac{16x(\pi - x)}{5\pi^2 - 4x(\pi - x)} \quad (3)$$

This approximation is accurate for $x \in [0; \pi]$. The division can be arithmetised using the Newton-Raphson method and fast converging sequences [5]. To compute $sin(2\pi kx)$ for any integer $k$ and any real number $x$, we use basic trigonometry formulae.

$$sin(4y) = 2sin(2y)cos(2y) = 2sin(2y)(1 - 2sin^2(y)) \quad (4)$$

We can use the formula from Equation 4 recursively to compute $sin(2^p y)$ from $sin(y)$ and $sin(2y)$.

Now, let $r$ be the smallest integer such that $2kx \le 2^r$. Then $\frac{2kx}{2^r} \le 1$ and $\frac{2\pi kx}{2^r} \le \pi$. Thus, we can compute $sin(\frac{2\pi kx}{2^r})$ and $sin(\frac{2\pi kx}{2^{r+1}})$ using Bhaskara I's formula from Equation 3. Taking $y = \frac{2\pi kx}{2^{r+1}}$ in Equation 4 and $p = r + 1$ gives a fully arithmetised computation of $sin(2\pi kx)$ in practical time.
## 2.5 Further improvements

### 2.5.1 Compatibility with integer inputs

The Fourier series in Equation 1 does not work for $x \in \mathbb{Z}$ as $\forall x \in \mathbb{Z}$, $sin(2k\pi x) = 0$. The $-\frac{1}{2}$ in Equation 1 would then disrupt the result. We tweak our method to work with integer values.

After the first restart in the first iteration of our method, the smallest bias allowed by the precision of the input is added to the current value. If the input is an integer, it was not affected by the first calculation, and the value is now the closest value to the lower discontinuity point. If it was not an integer, after the first reboot we are closer to 0.5 and the smallest bias is not large enough to disrupt the calculations if the input was the closest value to the higher discontinuity point. In any case, an additional reboot is performed.

### 2.5.2 Optimizing higher precisions

When the precision required for the floor function is greater than one, we rely on Proposition 2.1 to build the next decimal of precision. However, there is a way to ensure that the value on which the calculations are performed is far from the discontinuity points for this next iteration.

During the first calculation, we aim for a relative precision of 1 decimal bounded by $\alpha = 0.5$. The trick is to perform a bit more computation during this first phase to achieve $\alpha = 0.4$. As a result, we will have $\lfloor x \rfloor + 0.46 < f(x) < \lfloor x \rfloor + 0.54$. However, instead of retrieving $0.5 - 0.4 \times 10^{-1} = 0.46$, we retrieve 0.45. Consequently, we have $10 \times \lfloor x \rfloor + 0.1 < 10 \times (f(x) - 0.45) < 10 \times \lfloor x \rfloor + 0.9$. We have the guarantee that the computations for the next decimal of precision will not be performed on values close to discontinuity points, thus allowing for less reboots as the Fourier series convergence is faster in this case.

Another benefit of this method is that we are guaranteed that the next iterations are not performed on an integer value. There is no need to add the smallest bias possible after the first reboot in any iteration after the first one.

## 3 Conclusion

In this work, we detail a methodology for computing the floor function in an arithmetic fashion. This approach relies on several axes: a strategy to "build" the integer part one decimal of precision at a time, the use of a reduced Fourier series with restarts for faster convergence, and the use of Bhaskara I and some trigonometry to arithmetize the sinus.

Our method has several applications in cryptology: a direct application in generic side-channel masking for the FALCON signature, and indirect applications in the use of FHE in Artificial Intelligence or Machine Learning.

**Acknowledgments** Pierre-Augustin Berthet thanks Jules Dumezy and Marc Renard for the discussion we had on the applicability of this work to Fully Homomorphic Encryption. This work was realised thanks to the grant 2022156 from the Appel à projets 2022 thèses AID Cifre-Défense by the Agence de l'Innovation de Défense (AID), Ministère des Armées (French Ministry of Defence).

This paper is also part of the ongoing work of Hensoldt France SAS for the Appel à projets Cryptographie Post-Quantique launched by Bpifrance for the France 2030 vision. In this, Hensoldt France SAS is part of the X7-PQC project in partnership with Secure-IC, Télécom Paris, and Xlim.

## References

[1] Maxime Bocher. Introduction to the theory of fourier's series. *Annals of Mathematics*, 7(3):81-152, 1906.
[2] Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. Homomorphic encryption for arithmetic of approximate numbers. In *Advances in Cryptology – ASIACRYPT 2017*, pages 409–437, 2017.

[3] Radha Charan Gupta. Bhaskara i’s approximation to sine. *Indian J. Hist. Sci.*, 2:121–136, 1967.

[4] Thomas Prest, Pierre-Alain Fouque, Jeffrey Hoffstein, Paul Kirchner, Vadim Lyubashevsky, Thomas Pornin, Thomas Ricosset, Gregor Seiler, William Whyte, and Zhenfei Zhang. Falcon. *Post-Quantum Cryptography Project of NIST*, 2020.

[5] Peter Soderquist and Miriam Leeser. Division and square root: choosing the right implementation. *IEEE Micro*, 17(4):56–66, 1997.