Homomorphisme partiel : RSA et Paillier

Le chiffrement totalement homomorphe est difficile à obtenir. Mais bien avant lui, on connaissait déjà des schémas partiellement homomorphes, qui laissent passer une seule sorte d'opération. Et ils sont déjà très utiles.

Homomorphe, mais partiellement

Un schéma partiellement homomorphe autorise un seul type d'opération sur les clairs — soit la multiplication, soit l'addition, mais pas les deux, et sans limite de nombre d'opérations de ce type. Plusieurs schémas classiques, connus de longue date, ont cette propriété « par accident ».

RSA est multiplicativement homomorphe

Reprenons RSA (dans sa version brute, sans remplissage aléatoire). Le chiffrement d'un message m est c = m^e mod n. Prenons deux messages m1 et m2 :

c1 = m1^e mod n
c2 = m2^e mod n

c1 × c2 = (m1^e)(m2^e) = (m1 × m2)^e  mod n

Le produit des deux chiffrés est exactement le chiffré du produit m1 × m2. On a donc multiplié deux nombres cachés sans les connaître. RSA est multiplicativement homomorphe.

Attention : c'est aussi une faiblesse si l'on n'ajoute pas de remplissage (padding). C'est l'une des raisons pour lesquelles le RSA réel n'est jamais utilisé « brut ».

Paillier est additivement homomorphe

Le schéma de Paillier (1999) possède la propriété duale, et bien plus utile en pratique : le produit de deux chiffrés donne le chiffré de la somme des clairs.

D( E(m1) × E(m2) ) = m1 + m2

On multiplie les chiffrés, on obtient (après déchiffrement) l'addition des messages. Paillier est additivement homomorphe.

Schéma	Opération sur les chiffrés	Effet sur les clairs
RSA brut	multiplication	multiplication
Paillier	multiplication	addition

L'application phare : le vote électronique

L'homomorphisme additif de Paillier est parfait pour le vote chiffré. Chaque bulletin est un 0 ou un 1 chiffré. Pour compter les voix, l'urne n'a pas besoin de déchiffrer les bulletins : elle multiplie tous les chiffrés entre eux.

E(1) × E(0) × E(1) × E(1)  =  E(1 + 0 + 1 + 1)  =  E(3)

Le résultat est le chiffré du total des voix. On ne déchiffre qu'une seule fois, à la toute fin, pour révéler le décompte — sans jamais exposer un bulletin individuel. Le secret du vote est préservé.

En résumé

Beaucoup de schémas sont partiellement homomorphes : ils laissent passer une seule opération. RSA brut est multiplicativement homomorphe (c1 × c2 chiffre m1 × m2), tandis que Paillier est additivement homomorphe (le produit des chiffrés donne le chiffré de la somme). Cette dernière propriété rend Paillier idéal pour le vote électronique, où l'on additionne des bulletins chiffrés sans jamais les ouvrir.