# Fast & Fourier: tatouage spectral de graphes

Jade Garcia Bourrée, Anne-Marie Kermarrec, Erwan Le Merrer, Othmane Safsafi

► To cite this version:

Jade Garcia Bourrée, Anne-Marie Kermarrec, Erwan Le Merrer, Othmane Safsafi. Fast & Fourier: tatouage spectral de graphes. ALGOTEL 2025 – 27èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Jun 2025, Saint Valery-sur-Somme, France. pp.1-5. hal-05016042

HAL Id: hal-05016042

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

Submitted on 1 Apr 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
# Fast & Fourier: tatouage spectral de graphes

Jade Garcia Bourrée<fnref n="1" />, Anne-Marie Kermarrec<fnref n="2" />, Erwan Le Merrer<fnref n="1" /> et Othmane Safsafi<fnref n="2" />

Le tatouage numérique a suscité beaucoup d’intérêt au cours des deux dernières décennies, à des fins de traçabilité. Peu de recherches se sont cependant intéressées au problème du tatouage de graphes. Comme les matrices d’adjacence des graphes peuvent être traitées comme des images, nous proposons une nouvelle approche de tatouage de graphes adaptée d’une technique de tatouage d’image. La difficulté réside dans l’obtention d’une matrice non discrète suite à la transformée de Fourier, mais qui doit le redevenir pour pouvoir à nouveau représenter un graphe cohérent. Nous démontrons dans cet article que notre méthode produit des graphes tatoués uniques.

**Mots-clefs** : Graphes, tatouage, transformée de Fourier

## 1 Introduction

Le tatouage numérique consiste à insérer une signature unique dans un objet. Cela a différentes utilités comme : certifier la source de l’information, prouver son intégrité ou encore identifier des copies uniques d’un même objet. Dans cet article, nous nous intéressons au tatouage de graphes non dirigés et non pondérés, dans lesquels sera insérée une signature topologique unique.

**Travaux connexes.** Il y a seulement deux méthodes pour tatouer de tels objets [EGL+16, ZLZZ15]. Ces deux méthodes consistent en des ajouts ou suppressions d’arêtes basés sur la structure des graphes, en modifiant les sommets de plus hauts degrés. Or, pour calculer entre quels sommets le tatouage est inséré, les deux articles proposent des solutions algorithmiques basées sur la résolution de problèmes NP-complets. Même en utilisant des résolutions approximatives, les complexités temporelles de ces méthodes sont mauvaises.

**Notre contribution.** Nous proposons une méthode de tatouage de graphe alternative, nommée FFG, qui est beaucoup plus efficace que celles-ci. Sous forme de matrice d’adjacence, un graphe est finalement la même représentation numérique qu’une image binaire. On peut donc tatouer un graphe avec une méthode de tatouage d’image. Nous utilisons une méthode pionnière dans le tatouage d’images [CKLS97]. Cette méthode utilise la transformée de Fourier (des images) comme opération de base. Cependant, le résultat de ce tatouage est une image, sous forme d’une matrice de réels, non nécessairement symétrique. Par conséquent, notre méthode de tatouage de graphe contient des étapes supplémentaires pour transformer cette matrice en matrice d’adjacence binaire et symétrique afin d’obtenir un graphe tatoué non dirigé et non pondéré. Nous donnons un algorithme qui résout le problème de tatouage de graphe, puis, nous prouvons l’unicité des tatouages insérés. Plus de détails sont disponibles dans la version longue de l’article [GBKLMS25].

## 2 Modèle

Une procédure de tatouage est constituée d'un ensemble de fonction (Keygen, Embed, Extract) applicable à un graphe. Grâce à Keygen, le détenteur du graphe génère une clef secrète. Cette clef secrète est insérée dans son graphe G via la fonction Embed. En résultent une version modifiée du graphe $G_W$ et un tatouage W (défini relativement à la différence entre G et $G_W$). Le détenteur du graphe peut prouver son droit d'auteur sur un graphe $G^*$ avec le tatouage W en utilisant une fonction Extract. La fonction

<footnote n="1">¹Univ Rennes, Inria, CNRS, IRISA</footnote>

<footnote n="2">²EPFL, Lausanne, Switzerland</footnote>
<figure><img src="image_2.png" /><figcaption>**FIGURE 1** : La méthode FFG de tatouage de graphes non dirigés et non pondérés basée sur une adaptation de la méthode de tatouage d'image de Cox et al. [CKLS97].</figcaption></figure>

Extract renvoie vrai si $G^*$ a été tatoué avec $W$. Sinon, soit $G^*$ n'a pas été tatoué avec $W$ soit un attaquant a réussi à modifier suffisamment $G^*$ pour empêcher le détenteur du graphe de prouver son droit d'auteur.

Le principe de Kerckhoffs [Pet83] peut être appliqué à notre travail. C'est-à-dire que nous supposons que la procédure de tatouage est entièrement publique et que le seul secret est généré par la fonction Keygen.

**Représentation d'un graphe.** Les graphes peuvent être définis par leur matrice d'adjacence. Nous tra- vaillons sous l'hypothèse qu'il existe une bijection déterministe entre les sommets d'un graphe et sa matrice d'adjacence. Pour chaque paire de sommets *i*, *j*, le coefficient en place (*i*, *j*) de la matrice d'adjacence est égal à 1 s'il existe une arête entre *i* et *j* dans le graphe, égal à 0 sinon.

**Unicité du tatouage.** Il existe de nombreux objectifs et contraintes à respecter. En raison de contraintes d'espace, nous allons nous concentrer sur l'unicité du tatouage inséré. Les autres objectifs du tatouage de graphes sont traités dans la version complète de l'article [GBKLMS25]. L'unicité est définie de la façon suivante : $P(G_{W_1} \neq G_{W_2}) \gg 0$. En d'autres termes, si deux personnes tatouent le même graphe $G$ avec des signatures différentes $W_1$ et $W_2$, alors, elles obtiennent deux graphes différents avec une haute probabilité. Cette propriété est essentielle pour garantir l'unicité du détenteur du droit d'auteur du graphe.

## 3 Solution proposée

La méthode [CKLS97] propose de tatouer des images de la façon suivante. Le secret $\omega$ est une séquence de $m$ réels choisis aléatoirement dans une distribution Gaussienne. La première étape de la fonction Embed est de calculer $\chi = \{(i_1, j_1), \dots, (i_m, j_m)\}$ comme la séquence des $m$ premiers indices qui trient les modules des coefficients de Fourier de la matrice d'adjacence $A$ de $G$. Cette séquence $\chi$ est utilisée pour insérer le secret dans la transformée de Fourier de $A$ et forme le tatouage du graphe. On note $\mathcal{W}$ la représentation matricielle du secret où chaque élément $\omega[n]$ est à la position $\chi[n] = (i_n, j_n)$. Enfin, la transformée inverse du tatouage $\mathcal{W}$ est ajoutée à la matrice d'adjacence $A$ de $G$ pour obtenir la matrice d'adjacence $A'$ du graphe tatoué, qui est prête à être partagée. En ce qui concerne l'extraction de tatouage, dans [CKLS97], la fonction Extract est définie de la façon suivante. Pour une image donnée (possiblement modifiée), un tatouage $W^*$ est extrait du domaine spectral et comparé au tatouage original $W$. Un score de similarité est alors calculé entre ces deux objets. Si la similarité entre $W^*$ et $W$ est plus grande qu'un certain seuil $\theta$ alors l'extraction du tatouage est considérée comme un succès.

Voici les détails de FFG, une adaptation de [CKLS97] au domaine des graphes. Le pseudo-code de notre solution est donné dans Algorithme 1.

**Key generation.** La génération d'une clef avec la fonction Keygen($m, \sigma$) est identique à celle de [CKLS97].
**Insertion du tatouage.** La matrice $A'$ subit une binarisation et symétrisation en plus et devient $A_W$ (Figure 1). Plus spécifiquement, la binarisation est un seuillage des valeurs de $A'$ par la moyenne de $A$ (notée $av(A)$). Chaque élément est fixé à 0 si son module est plus petit que $av(A)$, 1 sinon. Le tatouage $W$ est défini comme la différence de **tous** les coefficients de Fourier de $A$ et $A_W : W = FT(A) - FT(A_W)$.

**Extraction du tatouage.** La fonction Extract est appliquée au tatouage $W$ obtenu par la binarisation après l'insertion de $\omega$ avec la technique de Cox et al. Cependant, Extract **n'est pas** appliquée directement au secret $\omega$ inséré initialement grâce aux coefficients de la séquence $\chi$ mais bien à tous coefficients de la matrice. Cela est dû à l'étape de binarisation qui étale le secret sur l'entièreté de la matrice. Par conséquent, $W \neq W$. De plus, la similitude entre $W^*$ et $W$ est calculée via la norme 2 de leur différence, qui n'est pas la métrique utilisée dans [CKLS97].

<caption>**Algorithm 1 FFG scheme**</caption>

1: **function** KEYGEN($m, \sigma$)
2:     $\omega = [G(0, \sigma^2), \dots, G(0, \sigma^2)]$ // of length $m$
3:     **Return** $\omega$
4: **function** EMBED($A, \omega$)
5:     $m = |\omega|$
6:     $th = av(A)$ // real number
7:     FT($A$) = Fourier transform of $A$
8:     $\chi = argsort(|FT(A)|)[0: m]$
9:     $W[i, j] = \omega[n]$ if there exists $n \le m$, $\chi[n] = (i, j)$
10:    $A' = A + FT^{-1}(W)$
11:    $A_W[i, j] = \begin{cases} 1 & \text{if } |A'[i, j]| > th \\ 0 & \text{else} \end{cases}$ // binarization
12:    **Return** $A_W$
13: **function** EXTRACT($A, A^*, \omega, \theta$)
14:    $A_W = \dots$ // generated as in Embed
15:    $W^* = FT(A - A^*)$
16:    $W = FT(A - A_W)$
17:    $s = \|W^* - W\|_2$
18:    **Return** $s \le \theta * \|W\|_2$ // True: watermark
retrieved

<table><caption>**TABLE 1 :** Complexité temporelle en pire cas de FFG pour tatouer un graphe $G$ a $N$ sommets avec une clef de longueur $m$.</caption><thead><tr><th>FFG</th><th>raw complexities</th></tr></thead><tbody><tr><td>Keygen</td><td>O(m)</td></tr><tr><td>Embed</td><td>O(N<sup>2</sup> log N)</td></tr><tr><td>Extract</td><td>O(N<sup>2</sup> log N)</td></tr></tbody></table>

Maintenant que nous avons détaillé notre solution algorithmique au tatouage de graphe, étudions l'effet de la binarisation sur l'unicité des tatouages. La propriété est non triviale à cause de l'étape de binarisation qui étale le secret sur tous les coefficients de Fourier des matrices d'adjacence.

**Théorème 1.** *Les complexités temporelles de FFG sont polynomiales en $N$ et $m$ (Table 1).*

La preuve de ce théorème ainsi qu'une comparaison à [EGL+16, ZLZZ15] est disponible dans la version complète de l'article [GBKLMS25]. FFG est la méthode avec la meilleure complexité algorithmique grâce à l'hypothèse qu'il existe une bijection déterministe entre les sommets d'un graphe et sa matrice d'adjacence.

**Théorème 2.** *L'unicité des tatouages est calculable. Numériquement, pour des graphes de densité supérieure à 2 : $P(G_{W_1} \neq G_{W_2}) \sim 1$.*

**Preuve.** Soit $\omega_1$ et $\omega_2$ deux secrets différents générés par Keygen. On note $G_{W_1}$ (resp. $G_{W_2}$) le graphe tatoué à partir d'une paire $(G, \omega_1)$ (resp. $(G, \omega_2)$). Notons $A_{W_1}$ et $A_{W_2}$ leurs matrices d'adjacence en utilisant l'hypothèse de bijection déterministe entre les sommets et ces matrices.

Avec la même bijection, considérons $A'_1$, (resp. $A'_2$) la matrice correspondant à $A_{W_1}$ (resp. $A_{W_2}$) **avant** binarisation. Par définition, la binarisation est faite par seuillage par $av(A)$, la moyenne de la matrice d'adjacence $A$ du graphe original $G$.
$$
\begin{align}
P(G_{W_1} = G_{W_2}) &= P\left(\bigcap_{i,j} (A_{W_1}[i,j] = A_{W_2}[i,j])\right) \nonumber \\
&= P\left(\bigcap_{i,j} \left[ \begin{array}{l} |A'_{1,2}[i,j]| \le av(A) \land A[i,j] = 0 \lor |A'_{1,2}[i,j]| > av(A) \land A[i,j] = 1 \\ \cup |A'_{1,2}[i,j]| \le av(A) \land A[i,j] = 1 \lor |A'_{1,2}[i,j]| > av(A) \land A[i,j] = 0 \end{array} \right] \right). \tag{1}
\end{align}
$$

Ici, la notation $A'_{1,2}$ signifie que le résultat doit être vrai à la fois pour $A'_1$ et pour $A'_2$. Par linéarité de la transformée de Fourier inverse, pour tout entier $n \in \{1, 2\}$ :

Par construction, tous les éléments du secret $\omega$ (et de sa version matricielle $\mathcal{W}$) sont indépendants. La probabilité $P(G_{W_1} = G_{W_2})$ est calculée grâce à la distribution cumulée de $FT^{-1}(\mathcal{W}_n)$ ($n \in \{1, 2\}$).

Premièrement, notons que $FT^{-1}(\tilde{\mathcal{W}}_n) = Z\tilde{\mathcal{W}}_n Z$, où $Z[k,l] = \frac{1}{N}e^{2i\pi kl/N}$. Donc $FT^{-1}(\tilde{\mathcal{W}}_n)$ est une matrice Gaussienne. Ainsi, il est possible de déduire la formule exacte de la distribution de probabilité de la transformée de Fourier inverse en la vectorisant [Fes05]. En effet, soit $\tilde{\mathcal{W}}_n$ la vectorisation de $\mathcal{W}_n$, avec :
$$ \forall k \in \{1, ..., N^2\}, \quad \tilde{\mathcal{W}}_n[k] = \mathcal{W}_n[\lfloor k/N \rfloor, (k-1) \mod N + 1], \text{ où } \lfloor k/N \rfloor \text{ est la partie entière supérieure de } k/N \text{ et } (k-1) \mod N \text{ le reste de la division Euclidienne de } k-1 \text{ par } N. \text{ Alors, } FT^{-1}(\tilde{\mathcal{W}}_n) = \tilde{\mathcal{Z}}\mathcal{W}_n, \text{ avec } \tilde{\mathcal{Z}} = Z \otimes Z \text{ étant le } N^2 \times N^2 \text{ produit de Kronecker de } Z \text{ avec lui-même. Notons } (z_{k,l}) \text{ les coefficients de } Z, \text{ alors pour tout } (k', l') \in \{1, ..., N^2\} : (\tilde{z})_{k',l'} = z_{\lfloor k'/N \rfloor, \lfloor l'/N \rfloor} z_{(k'-1) \mod N+1, (l'-1) \mod N+1}. \text{ Comme } \tilde{\mathcal{W}}_n \text{ est un vecteur Gaussien, } FT^{-1}(\tilde{\mathcal{W}}_n) \text{ est aussi un vecteur Gaussien. Sa moyenne et son écart type sont donnés par la matrice } \tilde{\mathcal{Z}}. \text{ Ainsi, l'unicité des tatouages est bien calculable.} \quad \square $$

**Approximation computationnelle.** Donnons une approximation de l'Équation (1) dans des cas standards (beaucoup de sommets et densités faibles). Comme $av(A) = \frac{|E|}{N^2}$, le seuil de la binarisation est directement lié à la densité du graphe original. Nous testons l'unicité des tatouages pour trois modèles de graphes avec un million d'arêtes et différentes faibles densités dans la Figure 2.

Il y a des collisions (i.e. rupture d'unicité) seulement pour les densités les plus basses, plus petite que 2. Ce n'est pas un problème, car ces graphes sont rares ou atypiques : une densité plus petite que 2 signifie que le graphe a, ou est près d'avoir, des composantes déconnectées.

Au-dessus de 2, il n'y a jamais de collisions (i.e. il y a un unicité). C'est le résultat attendu, car les graphes candidats au tatouage ont généralement des densités plus grandes que 2.

<figure><img src="image_3.png" /><figcaption>**FIGURE 2 :** Taux de réussite (axe y, moyenné sur 3 répétitions) dans l'insertion de tatouage unique en fonction de la densité $|E|/|N|$ du graphe original (axe x). Les graphes testés ont un million de sommets et ont été générés par les modèles de Barabási–Albert (BA), Erdös–Rényi (ER) ou Watts–Strogatz (WS).</figcaption></figure>

# 4 Conclusion

Nous avons montré que les techniques de tatouage d'image peuvent être transférées au tatouage de graphes, ce qui permet d'améliorer considérablement la complexité algorithmique comparé aux travaux précédents. Cela est réalisé en étudiant les transitions entre la matrice d'adjacence binaire d'un graphe à une matrice réelle, et vice versa. Notre méthode, FFG, montre de bonnes performances sur plusieurs mé- triques, en particulier sur l'unicité du tatouage. Pour les travaux futurs, une direction prometteuse consiste à adapter les schémas de tatouage numérique d'image plus récents à notre cadre.
Références

[CKLS97] Ingemar Johansson Cox, Joe Kilian, Frank Thomson Leighton, and Talal Shamoon. Secure
spread spectrum watermarking for multimedia. *IEEE transactions on image processing*,
6(12):1673–1687, 1997.

[EGL+16] David Eppstein, Michael T. Goodrich, Jenny Lam, Nil Mamano, Michael Mitzenmacher, and Manuel Torres. Models and algorithms for graph watermarking. In *Information Security*, pages 283–301, 2016.

[Fes05] Jeffrey Fessler. Introduction to discrete transforms. *Digital Signal Processing and Analysis*, 3, 2005.

[GBKLMS25] Jade Garcia Bourrée, Anne-Marie Kermarrec, Erwan Le Merrer, and Othmane Safsafi. Fast in-spectrum graph watermarks. *arXiv preprint arXiv:2502.04182*, 2025.

[Pet83] Fabien Petitcolas. La cryptographie militaire. *J. des Sci. Militaires*, 9:161–191, 1983.

[ZLZZ15] Xiaohan Zhao, Qingyun Liu, Haitao Zheng, and Ben Y. Zhao. Towards graph watermarks. In *Proceedings of the 2015 ACM on Conference on Online Social Networks*, COSN '15, page 101–112, New York, NY, USA, 2015. Association for Computing Machinery.