Partage visuel de secrets et schémas additifs

Le partage visuel de secret (Naor et Shamir, 1994) divise une image en n transparents, de sorte que la superposition de k transparents révèle l'image secrète, tandis qu'un nombre inférieur de transparents ne révèle rien — même à un adversaire dont les capacités de calcul sont illimitées.

Chaque pixel du secret est agrandi en un bloc de 2x2. Pour un pixel noir : les deux parts reçoivent des motifs complémentaires (une fois superposées, ils sont entièrement noirs). Pour un pixel blanc : les deux parts reçoivent le même motif (une fois superposées, 50 % sont noirs, ce qui donne du gris). L'œil perçoit la différence.

Pour des chaînes de bits : partagez le secret S en générant R_1, R_2, ..., R_{n-1} de manière aléatoire. Définissez R_n = S XOR R_1 XOR ... XOR R_{n-1}. Le XOR des n parts donne S. Tout sous-ensemble de n-1 parts est uniformément aléatoire et ne révèle rien sur S.

Le partage XOR ou additif est de type n-sur-n (toutes les parts sont nécessaires). Le SSS de Shamir est de type k-sur-n (n'importe quelles k parts suffisent). Le partage additif est plus simple et plus rapide ; Shamir gère des seuils arbitraires. Les protocoles MPC utilisent souvent le partage additif pour les opérations arithmétiques.

Pour des secrets entiers : partagez S selon S = s_1 + s_2 + ... + s_n (mod p). Chaque s_i est un élément aléatoire de Z_p. Pour additionner deux valeurs partagées A+B, chaque partie additionne localement ses parts : (a_i + b_i) mod p. Aucune communication n'est nécessaire pour l'addition.

La multiplication de valeurs partagées secrètement nécessite une interaction. La méthode classique des triplets de Beaver consiste à précalculer (a, b, c=ab), un triplet aléatoire partagé. Pour multiplier x*y, révélez (x-a) et (y-b) à toutes les parties (ces valeurs ne révèlent rien sur x et y), puis calculez x*y à l'aide du triplet.

Un schéma linéaire de partage de secret (LSSS) réalise toute structure d'accès monotone. Shamir est un LSSS. Les LSSS sont les éléments de base du chiffrement fondé sur les attributs (ABE) et des systèmes de contrôle d'accès multi-autorités.

Le partage de Shamir groupé place plusieurs secrets dans un seul polynôme : codez k secrets comme coefficients d'un polynôme de degré (n-k). Cela permet d'amortir le coût de communication dans les protocoles MPC lorsque de nombreuses valeurs doivent être partagées simultanément.

Les schémas de partage de base n'offrent aucune protection contre les détenteurs malveillants qui soumettent des parts invalides. Le partage de secret vérifiable (VSS) ajoute des engagements ; le partage de secret robuste ajoute une correction d'erreurs, de sorte que la reconstruction réussit même avec t parts incorrectes.

Cryptographie visuelle : authentification de documents imprimés et bulletins de vote sécurisés. Partage additif : MPC SPDZ et agrégation sécurisée dans l'apprentissage fédéré (Google). Schémas à seuil : sauvegarde de graines de portefeuilles matériels et gestion des clés d'entreprise.

Un schéma à rampe (k,n) est moins puissant : moins de k-d parts révèlent des informations partielles (d niveaux de secret). Il est utilisé lorsque le secret parfait des parts partielles n'est pas nécessaire, mais que l'efficacité du stockage est essentielle. Il permet d'utiliser des parts plus courtes qu'avec Shamir.

Dans un partage additif XOR de type n-sur-n, combien de parts sont nécessaires pour reconstruire le secret ?

La cryptographie visuelle divise les images en transparents ; le partage additif utilise XOR pour les schémas n-sur-n ; Shamir gère les schémas k-sur-n. Le MPC utilise le partage additif avec des triplets de Beaver pour la multiplication. Ensuite : les signatures à seuil et leurs utilisations concrètes.