# Arithmétisation de la partie entière et applications à la cryptographie

Pierre-Augustin Berthet, Cédric Tavernier

► To cite this version:

Pierre-Augustin Berthet, Cédric Tavernier. Arithmétisation de la partie entière et applications à la cryptographie. Opération CIEDS 2025, Jul 2025, Palaiseau (Ecole Polytechnique), France. 2025. [hal-05127083](https://hal.science/hal-05127083v1)

HAL Id: hal-05127083

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

Submitted on 24 Jun 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished 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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Arithmétisation de la partie entière et applications à la cryptographie

## Berthet Pierre-Augustin, Tavernier Cédric

03 Juillet 2025

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

## Arithmétisation et cryptographie homomorphe

* **Arithmétisation** : Le fait d'exprimer une fonction sous la forme uniquement d'additions et de multiplications

* **Chiffrement homomorphe** : la somme (resp. le produit) de deux chiffrés est un chiffré de la somme (resp. du produit).

* Fonction arithmétisée $\Rightarrow$ Évaluable par un chiffrement homomorphe.

## Partie entière et fonction floor

La fonction floor de $x \in \mathbb{R}$, dénotée $\lfloor x \rfloor$, retourne le plus grand entier $z \in \mathbb{Z}$ tel que

<figure><img src="image_3.png" /><figcaption>Figure: Fonction floor</figcaption></figure>

## Applications possibles d'un floor arithmétisé

* contremesure générique pour la fonction floor contre les attaques par canaux auxiliaires

* discrétisation/normalisation dans des réseaux neuronaux chiffrées

## Précisions absolue et relative

Définitions :

* Une approximation $f_a(x, k)$ de $\lfloor x \rfloor$ pour $x \in \mathbb{R}$ a une **précision absolue** de $k$ décimales lorsque

$$f_a(x, k) = \lfloor x \rfloor + \epsilon \quad \text{with} \quad \epsilon = \alpha \times 10^{-k}, \alpha \in [0, 1).$$

* Une approximation $f_r(x, k, \omega)$ de $\lfloor x \rfloor$ pour $x \in \mathbb{R}$ a une **précision relative bornée** par $\omega$ de $k$ décimales lorsque

$$f_r(x, k, \omega) = \lfloor x \rfloor + \epsilon \quad \text{with} \quad \epsilon = \alpha \times 10^{-k}, \alpha \in (-\omega, \omega).$$

Propriétés :

* **Construction** : Soit $y = f_a(x, 1)$. Alors $f_a(10 * y, 1)/10 \approx f_a(x, 2)$.

* **De relative bornée à absolue** : $f_r(x, 1, 0.5) + 0.05 \approx f_a(x, 1)$.

## Développement en série de Fourier

$$\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 kx)}{k}, \text{ avec } n \to \infty. \quad (1)$$

Problème : Phénomène de Gibbs [1] (voir Figure 1). Pour une précision relative de 1 décimale pour $x = z + 1e^{-16}$, $z \in \mathbb{Z}$, on calcule $\approx 2.5e^{13}$ termes!

<figure><img src="image_4.png" /><figcaption>Figure: Phénomène de Gibbs pour 10 termes et 100 termes</figcaption></figure>

## Calcul par composition de séries partielles

* **Biais et précision** : approcher $\lfloor x \rfloor + 0.5$ avec une précision relative bornée par 0.5 de 1 décimale

$$\Rightarrow \lfloor x \rfloor + 0.45 < f(x) = f_r(x, 1, 0.5) + 0.5 < \lfloor x \rfloor + 0.55$$

* On étudie la série partielle et biaisée suivante :

$$\forall x \in \mathbb{R} \sim \mathbb{Z}, g(x) = x + \frac{1}{\pi} \sum_{k=1}^{3} \frac{\sin(2\pi kx)}{k}. \quad (2)$$

* Soit $u_{n+1} = g(u_n)$, $u_0 = g(x)$, $x \in (0, 1)$.

* Observations (voir Figure 1) :

* Si $u_k$ proche de 0 ou 1, alors $u_{k+1}$ s'en éloigne (Newton).

* Si $0.45 < u_k < 0.55$, alors $0.45 < u_{k+1} < 0.55$ (Puit).

* $\forall k, 0 < u_k < 1$.

Conséquemment, $f(x) = u_n$, et $f_a(x, 1) \approx f(x) - 0.45$. Pour $x = z + 1e^{-16}$, $z \in \mathbb{Z}$, on calcule l'équivalent de 72 termes.

<figure><img src="image_5.png" /><figcaption>Figure: Equation 2 en bleu et zone visée en vert.</figcaption></figure>

## Astuces supplémentaires

* Extension aux entiers. Si $x = 0$ (resp. 1), alors $u_0 = 0$ (resp. 1). Astuce : ajouter la plus petite erreur positive possible $\epsilon$ telle que

$$\forall x \in \mathbb{R} \sim \mathbb{Z}, \epsilon < |u_0 - x| \text{ à } u_0.$$

* Amélioration pour la précision supérieure. Plutôt que de viser $f_r(x, 1, 0.5)$, on vise $f_r(x, 1, 0.4)$ car $10\lfloor x \rfloor + 0.1 < 10(f_r(x, 1, 0.4) - 0.45) < 10\lfloor x \rfloor + 0.9$.

Conséquence, pour les précisions 2 et plus, on ne calcule que l'équivalent de 9 termes.

## Arithmétisation du sinus (travail en cours)

* Actuellement : formule de Bhaskara I [2]

* Seulement pour $x \in [0, 2\pi]$, erreur de 2%

* Amélioration en cours : Approximants de Padé

* Pleinement paramétrable, erreur de 0.01% pour $x \in [-\pi, \pi]$

* Soit $y = \frac{x}{2^p}, 2^p > x$. On calcule $\sin(2^p y)$ à partir de $\sin(y)$ et $\sin(2y)$ avec :

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

* Arithmétisation de l'inverse pour Padé et Bhaskara I: Newton-Raphson [3]

$$a_{n+1} = a_n(2 - a_n x), \quad a_n \to \frac{1}{x} \quad \text{si} \quad a_0 \approx \frac{1}{x}$$

## Financements

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

Ce travail est financé par la bourse 2022156 des thèses CIFRE Défense 2022-2025 de l'Agence de l'Innovation de Défense.

Ce travail fait partie du projet X7-PQC sélectionné pour France 2030. Hensoldt SAS France forme sur ce projet un consortium avec Secure-IC, Télécom Paris et Xlim.

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

## Références

[1] M. Bocher. Introduction to the theory of fourier's series. Annals of Mathematics, 7(3):81-152, 1906. ISSN 0003486X. URL http://www.jstor.org/stable/1967238.

[2] R. C. Gupta. Bhaskara's approximation to sine. Indian J. Hist. Sci., 2:121-136, 1967.

[3] P. Soderquist and M. Leeser. Division and square root: choosing the right implementation. IEEE Micro, 17(4):56-66, 1997.