calcul partagé à base d’encryption probabiliste

par Claude Crépeau

1 Chiffrement probabiliste à la Goldwasser-Micali

Soit n = pq tel que p et q sont premiers et p ≡ q ≡ 3 (mod 4). Donc (\frac{−1}{n}) = +1 mais −1 ∈ NRQ_{n}. La clef publique du système est n et la clef secrète est p, q. L’algorithme de chiffrement d’un bit b est

E(b) = (−1)^{b}r^{2} mod n

où r est choisit au hasard tel que pgcd(r, n) = 1 et le déchiffrement est

D(c) = (b, r) tels que c = (−1)^{b}r^{2} mod n.

Puisque (\frac{−1}{n}) = +1, on aura toujours (\frac{E(b)}{n}) = +1 pour tous b, r, mais également E(b) ∈ RQ_{n} si b = 0 et E(b) ∈ NRQ_{n} si b = 1. On ne connait aucun algorithme efficace pour décider si E(b) est dans RQ_{n} ou NRQ_{n} quand on ne dispose pas des facteurs de n.

2 Transfert inconscient

Alice possède deux bits d’input b_{0}, b_{1} qu’elle met en gage avec Bob par E_{A}(b_{0}), E_{A}(b_{1}). Bob, d’autre part, met en gage son bit de choix c par E_{B}(c) et la future réponse du calcul b_{c} par E_{B}(z) pour un bit z aléatoire. La réponse finale du calcul sera ±E_{B}(z).

\begin{matrix}E_{A}(b_{0}) & E_{B}(c) \\ E_{A}(b_{1}) & E_{B}(z) \end{matrix}

Afin d’obtenir b_{c}, Bob prépare une “question” E_{A}(b_{c} ⊕ z) = E_{A}(b_{c})E_{A}(z) à partir de E_{A}(b_{c}) et z.

\begin{matrix}E_{B}(c) \\ E_{B}(z) \\ E_{A}(b_{c} ⊕ z) \end{matrix}

Si cette question est construite correctement, il suffit à Alice de décrypter cette question par D_{A}(E_{A}(b_{c} ⊕ z)) pour que chacun sache si z = b_{c} ou non: si E_{A}(b_{c} ⊕ z) est un résidu quadratique alors z = b_{c} et E_{B}(z) est la réponse correcte du calcul, sinon −E_{B}(z) est correcte.

Mais pourquoi Alice croirait-elle que la question est construite correctement? Bob peut la convaincre que la question est correcte sans lui faire savoir si elle porte sur b_{0} ou sur b_{1}. À cette fin, Bob choisit des bits aléatoires c_{1}, c_{2}, ..., c_{s}, z_{0}^{1}, z_{0}^{2}, ..., z_{0}^{s}, z_{1}^{1}, z_{1}^{2}, ..., z_{1}^{s}. Il en obtient s paires de questions construites comme suit:

\begin{matrix}E_{B}(c_{1}) & E_{B}(c̄_{1}) \\ E_{B}(z_{c_{1}}^{1}) & E_{B}(z1 ; c̄_{1}) \\ E_{A}(b_{c_{1}} ⊕ z_{c_{1}}^{1}) & E_{A}(bc̄_{1} ⊕ z1 ; c̄_{1}) \end{matrix} \begin{matrix}E_{B}(c_{2}) & E_{B}(c̄_{2}) \\ E_{B}(z_{c_{2}}^{2}) & E_{B}(z2 ; c̄_{2}) \\ E_{A}(b_{c_{2}} ⊕ z_{c_{2}}^{2}) & E_{A}(bc̄_{2} ⊕ z2 ; c̄_{2}) \end{matrix} … \begin{matrix}E_{B}(c_{s}) & E_{B}(c̄_{s}) \\ E_{B}(z_{c_{s}}^{s}) & E_{B}(zs ; c̄_{s}) \\ E_{A}(b_{c_{s}} ⊕ z_{c_{s}}^{s}) & E_{A}(bc̄_{s} ⊕ zs ; c̄_{s}) \end{matrix}

Dans chaque paire, une question porte sur b_{0} et l’autre sur b_{1}. Alice ne sais pas a priori laquelle est laquelle car elle ne connais pas c_{i}.

\begin{matrix}E_{B}(c_{i}) & E_{B}(c̄_{i}) \\ E_{B}(z_{c_{i}}^{i}) & E_{B}(zi ; c̄_{i}) \\ E_{A}(b_{c_{i}} ⊕ z_{c_{i}}^{i}) & E_{A}(bc̄_{i} ⊕ zi ; c̄_{i}) \end{matrix}

Ensuite, pour chacune de ces paires, Alice va choisir soit de vérifier explicitement que ses question sont construites correctement, soit de vérifier qu’elle contient une question équivalente à la question originale. La première possibilité est démontrée en dévoilant les informations suivantes:

\begin{matrix}D_{B}(E_{B}(c_{i})) & D_{B}(E_{B}(c̄_{i})) \\ D_{B}(E_{B}(z_{c_{i}}^{i})) & D_{B}(E_{B}(zi ; c̄_{i})) \\ D_{A}(E_{A}(z_{c_{i}}^{i})) & D_{A}(E_{A}(zi ; c̄_{i})) \end{matrix}

et la seconde, en dévoilant les informations suivantes:

\begin{matrix}D_{B}(E_{B}(c_{i} ⊕ c)) & D_{B}(E_{B}(c̄_{i} ⊕ c)) \\ D_{B}(E_{B}(z_{c_{i}}^{i} ⊕ z)) & D_{B}(E_{B}(zi ; c̄_{i} ⊕ z)) \\ D_{A}(E_{A}(z_{c_{i}}^{i} ⊕ z)) & D_{A}(E_{A}(zi ; c̄_{i} ⊕ z)) \end{matrix}

Dans le cas où Bob a construit la question originale correctement et les s paires de questions correctement, il n’aura aucune difficulté à dévoiler les informations correctes à Alice. Par contre dans le cas contraire, quand Bob n’a pas construit la question originale correctement il devra choisir pour chaque paire de questions s’il la construira correctement ou non.

• s’il construit une paire de questions correctes il ne pourra montrer qu’elle contient une question équivalente à la question originale (qui n’est pas correcte)

• s’il construit une paire de questions incorrectes il ne pourra montrer explicitement que ses question sont construites correctement.

Dans tous les cas, Bob aura au moins une probabilité 1/2 de ne pas savoir satisfaire aux exigeances d’Alice. Bob a donc au plus une probabilité 1/2^{s} de satisfaire Alice si sa question originale n’est pas correctement construite.

2.1 calcul partiel

On utilise le transfert inconscient pour obtenir à partir d’un bit a appartenant à Alice connu publiquement par E_{A}(a) et d’un bit b appartenant à Bob connu publiquement par E_{B}(b), deux nouveau bits a′ appartenant à Alice connu publiquement par E_{A}(a′) et b′ appartenant à Bob connu publiquement par E_{B}(b′), tels que

a ∧ b = a′ ⊕ b′.

Pour ce faire, Alice choisit un bit a′ au hasard puis calcule a′′ = a′ ⊕ a et publie E_{A}(a′), E_{A}(a′′) = E_{A}(a)E_{A}(a′). Alice et Bob font le transfert inconscient avec b_{0} = a′, b_{1} = a′′ et c = b. Soit b′ le bit de sortie obtenu par Bob lors du transfert. Remarquons que si b = 0 alors a ∧ b = 0, et que b′ = a′ et donc a ∧ b = 0 = a′ ⊕ b′. D’autre part, si b = 1 alors a ∧ b = a, et que b′ = a′′ et donc a ∧ b = a = a′ ⊕ b′.

2.2 calcul partagé

Le calcul partagé s’effectue en phases. La phase initiale permet à chaque participant de mettre en gage ses bits d’inputs. À travers toutes les étapes du calcul, chaque bit sera partagé par Alice et Bob de la façon suivante: à chaque bit x sont associés des bits x_{A}, x_{B} tels que x = x_{A} ⊕ x_{B}. Quand Alice veut mettre en gage des bits précis, Bob utilisera x_{B} = 0 et vice versa.

exemple: Si Alice veut mettre en gage un bit b elle annonce à Bob E_{A}(b_{A}) pour b_{A} = b, et Bob annonce E_{B}(b_{B}) pour b_{B} = 0 et montre que c’est bien le cas en révélant D_{B}(E_{B}(0)).

Tous les bits d’input d’Alice et de Bob sont mis en gage ainsi. Alice et Bob s’étant mis d’accord sur un circuit (fait de portes ∧ et ¬) permettant de calculer la fonction voulue il feront ensuite l’évaluation du circuit porte par porte.

Supposons que (b_{A}^{1}, b_{B}^{1}) soit un bit partagé. S’ils veulent en obtenir la négation il suffit de remplacer E_{A}(b_{A}^{1}) par −E_{A}(b_{A}^{1}) ou E_{B}(b_{B}^{1}) par −E_{B}(b_{B}^{1}). Supposons maintenant que (b_{A}^{1}, b_{B}^{1}) et (b_{A}^{2}, b_{B}^{2}) soient deux bits partagés desquels Alice et Bob voudraient obtenir un troisième bit (b_{A}^{3}, b_{B}^{3}) tel que

(b_{A}^{3} ⊕ b_{B}^{3}) = (b_{A}^{1} ⊕ b_{B}^{1}) ∧ (b_{A}^{2} ⊕ b_{B}^{2}).

Il suffit d’observer que (b_{A}^{1} ⊕ b_{B}^{1}) ∧ (b_{A}^{2} ⊕ b_{B}^{2}) = (b_{A}^{1} ∧ b_{A}^{2}) ⊕ (b_{A}^{1} ∧ b_{B}^{2}) ⊕ (b_{B}^{1} ∧ b_{A}^{2}) ⊕ (b_{B}^{1} ∧ b_{B}^{2}). S’ils évaluent ces valeurs par la méthode ci-haut on aura des c_{A}^{1}, c_{A}^{2}, c_{A}^{3}, c_{A}^{4} et c_{B}^{1}, c_{B}^{2}, c_{B}^{3}, c_{B}^{4} tels que

(b_{A}^{1} ⊕ b_{B}^{1}) ∧ (b_{A}^{2} ⊕ b_{B}^{2}) = (c_{A}^{1} ⊕ c_{A}^{2}) ⊕ (c_{A}^{3} ⊕ c_{B}^{1}) ⊕ (c_{B}^{2} ⊕ c_{A}^{4}) ⊕ (c_{B}^{3} ⊕ c_{B}^{4})
= (c_{A}^{1} ⊕ c_{A}^{2} ⊕ c_{A}^{3} ⊕ c_{A}^{4}) ⊕ (c_{B}^{1} ⊕ c_{B}^{2} ⊕ c_{B}^{3} ⊕ c_{B}^{4}).

Il s’agit donc de poser b_{A}^{3} = c_{A}^{1} ⊕ c_{A}^{2} ⊕ c_{A}^{3} ⊕ c_{A}^{4} et b_{B}^{3} = c_{B}^{1} ⊕ c_{B}^{2} ⊕ c_{B}^{3} ⊕ c_{B}^{4}.