Marie Valérie

Linda

Mohamed Fanny

Jacques Ludovic

Merci À Céline

Fënril, Solal Baptiste

Côme

Pierre Thomas

Jacquelin Merci

Arnault

Antoine Valentin

Emma Baptiste

Madeleine Billy Pascal

Vladimir Eve Je Remercie Également Elie

Louise Araxe

Baptiste Roméo

Françoise Louise Merci À Igor

Keywords: PSM, MPC, Boîte-Blanche, ORAM, SSE, Cryptanalyse ⋆ PSM, MPC, White-Box, ORAM, SSE, Cryptanalysis

Dans cette thèse, nous étudions différentes méthodes permettant de faire des calculs sur de l'information cachée. Nous présentons de nouvelles constructions de protocoles, allant de l'amélioration des complexités de l'état de l'art à l'ajout de fonctionnalités. Nous analysons également la sécurité d'autres protocoles, et présentons des attaques dessus.

En premier lieu, nous nous intéressons au Private Simultaneous Messages, où un groupe d'individus souhaite faire apprendre à une entité externe le résultat d'un calcul sur leurs données privées. En utilisant un nouveau cadre, nous montrons de nouvelles constructions avec un coût en communication plus bas que celles déjà existantes. Ensuite, nous étudions des protocoles d'Oblivious RAM, qui dissimulent le motif d'accès qu'un client fait lorsqu'il accède à des données privées stockées sur un serveur non fiable. Nous présentons les premières constructions permettant au client d'enregistrer des objets de tailles arbitrairement différentes. Nous montrons également comment ces constructions permettent de construire des protocoles de Chiffrement Recherchable. Enfin, nous nous intéressons à la cryptographie en boîte-blanche, qui a pour objectif de donner à un appareil non fiable un accès sans restrictions à un algorithme de chiffrement, tout en empêchant la fuite de la clé secrète. Nous présentons une cryptanalyse de la construction de Ranea et al. de CRYPTO 2022, où des cryptosystèmes en boîte blanche sont donnés à partir de chiffrements symétriques basés sur des SPN et ARX. Nous prouvons que ce système n'est pas sûr en présentant une attaque structurelle de récupération de clé.

Introduction en Français

L'Informatique est la science de l'information : les différentes sous-disciplines de cette science étudient les manières de créer l'information, de la stocker, de la transformer. . . La cryptologie est l'étude de l'information secrète. Nous faisons la distinction entre deux sujets en cryptologie : la cryptographie cherche à cacher de l'information, la cryptanalyse vise à récupérer de l'information cachée. Dans cette thèse, nous présentons des résultats s'intégrant dans chacun de ces deux sujets. Un fil conducteur de notre travail concerne des défis contemporains, qui existent car nous vivons dans une époque avec internet, des accès à distance et du calcul délégué. Cette ère est parfois appelée l'Âge de l'Information.

Avant le début de cet âge de l'information (qui commence à se former après la Seconde Guerre Mondiale), la cryptologie était utilisée pour cacher un message (par chiffrement), devant rester masqué jusqu'à ce que le destinataire retire le voile servant à dissimuler le message (le déchiffrement), et puisse le lire. Les usages les plus courants étaient alors de transmettre des ordres en temps de guerre, de comploter entre alliés politiques ou d'aider des actes d'espionnage. Le fait que les messages puissent rester masqués était crucial : les États-Unis ont rejoint la Triple-Entente pendant la Première Guerre Mondiale en grande partie grâce à la décryption par des cryptanalystes britanniques du télégramme Zimmerman, où l'Allemagne demandait au Mexique de déclarer la guerre à leur voisin du Nord. Marie Stuart, reine d'Écosse, a été exécutée à cause de son implication dans un complot visant à assassiner la reine Elizabeth Ière, découverte lorsque que le chiffre qu'elle utilisait a été décrypté. Ethel et Julius Rosenberg ont transféré les plans d'armes atomiques à l'Union Sovétique. Leur responsabilité a été découverte par le programme secret Venona, où des cryptanalystes américains ont brisé le chiffrement utilisé par les soviétiques.

Une cryptographie robuste était une question de vie ou de mort. Aujourd'hui, bien qu'il y ait toujours des guerres, complots d'assassinat et cercles d'espionnage, l'utilisation de la cryptographie est bien plus répandue. Le fil d'Ariane de données que nous laissons derrière nous dans la vie de tous les jours au XXIème siècle est immense, et fait fuiter beaucoup d'information sur nous. C'est en partie fait intentionnellement lorsque l'on publie quelque chose sur un réseau social. Cependant, l'écrasante majorité de cette fuite de données trouve son origine en coulisses : des métadonnées fuitent dès que l'on fait le moindre mouvement dans le cyberespace.

Imaginons un arbitre au milieu d'un terrain de football, tourné vers la moitié Est du stade. Soudainement, un ballon -frappé dans la moitié Ouest -entre dans son champ de vision et termine sa course sur le gazon. Si cet arbitre possède quelques connaissances en mécanique Newtonienne, il peut -étant donné deux positions distinctes occupées par le ballon à deux instants différents -calculer la position exacte à partir de laquelle le ballon a été lancé.

CRYPTOGRAPHIE SYMÉTRIQUE ET ASYMÉTRIQUE

N'importe qui peut faire la même chose en regardant les effets de bord d'une action en ligne, et déduire de ces métadonnées de l'information qui aurait potentiellement dû rester secrète. Une des questions qu'un cryptographe peut se poser est "comment puis-je tirer un ballon de football sans que quiconque ne puisse retracer cet événement à moi ?"

Cryptographie symétrique et asymétrique

Nous présentons maintenant deux personnages bien connus dans le folklore cryptologique : Alice souhaite envoyer de l'information sensible à son ami Bob, en passant par un canal non-sécurisé (i.e. quelqu'un est susceptible d'écouter le trafic). Pendant longtemps la cryptographie était limitée au chiffrement symétrique : Alice et Bob partagent une clé secrète K, Alice chiffre son message m : elle utilise la clé pour transformer m en un chiffré c initelligible. Elle envoie c à Bob, qui quant à lui déchiffre c à l'aide de K, et obtient le message originel m.

Ce procédé -aussi appelé chiffrement à clé secrète ou à clé privée -nécessite un accord préalable entre Alice et Bob sur la clé K qu'ils se partagent. C'est une limite, en particulier si Alice et Bob ne se connaîssent ni d'Ève ni d'Adam et doivent établir un premier contact de manière sécurisée.

La solution à ce problème a été trouvée dans les années soixante-dix : en utilisant de la cryptographie asymétrique, Bob peut publier sa clé publique P K, celle-ci est utilisée par Alice pour chiffrer m. Elle envoie ensuite le chiffré c à Bob, qui le déchiffre avec sa clé secrète SK.

Également appelé chiffrement à clé publique, ce nouveau genre de protocole ouvre la voie vers la cryptographie moderne : Alice et Bob peuvent utiliser des protocoles à clé publique, ainsi que d'autres outils, pour faire une "poignée de main" numérique et se mettre d'accord sur une clé symétrique, Alice peut aussi signer ses messages afin de prouver qu'elle en est bien l'auteure, elle peut assurer leur intégrité afin d'empêcher quiconque d'en altérer le contenu. . . Dans cette thèse, nous étudions trois différents types de protocoles en lien avec le chiffrement symétrique et asymétrique, et nous apportons des contributions dans leurs disciplines respectives. Un fil conducteur entre ces sujets est de faciliter les calculs délégués sécurisés.

Laisser le calcul à un tiers

La découverte de la cryptographie à clé publique va de pair avec l'arrivée de l'Âge de l'Information. Avant l'utilisation répandue d'ordinateurs connectés les uns aux autres dans un réseau, la cryptographie symétrique était suffisante pour ses applications militaires et diplomatiques. Il est logique que les membres d'une même nation (par exemple deux généraux discutant de stratégies) partagent la même clé secrète. Des précautions sont en place pour éviter de révéler cette clé à l'ennemi, mais il n'apparaît pas comme indispensable de créer de toutes nouvelles bases théoriques pout ça. Une anecdote illustrant cette attitude est le fait que des cryptologues du GCHQ -une agence de renseignements britannique -ont inventé un algorithme similaire au cryptosystème RSA (l'algorithme à clé publique le plus utilisé aujourd'hui) entre cinq et dix ans avant la publication de celui-ci. L'idée a été mise de côté à cause de son manque d'applications militaires.

CHAPTER 1. INTRODUCTION EN FRANÇAIS

Actuellement, nous avons accès à une grande puissance de calcul et de la cryptographie disponible publiquement. Alice peut choisir parmi des dizaines voire des centaines de cryptosystèmes pour discuter en sécurité avec Bob. Mais les besoins d'Alice ont aussi évolué : elle peut souhaiter vouloir faire plus que simplement bavarder avec ses amis. Elle pourrait avoir un grand jeu de données sensibles mais pas la place pour les stocker. Elle pourrait aussi vouloir faire des calculs sur ces données mais sans posséder une puissance de calcul adéquate. Heureusement, l'offre s'est adaptée à sa demande : elle peut externaliser le stockage et le calcul dont elle a besoin. Si Alice ne fait confiance à personne, comment ses données peuvent-elles rester sécurisées ?

Laisser une entité externe s'occuper de calculs sur des données confidentielles peut se faire de plusieurs façons. Le chiffrement totalement homomorphe est une solution généraliste pour permettre de faire des calculs sur des données chiffrées : n'importe qui peut calculer une fonction arbitraire sur un ensemble de chiffrés, resultant en un chiffré de la sortie de la fonction appliquée sur les messages en clair d'origine. Le chiffrement totalement homomorphe nécessite une grande capacité de calcul et de stockage mais demeure une bonne solution prête à l'emploi. Alice pourraît aussi obfusquer un programme avec de l'obfuscation indistinguable, c'est-à-dire (en grossissant le trait) le transformé de telle sorte que quelqu'un faisant tourner le programme obfusqué obtient les mêmes paires entrée-sortie qu'avec le programme d'origine, mais sans savoir comment les rouages de ce programme fonctionnent.

Nous allons maintenant nous intéresser à différentes propositions qui permettent de partager de l'information secrète entre plusieurs parties. Nous commencerons avec un cas particulier de calcul multi-partie appelé Private Simultaneous Messages1 (PSM), où un arbitre calcule une fonction publique prenant en entrée des valeurs secrètes possédées par les parties avec lesquelles il intéragit. Puis nous verrons comment une personne peut stocker et accèder à ses données de manière sécurisée sur un serveur non-fiable en utilisant des protocoles d'Oblivious RAM (ORAM). Enfin, nous étudierons la Cryptographie Boîte-Blanche, où un algorithme à clé secrète est fait pour être évalué publiquement, et nous montrerons une attaque sur un tel protocole.

Différentes saveurs de calcul délégué

Durant ma thèse, j'ai travaillé sur des sujets divers dans différents domaines de la cryptologie. Je présente dans ce manuscrit des résultats dans trois de ces sujets, qui font partie du contenu de publications. J'introduis et présente une motivation derrière ces sujets dans cette section. Dans la suivante, je donnerai un résumé des contributions qui ont été apportées.

Calculer avec d'autres

Mettre les données de différentes parties en commun afin d'augmenter sa connaissance est souvent nécessaire. Un exemple typique de notre domaine est le problème des millionaires 1.3. DIFFÉRENTES SAVEURS DE CALCUL DÉLÉGUÉ de Yao : Alice et Bob veulent savoir lequel parmi eux est le plus riche mais ils ne veulent pas révéler précisément le montant de leurs fortunes [START_REF] Andrew | Protocols for secure computations (extended abstract)[END_REF]. Ce problème peut sembler superficiel, mais l'existence d'un protocole qui le résout est en réalité significatif. Nous pouvons imaginer une autre situation : une entreprise pharmaceutique cherche à collecter des données l'assistant dans le développement d'un nouveau traitement qui pourrait aider les patients souffrant d'une maladie. Les hôpitaux ont des grandes quantités de données potentiellement utiles sur leurs patients (par exemple l'âge, le sexe, le poids, le taux de mortalité . . . ), néanmoins laisser carte blanche à une entreprise pour utiliser les données des patients est une catastrophe de sécurité en devenir, et c'est à juste titre illégal dans la plupart des pays. La solution naïve serait de simplement anonymiser les données (i.e. en ôtant les noms d'une base de données sans la modifier davantage, un procédé aussi appelé "pseudonymiser"), cela ne fonctionne pas [NS06, Swe00]. Il peut rester assez de bits d'information dans une telle base de données pour identifier personnellement les personnes qui en font partie. Nous pouvons nous tourner vers la cryptographie pour notre salut : dans ce cas toute l'information est cachée, pas seulement les noms et lieux de naissance, qui sont des identifiants suffisants mais pas nécessaires.

Si nous chiffrons toutes ces données, comment pouvons-nous faire des calculs dessus ? Une façon de le faire est par le calcul multipartie sécurisé (Multi-Party Computation en anglais, ou MPC).

Dans un protocole MPC, des parties P 1 , . . . , P k détiennent chacune une entrée secrète x 1 , . . . , x k , et elles souhaitent calculer le résultat d'une fonction (publique) f , de façon à ce que chaque partie apprenne f (x 1 , . . . , x k ) et aucune autre information sur les autres entrées. Le MPC recouvre un vaste domaine de protocoles, avec différentes exigences de sécurité. Pour aller plus loin, cette excellente étude par Yehuda Lindell plonge dans les détails du MPC [START_REF] Lindell | Secure multiparty computation (mpc)[END_REF]. Nous nous intéresserons dans cette thèse à une instance minimaliste du MPC appelée Private Simultaneous Messages (PSM).

Là, en plus des k parties, nous ajoutons un arbitre qui sera celui qui exécutera le calcul. Le protocole est non-interactif : chaque partie envoie un unique message à l'arbitre et les parties ne communiquent pas entre elles. Elles partagent uniquement une chaîne de caractères aléatoire en commun qu'elles utilisent pour cacher leurs entrées à l'arbitre. Ce protocole suppose que seul l'arbitre puisse être corrompu, les autres parties demeurent honnêtes. Les entrées des parties seront cachées au sens de la théorie de l'information (aussi appelé sécurité parfaite) : peu importe la puissance de l'adversaire, aucune information ne peut être obtenue sur les entrées en étudiant les messages reçus par l'arbitre.

Stocker ses données ailleurs

La quantité de données produites augmente indéfiniment et la capacité à faire des calculs sur ces données (par exemple pour entraîner un model de Machine Learning) a une importance cruciale. Bien que la capacité de stockage ait également augmenté, l'espace requis pour entreposer la quantité de données nécessaires à la réalisation de telles tâches est hors de la portée de la plupart des particuliers ou des petites entrepises. Pour externaliser le stockage de ces données de manière sécurisée, la solution naïve serait de chiffrer les données et de télécharger les chiffrés vers le cloud. Cette méthode est aussi sûre que l'est le système symétrique utilisé (i.e. aussi sécurisé que faire se peut si l'on choisit judicieusement), ce qui est une bonne nouvelle si on n'est intéressé que par la sécurité de nos données, quelqu'en soit le coût. Mais c'est comme dire que la meilleure façon d'éviter un accident de voiture est de ne jamais mettre le contact : c'est techniquement correct, mais CHAPTER 1. INTRODUCTION EN FRANÇAIS ça ne nous fait pas avancer. Si on chiffre un téraoctet de données avec AES et que nous le stockons, nous devrons télécharger un téraoctet de chiffré même si on désire ne lire qu'un octet du message clair. Cela devient rédhibitoire dès que l'on veut mettre cette solution en pratique dans une application de la vie réelle.

Pour avoir le beurre et l'argent du beurre, pourquoi ne pouvons-nous pas juste chiffrer de "petits" morceaux de nos données, stocker ces chiffrés en ligne et ne télécharger que certains morceaux lorsque nous en avons besoin ? C'est possible, mais cette solution apporte de nouveaux problèmes. En premier lieu, nous devons indexer les morceaux que nous stockons et cela a un prix, mais nous pouvons gérer ceci de plusieurs manières. En second lieu, le fait que nous accédons à un morceau en particulier révèle en soi de l'information sur les données auxquelles on accède et la façon dont on les utilise. Imaginons un enfant allant se servir un biscuit dans la cuisine, et cachant celui-ci derrière son dos lorsque sa mère vient le voir. Bien entendu, elle ne voit pas ce qu'il tient dans la main, cependant le fait qu'il cache quelque chose, dans la cuisine, alors qu'elle lui avait formellement interdit de manger un autre biscuit, lui permet de deviner ce que son fils lui cache.

Pour empécher qui que ce soit de deviner ce que l'on fait avec nos données, les algorithmes d'Oblivious RAM (ORAM) ont été inventés dans les années quatre-vingt-dix : ils cachent le motif d'accès que l'on fait lorsque l'on envoie une requête pour des données. Originellement, le model ORAM concernait la vraie RAM : si un processeur envoie des requêtes vers des données (chiffrées) dans sa mémoire vive, quelqu'un analysant le trafic pourraît étudier le motif d'accès et apprendre de l'information confidentielle sur le calcul en train d'être fait. Récemment, ce cadre a été appliqué dans le cas de communications entre client et serveur dans le cloud. Néanmoins, il existe toujours des applications dans le modèle initial de la RAM, ou bien dans des mélanges en ligne et hors ligne, par exemple lorsque des calculs ont lieu dans des enclaves sécurisées sur un serveur à distance [START_REF] Connell | Technology deep dive: Building a faster oram layer for enclaves[END_REF].

Dans cette thèse, nous donnons de nouvelles constructions de protocoles d'ORAM et les utilisons pour construire du chiffrement symétrique recherchable (Searchable Symmetric Encryption ou SSE en anglais). Avec le SSE, il est possible de faire des recherches par mot-clé sur une base de données chiffrée.

Laisser quelqu'un d'autre chiffrer

Dupliquer et partager du contenu numérique est devenu un jeu d'enfant avec la démocratisation de l'accès aux ortinateurs et à internet. Le piratage numérique a fait ses début à l'époque des cassettes audio, mais avec la disponibilité de lecteurs CD bon marché dans les années quatre-vingt-dix et l'arrivée des torrents pair à pair, les détenteurs de propriétés intellectuelles (en particulier les labels de musique) se sont mis à prendre note : comment une entreprise peut-elle rester dans profitable si un consommateur peut acheter un produit et des millions d'acheteurs potentiels décident de le télecharger à la place ? Aujourd'hui, le téléchargement de contenu sur internet nous paraît évident cependant ce n'a pas toujours été le cas, en raison de la crainte que le télechargement de musique saborde toute l'industrie musicale. Il a fallu convaincre les industriels de permettre le téléchargement de morceaux sur une plate-forme numérique sécurisée.

Parmi les solutions proposées, une nouvelle technologie était présentée pour la gestion des droits numériques (DRM), où un utilisateur pourraît consommer le média (par exemple écouter une chanson), mais sans réellement posséder le MP3. Cette technologie s'appelle la Cryptographie Boîte-Blanche, et a participé à ce pourquoi nous avons iTunes, Spotify et Netflix aujour'hui [START_REF] Cioschi | White-Box Cryptography: A Time-Security Trade-Off for the SPNbox Family[END_REF].

1.4. RÉSUMÉ DES RÉSULTATS L'objectif de la cryptographie boîte-blanche est de donner accès à un agent non-fiable à un algorithme de chiffrement opérant avec une clé secrète : la clé est cachée dans l'implémentation de l'algorithme. Avec ce système, l'agent ne doit pas être en mesure de retrouver la clé, même avec un accès en boîte blanche (i.e. l'agent a le contrôle total des rouages de l'algorithme). Idéalement, un morceau de musique serait chiffré de telle manière que la seule façon de l'écouter serait d'utiliser l'algorithme boîte-blanche : l'agent ne peut pas obtenir le fichier MP3 déchiffré.

La promesse d'une contre-mesure permettant de sauvegarder du contenu numérique contre le piratage a donné la confiance nécessaire aux parties prenantes pour permettre à leurs produits d'être vendus en ligne et téléchargés ou streamés. Cela n'a pas freiné les tentatives de piratage : il reste possible d'utiliser l'astuce datant de l'époque des cassettes de simplement enregistrer une chanson pendant qu'elle est jouée. Des attaques en tout genre sur les DRM sont apparues en réponse, il y a même une course à l'armement dans les communautés en ligne de piratage (par exemple la Scène Warez), pour retirer les protections anti-piratage des jeux vidéos [Wik23].

Les attaques qui nous intéressent en particulier sont les cryptanalyses de systèmes en boîte blanche. Nous présentons une telle attaque dans ce manuscrit.

Résumé des résultats

Nous avons désormais une idée générale de certains domaines de la cryptographie. Dans cette section, je présente les avancées que nous avons produites dans ces sujets.

De nouvelles bornes supérieurs sur la complexité des PSM

Dans un protocole PSM, il y a k parties P 1 , . . . , P k et un arbitre Ref . Soit N ∈ N. Pour tout i ∈ [k], chaque partie P i détient une entrée secrète x i ∈ [N ], et chacune envoie un message m i à l'arbitre, de façon à ce que ce dernier puisse faire un calcul sur les messages qui donne f (x 1 , . . . , x k ) où f est une fonction publique. Les parties sont supposées honnêtes. Nous nous intéressons en particulier à la complexité de communication du protocole, i.e. le nombre de bits que chaque partie doit envoyer afin que le calcul se déroule correctement. Nous regardons aussi la complexité d'aléas : combien de bits aléatoires les parties doivent partager.

Le modèle PSM a été présenté pour la première fois en 1994 par Feige, Kilian et Naor [START_REF] Feige | A minimal model for secure computation (extended abstract)[END_REF] pour le cas à deux parties (bien que celui à k parties ait été évoqué dans l'annexe), puis a été étendu au cas multi-parties dans le travail d'Ishai et Kushilevitz [START_REF] Ishai | Private simultaneous messages protocols with applications[END_REF]. Depuis, de nouvelles bornes inférieures et supérieures ont été découvertes : dans le cas à deux parties, [START_REF] Feige | A minimal model for secure computation (extended abstract)[END_REF] présente un protocole avec une complexité de communication en O(N ), puis [START_REF] Beimel | On the cryptographic complexity of the worst functions[END_REF] montre qu'une complexité en O( √ N ) est possible. Dans [START_REF] Beimel | The complexity of multiparty PSM protocols and related models[END_REF], un coût de O(poly(k) • N k/2 ) a été trouvé pour tout k ≥ 2, améliorant le coût en O(poly(k) • N k-1 ) de [START_REF] Feige | A minimal model for secure computation (extended abstract)[END_REF]. D'autres coûts encore plus bas sont trouvés pour k ≤ 5. Cette publication a aussi proposé des protocoles avec une complexité déséquilibrée : certaines parties envoient plus d'information que d'autres.

S'agissant des bornes inférieures, [START_REF] Feige | A minimal model for secure computation (extended abstract)[END_REF] montre une limite de 3k -O(1) bits, qui a été étendue en une borne inférieure de 3k -O(log(k)) par [START_REF] Applebaum | The communication complexity of private simultaneous messages, revisited[END_REF]. Pour k = ω(log(n)), cette borne inférieure de Ω(n) est améliorée en une borne de Ω(k 2 n/ log(kn)) par [BR22].

À l'issue d'une collaboration avec Tianren Liu [START_REF] Assouline | Multi-party psm, revisited: Improved communication and unbalanced communication[END_REF], nous montrons de nouvelles 2 ). Nous présentons un nouveau cadre dans lequel nous construisons ces PSM au Chapitre 3. Plus précisément, nous décrivons une manière de créer des codages aléatoires, les PSM en étant des instanciations particulières. En bref, un codage aléatoire f : X × R → Ŷ d'une fonction f : X → Y x → f (x) est tel que pour r ∈ R une valeur aléatoire, f (x, r) contient suffisamment d'informations pour récupérer f (x) et rien de plus concernant x. Les PSM en sont un cas particulier : en considérant x comme x = (x 1 , . . . , x k ), les messages m 1 , . . . , m k reçus par l'arbitre constituent un codage aléatoire (où r est l'aléa partagé) de f (x 1 , . . . , x k ).

L'idée derrière ce nouveau cadre vient de [START_REF] Beimel | On the cryptographic complexity of the worst functions[END_REF] : chaque entrée x i est représentée par son vecteur identité z i , où la i-ème coordonnée de zi est 1 et les autres sont 0. Ensuite, nous scindons ce vecteur en deux : z i = y 2i ⊗ y 2i+1 . Nous donnons des exemples simples de constructions de PSM pour 3 et 5 parties en utilisant cette technique au Chapitre 3.1.2. Comme amuse-bouche, voici un exemple très simple de PSM à 2 parties en utilisant ce produit tensoriel des entrées.

Alice et Bob souhaitent s'engager dans un protocole PSM avec l'arbitre. Comme expliqué précédemment, nous scindons les entrées en deux, de façon à ce que les parties envoient deux entrées de taille N 1/2 .

• Alice et Bob partageront l'aléa suivant :

a 1 , a 2 , b 1 , b 2 $ ← -{0, 1} √ N . • L'entrée d'Alice x est telle que x = x 1 ⊗ x 2 , avec x 1 , x 2 ∈ {0, 1} √ N .
• De façon similaire, l'entrée de Bob est y = y 1 ⊗ y 2 . Maintenant, avant de voir comment le protocole fonctionne, Alice et Bob vont construire individuellement certains polynômes privés :

• Alice calcule q 1 , q 2 de taille O( √ N ) tels que

⟨q 1 , z 1 ⟩ = ⟨p, (x 1 + a 1 ) ⊗ (x 2 + a 2 ) ⊗ (z 1 ⊗ b 2 + b 1 ⊗ b 2 )⟩ et ⟨q 2 , z 2 ⟩ = ⟨p, (x 1 + a 1 ) ⊗ (x 2 + a 2 ) ⊗ b 1 ⊗ z 2 ⟩. • Bob calcule h 1 , h 2 de taille O( √ N ) tels que ⟨h 1 , z 1 ⟩ = ⟨p, (z 1 ⊗ a 2 + a 1 ⊗ a 2 ) ⊗ y 1 ⊗ y 2 ⟩ et ⟨h 2 , z 2 ⟩ = ⟨p, a 1 ⊗ z 2 ⊗ y 1 ⊗ y 2 ⟩.
Le protocole fonctionne de la façon suivante :

• Alice envoie (x 1 + a 1 , x 2 + a 2 ) à Ref . • Bob envoie (y 1 + b 1 , y 2 + b 2 ) à Ref .
• Alice et Bob s'engagent dans 4 instances d'un protocole PSM pour l'évaluation de polynômes comme dans la section précédente, de façon à ce que Ref puisse En premier lieu, le client permute de manière sécurisée (oblivious permutation dans la langue de Turing) les premiers N + √ N objets et garde une représentation de la permutation secrète π. Le client effectue ensuite plusieurs accès. Le j-ème accès à un objet (par exemple, le i-ème objet) consiste en :

apprendre γ = ⟨q 1 , y 1 ⟩ + ⟨q 2 , y 2 ⟩ + ⟨h 1 , x 1 ⟩ + ⟨h 2 , x 2 ⟩. • Ref calcule ⟨F, (x 1 + a 1 ) ⊗ (x 2 + a 2 ) ⊗ (y 1 + b 1 ) ⊗ (y 2 + b 2 )⟩ -γ.
• La lecture de tout le refuge de taille √ N pour trouver l'objet.

• Si trouvé : le client accède à l'objet factice suivant. Dans les premières N + √ N cellules, il est à l'index π(N + j).

• Si non trouvé : le client accède à l'objet à son véritable emplacement à l'index π(i).

• Le client met finalement à jour la valeur de l'objet i, le rechiffre et le stocke dans le refuge.

Après au plus √ N accès, le client met à jour les valeurs des objets réels dans les premières N + √ N cellules à partir de celles du refuge en utilisant un oblivious sort. Cette méthode a ensuite été généralisée dans le paradigme ORAM hiérarchique dans le même article. Ici, il y a plusieurs niveaux, avec des tableaux doublant leur taille à chaque niveau. Les plus petits tableaux sont réorganisés plus fréquemment que les plus grands. Cela a un coût polylogarithmique. Depuis, des améliorations ont été apportées à la technique hiérarchique dans [AKL + 18], conduisant au protocole "OptORAMa" qui atteint la borne inférieure de log(n) en complexité de communication. Cependant, cette méthode n'est pas réalisable en pratique. Les implémentations des protocoles ORAM sont généralement basées sur l'algorithme à base d'arbre, appelé tree-ORAM.

Le tree-ORAM le plus connu est Path-ORAM [SvS + 13a], que nous présentons en détail au Chapitre 4.5.2. Un tree-ORAM encore plus simple, qui ne nécessite pas d'avoir un client avec un stockage de taille ω(log(N )), s'appelle "Simple ORAM" [START_REF] Chung | A simple ORAM[END_REF]. Ici, le stockage du serveur est structuré sous forme d'arbre binaire complet de profondeur L = ⌈log(N )⌉, où chaque noeud, appelé panier, peut stocker jusqu'à log(N ) objets. Le client ne connaît pas la position exacte de chaque objet, mais connaît la feuille de l'arbre qui identifie le chemin où se trouve cet objet, allant de la racine à cette feuille. Ainsi, pour accéder à l'objet i-ème, le client commence par calculer la feuille l associée à cet objet (à partir d'une fonction de position), puis lit (et rechiffre) le contenu de chaque panier CHAPTER 1. INTRODUCTION EN FRANÇAIS présent sur le chemin de la racine à la feuille l. Lorsque l'objet recherché est rencontré, le client le télécharge, effectue une opération de lecture ou d'écriture, et sélectionne de façon uniformément aléatoire une nouvelle feuille à associer à cet objet. Cet objet est enfin écrit là où on trouve de la place, sur le sous-chemin à l'intersection de l'ancien chemin et du nouveau (ce dernier correspond à la feuille nouvellement sélectionnée).

Dans un travail réalisé avec mon directeur de thèse Brice Minaud [START_REF] Assouline | Weighted oblivious ram, with applications to searchable symmetric encryption[END_REF] au Chapitre 4, nous avons étudié comment permettre aux ORAM d'accueillir des objets pondérés, i.e. de tailles variables (weighted-ORAM). Nous avons une transformation universelle réalisant cette fonctionnalité, permettant ainsi à tous les ORAM de fonctionner avec des objets pondérés. Néanmoins, elle nécessite un coût asymptotiquement plus élevé. Notre résultat principal est une transformation générique asymptotiquement équivalente à l'ORAM de départ, s'appliquant à la plupart des tree-ORAM utilisés en pratique. L'idée générale est de considérer le poids total des objets : chaque objet a une taille ≤ B bits, supposons que le serveur héberge un poids total d'au plus N •B. Dans le cas standard (non pondéré), les paniers ne pouvaient stocker qu'un nombre borné Z d'objets. Maintenant, nous permettons aux paniers de stocker un poids total de Z • B bits. Nous pouvons placer un objet dans un panier tant que la limite de Z • B n'est pas atteinte. Le panier est considéré comme plein si le poids total dépasse Z • B (il sera toujours en dessous de (Z + 1) • B). Cette modification est naturelle et efficace. La difficulté principale est de montrer qu'elle conserve l'exactitude (le fait que l'ORAM se comporte sans échecs) : en effet, les preuves d'exactitude de tree-ORAM sont notoirement complexes, même sans des objets pondérés. Pour pallier ceci nous utilisons un nouvel argument de Schur-convexité qui correspond parfaitement au cadre.

Nous construisons également du chiffrement recherchable en utilisant ces ORAM pondérés.

Cryptanalyse structurelle de systèmes en boîte blanche basés sur des protocoles ARX

Étudions la façon dont un algorithme de chiffrement symétrique Enc, pour une clé secrète K, fonctionne lorsqu'un adversaire y a accès. L'adversaire fait une requête pour l'entrée x et obtient la sortie y = Enc K (x). Le modèle de cryptographie en boîte noire consiste à se représenter un algorithme comme une fonction opaque, transformant les entrées en sorties sans rien expliquer sur le fonctionnement interne. On dit d'un adversaire essayant d'attaquer un système cryptographique en boîte noire qu'il a un accès oracle à ce système. Évidemment, ce n'est pas ainsi que cela fonctionne dans le monde réel : certaines informations fuitent. Les calculs ne sont pas instantanés, donc le temps nécessaire pour produire une sortie peut révéler quelque chose sur la clé secrète [START_REF] Paul | Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems[END_REF]. Un attaquant plus raffiné peut étudier les perturbations électromagnétiques autour de l'appareil effectuant les calculs, ou peut faire des mesures sur les lignes de courant pour étudier la consommation électrique utilisée pour calculer Enc K [START_REF] Gandolfi | Electromagnetic analysis: Concrete results[END_REF]. Dans ce cas, on dit que l'attaquant a des informations par un canal auxiliaire. Ce modèle est également appelé boîte grise.

Dans le modèle en boîte blanche, l'attaquant dispose d'une implémentation de Enc K . Il lui est possible d'en étudier le fonctionnement interne et de la modifier. La cryptographie en boîte blanche est l'étude de ce modèle, c'est-à-dire des moyens de produire une implémentation de Enc K de façon à ce que l'adversaire ne puisse pas obtenir d'informations sur K. La première implémentation en boîte blanche d'un cryptosystème (AES) a été présentée dans [START_REF] Chow | White-box cryptography and an AES implementation[END_REF], on parle de cadre CEJO. Ici, un chiffrement est décomposé en une série de tables de correspondance composées. Elles sont chacune 1.4. RÉSUMÉ DES RÉSULTATS obfusquées en composant leurs entrées et sorties avec des permutations aléatoires. La permutation de sortie d'une table est annulée par celle à l'entrée de la table suivante (en prenant la permutation inverse). L'idée derrière ce modèle est la suivante : un réseau de substitution-permutation (SPN) comme AES est représenté par une composition de couches non linéaires :

Enc K = E 1 • . . . • E n . Le système en boîte blanche est composé d'une suite de couches (E ′ i ) i∈[n] = (O i • E i • I i ) i∈[n] où O i = I -1 i+1 pour tout i ∈ [n -1]. La paire (I 1 , O n ) est
appelée les encodages externes. Les autres encodages sont appelés encodages internes. Le chiffrement en boîte blanche est évalué par

Enc ′ K = E ′ 1 • . . . • E ′ n = I 1 • Enc K • O n . Plusieurs implémentations de cette méthode ont été cryptanalaysées dans [RW19, MDFK15, ABMT18, AMR19].
Une nouvelle proposition pour les chiffrements en boîte blanche a été présentée à CRYPTO 2022 par Ranea et al. [START_REF] Ranea | Implicit whitebox implementations: White-boxing ARX ciphers[END_REF], en utilisant des implémentations implicites. Ici, la fonction de tour F d'un chiffrement par bloc est représentée par une fonction P telle que ∀x, y, P (x, y) = 0 ⇐⇒ F (x) = y. P doit être telle que pour tous les x, la fonction y → P (x, y) soit affine. Ce nouveau cadre permet une plus grande souplesse dans le choix de la fonction de tour, ce qui fait de ce cryptosystème en boîte blanche le premier capable de traiter les chiffres ARX (Addition-Rotation-XOR), tels que Speck [BSS + 13].

Avec Brice Minaud et Antoine Houssais, nous montrons au Chapitre 5 une attaque structurelle sur ce modèle : il peut être attaqué dans un contexte en boîte noire. Nous utilisons une technique similaire à celle de [START_REF] Minaud | Key-recovery attacks on ASASA[END_REF] lors de l'attaque des implémentations implicites des cryptosystèmes SPN : bien que la première couche soit désormais non-linéaire, alors qu'elle n'était qu'affine auparavant, il est possible de reconstruire cette couche avec un nombre calculatoirement faisable d'échantillons. Nous montrons également une attaque sur les implémentations de cryptosystèmes ARX. Nous suivons la même trame de décomposition du programme couche par couche, reconstruisant ainsi chaque encodage.

En substance, l'idée est la suivante : considérons un cryptosystème ARX simple qui prend en entrée t = (x||y) ∈ {0, 1} n , où x, y ∈ {0, 1} n/2 , et donne en sortie (x||x ⊞ y) où ⊞ est l'addition modulaire dans Z 2 n (la clé secrète apparaîtra dans les couches externes). Nous avons trois couches : I la couche non-linéaire de faible degré au niveau de l'entrée, M est l'addition modulaire telle que décrite plus haut et A est la couche affine au niveau de la sortie. L'attaquant fournit en entrée a et obtient en sortie b = A • M • I(a). Notons t = (x||y) par N (a) et z = x ⊞ y. On remarque que, pour tout i ∈ [n/2], z i = x i + y i + c i , où c i est la retenue de l'addition qui donne z i-1 (et c n/2 = 0). En utilisant cette relation de récurrence, nous sommes en mesure de reconstruire l'intégralité de l'addition modulaire. Cela nous permet ensuite de décomposer la couche A. Puis, nous pouvons décomposer les couches restantes M et I en résolvant certaines équations polynomiales.

Computer Science ("Informatique" in French) is the science of information: different subdisciplines of Computer Science study how to create information, how to store it, how to transform it . . . Cryptology is the study of secret information. We distinguish two subjects in cryptology: cryptography regards how we hide information, cryptanalysis deals with recovering hidden information.

In this thesis, we present results pertaining to both of these subjects. A common thread is that our work concerns itself with contemporary challenges, that exist because we live in the age of the Internet, remote accesses and delegated computing. This era is sometimes called the Information Age.

Before this age of information (which begins to hatch after WWII), cryptology was used to hide a message (encryption), designed to stay hidden until the intended recipient would undo the hiding process (decryption) and read the original message. The most common uses were to give orders during wartime, to plot among political allies or to assist in acts of espionage. The fact that messages indeed stay hidden was crucial: the United States joined the Entente in WWI in no small part thanks to the decryption by British cryptanalists of the Zimmerman Telegram, in which Germany asked Mexico to declare war on their Northern neighbours. Mary Stuart, Queen of Scots, was executed because of her involvement in a plot to assassinate Queen Elizabeth I, which was uncovered when her cipher was broken. Ethel and Julius Rosenberg were also executed after being found guilty of treason and espionage against the United States, because Julius Rosenberg gave the plans to nuclear weapons to the Soviet Union. Their responsiblity was uncovered because of the secret Venona program, where American cryptanalists broke the cipher used by the Soviets.

Robust cryptography was a matter of life and death. Today, while wars, assassination plots and espionage rings are still around, the use of cryptography is much more widespread. The breadcrumb trail of data that we leave behind us as a result of everyday life in the twenty-first century is massive and leaks much information on us. Some of it is done intentionally when one makes a post on social media. But the vast majority of this dataspill happens behind the scenes: metadata leaks whenever we make any movement in the cyberspace.

Consider a referee standing in the middle of a football field, looking at the eastern half of the stadium. At some point, a football -kicked from the western half -enters his field of view and finishes its course after bouncing a few times on the grass. If this referee knows enough about Physics, he can -from two distinct positions the ball took at two separate points in time -compute the exact position from where that ball was kicked.

Any observer can do the same when looking at the side effects of an online action, and infer from this metadata some information, that may have been intended to remain hidden. One of the questions a cryptographer can ask themselves is "how can I kick a 2.1. SYMMETRIC AND ASYMMETRIC CRYPTOGRAPHY football accross the field, without anyone tracing that back to me?"

Symmetric and asymmetric cryptography

Let us introduce two well-known characters from crypto lore: Alice, who wishes to send some critical information to her friend Bob, over an unsecured channel (i.e. there may be an eavesdropper). For a long time, the practice of cryptography was limited to symmetric encryption: Alice and Bob share a secret key K, Alice encrypts her message m: using that key, she turns m into an unintelligible ciphertext c. She sends c to Bob, who then decrypts c using K, and gets the original message m.

This process -also called secret-key or private-key encryption -requires Alice and Bob to have agreed on a shared key K beforehand. This is a limitation, especially if Alice and Bob are complete strangers from one another and need to establish first contact securely.

The solution to that problem was invented in the seventies: using asymmetric cryptography, Bob can publish his public key P K, which Alice uses to encrypt m. She then sends the ciphertext c to Bob, who decrypts it using his secret key SK.

Also called public-key encryption (PKE), this new kind of protocol opens the way for modern cryptography: Alice and Bob can use PKE, along with other tools, to do a digital "handshake" and agree on a symmetric key, Alice can sign her messages to prove that she is the true sender, she can add integrity to prevent anyone from tampering with it. . .

In this thesis, we study three different types of protocols related to both symmetric and asymmetric encryption, and make contributions to their respective fields. A common thread between these subdisciplines of cryptography is the goal of facilitating secure delegated computation.

Having someone else do the computing

The discovery of public-key cryptography goes hand in hand with the ushering in of the Age of Information. Before the widespread use of computers, linked to each other in a network, symmetric cryptography was enough for its military and diplomatic uses. It is logical that members of the same nation (e.g. two generals discussing strategies) share the same secret key. Considerations about preventing the leakage of that key to the enemy are taken, but they seemingly do not warrant the need for a completely novel framework. An anecdote that illustrates this is the fact that cryptologists from GCHQ -a British intelligence agency -invented an algorithm similar to the RSA cryptosystem (the most used public-key scheme today) five to ten years before the publication of the scheme. The idea was shelved for lack of military uses. Now, we have access to good computing power and publically available cryptography. Alice can choose among dozens if not hundreds of cryptosystems to securely communicate with Bob. But Alice's needs have also evolved: she might want to do more than just chat with friends. She could have a lot of sensitive data but no place to store it. Or she might want to perform some computations on this data, but does not have the processing power needed for such a task. Thankfully, supply has adapted to her demand: she can outsource the storage and computation she needs. If Alice trusts no one, how can her data remain secure?

Letting an exterior entity handle computation on sensitive data can be done securely in a number of ways. Fully Homomorphic Encryption (FHE) is a general way of enabling CHAPTER 2. INTRODUCTION computation over encrypted data: anyone can compute an arbitrary function on a tuple of ciphertexts, which results in a new ciphertext which is an encryption of the output of that function on the original plaintexts. FHE requires high computational and spatial overhead, but is a great ready-to-use solution. Alice could also obfuscate a program using indistinguishability obfuscation (iO): roughly speaking, someone could run the obfuscated program and have the same input-output couples that the original program would produce, but without any knowledge on the inner workings of said program.

In this thesis, we will look at three different proposals that deal with sharing hidden information among various parties. We will first look at a special case of Multi-Party Computation (MPC) called Private Simultaneous Messages (PSM) where a referee computes a public function on the private inputs of the parties it interacts with. Then we will see how a person can securely store and access data on an untrusted server using Oblivious RAM (ORAM) protocols. Finally, we will study White-Box Cryptography, where a secret-key algorithm is made to be publically computed, and show an attack on such a protocol.

Flavors of delegating computation

In the course of my thesis, I have worked on various subjects within different areas of cryptology. I present in this manuscript results in three of these subjects, which were made into articles. In this section, I introduce and motivate these subjects. In the next section, I will give a summary of the contributions that were made.

Computing with others

Pooling data from different parties to aquire new knowledge is often a necessity. A typical example from our field is Yao's millionaire problem: Alice and Bob want to know who among them is the wealthiest, but they do not want to reveal what their net worth actually is [START_REF] Andrew | Protocols for secure computations (extended abstract)[END_REF]. The subject matter might seem vain, but the existence of a protocol that solves this problem is in fact consequential. We can imagine another situation: a pharmaceutical company wants to collect data to help in developping a new drug that could help patients suffering from a particular disease. Hospitals have plenty of potentially relevant data on their patients (e.g. age, gender, weight, mortality rate . . . ), however giving carte blanche to a company to use patient data is a recipe for confidentiality disaster, and is justly illegal in most countries. The naive solution of simply anonymizing the data (i.e. removing the names in an otherwise unchanged database, sometimes called "pseudonymization") does not work [NS06,[START_REF] Sweeney | Simple Demographics Often Identify People Uniquely[END_REF]. Enough bits of information can remain in such a database to personally identify persons present in it. We can turn to cryptography for salvation: here all of the information is hidden, not only names or places of birth, which are sufficient identifiers, but not necessary.

If we encrypt this data, how will we be able to perform computations on it? A way to do so is through secure Multi-Party Computation (MPC).

In an MPC protocol, several parties P 1 , . . . , P k each hold a secret input x 1 , . . . , x k , and they wish to compute the output of some (public) function f , such that each party learns f (x 1 , . . . , x k ) and no additional information on the other inputs. MPC covers a vast field of protocols, with many different security requirements. This great survey by Yehuda Lindell delves in more depth about MPC in general [START_REF] Lindell | Secure multiparty computation (mpc)[END_REF]. In this thesis, we 2.3. FLAVORS OF DELEGATING COMPUTATION will focus on a minimalist instance of MPC called Private Simultaneous Messages (PSM).

Here, in addition to the k parties, we add a Referee who will be the one actually doing the computation. The protocol is non-interactive: each party sends a single message to the referee, and the parties do not discuss among each other. They only share a common random string which they will use to hide their input from the referee. This protocol assumes that only the referee can be corrupted, the other parties must remain honest. The parties' inputs will be information-theoretically hidden (also called perfect secrecy): no matter how powerful an adversary's computing powers are, no information can be obtained on the inputs by studying the messages received by the referee.

Storing data elsewhere

The amount of data produced keeps growing, and doing computation on this data (e.g. to train a Machine Learning model) is valuable. Although storage capacity has grown as well, the space needed to store enough data to perform such tasks is out of reach for most private citizens or smaller companies. To outsource this storage in a secure manner, the naive solution is to encrypt the data and store the ciphertexts in the cloud. This method is as secure as the symmetric encryption algorithm used (i.e. as secure as it gets if one chooses wisely), which is good news if one is only concerned with the security of the data, no matter the cost. But this is as saying that the best way to ensure not getting in an accident in a car is to never start it: technically not wrong, but we are not going anywhere. If we encrypt a terabyte of data using AES and store that, we must download a terabyte of ciphertext even if we only want to read one byte of cleartext whose index is unknown in it. This becomes bad news when we are concerned with any kind of practical application.

To have our cake and eat it too, why could we not just encrypt "small" blocks of our data, store them remotely and only download the small blocks we require as they are needed? We can actually, but this solution raises new problems. First of all, we need to index the blocks we store, this comes at some cost, but we can deal with it in several ways. Secondly, the fact that we access some block in itself reveals information on the data we query and the way we use it. Think of a boy grabbing a cookie from the kitchen, and hiding it behind his back when his mother comes to check on him. Sure, she does not see what he is holding, but the fact that he is hiding something, in the kitchen, after she explicitely forbade him to eat another cookie, should enable her to make an educated guess regarding what is being hidden from her.

To keep anyone from guessing what we are doing with our data, Oblivious RAM (ORAM) algorithms were introduced in the 1990s: they hide the access pattern one makes when querying data. Initially, the ORAM model was concerned with actual RAM: if a CPU makes queries to (encrypted) values in its random access memory, an eavesdropper could analyze the access pattern and learn confidential information on the computation that is being performed. More recently, this framework has been applied in client-server communications that happen when computing in the cloud. However, there are still applications in the originally intended RAM model, or as a mix of both online and offline computation when considering such actions in a secure enclave on a remote server [START_REF] Connell | Technology deep dive: Building a faster oram layer for enclaves[END_REF].

In this thesis, we give new constructions of ORAM protocols and use them to build new Searchable Symmetric Encryption (SSE) schemes. In SSE, one is able to perform keyword searches on an encrypted database.

Letting someone else encrypt

Duplicating and sharing digital content has become orders of magnitude easier with the ubiquitous presence of computers and internet access. Digital piracy began in the era of cassette tapes, but with the inexpensive access to CD readers in the nineties and the advent of peer-to-peer torrents, intellectual property holders (especially music labels) began to take notice: how can a company protect its bottom line if a customer can purchase one product and millions of would-be buyers can just opt to dowload it instead? Today, we find it obvious that downloading digital content on the internet is the way to go, however this was not always the case: because of the aforementionned fear that letting people download music means scuttling the business model, allowing pieces to be sold on a digital marketplace required some convincing.

Among the proposals was a new technology used for Digital Rights Management (DRM), where a user could consume the media (i.e. listen to a song), but not actually own the MP3 file. This technology is called White-Box Cryptography, and contributed to the reason why we have iTunes, Netflix and Spotify today [START_REF] Cioschi | White-Box Cryptography: A Time-Security Trade-Off for the SPNbox Family[END_REF].

The goal of White-Box Cryptography is to allow an untrusted agent to have access to an encryption algorithm under some secret key: the key is hidden in the implementation of the algorithm. With this obfuscated cipher, the agent should not be able to reverseengineer the key even with white-box access (i.e. it is possible to study the inner workings of the algorithm). Ideally, a music piece could be encrypted such that the only way for someone to listen to it is to use the white-box algorithm: the agent cannot obtain the fully decrypted MP3 file.

The promise of a counter-measure to safeguard digital content against piracy gave stakeholders some confidence in allowing their products to be sold online and downloaded or streamed. This has not halted piracy attempts: it remains entirely possible to use the cassette-tape era ruse of simply recording the song as it is being played. In fact, all sorts of attacks on DRMs surfaced as a response. There even is an arms race in online piracy communities (e.g. the Warez Scene) to remove anti-piracy protections from video-games [Wik23].

Attacks of a more compelling nature to us are cryptanalyses of white-box cryptosystems. We give one such attack in this work.

Summary of results

We now have a bird's-eye view of certain subfields of cryptography. In this section, I summarize the advances that we made in these fields.

New upper bounds on the complexity of PSM protocols

In a PSM protocol, there are k parties P 1 , . . . , P k and a referee Ref . Let N ∈ N. For all i ∈ [k], each party P i holds a secret input x i ∈ [N ], and each sends a message m i to the referee, such that the referee can perform a computation on the messages that outputs f (x 1 , . . . , x k ) where f is a public function. The parties are assumed to be honest. We are mainly interested in the communication complexity of the protocol, i.e. the number of bits each party has to send to have the computation performed correctly. We are also concerned with the randomness complexity: how many random bits the parties must share.

SUMMARY OF RESULTS

The PSM model was presented first in 1994 by Feige, Kilian and Naor [START_REF] Feige | A minimal model for secure computation (extended abstract)[END_REF] for the 2-party case (although the k-party case was touched on in the appendix), then expanded to multiple parties in a work by Ishai and Kushilevitz [START_REF] Ishai | Private simultaneous messages protocols with applications[END_REF]. Since then, new upper and lower bounds have been found: in the 2-party case, [START_REF] Feige | A minimal model for secure computation (extended abstract)[END_REF] showed a protocol with communication complexity O(N ), then it was shown that one can achieve a communication complexity of O( √ N ) [START_REF] Beimel | On the cryptographic complexity of the worst functions[END_REF]. In [START_REF] Beimel | The complexity of multiparty PSM protocols and related models[END_REF], a cost of O(poly(k) • N k/2 ) was shown for all k ≥ 2, improving on the O(poly(k)•N k-1 ) cost from [START_REF] Feige | A minimal model for secure computation (extended abstract)[END_REF], along with better results for k ≤ 5. This work also proposed protocols with unbalanced complexity: some parties send more information than others.

Regarding lower bounds, [START_REF] Feige | A minimal model for secure computation (extended abstract)[END_REF] showed a limit of 3k-O(1) bits, which was expanded into a 3k-O(log(k)) lower bound by [START_REF] Applebaum | The communication complexity of private simultaneous messages, revisited[END_REF]. For k = ω(log(n)), this Ω(n) lower bound is improved into a Ω(k 2 n/ log(kn)) one by [BR22].

In a work done in collaboration with Tianren Liu [START_REF] Assouline | Multi-party psm, revisited: Improved communication and unbalanced communication[END_REF], we show new upper bounds and introduce 2-party unbalanced communication PSM protocols. Our main result is a PSM protocol for infinitely many k (namely, all k ≤ 20 and all prime powers) with a cost of O(poly(k)

• N k-1 2 ).
We give a new framework in which we can build PSM protocols in Chapter 3. In fact, we describe a way to build randomized encodings, which PSM can be seen as a special instantiation of. In short, a randomized encoding f : X × R → Ŷ of a function f :

   X → Y x → f (x)
is such that for r ∈ R some random value, f (x, r) has enough information to recover f (x) and nothing else about x. PSM are a special case of randomized encodings: seing x as x = (x 1 . . . , x k ), the messages {m 1 , . . . , m k } received by the referee are a randomized encoding (with r being the shared randomness) of f (x 1 , . . . , x k ). The idea behind this new framework comes from [START_REF] Beimel | On the cryptographic complexity of the worst functions[END_REF]: we represent each input x i with its one-hot encoding: x i is seen as an identity vector z i , where the x i th coordinate of z i is 1 and the others are 0. We then split this vector in two: z i = y 2i ⊗ y 2i+1 . We give simple examples of PSM constructions for 3 and 5 parties using this technique in Chapter 3.1.2. To serve as an appetizer, here is a very simple 2-party PSM using this tensoring of inputs.

Alice and Bob wish to engage in a PSM protocol with the referee. As explained above, we cut the inputs in half, so that the parties send two inputs of size N 1/2 . The function f to be evaluated is represented as a polynomial p ∈ {0, 1} N .

• Alice and Bob will share the following randomness:

a 1 , a 2 , b 1 , b 2 $ ← -{0, 1} √ N . • Alice's input x is s.t. x = x 1 ⊗ x 2 , with x 1 , x 2 ∈ {0, 1} √ N .
• In the same way, Bob's input is y = y 1 ⊗ y 2 . Now, before we see how the protocol works, Alice and Bob will construct privately some polynomials:

• Alice computes q 1 , q 2 of size O( √ N ) such that ⟨q 1 , z 1 ⟩ = ⟨p, (x 1 + a 1 ) ⊗ (x 2 + a 2 ) ⊗ (z 1 ⊗ b 2 + b 1 ⊗ b 2 )⟩ and
⟨q 2 , z 2 ⟩ = ⟨p, (x 1 + a 1 ) ⊗ (x 2 + a 2 ) ⊗ b 1 ⊗ z 2 ⟩. • Bob computes h 1 , h 2 of size O( √ N ) such that CHAPTER 2. INTRODUCTION ⟨h 1 , z 1 ⟩ = ⟨p, (z 1 ⊗ a 2 + a 1 ⊗ a 2 ) ⊗ y 1 ⊗ y 2 ⟩ and ⟨h 2 , z 2 ⟩ = ⟨p, a 1 ⊗ z 2 ⊗ y 1 ⊗ y 2 ⟩.
The protocol works as follows:

• Alice sends (x 1 + a 1 , x 2 + a 2 ) to Ref .

• Bob sends (y 1 + b 1 , y 2 + b 2 ) to Ref .

• Alice and Bob engage in 4 instances of a PSM protocol for polynomial evaluation as in the previous section, so that Ref

can learn γ = ⟨q 1 , y 1 ⟩ + ⟨q 2 , y 2 ⟩ + ⟨h 1 , x 1 ⟩ + ⟨h 2 , x 2 ⟩. • Ref computes ⟨F, (x 1 + a 1 ) ⊗ (x 2 + a 2 ) ⊗ (y 1 + b 1 ) ⊗ (y 2 + b 2 )⟩ -γ.
The communication cost of that protocol is O( √ N ) for both Alice and Bob. In Chapter 3.4, we present PSM protocols with unbalanced communication: Alice sends O(N η ) bits and Bob sends O(N 1-η ) bits, with η ∈ [0, 1].

Oblivious RAM protocols for objects of variable sizes

The Oblivious RAM framework is concerned with hiding the access pattern that a client makes when querying a server for the encrypted data it has stored there. If we assume that the client has stored N objects, each of size B bits, we want to be able to perform read/write queries with a communication complexity lower than that of the trivial ORAM, where the client simply downloads the entire database. ORAM protocols were first introduced by Goldreich and Ostrovsky in [START_REF] Goldreich | Software protection and simulation on oblivious RAMs[END_REF]. They present the first non-trivial ORAM which is now called the square-root ORAM (named after its bandwidth cost of O( √ N • B)). In the square-root ORAM, the server holds an array of size N + 2 • √ N , composed (Initially) of the N items the ORAM must store, followed by √ N dummy items (e.g. encryptions of random words) and √ N sheltered items. The shelter will serve as a temporary storage, useful during queries. The high-level idea behind this system is as follows:

First, the client obliviously permutes the first N + √ N items and keeps a representation of the secret permutation π. The client then makes several accesses. The jth access to an object (e.g. the ith object) consists of:

• Reading the entire shelter of size √ N to find the object.

• If found: the client accesses the next dummy object. In the first N + √ N memory cells, it is at index π(N + j).

• If not found: the client accesses the object at its true location at index π(i).

• The client eventually updates the value of the ith item, reencrypts it and stores it in the shelter.

After at most √ N accesses, the client updates the values of the real objects in the first N + √ N cells from the ones in the shelter using oblivious sorting. This method was then generalized into the hierarchical ORAM paradigm in the same paper. Here, there are several levels, with arrays doubling in size at each one. The 2.4. SUMMARY OF RESULTS smaller arrays are reshuffled more frequently than the larger ones. This yields a polylogarithmic overhead. In fact, improvements were made on the hierarchical technique in [AKL + 18], yielding the "OptORAMa" protocol that achieves the lower bound of log(n) in communication overhead. However this method is impractical. Implementations of ORAM protocols are usually of algorithm following the tree-based paradigm.

The most well known tree-ORAM is Path-ORAM [SvS + 13a], which we present in detail in Chapter 4.5.2. An even simpler tree-ORAM, that removes Path-ORAM's need for a ω(log(N )) client storage is aptly named "Simple ORAM" [START_REF] Chung | A simple ORAM[END_REF]. Here, the server storage is structured as a complete binary tree of depth L = ⌈log(N )⌉, where each node, called bucket, can store up to log(N ) items. The client does not know the exact position of each item, but knows the tree leaf that identifies the path from root to leaf on which that object is. Thus, to access the ith object, the client first compute the leaf l associated with that object (from a position map), then reads (and reencrypts) the content of each bucket on the path from the root node to the leaf l. When the desired object is at some point encountered, the client downloads it, performs a read or write operation, and selects uniformly at random a new leaf to be associated with it. That object is finally written wherever there is space for it, at the intersection of the old path and the new one (corresponding to the freshly selected leaf).

In a joint work with my advisor Brice Minaud [START_REF] Assouline | Weighted oblivious ram, with applications to searchable symmetric encryption[END_REF] in Chapter 4, we explored ways to have ORAM schemes handle weighted objects (i.e. of variable sizes). We have a universal transformation achieving this, thus having all ORAMs work with weighted objects, however it requires an asymptotically higher bandwidth. Our main result is a generic transformation with no added asymptotic cost that works on most tree-ORAMs used in practice. The general idea is to consider the total weight of the objects: every object has a size ≤ B bits, we will assume that the server will host a total weight of at most N • B. In the standard (non-weighted) case, buckets could only store a bounded number Z of items. Now, we allow the buckets to store a total weight of Z • B bits. We can put an object in a bucket as long as that bound of Z • B is not reached. The bucket is considered full if the total weight exceeds Z • B (it will always be less than (Z + 1) • B). This modification is natural and efficient. The main difficulty is to show that it preserves correctness: indeed, tree-ORAM correctness proofs are notoriously intricate, even without variable-size objects. To resolve that issue, we introduce a new Schur-convexity argument, which turns out to fit the setting perfectly.

We also build Searchable Symmetric Encryption using the aforementioned weighted-ORAMs.

Structural cryptanalysis of white-box schemes of ARX ciphers

Let us think about how a symmetric encryption algorithm Enc, for some secret key K, works when an attacker is given access to it. Here, the attacker makes a query for the input x and is given the output y = Enc K (x). The black-box model of cryptography consists of looking at an algorithm as an opaque functionality, turning inputs into outputs without giving any explaination as to how. An adversary trying to attack a cryptosystem in a black-box way is said to have been given oracle access to that system. Of course, that is not how it works in the real world: some information leaks. Computations are not done instantaneously, thus the time it takes for an output to be produced can reveal something on the secret key [START_REF] Paul | Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems[END_REF]. A more elaborate attacker can study elec-CHAPTER 2. INTRODUCTION tromagnetic perturbations around the device performing the computing, or make measure on the power lines to study the electrical consumption used to compute Enc K [START_REF] Gandolfi | Electromagnetic analysis: Concrete results[END_REF].

Here, the attacker is said to be given side-channel information. We also see this model refered to as the grey-box model.

In the white-box model, the attacker has at its disposal an implementation of Enc K . It is possible to study the inner workings of the program and to modify them. White-box cryptography is the study of cryptography in the white-box model, i.e. ways of producing an implementation of Enc K such that the adversary cannot learn any information on K. The first white-box implementation of a cipher (AES) was introduced in [START_REF] Chow | White-box cryptography and an AES implementation[END_REF], this is refered to as the CEJO framework. Here, a cipher is decomposed into a series of composed look-up tables. They are individually obfuscated by composing their inputs and outputs with random permutations. The permutation at the output of one table is cancelled by the one at the input of the next table (by taking the inverse permutation). Here is a description of the design at a high-level: a subsitution-permutation network such as AES is seen as a composition of non-linear layers:

Enc K = E 1 • . . . • E n . The white-box cipher is made up of a sequence of layers (E ′ i ) i∈[n] = (O i • E i • I i ) i∈[n]
where

O i = I -1 i+1 for all i ∈ [n -1]. The pair (I 1 , O n ) is called the external encodings.
The other encodings are called internal encodings. The white-box cipher is evaluated as

Enc ′ K = E ′ 1 • . . . • E ′ n = I 1 • Enc K • O n . Several implementations of this method have been cryptanalyzed in [RW19, MDFK15, ABMT18, AMR19].
A new proposal for white-box ciphers was presented at CRYPTO 2022 by Ranea et al [START_REF] Ranea | Implicit whitebox implementations: White-boxing ARX ciphers[END_REF], using implicit implementations. Here, the round function F of a block cipher is represented by a function P such that ∀x, y, P (x, y) = 0 ⇐⇒ F (x) = y. P must be such that for all x, the function y → P (x, y) is affine. This new framework allows a greater flexibility in the choice of round function, thus this white-box cryptosystem is the first one able to handle ARX (Addition-Rotation-XOR) ciphers, such as Speck [BSS + 13].

With Brice Minaud and Anoine Houssais, we show in Chapter 5 a structural attack on this framework: it can be attacked in a black-box setting. We use a technique similar to that of [START_REF] Minaud | Key-recovery attacks on ASASA[END_REF] to attack implicit implementations of SPN ciphers: even though the first layer is now non-linear whereas it was only affine before, it is possible to reconstruct this layer with a computationally feasible number of samples. We also show an attack on implementation of ARX ciphers. We follow the same pattern of peeling off the program layer by layer, thus reconstructing every encoding.

Here is, roughly, how it works: let us consider a simple ARX cipher that takes as input t = (x||y) ∈ {0, 1} n , where x, y ∈ {0, 1} n/2 , and outputs (x||x ⊞ y) where ⊞ is the modular addition in Z 2 n (the secret key will appear in the external layers). At a high-level, we have three layers: I the low-degree non-linear layer at the input level, M the modular addition as described above and A the affine layer at the output level. The attacker thus feeds an input a and gets an output b = A • M • I(a). Let us write t = (x||y) as N (a) and z = x ⊞ y. We can notice that, for all i ∈ [n/2], z i = x i + y i + c i , where c i is the carry of the addition that gives z i-1 (and c n/2 = 0). Using this recurrence relation, we are able to reconstruct the entire modular addition. This, in turn, allows us to peel off the A layer. We can then peel off the remaining M and I layers by solving some polynomial equations.

Chapter

3

New techniques for Multi-party PSM

Introduction

Private Simultaneous Messages (PSM) is a minimal model of secure multi-party computation. It was introduced by Feige, Kilian and Naor [START_REF] Feige | A minimal model for secure computation (extended abstract)[END_REF], and was generalized to the multi-party setting by Ishai and Kushilevitz [START_REF] Ishai | Private simultaneous messages protocols with applications[END_REF].

In a PSM protocol for evaluating a k-ary functionality f : [N ] k → {0, 1}, there are k parties. They all share a common random string. For all i ∈ [k], the i-th party holds a private input x i . There is additionally a special party, called the referee. The referee receives one message from each party and is able to compute f (x 1 , . . . , x k ), and should learn no other information about x 1 , . . . , x k . referee Referee learns f (x 1 , . . . , x 4 ) PSM is studied as an information-theoretic primitive. The key complexity measure is the communication complexity. The common random string is crucial for the model as the common random string is the only mean to protect the privacy against an unbounded adversarial referee, when the k parties cannot communicate with each other.

P 1 input x 1 msg 1 P 2 input x 2
In the PSM model, there are relatively efficient PSM protocols for computing nondeterministic branching programs [START_REF] Feige | A minimal model for secure computation (extended abstract)[END_REF] and modular branching programs [START_REF] Ishai | Private simultaneous messages protocols with applications[END_REF]. But for general functionalities, little is known regarding their communication complexity in the PSM model. Assuming every party holds an input in [N ], the best known lower bound of 2-party PSM is 3 log N -O(log log N ) [START_REF] Applebaum | The communication complexity of private simultaneous messages, revisited[END_REF]. In k-party PSM where each party holds a 1-bit input, Ball et al. showed an Ω(k 2 / log k) lower bound [BHI + 20]. This lower bound was then improved to be Ω(k 2 n/log(kn)) in [BR22]. Though the lower bounds are at most polynomial in the total input length, all known upper bounds are exponential, leaving an exponential gap between upper and lower bounds. For any functionality f :

3.1. INTRODUCTION Number of parties [BIKK14] [BKN18] This work 2 O(N 1/2 ) O(N 1/2 ) O(N 1/2 ) 3 O(N ) O(N ) 4 O(N 5/3 ) O(N 3/2 ) 5 O(N 7/3 ) O(N 2 ) k ≥ 6 O(poly(k) • N k/2 ) 2 O(k) • N k-1 2
for infinitely many k including all k ≤ 20

O(log N ) N [BIKK14] O(N 1/2 ) O(N 1/2 ) This work O(N η ) O(N 1-η ) Table 3.2: The unbalanced communication complexity of general f : [N ]×[N ] → {0, 1} in 2-party PSM model [N ] k → {0, 1}, a "naïve" k-party PSM requires O(N k-1
) communication (the 2-party version was presented in [START_REF] Feige | A minimal model for secure computation (extended abstract)[END_REF]). The first novel upper bound is O( √ N ) for 2-party PSM [START_REF] Beimel | On the cryptographic complexity of the worst functions[END_REF], and it was recently generalized to an O k (N k/2 ) upper bound for k-party PSM [START_REF] Beimel | The complexity of multiparty PSM protocols and related models[END_REF]. In the same paper, Beimel, Kushilevitz and Nissim also further optimize the communication complexity for small k = 3, 4, 5. In particular, they obtain an O(N ) upper bound for 3-party PSM. For k = 4 or 5, they improve the protocol by letting parties jointly emulate their 3-party PSM. Their results are summarized in Table 3.1.

Our Contributions

In this chapter, we present two classes of results: We present new k-party PSM protocols that improve the communication complexity for infinitely many k. We introduce the notion of unbalanced 2-party PSM protocols, which allows a flexible repartition of the communication complexity among the two parties, and we present such protocols. k-party PSM protocols. We present a framework for constructing multi-party PSM. The new framework improves the communication complexity upper bounds for infinitely many k. To compute any k-ary functionality f :

[N ] k → {0, 1}, • For all k ≤ 20, our framework yields a k-party PSM protocol of communication complexity O(N k-1 2 ).
• For all k such that k + 1 is a prime or a prime power, our framework yields a k-party

PSM protocol of communication complexity O k (N k-1 2 ).
• For all k, we conjecture that our framework will yield a k-party PSM protocol of communication complexity

O k (N k-1 2 ).
CHAPTER 3. NEW TECHNIQUES FOR MULTI-PARTY PSM 2-party unbalanced PSM protocols. We also present a framework for constructing 2-party PSM protocols with unbalanced communication complexity. The new framework allows us to reduce the message length of one party at the cost of increasing the communication of the other party. We offer an almost smooth trade-off between the communication complexity of the two parties. To compute any functionality f :

[N ] × [N ] → {0, 1},
• For every rational η ∈ (0, 1) whose denominator is no more than 20, our framework yields a 2-party PSM protocol, where one party sends O(N η ) bits and the other sends O(N 1-η ) bits.

• For every rational η ∈ (0, 1), we conjecture that our framework will yield a 2-party PSM protocol, where one party sends O η (N η ) bits and the other sends O η (N 1-η ) bits.

To some extent, such a trade-off was known in the literature when η = 0. The first 2-party PSM protocol is of communication complexity O(N ) but is strongly unbalanced: one of the two parties only sends O(log N ) bits [START_REF] Feige | A minimal model for secure computation (extended abstract)[END_REF].

Proof Overview

This section presents the main ideas behind our new multi-party PSM protocols. We start with a warm-up example of a 3-party PSM, which is originally constructed by [START_REF] Beimel | The complexity of multiparty PSM protocols and related models[END_REF].

We present it in a way that matches the framework we will later introduce. Then we present a new 5-party PSM to demonstrate the power of our framework. The 5-party PSM example relies on new technique such as "hard terms cancelling". It can be easily generalized into a framework for constructing k-party PSM protocols for any odd k. But we do not formally present this framework in this chapter. Instead, in section 3.3, we develop a modified framework that supports odd as well as even values of k. The modified framework evenly divides every party's input into two halves, this idea was first introduced in [START_REF] Beimel | On the cryptographic complexity of the worst functions[END_REF]. When we formally present the modified framework in Section 3.3.1, we use a 4-party PSM as an example.

In section 3.4, we develop another framework for constructing unbalanced 2-party PSM protocols. Most terminologies and techniques are shared between the framework for k-party and the framework for unbalanced 2-party. Informally, the unbalanced 2-party PSM framework is the "tensor product" of two copies of the k-party framework. When we present the new framework in Section 3.4.1, we use as an exmaple a 2-party PSM with unbalanced communication O(N 1/3 ), O(N 2/3 ).

Background: 3-Party PSM [BKN18].

In this 3-party PSM protocol, three parties hold x 1 , x 2 , x 3 ∈ [N ] respectively. The protocol takes O(N ) communication and allows the referee to learn f (x 1 , x 2 , x 3 ).

Fix a finite field F. Let the i-th party locally computes a unit vector

x i ∈ F N . That is, all entries in x i are zero except for x i [x i ] = 1. Let F be the truth table of f represented as an N × N × N array, we have f (x 1 , x 2 , x 3 ) = ⟨F, x 1 ⊗ x 2 ⊗ x 3 ⟩,
where ⊗ denotes the tensor product and ⟨•, •⟩ denotes the inner product.

Therefore, it is sufficient to construct a 3-party PSM protocol, where the i-th party has input x i ∈ F N (not necessarily being an unit vector) and the referee learns ⟨F, x 1 ⊗x 2 ⊗x 3 ⟩ for some public F ∈ F N ×N ×N .

INTRODUCTION

We start by letting the i-th party sample random r i ∈ F N from the common random string and send the one-time padded xi := x i + r i to the referee. Then the referee can compute ⟨F, x1 ⊗ x2 ⊗ x3 ⟩. We call this term a "masked term", because it is computed from the masked inputs x1 , x2 , x3 . This masked term can be decomposed as the sum of several "pure terms"

⟨F, x1 ⊗ x2 ⊗ x3 ⟩ = ⟨F, x 1 ⊗ x 2 ⊗ x 3 ⟩ + ⟨F, x 1 ⊗ x 2 ⊗ r 3 ⟩ + ⟨F, x 1 ⊗ r 2 ⊗ x 3 ⟩ + ⟨F, r 1 ⊗ x 2 ⊗ x 3 ⟩ + ⟨F, x 1 ⊗ r 2 ⊗ r 3 ⟩ + ⟨F, r 1 ⊗ x 2 ⊗ r 3 ⟩ + ⟨F, r 1 ⊗ r 2 ⊗ x 3 ⟩ + ⟨F, r 1 ⊗ r 2 ⊗ r 3 ⟩. (3.1)
We classify the pure terms into two categories:

Target Term The term ⟨F, x 1 ⊗ x 2 ⊗ x 3 ⟩.
It is the term that the referee should learn as a consequence of the 3-party PSM protocol.

Easy Term All the other terms fall into this category. As the name suggested, there also exist "hard terms", which will be introduced in the next example of 5-party PSM.

The easy terms are called "easy" because each of them can be securely revealed to the referee using only O(N ) communication. More formally, let the parties additionally sample random r 1 , . . . , r 7 ∈ F from their common random string such that r 1 +• • •+r 7 = 0. There exist sub-protocols revealing each of

r 1 + ⟨F, x 1 ⊗ x 2 ⊗ r 3 ⟩, r 2 + ⟨F, x 1 ⊗ r 2 ⊗ x 3 ⟩, r 3 + ⟨F, r 1 ⊗ x 2 ⊗ x 3 ⟩, r 4 + ⟨F, x 1 ⊗ r 2 ⊗ r 3 ⟩, r 5 + ⟨F, r 1 ⊗ x 2 ⊗ r 3 ⟩, r 6 + ⟨F, r 1 ⊗ r 2 ⊗ x 3 ⟩, r 7 + ⟨F, r 1 ⊗ r 2 ⊗ r 3 ⟩ (3.2)
to the referee without leaking any other information, taking at most O(N ) communication.

Assume that such sub-protocols exist, we can easily finish the 3-party PSM: The i-th party sends xi := x i + r i , they use the the aforementioned sub-protocols to reveal (3.2). The correctness follows almost directly from (3.1).

The only missing piece is to contruct sub-protocols for computing the terms in (3.2). Let us discuss them individually:

• For the last term r 7 + ⟨F, r 1 ⊗ r 2 ⊗ r 3 ⟩, any party (e.g. the first party) can compute it and send it to the referee.

• For the term r 4 + ⟨F, x 1 ⊗ r 2 ⊗ r 3 ⟩, the first party computes it and sends it to the referee. Similarly for r 5 + ⟨F,

r 1 ⊗ x 2 ⊗ r 3 ⟩ and r 6 + ⟨F, r 1 ⊗ r 2 ⊗ x 3 ⟩.
• For the term r 1 + ⟨F, x 1 ⊗ x 2 ⊗ r 3 ⟩, both first and second party need to participate. Since the first party knows F, x 1 , r 3 , it can locally compute a vector g ∈ F N such that

r 1 + ⟨F, x 1 ⊗ x 2 ⊗ r 3 ⟩ = r 1 + ⟨g, x 2 ⟩.
Then they can jointly reveal it to the referee using the PSM for inner product (more details are provided in Section A.2.1). Similarly for r 2 + ⟨F,

x 1 ⊗ r 2 ⊗ x 3 ⟩ and r 3 + ⟨F, r 1 ⊗ x 2 ⊗ x 3 ⟩.

CHAPTER 3. NEW TECHNIQUES FOR MULTI-PARTY PSM

Example: 5-Party PSM. We will sketch a 5-party PSM protocol for any f :

[N ] 5 → {0, 1} with communication complexity O(N 2 ).
Let F be a finite field. Following the same observation we made in the 3-party PSM example, it is sufficient to construct a PSM protocol for any function of the form (x 1 , . . . , x 5 ) → ⟨F, x 1 ⊗ • • • ⊗ x 5 ⟩, where ⊗ denotes the tensor product, the i-th party having input x i ∈ F N , F is public and fixed being the truth table of f .

For each Ω ⊆ {1, 2, 3, 4, 5}, parties sample a dimension-|Ω| tensor R Ω ∈ F N |Ω| from the common random string. Define XΩ := R Ω + i∈Ω x i . For example, X{2} := R {2} + x 2 and X{3,4} := R {3,4} + x 3 ⊗ x 4 . Since the communication budget is O(N 2 ), they can perform a PSM sub-protocol so that the referee learns XΩ for all Ω such that |Ω| ≤ 2.

Learning those tensors allows the referee to compute many terms, including ⟨F, X{1,2} ⊗ X{3,4} ⊗ X{5} ⟩. This term can be decomposed into the sum of the following 8 terms:

⟨F, X{1,2} ⊗ X{3,4} ⊗ X{5} ⟩ = ⟨F, x 1 ⊗ x 2 ⊗ x 3 ⊗ x 4 ⊗ x 5 ⟩ + ⟨F, x 1 ⊗ x 2 ⊗ x 3 ⊗ x 4 ⊗ R {5} ⟩ + ⟨F, x 1 ⊗ x 2 ⊗ R {3,4} ⊗ x 5 ⟩ + ⟨F, x 1 ⊗ x 2 ⊗ R {3,4} ⊗ R {5} ⟩ + ⟨F, R {1,2} ⊗ x 3 ⊗ x 4 ⊗ x 5 ⟩ + ⟨F, R {1,2} ⊗ x 3 ⊗ x 4 ⊗ R {5} ⟩ + ⟨F, R {1,2} ⊗ R {3,4} ⊗ x 5 ⟩ + ⟨F, R {1,2} ⊗ R {3,4} ⊗ R {5} ⟩. (3.3)
Any term that is formed in the same way as the left-hand side of (3.3), i.e. ⟨F,

XS 1 ⊗ • • • ⊗ XSt ⟩ for some S 1 + • • • + S t = {1, 2, 3, 4, 5}, is called a masked term. It can be computed by the referee if |S i | ≤ 2 for all i.
Any term that is formed in the same way as the right-hand side of (3.3), i.e. ⟨F,

R S 1 ⊗ • • • ⊗ R St ⊗ x i 1 ⊗ • • • ⊗ x iw ⟩ for some S 1 + • • • + S t + {i 1 , . . . , i w } = {1, 2, 3, 4, 5}
, is called a pure term. As hinted by equation (3.3), every masked term is equal to the sum of 2 t pure terms.

The pure terms fall naturally into three categories. In particular, we introduce a new category called hard terms.

Target term

The term ⟨F,

x 1 ⊗ x 2 ⊗ x 3 ⊗ x 4 ⊗ x 5 ⟩ is called the target term. Easy term A pure term ⟨F, R S 1 ⊗ • • • ⊗ R St ⊗ x i 1 ⊗ • • • ⊗ x iw ⟩ is easy if w ≤ 3. Every
easy term can be computed using a PSM protocol with communication complexity O(N 2 ). For example, ⟨F, R {1,2} ⊗ x 3 ⊗ x 4 ⊗ x 5 ⟩ is an easy term. The 5 th party, based on its view, can compute a tensor

G ∈ F N 2 such that ⟨F, R {1,2} ⊗ x 3 ⊗ x 4 ⊗ x 5 ⟩ = ⟨G, x 3 ⊗ x 4 ⟩. And ⟨G, x 3 ⊗ x 4 ⟩ can be computed using a PSM protocol (Section A.2.1) with communication complexity O(N 2 ).
Hard term Any pure term that is neither the target term nor an easy term.

Let us ignore the easy terms for now. Then equation (3.3) can be rewritten as

⟨F, X{1,2} ⊗ X{3,4} ⊗ X{5} ⟩ = ⟨F, x 1 ⊗ • • • ⊗ x 5 ⟩ + ⟨F, x 1 ⊗ x 2 ⊗ x 3 ⊗ x 4 ⊗ R {5} ⟩ + easy terms.
There is only one hard term left. We would like to cancel out the hard term by combining a few masked terms. Let us consider the following masked terms:

⟨F, X{1,2} ⊗ X{3} ⊗ X{4,5} ⟩, ⟨F, X{1,2} ⊗ X{3,5} ⊗ X{4} ⟩ and ⟨F, X{1,2} ⊗ X{3} ⊗ X{4} ⊗ X{5} ⟩. 3.2. PRELIMINARIES ⟨F, X{1,2} ⊗ X{3} ⊗ X{4,5} ⟩ = ⟨F, x 1 ⊗ • • • ⊗ x 5 ⟩ + ⟨F, x 1 ⊗ x 2 ⊗ R {3} ⊗ x 4 ⊗ x 5 ⟩ + easy terms, ⟨F, X{1,2} ⊗ X{3,5} ⊗ X{4} ⟩ = ⟨F, x 1 ⊗ • • • ⊗ x 5 ⟩ + ⟨F, x 1 ⊗ x 2 ⊗ x 3 ⊗ R {4} ⊗ x 5 ⟩ + easy terms, ⟨F, X{1,2} ⊗ X{3} ⊗ X{4} ⊗ X{5} ⟩ = ⟨F, x 1 ⊗ • • • ⊗ x 5 ⟩ + ⟨F, x 1 ⊗ x 2 ⊗ R {3} ⊗ x 4 ⊗ x 5 ⟩ + ⟨F, x 1 ⊗ x 2 ⊗ x 3 ⊗ R {4} ⊗ x 5 ⟩ + ⟨F, x 1 ⊗ x 2 ⊗ x 3 ⊗ x 4 ⊗ R {5} ⟩ + easy terms.
By carefully combining these masked tensors, we have

⟨F, X{1,2} ⊗ X{3,4} ⊗ X{5} ⟩ + ⟨F, X{1,2} ⊗ X{3} ⊗ X{4,5} ⟩ + ⟨F, X{1,2} ⊗ X{3,5} ⊗ X{4} ⟩ -⟨F, X{1,2} ⊗ X{3} ⊗ X{4} ⊗ X{5} ⟩ = 2 • ⟨F, x 1 ⊗ • • • ⊗ x 5 ⟩ + easy terms.
(3.4) Equation (3.4) shows us how to construct the desired PSM protocol. All of the masked tensors on the left-hand side of (3.4) can be computed by the referee. The parties perform a PSM sub-protocol so that the referee learns the sum of these easy terms. (The details are demonstrated in the last example of 3-party PSM, and are explained in Section 3.3.2.) Then from equation (3.4), the referee learns 2

• ⟨F, x 1 ⊗ • • • ⊗ x 5 ⟩.
As long as F is a finite field in which 2 ̸ = 0, the referee has learned the target term. The protocol takes a communication cost of O(N 2 ) field elements.

Related Works

Besides [START_REF] Beimel | On the cryptographic complexity of the worst functions[END_REF][START_REF] Beimel | The complexity of multiparty PSM protocols and related models[END_REF], our construction of PSM protocols is also inspired by the progress in Conditional Disclosure of Secrets (CDS). Until recently, CDS had a similar exponential gap between known upper and lower bounds. CDS can be viewed as a variant of PSM where the referee knows all but 1 bit of the input: Consider the 2-party case and let [N ] be the input domain for both parties. The upper bounds of O( √ N ) is conserved [START_REF] Beimel | On the cryptographic complexity of the worst functions[END_REF][START_REF] Gay | Communication complexity of conditional disclosure of secrets and attribute-based encryption[END_REF]. A similar lower bound of Ω(log N ) is known [START_REF] Gay | Communication complexity of conditional disclosure of secrets and attribute-based encryption[END_REF][START_REF] Applebaum | Conditional disclosure of secrets: Amplification, closure, amortization, lower-bounds, and separations[END_REF]. Recently, Liu, Vaikuntanathan and Wee improved the CDS upper bound for arbitrary function to 2 Õ√ log N [START_REF] Liu | Conditional disclosure of secrets via non-linear reconstruction[END_REF]. In a slightly different setting, the amortized CDS upper bound per party is improved to Θ(1) [START_REF] Applebaum | Conditional disclosure of secrets: Amplification, closure, amortization, lower-bounds, and separations[END_REF][START_REF] Applebaum | On the power of amortization in secret sharing: d-uniform secret sharing and CDS with constant information rate[END_REF].

Gay, Kerenidis and Wee constructed 2-party CDS with smooth communication complexity trade-off between the two parties [START_REF] Gay | Communication complexity of conditional disclosure of secrets and attribute-based encryption[END_REF]. In particular, for any η ∈ [0, 1], they constructed a 2-party CDS protocol where one party sends O(N η ) bits and the other sends O(N 1-η ) bits.

In [ABF + 19, CGO21], constructions of ad hoc PSM are presented. In this framework, there are k parties, but only a subset of them will perform the computation. This notion, expanded in [START_REF] Beimel | Ad hoc PSM protocols: Secure computation without coordination[END_REF], was shown to imply obfuscation.

Preliminaries

Let N := {0, 1, . . .} denote the set of all natural numbers, and let [n] := {1, . . . , n}. In this chapter, F denotes a field, R denotes a finite commutative ring. For some prime power CHAPTER 3. NEW TECHNIQUES FOR MULTI-PARTY PSM p, let F p denote the unique finite field of order p. A vector will be denoted by a bold face lowercase letter. For a vector v, let v[i] denote its i-th entry.

Tensor

A tensor refers to the generalization of vectors and matrices which have multiple indices. Roughly speaking, a tensor is a multi-dimensional array. In the chapter, a tensor will be denoted by a bold face capital letter. A k-dimensional tensor T ∈ F n 1 ×n 2 ×...×n k is essentially an array of size

n 1 × n 2 × • • • × n k . The entries in T are indexed by (i 1 , . . . , i k ) ∈ [n 1 ]ו • •×[n k ]
, and denoted by T[i 1 , . . . , i k ]. A tensor can also be viewed as a representation of a multi-linear function: any k-linear function f :

F n 1 ×F n 2 ×. . .×F n k → F can be uniquely determined by its coefficient tensor F ∈ F n 1 ×...×n k , such that f (v 1 , . . . , v k ) = i 1 ∈[n 1 ],••• ,i k ∈[n k ] F[i 1 , . . . , i k ] • v 1 [i 1 ] • . . . • v k [i k ].
(3.5)

The inner product of two tensors S, T ∈ F n 1 ×n 2 ×...×n k is defined as

⟨S, T⟩ := i 1 ∈[n 1 ],••• ,i k ∈[n k ] S[i 1 , . . . , i k ] • T[i 1 , . . . , i k ]. Given two tensors S ∈ F n 1 ×...×n k and T ∈ F m 1 ×...×m ℓ , we define S ⊗ T, their tensor product. It is a tensor in F n 1 ×...×n k ×m 1 ×...×m ℓ such that (S ⊗ T)[i 1 , . . . , i k , j 1 , . . . , j ℓ ] = S[i 1 , . . . , i k ] • T[j 1 , . . . , j ℓ ].
Using the notation of inner product and tensor product, Equation (3.5) can also be written as

f (v 1 , . . . , v k ) = ⟨F, v 1 ⊗ . . . ⊗ v k ⟩.

Private Simultaneous Messages

Definition 1 (private simultaneous message). A k-party functionality is a mapping f : X 1 × . . . × X k → Y, where X 1 , . . . , X k are its input spaces and Y is its output space.

A private simultaneous message (PSM) protocol for a functionality f consists of a randomness space W and a tuple of deterministic functions (M 1 , . . . , M k , R)

M i : X i × W → {0, 1} cc i , for all i ∈ [k], R : {0, 1} cc 1 × . . . {0, 1} cc k → {0, 1},
where cc i is the communication complexity of the i-th party, cc := cc 1 + . . . + cc k is the total communication complexity.

A perfectly secure PSM protocol for f satisfies the following properties:

(correctness.) For all input tuple (x 1 , . . . , x k ) ∈ X 1 × . . . × X k and randomness w ∈ W, R(M 1 (x 1 , w), . . . , M k (x k , w)) = f (x 1 , . . . , x k )
(privacy.) There exists a randomized simulator S, such that for any input (x 1 , . . . ,

x k ) ∈ X 1 × . . . × X k , the joint distribution of M 1 (x 1 , w), . . . , M k (x k , w) is the same as the distributions of S(f (x 1 , . . . , x k ))
, where the distributions are taken over w ← W and the coin tosses of S.

NEW MULTI-PARTY PSM PROTOCOLS

Randomized Encoding

Randomized encoding is a primitive closely related to PSM. The randomized encoding of a function f is a randomized function f . The output f (x, w), where w denotes the randomness, contains sufficient information to recover f (x) and no other information about x.

Definition 2 (randomized encoding). A randomized encoding for a function f : X → Y consists of a randomized encoding function f : X × W → Ŷ and a deterministic decoding function R : Ŷ → Y, where W denotes the randomness space and Ŷ denotes the coding space.

A perfectly secure randomized encoding satisfies the following properties:

(correctness.) For all x ∈ X and randomness w ∈ W,

R( f (x, w)) = f (x)
(privacy.) There exists a randomized simulator S, such that for any input x ∈ X , the distribution of f (x, w) is the same as the distributions of S(f (x)), where the distributions are taken over w ← W and the coin tosses of S.

Follows directly from the definitions, (M

1 , . . . , M k , R) is a PSM protocol for f if and only if ( f , R) is a randomized encoding for f , where f (x 1 , . . . , x k , w) := (M 1 (x 1 , w), . . . , M k (x k , w)).
In other words, PSM is a special form of randomized encoding, where the input is divided into a few portions, and each bit of the encoding only depends on the randomness and one portion of the input.

New Multi-party PSM Protocols

In this section, we present one of our main results: for many k, every functionality

f : [N ] k → {0, 1} admits a PSM protocol of communication complexity O k (N k-1 2 ). Theorem 3.3.1. Let f : [N ] k → {0, 1}

be an arbitrary k-party functionality.

• There is a k-party PSM protocol for f with communication and randomness com-

plexity O(N k-1 2 ), if k ≤ 20.
• There is a k-party PSM protocol for f with communication and randomness com-

plexity O k (N k-1 2 ), if k + 1 is a prime or a prime power.
In this section, we prove a stronger statement. Let F be a finite field, consider the following auxiliary k-party functionality Aux k N :

k-party functionality Aux k N • The i-th party has input x 2i-1 , x 2i ∈ F √ N • The output is ⟨F, x 1 ⊗ • • • ⊗ x 2k ⟩,
(N k-1
2 ). Roughly speaking, the framework reduces the problem to a system of linear equations. A solution of the system implies a PSM protocol with the desired communication complexity. Therefore, we should rule out the possibility that the induced system has no solution. We partially achieve such a goal. We solve the induced system for infinitely many k:

• For all k ≤ 20, we checked that the induced system of linear equations is solvable.

For small k we solve the system by hand, and for larger k we verified it with a computer program.

• For all k such that k + 1 is a prime power, we prove that the system is solvable.

Backed by the above observations, we strongly believe the induced system is solvable for all k.

Conjecture 1. Let f : [N ] k → {0, 1} be an arbitrary k-party functionality. There is a k-party PSM protocol for f with communication and randomness complexity

O k (N k-1 2 ).
Organization Section 3.3.1 presents our framework for constructing multi-party PSM, introduces new notations, and gives a 4-party PSM as a concrete example. The following Sections 3.3.2, 3.3.3, 3.3.4 are independent. Section 3.3.2 provides more technical detail of the PSM protocols yielded by our framework. Section 3.3.3 shows how the framework works for small k, and Section 3.3.4 shows how the framework works for any integer k such that k + 1 is a prime power.

A Framework for Multi-party PSM

As mentioned in the beginning of Section 3.3, the functionality f : [N ] k → {0, 1} can be reduced to functionality Aux k N . The reduction works as follows: Let x 1 , . . . , x k be the input, the j-th party has input

x j ∈ [N ]. We evenly divide x j into x ′ 2j-1 , x ′ 2j ∈ [ √ N ]. For each i ∈ [2k], let x i := e x ′ i ∈ F √ N be the x ′ i -th standard unit vector. We reduce f to Aux k N : f (x 1 , . . . , x 2k ) = ⟨F, x 1 ⊗ . . . ⊗ x 2k ⟩
where F is the truth-table of f . For the remainder of the section, it is thus sufficient to construct a PSM protocol for Aux k N . For each non-empty Ω ⊆ [2k], our protocol will sample a random dimension-|Ω| tensor

R Ω ∈ R ( √ N ) |Ω| from the common random string 1 . Define XΩ := R Ω + i∈Ω x i . E.g., X{2} := R {2} + x 2 , X{3,4} := R {3,4} + x 3 ⊗ x 4 .

Within the communication complexity budget O(N k-1

2 ), we can let the referee learn XΩ for all Ω such that |Ω| ≤ k-1 (more details in Section 3.3.2). The referee does not learn extra information as XΩ is one-time padded by R Ω . For example when k = 4, we can let the referee learn tensors X{1} , X{2} , . . . , X{8} , X{1,2} , X{1,3} , . . . , X{7,8} , X{1,2,3} , X{1,2,4} , . . . , X{6,7,8} . The referee learns those tensors by having subsets of the parties recursively perform PSM 3.3. NEW MULTI-PARTY PSM PROTOCOLS protocols with a smaller number of parties, so that the referee learns the required information. Learning those tensors allows the referee to compute many terms including ⟨F, X{1,2,3} ⊗ X{4,5,6} ⊗ X{7,8} ⟩, which equals to the sum of the following 8 terms,

⟨F, X{1,2,3} ⊗ X{4,5,6} ⊗ X{7,8} ⟩ = ⟨F, x 1 ⊗ x 2 ⊗ x 3 ⊗ x 4 ⊗ x 5 ⊗ x 6 ⊗ x 7 ⊗ x 8 ⟩ + ⟨F, x 1 ⊗ x 2 ⊗ x 3 ⊗ x 4 ⊗ x 5 ⊗ x 6 ⊗ R {7,8} ⟩ + ⟨F, x 1 ⊗ x 2 ⊗ x 3 ⊗ R {4,5,6} ⊗ x 7 ⊗ x 8 ⟩ + ⟨F, x 1 ⊗ x 2 ⊗ x 3 ⊗ R {4,5,6} ⊗ R {7,8} ⟩ + ⟨F, R {1,2,3} ⊗ x 4 ⊗ x 5 ⊗ x 6 ⊗ x 7 ⊗ x 8 ⟩ + ⟨F, R {1,2,3} ⊗ x 4 ⊗ x 5 ⊗ x 6 ⊗ R {7,8} ⟩ + ⟨F, R {1,2,3} ⊗ R {4,5,6} ⊗ x 7 ⊗ x 8 ⟩ + ⟨F, R {1,2,3} ⊗ R {4,5,6} ⊗ R {7,8} ⟩.
(3.6)

Before we continue, let us introduce a few notations to describe the terms appearing in (3.6). The term (tensor) on the left hand side of the equation will be called a masked term (masked tensor). The terms (tensors) on the right hand side of the equation will be called pure terms (pure tensors).

Definition (masked tensor & masked term). A masked tensor is a tensor product XΩ

1 ⊗ . . . ⊗ XΩt 2 such that Ω 1 , . . . , Ω t are disjoint and their union equals [2k]. The shape of a masked tensor XΩ 1 ⊗ . . . ⊗ XΩt is the multiset {|Ω 1 |, . . . , |Ω t |}.
The inner product of a masked tensor and F is called a masked term.

For any multiset P such that sum(P ) = 2k, let X(P ) denote the sum of all masked tensors of shape P , let ⟨F, X(P )⟩ denote the sum of all masked terms of shape P . We thus have ⟨F, X(P )⟩ = ⟨F, X(P )⟩.

Definition (pure tensor & pure term). A pure tensor is a tensor product

R Ω 1 ⊗. . .⊗R Ωt ⊗ x i 1 ⊗ . . . ⊗ x iw such that {i 1 , . . . , i w }, Ω 1 , . . . , Ω t are disjoint and their union equals [2k]. The shape of a pure tensor R Ω 1 ⊗ . . . ⊗ R Ωt ⊗ x i 1 ⊗ . . . ⊗ x iw is the multiset {|Ω 1 |, . . . , |Ω t |}.
The inner product of a pure tensor and F is called a pure term.

For any multiset P such that sum(P ) ≤ 2k, let R(P ) denote the sum of all pure tensors of shape P , let ⟨F, R(P )⟩ denote the sum of all pure terms of shape P . We thus have ⟨F, R(P )⟩ = ⟨F, R(P )⟩.

The pure terms (pure tensors) can be grouped into 3 natural categories:

Target term (target tensor) ⟨F, x 1 ⊗. . .⊗x 2k ⟩ is called the target term as it is desired functionality output. The corresponding tensor x 1 ⊗ . . . ⊗ x 2k is called the target tensor. With this terminology, we can give an overview of our PSM protocol. As the referee can learn XΩ for all Ω such that |Ω| ≤ k -1, the referee can compute any masked term of shape P if max(P ) ≤ k -1. As suggested by Equation (3.6), every masked term is the linear combination of a few pure terms. Ideally, the referee only has to combine some computable masked terms, so that all the hard terms cancel out, resulting a linear combination of the target term and easy terms: a linear combination of masked terms = target term + some easy terms.

Easy terms (easy tensors)

A pure tensor R Ω 1 ⊗ . . . ⊗ R Ωt ⊗ x i 1 ⊗ . . . ⊗
(3.7)

Once we are in this ideal case, the easy terms can be easily removed by standard techniques, resulting the desired k-party PSM protocol for Aux k N . (More details are presented in Section 3.3.2.) Therefore, the task is reduced to a linear algebra problem: is the target term (resp. tensor) spanned by the referee-computable masked terms (resp. tensors) and easy terms (resp. tensors)?

When solving such linear algebra problem, it is fair to assume that the solution is symmetric. (Otherwise, assume that a solution that looks like (3.7) is asymmetric, it can be symmetrized by applying the symmetric sum on both sides.)

We have defined the (symmetric) sum of terms or tensors of the same shape. For example when k = 4, X(3, 3, 2) is defined as the sum of all masked tensors

XΩ 1 ⊗ XΩ 2 ⊗ XΩ 3 such that the multiset {|Ω 1 |, |Ω 2 |, |Ω 3 |} equals {3, 3, 2}, i.e. X(3, 3, 2) := X{1,2,3} ⊗ X{4,5,6} ⊗ X{7,8} + X{1,2,3} ⊗ X{4,5,7} ⊗ X{6,8} + X{1,2,3} ⊗ X{4,5,8} ⊗ X{5,6} + X{1,2,3} ⊗ X{4,6,7} ⊗ X{5,8} + . . . + X{3,4,5} ⊗ X{6,7,8} ⊗ X{1,2} . Let's revisit Equation (3.6), ⟨F, X{1,2,3} ⊗ X{4,5,6} ⊗ X{7,8} ⟩ a masked term of shape {3, 3, 2} = ⟨F, x 1 ⊗ • • • ⊗ x 8 ⟩ a pure term of shape {} + ⟨F, x 1 ⊗ • • • ⊗ x 6 ⊗ R {7,8} ⟩ a pure term of shape {2} + ⟨F, x 1 ⊗ x 2 ⊗ x 3 ⊗ R {4,5,6} ⊗ x 7 ⊗ x 8 ⟩ + ⟨F, R {1,2,3} ⊗ x 4 ⊗ • • • ⊗ x 8 ⟩ pure terms of shape {3} + ⟨F, x 1 ⊗ x 2 ⊗ x 3 ⊗ R {4,5,6} ⊗ R {7,8} ⟩ + ⟨F, R {1,2,3} ⊗ x 4 ⊗ x 5 ⊗ x 6 ⊗ R {7,8} ⟩ pure terms of shape {3, 2} + ⟨F, R {1,2,3} ⊗ R {4,5,6} ⊗ x 7 ⊗ x 8 ⟩ a pure term of shape {3, 3} + ⟨F, R {1,2,3} ⊗ R {4,5,6} ⊗ R {7,8} ⟩ a pure term of shape {3, 3, 2}
.

By applying a symmetric sum on both sides, we get

⟨F, X(3, 3, 2)⟩ = 280 • ⟨F, R()⟩ the target term + 10 • ⟨F, R(2)⟩ hard pure terms + 10 • ⟨F, R(3)⟩ + ⟨F, R(3, 2)⟩ + ⟨F, R(3, 3)⟩ + ⟨F, R(3, 3, 2)⟩ easy pure terms .

NEW MULTI-PARTY PSM PROTOCOLS

As another example of the symmetric sum of masked term that the referee can compute,

⟨F, X(2, 2, 2, 2)⟩ = 105 • ⟨F, R()⟩ target term + 15 • ⟨F, R(2)⟩ hard pure terms + 3 • ⟨F, R(2, 2)⟩ + ⟨F, R(2, 2, 2)⟩ + ⟨F, R(2, 2, 2, 2)⟩ easy pure terms .
By carefully combining the above two equations, we get In the general k-party case, for each legit shape P of masked term (i.e., P is a multiset consisting of positive integers and sum(P ) = 2k),

3 • ⟨F, X(3, 3, 2)⟩ -2 • ⟨F, X(2, 2, 2, 2)⟩ = 630 • ⟨F, R()⟩ +
⟨F, X(P )⟩ = Q⊆P α(Q) • ⟨F, R(P \ Q)⟩, (3.9)
where P \ Q is the multiset subtraction and

α(Q) := (sum(Q))! i∈Q i! • m∈Z + (number of m's in Q)! (3.10)
is the following combinatoric number: α(Q) is the number of ways to partition sum(Q) distinct elements into some unordered subsets S 1 , . . . , S t such that

Q = {|S 1 |, . . . , |S t |}.
Equations (3.9), (3.10) are proved in Appendix A.1.

The Induced PSM Protocol

In order to develop the previous section smoothly, we skipped some technique details in Section 3.3.1. In this section, we will show how to construct a k-party PSM protocol assuming that the target term is spanned by referee-computable masked terms and easy pure terms. By our assumption, there are referee-computable masked terms X(1) , . . . , X(t) , easy pure terms R (1) , . . . , R (s) , and coefficients a

1 , . . . a t , b 1 , . . . , b s ∈ F such that ⟨F, x 1 ⊗ • • • ⊗ x 2k ⟩ = t j=1 a j X(j) + s j=1 b j R (j) . (3.11)
A k-party PSM for f , together with its correctness and security, is yielded by the following facts:

• Fact I: s j=1 b j R (j) and XΩ for all 0

< |Ω| ≤ k -1 form a randomized encoding of ⟨F, x 1 ⊗ • • • ⊗ x 2k ⟩.
That is, they contain the sufficient information to recover ⟨F, x 1 ⊗ • • • ⊗ x 2k ⟩, and they are garbled with additional randomness so that no other information can be recovered.

• Fact II: For every Ω ⊆ [2k] such that 0 < |Ω| ≤ k -1, there is a PSM protocol for XΩ with communication complexity poly(k)

• N k-1 2 field elements.
CHAPTER 3. NEW TECHNIQUES FOR MULTI-PARTY PSM

• Fact III: There is a PSM protocol for s j=1 b j R (j) with communication complexity poly(k)

• s • N k-1 2 field elements.
The k-party PSM for f works as the follows: For each Ω ⊆ [2k] such that 0 < |Ω| ≤ k -1, use the PSM guaranteed by Fact II to reveal XΩ to the referee. Use the PSM guaranteed by Fact III to reveal s j=1 b j R (j) to the referee. Then Fact I allows the referee to compute the output from Equation (3.11).

Proof of Fact I. Equation (3.11) shows that ⟨F, x 1 ⊗ • • • ⊗ x 2k ⟩ can be computed from the encoding. Moreover, the distribution of the encoding is perfectly simulatable: The joint distribution of tensors XΩ for 0 < |Ω| ≤ k -1 is uniform distribution, as they are independently one-time padded. Then the value of s j=1 b j R (j) is uniquely determined by equation (3.11).

Proof of Fact II

. Let t = |Ω|. Each coordinate of XΩ is defined as X{j 1 ,...,jt} [i 1 , . . . , i t ] = R {j 1 ,...,jt} [i 1 , . . . , i t ] + x j 1 [i 1 ] • . . . • x jt [i t ],
which is an arithmetic formula of size O(k). Thus each coordinate has a PSM protocol with communication complexity poly(k) field elements [START_REF] Ishai | Randomizing polynomials: A new representation with applications to round-efficient secure computation[END_REF].

Proof of Fact III. Sample random c 1 , . . . , c s ∈ F from the common random string such that c 1 + . . . + c s = 0. Then it's sufficient to construct a PSM protocol for computing b j R (j) + c j for each j. Say this easy pure term

R (j) is ⟨F, R Ω 1 ⊗ . . . ⊗ x i 1 ⊗ . . . ⊗ x iw ⟩.
By our definition of an easy term, w ≤ k + 1. There exists a special party, such that the other parties hold at most k -1 of x i 1 , . . . , x iw . When w = k + 1, the special party is the one who holds two of x i 1 , . . . , x iw (the existence is guaranteed by the pigeonhole principle). W.l.o.g. assume that the other parties hold x i 1 , . . . , x i w ′ such that w ′ ≤ k -1. Then the special party knows a dimension-w ′ tensor G (which is determined by its input and b

j , R Ω 1 , R Ω 2 , . . . ) such that b j R (j) + c j = ⟨G, x i 1 ⊗ . . . ⊗ x i w ′ ⟩ + c j ,
which admits a PSM protocol (presented in Section A.2.1) with communication complexity O(poly(k) • N w ′ /2 ) field elements.

When k is Small

As shown in Section 3.3.1, to construct PSM protocol for Aux k N with communication complexity O k (N k-1
2 ), it is sufficient to prove the target term is spanned by the refereecomputable masked terms and easy pure terms. In this section, we verify that the condition holds for all k ≤ 20, which proves the first bullet of Theorem 3.3.1. However, we do not have a general construction of such linenar systems of equations for an arbitrary k.

The case when k = 2 was solved by [START_REF] Beimel | On the cryptographic complexity of the worst functions[END_REF]. Our framework yields the same protocol from ⟨F, X(1, 1, 1, 1)⟩ = ⟨F, R()⟩ + easy terms.

The case when k = 3 was solved by [START_REF] Beimel | The complexity of multiparty PSM protocols and related models[END_REF]. Our framework yields a similar protocol from ⟨F, X(2, 2, 2)⟩ = ⟨F, R()⟩ + easy terms.

NEW MULTI-PARTY PSM PROTOCOLS

The case when k = 4 is solved in section 3.3.1. For k = 5, consider the following two masked terms,

⟨F, X(4, 4, 2)⟩ = 1575 • ⟨F, R()⟩ + 35 • ⟨F, R(2)⟩ + easy terms, ⟨F, X(4, 2, 2, 2)⟩ = 3150 • ⟨F, R()⟩ + 210 • ⟨F, R(2)⟩ + easy terms.
We have 6 • ⟨F, X(4, 4, 2)⟩ -⟨F, X(4, 2, 2, 2)⟩ = 6300 • ⟨F, R()⟩ + easy terms, which induces a 5-party PSM with communication complexity O(N 2 ). For k = 6, consider the following masked terms

   ⟨F, X(5, 4, 3)⟩ ⟨F, X(4, 4, 4)⟩ ⟨F, X(3, 3, 3, 3)⟩    =    27720 126 56 5775 35 15400 280       ⟨F, R()⟩ ⟨F, R(3)⟩ ⟨F, R(4)⟩    + easy terms Therefore, 100• ⟨F, X(5, 4, 3)⟩-160• ⟨F, X(4, 4, 4)⟩-45• ⟨F, X(3, 3, 3, 3)⟩ = 1155000•
⟨F, R()⟩ + easy terms, which induces a 6-party PSM with communication complexity O(N 2.5 ).

For k = 7, consider the following masked terms

   ⟨F, X(4, 4, 4, 2)⟩ ⟨F, X(6, 6, 2)⟩ ⟨F, X(6, 4, 4)⟩    =   
525525 5775 1575 42042 462 105105 210

      ⟨F, R()⟩ ⟨F, R(2)⟩ ⟨F, R(4)⟩    + easy terms
Therefore, 14• ⟨F, X(4, 4, 4, 2)⟩-175• ⟨F, X(6, 6, 2)⟩-105• ⟨F, X(6, 4, 4)⟩ = -11036025• ⟨F, R()⟩ + easy terms, which induces a 7-party PSM with communication complexity O(N3 ).

For larger k, we wrote a simple program 3 to check if the target term can be spanned by referee-computable masked terms and easy terms. For simplicity, our program requires specifying the finite field in advance. Our program verifies that the framework yields a PSM protocol with c.c. O(N k-1 2 ) for every k ≤ 20. For example when k = 20, our program found: which induces a PSM protocol with c.c. O(N 9.5 ).

⟨F, R()⟩ = 2895 • ⟨F, X(

When k + 1 is a Prime Power

As shown in Section 3.3.1, to construct PSM protocol for

Aux k N with communication complexity O k (N k-1
2 ), it is sufficient to prove the target term is spanned by the refereecomputable masked terms and easy pure terms. In this section, we prove that the condition holds for all k such that k + 1 is a prime power, which proves the second bullet of Theorem 3.3.1.

When k + 1 is a prime p or a prime power p e , we obtain a simple k-party PSM, by doing computations in the finite field F p . CHAPTER 3. NEW TECHNIQUES FOR MULTI-PARTY PSM Proof. Consider the symmetric sum of all masked terms of shape {k -1, 1, . . . , 1} ⟨F, X(k -1, 1, . . . ,

1 k+1 1's )⟩ = k+1 i=0 α(k -1, 1, . . . , 1 k+1-i 1's ) • ⟨F, R(1, . . . , 1 i 1's )⟩ + k+1 i=0 α(1, . . . , 1 k+1-i 1's ) • ⟨F, R(k -1, 1, . . . , 1 i 1's )⟩ = α(k -1, 1, . . . , 1 k+1 1's ) • ⟨F, R()⟩ + k-2 i=1 α(k -1, 1, . . . , 1 k+1-i 1's ) • ⟨F, R(1, . . . , 1 i 1's
)⟩ + easy terms.

(3.12) (Recall that a pure term of shape P is easy iff sum(P

) ≥ k -1.) W.l.o.g. assume k > 2. By definition, α(k -1, 1, . . . , 1 t 1's ) = k-1+t k-1 . Lemma 3.3.3 shows that α(k -1, 1, . . . , 1 k+1 1's ) = 2k k-1 ≡ 1 mod p, while α(k -1, 1, . . . , 1 k+1-i 1's ) = 2k-i k-1 is a multiple of p for all 1 ≤ i ≤ k -2. Therefore, ⟨F, X(k -1, 1, . . . , 1 k+1 1's )⟩ = ⟨F, R()⟩ +
(N η ), O(N 1-η ).
In this section, we prove a stronger statement. Let F be a finite field, consider the following auxiliary 2-party functionality Aux 2 k,N :

2-party functionality Aux 2 k,N • Alice has input x 1 , . . . , x k ∈ F k √ N • Bob has input y 1 , . . . , y k ∈ F k √ N • The output is ⟨F, x 1 ⊗ . . . ⊗ x k ⊗ y 1 ⊗ . . . ⊗ y k ⟩, where F is public and fixed A PSM protocol for Aux 2 k,N implies a PSM for f : [N ] × [N ] → {0, 1}
with the same communication complexity of each party. The reduction consists of having F be the truth table of f . We present a framework for the construction of 2-party PSM protocols for Aux 2 k,N , where Alice sends O η (N η ) bits and Bob sends O η (N 1-η ) bits, for all η ∈ { 1 k , . . . , k-1 k }. Similar to the framework in Section 3.3, the framework in this section also reduces the problem to a system of linear equations. A solution of the system implies a 2-party PSM protocol with the desired communication complexity. By verifying with a computer, we find that our framework works well for all η whose denominator is no larger than 20. Backed by those observations, we believe that our framework allows for a smooth tradeoff between the communication complexity of Alice and Bob: Conjecture 2. For any functionality f : [N ] × [N ] → {0, 1}, and any 0 < η < 1, there is a 2-party PSM protocol for f with unbalanced communication complexity

O η (N η ), O η (N 1-η ).
Organization Section 3.4.1 presents our framework for constructing multi-party PSM, introduces new notations, and gives as a concrete example a 2-party PSM with communication O(N 1/3 ), O(N 2/3 ). The following Sections 3.4.2, 3.4.3 are independent. Section 3.4.2 provides more technical detail of the PSM protocols yielded by our framework. Section 3.4.3 shows how the framework works for small k.

A Framework for 2-party PSM

Consider a rational η = d k ∈ (0, 1). Let F be a finite commutative ring that we will fix later. All the operations are within ring F unless otherwise specified.

As mentioned in the beginning of Section 3.4, there is an non-interactive reduction from the functionality f :

[N ] × [N ] → {0, 1} to functionality Aux 2 k,N .
The reduction works as follows: Let x, y ∈ [N ] be the input of Alice and Bob respectively. Evenly divide

x into x 1 , . . . , x k ∈ [ k √ N ], similarly divide y into y 1 , . . . , y k ∈ [ k √ N ]. For each j ∈ [k], let x j := e x j ∈ F √ N be the x j -th standard unit vector. Similarly let y i := e y i ∈ F k √ N for every i ∈ [k].
The functionality f can be reduced to Aux 2 k,N by doing:

f (x 1 , . . . , x k , y 1 , . . . , y k ) = ⟨F, x 1 ⊗ . . . ⊗ x k ⊗ y 1 ⊗ . . . ⊗ y k ⟩.
where F is the truth-table of f . For the remainder of the section, it is thus sufficient to construct a PSM protocol for Aux 2 k,N . For every Ω ⊆ [k], our protocol will sample random R Ω , S Ω ∈ F ( k √ N ) |Ω| from the common random string. Let XΩ := R Ω + i∈Ω x i and ȲΩ := S Ω + i∈Ω y i .

As the communication complexity of Alice is O η (N d k ), she can send XΩ to the referee for every Ω that |Ω| ≤ d. So far no information is leaked as XΩ is one-time padded by R Ω . Similarly, Bob can send ȲΩ for every Ω that |Ω| ≤ k -d.

There are many meaningful terms that the referee can compute once he receives ( XΩ ) |Ω|≤d and ( ȲΩ ) |Ω|≤k-d . For example, when η = d/k = 1/3, the referee can compute:

⟨F, X{1} ⊗ X{2} ⊗ X{3} ⊗ Ȳ{1,2} ⊗ Ȳ{3} ⟩ = ⟨F, x 1 ⊗ x 2 ⊗ x 3 ⊗ y 1 ⊗ y 2 ⊗ y 3 ⟩ + ⟨F, x 1 ⊗ x 2 ⊗ x 3 ⊗ y 1 ⊗ y 2 ⊗ S {3} ⟩ + ⟨F, x 1 ⊗ x 2 ⊗ x 3 ⊗ S {1,2} ⊗ S {3} ⟩ + . . . (28 other terms) + ⟨F, R {1} ⊗ R {2} ⊗ R {3} ⊗ S {1,2} ⊗ S {3} ⟩. (3.13)
Before we continue, we have to introduce a few notations. We will define shape, masked tensor, pure tensor, easy & hard tensor, etc., in the same way as in Section 3.3.1.

Definition (masked tensor & masked term

). An Alice-side masked tensor is a tensor product XΩ 1 ⊗ . . . ⊗ XΩt such that Ω 1 , . . . , Ω t are disjoint and their union equals [k]. The shape of an Alice-side masked tensor XΩ 1 ⊗ . . . ⊗ XΩt is the multiset {|Ω 1 |, . . . , |Ω t |}. Bob-side masked tensors are defined symmetrically.

The tensor product of an Alice-side masked tensor and a Bob-side masked tensor is called a masked tensor. The inner product of F and a masked tensor is called a masked term.

An Alice-side masked tensor of shape P is referee-computable if max(P ) ≤ d. A Bob-side masked tensor of shape Q is referee-computable if max(Q) ≤ k -d. A masked tensor (and its corresponding masked term) is called referee-computable if it's the tensor product of a referee-computable Alice-side masked tensor and a referee-computable Bobside masked tensor. Definition (pure tensor & pure term). An Alice-side pure tensor is a tensor product The tensor product of an Alice-side pure tensor and a Bob-side pure tensor is called a pure tensor. The inner product of a pure tensor and F is called a pure term.

R Ω 1 ⊗ . . . ⊗ R Ωt ⊗ x i 1 ⊗ . . . ⊗ x iw such that {i 1 , . . . , i w }, Ω 1 , . . . ,

UNBALANCED 2-PARTY PSM PROTOCOLS

For any legit shape, let R(P ) denote the sum of all Alice-side pure tensor whose shape is P . Similarly, define Bob-side pure tensor sum S(P ).

Let's go back to the example when η = 1/3: examine the pure terms on the right side of equation (3.13), and check which of them has a 2-party PSM with communication complexity O(N

1 3 ), O(N 2 3 ). • The term ⟨F, x 1 ⊗ x 2 ⊗ x 3 ⊗ y 1 ⊗ y 2 ⊗ y 3 ⟩ is the desired functionality. • The term ⟨F, x 1 ⊗ x 2 ⊗ x 3 ⊗ S {1,2} ⊗ y 3 ⟩ has a PSM protocol with communication complexity O(N 1 3
). Because Alice knows a vector g (which is determined by F, Alice's input and randomness (R Ω ) Ω , (S Ω ) Ω ) such that ⟨F, x 1 ⊗x 2 ⊗x 3 ⊗S {1,2} ⊗y 3 ⟩ = ⟨g, y 3 ⟩.

• The term ⟨F, S {1} ⊗ x 2 ⊗ x 3 ⊗ y 1 ⊗ y 2 ⊗ y 3 ⟩ admits a PSM protocol with unbalanced communication complexity O(N 1 3 ), O(N 2 3 ). Because Bob knows a dimension-2 ten- sor G such that ⟨F, S {1} ⊗ x 2 ⊗ x 3 ⊗ y 1 ⊗ y 2 ⊗ y 3 ⟩ = ⟨x 2 ⊗ x 3 , G⟩. (This PSM is presented in Section A.2.2.)
The discussion above hints at the right classification of pure tensors.

target tensor The only Alice-side target tensor is

x 1 ⊗ • • • ⊗ x k . The only Bob-side target tensor is y 1 ⊗ • • • ⊗ y k . The only target tensor is x 1 ⊗ • • • ⊗ x k ⊗ y 1 ⊗ • • • ⊗ y k .
easy tensor An Alice-side pure tensor of shape P is called easy if sum(P )

≥ d. A Bob- side pure tensor of shape Q is called easy if sum(Q) ≥ k -d. A pure tensor R ⊗ S is called easy if either R or S is easy.
hard tensor The rest.

The inner product of F and a target/easy/hard tensor is called a target/easy/hard term. Then, equation (3.13) can be rewritten by grouping and ignoring the easy terms:

⟨F, X{1} ⊗ X{2} ⊗ X{3} ⊗ Ȳ{1,2} ⊗ Ȳ{3} ⟩ = ⟨F, x 1 ⊗ x 2 ⊗ x 3 ⊗ y 1 ⊗ y 2 ⊗ y 3 ⟩ + ⟨F, x 1 ⊗ x 2 ⊗ x 3 ⊗ y 1 ⊗ y 2 ⊗ S {3} ⟩ + easy terms .
By a symmetric sum, we get

⟨F, X(1, 1, 1) ⊗ Ȳ(2, 1)⟩ = 3 • ⟨F, R() ⊗ S()⟩ target +⟨F, R() ⊗ S(1)⟩ + easy terms.
Similarly, we have decomposed another referee-computable term

⟨F, X(1, 1, 1) ⊗ Ȳ(1, 1, 1)⟩ = ⟨F, R() ⊗ S()⟩ target +⟨F, R() ⊗ S(1)⟩ + easy terms.
Combine them to cancel out the hard terms: ). In general, a masked term ⟨F, X(P ) ⊗ Ȳ(Q)⟩ can be decomposed into pure terms by X(P ) =

⟨F, X(1, 1, 1) ⊗ Ȳ(2, 1)⟩ -⟨F, X(1, 1, 1) ⊗ Ȳ(1, 1, 1)⟩ = 2 • ⟨F,
P ′ ⊆P α(P ′ ) X(P \ P ′ ), Ȳ(Q) = Q ′ ⊆Q α(Q ′ ) Ȳ(Q \ Q ′ ), ⟨F, X(P ) ⊗ Ȳ(Q)⟩ = P ′ ⊆P Q ′ ⊆Q α(P ′ )α(Q ′ ) F, X(P \ P ′ ) ⊗ Ȳ(Q \ Q ′ ) .
with the combinatoric number α defined as in Section 3.3.1. The first two equations are essentially the same as equation (3.9) and they imply the third equation.

To construct a PSM protocol of the desired unbalanced communication complexity, it is sufficient to show the target term is spanned by the referee-computable masked terms and the easy terms. Namely, the target term = a linear combination of referee-computable masked terms + a linear combination of easy terms.

(3.14)

The details of how this sufficient condition implies a PSM with desired communication complexity is presented in Section 3.4.2.

This sufficient condition of form (3.14) is unfortunately too combinatorically hard to use in practice, especially since we are going to use a program to search for the proof for different values of η. There are too many distinct masked terms and pure terms -their number is equal to the number of pairs of legit shapes (P, Q).

Fortunately, we come up with a simpler sufficient condition. A PSM protocol of the desired unbalanced communication complexity exists if both of the following hold:

• The Alice-side target tensor is spanned by referee-computable Alice-side masked tensors and Alice-side easy tensors;

• The Bob-side target tensor is spanned by referee-computable Bob-side masked tensors and Bob-side easy tensors.

The proof is quite straight forward: Assume the new sufficient condition, a linear combination of referee-computable Alice-side masked tensors = R() + Alice-side easy tensors, a linear combination of referee-computable Bob-side masked tensors = S() + Bob-side easy tensors.

The tensor product of the above two equations is a linear combination of referee-computable masked tensors = R() ⊗ S() + a linear combination of easy tensors.

Multiplying both sides of the above equation with F yields the desired sufficient condition of form (3.14).

The Induced PSM Protocol

In order to develop the previous section smoothly, we skipped the technique details on how the condition (3.14) implies a 2-party PSM of the desired communication complexity.

In this section, we will show how to construct such a 2-party PSM protocol assuming that the target term is spanned by referee-computable masked terms and easy pure terms. By the condition (3.14), there are referee-computable masked terms Z(1) , . . . , Z(t) , easy pure terms T (1) , . . . , T (s) , and coefficients a 1 , . . .

a t , b 1 , . . . , b s ∈ F such that ⟨F, x 1 ⊗ • • • ⊗ x k ⊗ y 1 ⊗ • • • ⊗ y k ⟩ = t j=1 a j Z(j) + s j=1 b j T (j) .
(3.15)

A 2-party PSM for f , together with its correctness and security, is yielded by the following facts:

• Fact I: s j=1 b j T (j) together with XΩ for all 0 < |Ω| ≤ d and ȲΩ for all 0 < |Ω| ≤ k -d form a randomized encoding of the functionality output.

• Fact II: There is a PSM protocol for s j=1 b j T (j) , in which Alice sends k Proof of Fact II. Sample random c 1 , . . . , c s ∈ F from the common random string such that c 1 + . . . + c s = 0. Then it's sufficient to construct a PSM protocol for computing b j T (j) + c j for each j.

• s • N d k field elements, Bob sends k • s • N 1-d k field elements.
Because T (j) is an easy term, we have T (j) = ⟨F, R (j) ⊗ S (j) ⟩, where R (j) is an Aliceside pure tensor, S (j) is a Bob-side pure tensor, and either R (j) is an Alice-side easy tensor, S (j) is a Bob-side easy tensor. W.l.o.g., assume R (j) is an Alice-side easy tensor.

Say this Alice-side easy pure term

R (j) is R Ω 1 ⊗ . . . ⊗ x i 1 ⊗ . . . ⊗ x iw .
By the definition of an Alice-side easy term, w ≤ k -d. Then Bob knows a dimension-w tensor G (which is determined by

S (j) , b j , R Ω 1 , R Ω 2 , . . . ) such that b j T (j) + c j = ⟨G, x i 1 ⊗ . . . ⊗ x iw ⟩ + c j ,
which admits a PSM protocol (presented in Section A.2.2) in which Alice sends O(w•N 1/k ) field elements, Bob sends N w/k field elements.

When η has a Small Denominator

Section 3.4.1 proves a sufficient condition that implies 2-party PSM protocols with the desired unbalanced communication complexity. In this section, we will verify that the sufficient condition holds for all rational η ∈ (0, 1) whose denominator is no larger than 20. Theorem 3.4.1 follows as a consequence.

For η = 1/3, the 2-party PSM protocol in Section 3.4.1 is also induced by X(1, 1, 1) = R() + Alice-side easy tensors, Ȳ(2, 1) -Ȳ(1, 1, 1) = 2 • S() + Bob-side easy tensors.

For η = 1/4, a 2-party PSM protocol with c.c. O(N 1/4 ), O(N 3/4 ) is induced by

X(1, 1, 1, 1) = R() + Alice-side easy tensors, Ȳ(1, 1, 1, 1) + 2 • Ȳ(3, 1) + Ȳ(2, 2) -Ȳ(2, 1, 1) = 6 • S() + Bob-side easy tensors.
For η = 1/5, a 2-party PSM protocol with desired c.c. is induced by

X(1, 1, 1, 1, 1) = R() + Alice-side easy tensors, 6 • Ȳ(4, 1) + 2 • Ȳ(3, 2) -2 • Ȳ(3, 1, 1) -Ȳ(2, 2, 1) + Ȳ(2, 1, 1, 1) -Ȳ(1, 1, 1, 1, 1) = 24 • S() + Bob-side easy tensors.
For η = 2/5, a 2-party PSM protocol with desired c.c. is induced by

2 • X(2, 2, 1) -X(2, 1, 1, 1) = 20 • R() + Alice-side easy tensors, 3 • Ȳ(3, 2) + Ȳ(3, 1, 1)
-Ȳ(2, 2, 1) -Ȳ(1, 1, 1, 1, 1) = 24 • S() + Bob-side easy tensors.

For larger denominators, we wrote a computer program 4 to assist us in the proof. For example, for η = 7/20, a 2-party PSM with desired c.c. is induced by ΣR() = Alice-side easy tensors+18•Σ X(7, 7, 6)+10•Σ X(7, 7, 5, 1)+14•Σ X(7, 7, 4, 2)+14•Σ X(7, 7, 4, 1, 1)+17•Σ X(7, 7, 3, 3)+20•Σ X(7, 7, 3, 2, 1)+ 20 • Σ X(7, 7, 3, 1, 1, 1) + 10 • Σ X(7, 7, 2, 2, 2) + 10 • Σ X(7, 7, 2, 2, 1, 1) + 10 • Σ X(7, 7, 2, 1, 1, 1, 1) + 10 • Σ X(7, 7, 1, 1, 1, 1, 1, 1) + 6 • Σ X(7, 6, 6, 1) + 19 • Σ X(7, 6, 5, 2) + 19 • Σ X(7, 6, 5, 1, 1) + 21 • Σ X(7, 6, 4, 3) + 22 • Σ X(7, 6, 4, 2, 1) + 22 • Σ X(7, 6, 4, 1, 1, 1) + 7 • Σ X(7, 6, 3, 3, 1) + 15 • Σ X(7, 6, 3, 2, 2) + 15 • Σ X(7, 6, 3, 2, 1, 1)+15•Σ X(7, 6, 3, 1, 1, 1, 1)+19•Σ X(7, 6, 2, 2, 2, 1)+19•Σ X(7, 6, 2, 2, 1, 1, 1)+19•Σ X(7, 6, 2, 1, 1, 1, 1, 1)+19•Σ X(7, 6, 1, 1, 1, 1, 1, 1, 1) mod 23 ΣS() = Bob-side easy tensors + 13 • Σ Ȳ(13, 7) + 20 • Σ Ȳ(13, 6, 1) + 2 • Σ Ȳ(13, 5, 2) + 22 • Σ Ȳ(13, 5, 1, 1) + 1 • Σ Ȳ(13, 4, 3) + 17

• Σ Ȳ(13, 4, 2, 1) + 3 • Σ Ȳ(13, 4, 1, 1, 1)+19•Σ Ȳ(13, 3, 3, 1)+21•Σ Ȳ(13, 3, 2, 2)+1•Σ Ȳ(13, 3, 2, 1, 1)+11•Σ Ȳ(13, 3, 1, 1, 1, 1)+12•Σ Ȳ(13, 2, 2, 2, 1)+17•Σ Ȳ(13, 2, 2, 1, 1, 1)+ 3 • Σ Ȳ(13, 2, 1, 1, 1, 1, 1) + 10 • Σ Ȳ(13, 1, 1, 1, 1, 1, 1, 1) + 11 • Σ Ȳ(12, 8) + 17 • Σ Ȳ(12, 7, 1) + 1 • Σ Ȳ(12, 6, 2) + 11 • Σ Ȳ(12, 6, 1, 1) + 17 • Σ Ȳ(11, 9) + 14 • Σ Ȳ(11, 8, 1) + 6 • Σ Ȳ(11, 7, 2) + 20 • Σ Ȳ(11, 7, 1, 1) + 7 • Σ Ȳ(11, 6, 3) + 4 • Σ Ȳ(11, 6, 2, 1) + 21 • Σ Ȳ(11, 6, 1, 1, 1) + 2 • Σ Ȳ(10, 10) + 4 • Σ Ȳ(10, 9, 1) + 15 • Σ Ȳ(10, 8, 2) + 4 • Σ Ȳ(10, 8, 1, 1) + 1 • Σ Ȳ(10, 7, 3) + 17 • Σ Ȳ(10, 7, 2, 1) + 3 • Σ Ȳ(10, 7, 1, 1, 1) + 21 • Σ Ȳ(10, 6, 4) + 8 • Σ Ȳ(10, 6, 3, 1) + 4 • Σ Ȳ(10, 6, 2, 2) + 21 • Σ Ȳ(10, 6, 2, 1, 1) + 1 • Σ Ȳ(10, 6, 1, 1, 1, 1) + 20 • Σ Ȳ(9, 9, 2) + 13 • Σ Ȳ(9, 9, 1, 1) + 4 • Σ Ȳ(9, 8, 3) + 22 • Σ Ȳ(9, 8, 2, 1) + 12 • Σ Ȳ(9, 8, 1, 1, 1) + 14 • Σ Ȳ(9, 7, 4)+13•Σ Ȳ(9, 7, 3, 1)+18•Σ Ȳ(9, 7, 2, 2)+14•Σ Ȳ(9, 7, 2, 1, 1)+16•Σ Ȳ(9, 7, 1, 1, 1, 1)+11•Σ Ȳ(9, 6, 5)+13•Σ Ȳ(9, 6, 4, 1)+12•Σ Ȳ(9, 6, 3, 2)+ 17 • Σ Ȳ(9, 6, 3, 1, 1) + 20 • Σ Ȳ(9, 6, 2, 2, 1) + 13 • Σ Ȳ(9, 6, 2, 1, 1, 1) + 5 • Σ Ȳ(9, 6, 1, 1, 1, 1, 1) + 19 • Σ Ȳ(8, 8, 4) + 16 • Σ Ȳ(8, 8, 3, 1) + 8 • Σ Ȳ(8, 8, 2, 2) + 19 • Σ Ȳ(8, 8, 2, 1, 1) + 2 • Σ Ȳ(8, 8, 1, 1, 1, 1) + 17 • Σ Ȳ(8, 7, 5) + 18 • Σ Ȳ(8, 7, 4, 1) + 6 • Σ Ȳ(8, 7, 3, 2) + 20 • Σ Ȳ(8, 7, 3, 1, 1) + 10 • Σ Ȳ(8, 7, 2, 2, 1) + 18 • Σ Ȳ(8, 7, 2, 1, 1, 1) + 14 • Σ Ȳ(8, 7, 1, 1, 1, 1, 1) + 18 • Σ Ȳ(8, 6, 6) + 6 • Σ Ȳ(8, 6, 5, 1) + 13 • Σ Ȳ(8, 6, 4, 2) + 5 • Σ Ȳ(8, 6, 4, 1, 1) + 1 • Σ Ȳ(8, 6, 3, 3) + 17 • Σ Ȳ(8, 6, 3, 2, 1) + 3 • Σ Ȳ(8, 6, 3, 1, 1, 1) + 20 • Σ Ȳ(8, 6, 2, 2, 2) + 13 • Σ Ȳ(8, 6, 2, 2, 1, 1) + 5 • Σ Ȳ(8, 6, 2, 1, 1, 1, 1) + 9 • Σ Ȳ(8, 6, 1, 1, 1, 1, 1, 1) + 5 • Σ Ȳ(7, 7, 6) + 1 • Σ Ȳ(7, 7, 5, 1) + 6 • Σ Ȳ(7, 7, 4, 2) + 20 • Σ Ȳ(7, 7, 4, 1, 1) + 4 • Σ Ȳ(7, 7, 3, 3) + 22 • Σ Ȳ(7, 7, 3, 2, 1) + 12 • Σ Ȳ(7, 7, 3, 1, 1, 1) + 11 • Σ Ȳ(7, 7, 2, 2, 2)+6•Σ Ȳ(7, 7, 2, 2, 1, 1)+20•Σ Ȳ(7, 7, 2, 1, 1, 1, 1)+13•Σ Ȳ(7, 7, 1, 1, 1, 1, 1, 1)+15•Σ Ȳ(7, 6, 6, 1)+13•Σ Ȳ(7, 6, 5, 2)+5•Σ Ȳ(7, 6, 5, 1, 1)+ 18•Σ Ȳ(7, 6, 4, 3)+7•Σ Ȳ(7, 6, 4, 2, 1)+8•Σ Ȳ(7, 6, 4, 1, 1, 1)+20•Σ Ȳ(7, 6, 3, 3, 1)+10•Σ Ȳ(7, 6, 3, 2, 2)+18•Σ Ȳ(7, 6, 3, 2, 1, 1)+14•Σ Ȳ(7, 6, 3, 1, 1, 1, 1)+ 9 • Σ Ȳ(7, 6, 2, 2, 2, 1) + 7 • Σ Ȳ(7, 6, 2, 2, 1, 1, 1) + 8 • Σ Ȳ(7, 6, 2, 1, 1, 1, 1, 1) + 19 • Σ Ȳ(7, 6, 1, 1, 1, 1, 1, 1, 1) mod 23
We checked every rational η = d/k such that k ≤ 20, and verified that our framework does in fact yield a 2-party PSM protocol with unbalanced communication complexity O(N η ), O(N 1-η ).

OPEN PROBLEMS

Open Problems

This chapter presents two frameworks: a framework for constructing k-party PSM protocols for general f :

[N ] k → {0, 1} with c.c. O k (N k-1
2 ), and a framework for constructing 2-party PSM protocols for general f : [N ] × [N ] → {0, 1} where one party sends O η (N η ) bits and the other party sends O η (N 1-η ) bits. An immediate open problem is to prove our frameworks work for all integer k and all rational η. Currently, we can only prove it works for some k and η.

For simplicity, our analysis only considers the symmetric sum of terms. The symmetric sum incurs a blow-up exponential on k. Thus the communication complexity of our k-

party PSM protocols is exp(k)•N k-1 2 . While [BKN18] achieves communication complexity poly(k) • N k 2 .
Our protocols are less efficient in the domain where log N < k. A possible approach of getting rid of the exponential dependency in k is to break the symmetry. The potential of such an approach is evidenced by the 5-party PSM protocol in Section 3.1.2, which is asymmetric.

There is no clear reason why our framework will not yield more efficient PSM protocols. Can our multi-party framework yield PSM protocols with communication complexity O k (N k 2 -1 ), when k is sufficiently large? Can our 2-party framework yield PSM protocol with communication O η (N η ) for some rational η < 1 2 ? Our technique transfers such questions into some linear systems. Each question has an affirmative answer (for a given k or η) if and only if the corresponding linear system is solvable. We have modified our program to generate and solve these linear systems, but all the systems we have tried are unsolvable. This failure suggests that our new upper bounds might be tight, or are tight for a natural class of PSM protocols.

The question of the communication complexity trade-off for multi-party PSM remains widely open. In our k-party PSM protocol, every party sends O k (N k-1 2 ) bits. A variant of [START_REF] Feige | A minimal model for secure computation (extended abstract)[END_REF] provides a k-party PSM protocol where the i-th party sends Õk (N i-1 ) bits, whose geometric average is Õk (N k-1

2 ). Should a future work achieves the smooth trade-off between the two, there is little doubt that it will bring us a deep insight into PSM.

Finally, this work belongs to a not-fully-successful attempt at constructing PSM with sub-exponential communication complexity, which is probably the moonshot open problem in the PSM literature.

Chapter

4

Weighted ORAM with Applications to SSE

Introduction

When sensitive data is stored in an untrusted environment, encryption is not enough. The pattern of memory accesses to encrypted data can reveal a great deal about its contents.

In some settings, observing the pattern of memory accesses can allow a honest-but-curious host server to fully reconstruct the contents of an encrypted database [START_REF] Grubbs | Learning to reconstruct: Statistical learning theory and encrypted database attacks[END_REF]; in others, measuring cache misses can enable an attacker to recover secret key material [WHS12].

Untrusted environments where an adversary may be able to observe memory accesses, partially or completely, arise in many common scenarios. These include private information stored in an external cloud service, trusted enclaves running on an untrusted computer, or even public clouds where memory caches are shared across multiple tenants. In all these settings, security requires to hide not only the contents of each data item, but also which item is accessed. Oblivious RAM (ORAM) protocols provide a powerful tool to fully hide memory access patterns. The notion of ORAM was introduced by Goldreich and Ostrovsky [START_REF] Goldreich | Software protection and simulation on oblivious RAMs[END_REF], motivated by a scenario where a processor accesses untrusted memory. The processor operates in a RAM model of computation: it wishes to access memory words at arbitrary addresses. Naturally, memory words have a fixed size. In line with its historical motivation, ORAM is normally viewed as storing items of fixed size.

However, in many potential applications of ORAM, it is natural to consider items of variable size. Suppose for instance that a client wishes to store private files on an external cloud storage service. Different files may have different sizes; it may also be the case that the size of a file varies with time. This motivates the idea of ORAM for variable-size items.

The Trivial Approach. Of course, it is possible to generically emulate the storage of variable-size files using a memory allocation scheme for fixed-size items. In our case, using an ORAM for items of fixed size B, the most natural approach is to split each file into chunks of size B. Each chunk is then stored as a separate data item (called a block) within the ORAM, on the server side. To retrieve a file, the client simply queries all chunks corresponding to the desired file.

This simple variable-size-to-fixed-size reduction is not always satisfactory. A first issue relates to padding. If B > 1, before files can be split into chunks of size B, they must be padded to a multiple of the block size B. If many files are much smaller than the block size, padding becomes expensive. Both motivating applications given below show examples where padding can be prohibitive.

To reduce the cost of padding, it is tempting to reduce the block size B. However,

INTRODUCTION

this has several drawbacks, asymptotically and in practice. Let us start with theoretical ones. For a fixed total amount of data, reducing B increases the ORAM overhead (i.e. the ratio between the communication cost of the ORAM scheme, and the cost of an insecure exchange), since the overhead scales with the number of blocks. For example, an ORAM storing N blocks of size 1 typically has an overhead in polylog N ; whereas with N/B blocks of size B, the overhead becomes polylog(N/B). In later applications such as length-hiding ORAM, or ZeroSSE (Section 4.6.2), B can be very large, which makes the difference significant. In theory, larger block sizes are also preferable: for instance, Path ORAM achieves optimal O(log n) overhead if the block size is Ω(λ 2 ) bits, but its overhead is O(log 2 n) if the block size is Θ(λ) bits (where λ is the security parameter).

In practice, setting the block size to be very small, say a single memory word of 128 bits, has a deeper impact that is easy to overlook, but much more impactful in practice that the asymptotic difference above. Modern computers can only fetch memory from disk at the granularity level of a page, typically 4kB. This is enforced at all levels: by the operating system, in caches, and at the physical disk layer (for both HDDs and SSDs). When fetching many 128-bit words at random locations in the ORAM scheme, the server actually fetches the entire page for each. In each of those pages, only a fraction 1/256 of the data in the page is actually useful (128 bits out of 4kB). This results in very poor I/O efficiency, which correlates directly with disk throughput [BBF + 21]. The issue is easy to overlook because it is not reflected in the simple Random-Access Machine model of computation that is used to compute asymptotics, where all memory accesses have unit cost. But it has a very large impact in practice. This is well-known in Searchable Symmetric Encryption (SSE) literature, where an entire branch of the area studies memory efficiency [ANSS16, MM17, BBF + 21, MR22]. In ORAM literature, the PHANTOM implementation of Path ORAM uses blocks of size one page, likely for the same reason [MLS + 13]. Reading many tiny items at random memory locations is extremely inefficient, losing a factor up to B in throughput (when the bottleneck in throughput does not come from communication bandwidth).

If one thinks of storing entire documents in the context of a private online storage service, having many documents much smaller than the page size is rather unlikely. But in other applications, it is quite realistic. A case in point is the use of ORAM for Searchable Symmetric Encryption (SSE).

Motivating Application 1: Searchable Symmetric Encryption (SSE). The goal of SSE is to enable a client to outsource the storage of an encrypted database to an untrusted server, while being able to securely search the data. At minimum, the client is able to issue search queries asking for all entries that match a given keyword. To realize this functionality, for efficiency reasons, virtually all modern SSE constructions rely on a reverse index. The reverse index records, for each keyword, the list of identifiers of entries that match the keyword.

The majority of SSE solutions accept to leak the search pattern and access pattern of the client: that is, they leak to the server the repetition of queries, and the identifiers of documents matched by each query. This allows those constructions to trade off privacy for efficiency and scalability. Nevertheless, revealing access patterns to the server can be quite damaging, and has led to a number of attacks [START_REF] Cash | Leakageabuse attacks against searchable encryption[END_REF][START_REF] Grubbs | Learning to reconstruct: Statistical learning theory and encrypted database attacks[END_REF]. Those attacks have in turn motivated SSE approaches that rely on ORAM [START_REF] Garg | TWORAM: Efficient oblivious RAM in two rounds with applications to searchable encryption[END_REF][START_REF] Kamara | Structured encryption and leakage suppression[END_REF].

The most natural way to avoid leaking the search pattern is to store the reverse index in an ORAM. In that scenario, the "files" to be stored on an ORAM are actually the list of matches for a given keyword in an SSE scheme. For some databases, there may be many keywords that uniquely identify a file, or that match only a few files. In other words, there may be many lists much smaller than the block size B of the ORAM.

In practice, this is actually a major roadblock. As argued earlier, it is desirable to have a relatively large ORAM block size, at least one memory page. On the other hand, the identifier of an entry can be set to 64 bits, or even less. This means that a single ORAM block is 512 times larger than the minimal list size. If, say, many keywords match less than 10 entries in the database, padding those lists to the block size blows up their storage by a factor more than 50. More generally, if we set p to be the page size, measured in number of identifiers per page, then padding means that server storage grows at least in O(pN ), where N is the size of the plaintext reverse index; whereas we would like to achieve linear storage O(N ). Of course, with p = 512 as earlier, the practical difference is quite large.

Addressing that problem is not an easy task. In SSE literature, avoiding the cost of padding to the page size has been the focus of several recent works [BBF + 21, MR22]. Those works have motivated the creation of weighted memory allocation schemes, that can accommodate items of variable size, including weighted cuckoo hashing [BBF + 21], and weighted two-choice allocation [START_REF] Minaud | Dynamic local searchable symmetric encryption[END_REF]. However, there is no weighted ORAM. This means that in order to use ORAM with SSE, current options are either to choose a block size much smaller than the page size, or to suffer a prohibitive padding overhead for some data distributions-both of which are undesirable.

Motivating Application 2: Length-Hiding ORAM. Let us go back to the scenario where a client wishes to store private files of various sizes on a honest-but-curious cloud server. As noted earlier, the simplest way to hide access patterns is to store the files in an ORAM. Each file is split into chunks of size B, and each chunk is stored in a separate ORAM block. In order to fetch a file, the client queries all chunks of the file to the ORAM. When a file is queried, the only information leaked to the server is the number of chunks of the file.

In some settings, even that much information may be too much information. For instance, the number of chunks of a file might be enough information to uniquely identify the file [START_REF] Cash | Leakageabuse attacks against searchable encryption[END_REF]. In that case, repeated accesses to the file are leaked to the server. This reveals the access pattern of the client to the files, defeating the purpose of ORAM. More subtly, the length of answers to certain types of database queries can be enough to infer the entire contents of encrypted database [START_REF] Grubbs | Paterson. Pump up the volume: Practical database reconstruction from volume leakage on range queries[END_REF]. Traffic analysis attacks are another example of using length information to infer sensitive data [START_REF] Dyer | Peek-a-boo, i still see you: Why efficient traffic analysis countermeasures fail[END_REF]. Attacks that exploit length information can be particularly insidious, because traditional encryption does not attempt to hide length.

If leaking the lengths of the files is judged to be too damaging, the client may wish to use additional mechanisms to protect their privacy. Going back to our running example about private file storage, the simplest and most secure protection is to mandate that, whenever a file is accessed, the client should query as many chunks as the size of the largest file. In that case, only the number of chunks of the largest file is leaked to the server-or an upper bound on that number.

Let N be the total size of the files to be stored on the remote server. Let B be the ORAM block size, and let U be an upper bound on the size of the largest file (all quantities are counted in number of memory words). The overhead of ORAM constructions typically scales in Polylog(n), where n is the number of blocks stored in the ORAM. Setting aside padding issues for a moment, with block size B, we have n = N/B. In order to minimize the overhead, it would be attractive to simply set B = U . But here again, we would run 4.1. INTRODUCTION into padding issues: most files might be much smaller than the largest file. The optimal solution would be a weighted ORAM able to accommodate files of arbitrary size up to U , with an overhead Polylog(N/U ), or optimally, log(N/U ).

Our Contributions

The discussion so far leads to the following question: can we devise a weighted ORAM-that is, an ORAM that natively accommodates items of variable size? Beside the motivating applications given in the introduction, the existence of weighted ORAM may be viewed as a natural question: it fits within a long line of work on weighted allocation mechanisms, both within and outside cryptography, such as [TW07, BFHM08, ANSS16, BBF + 21, MR22].

We answer the previous question in the affirmative, and build a weighted ORAM. Our construction naturally handles not only items of different sizes, but items whose size varies with time, without the need for padding. To state the result precisely, let us introduce some notation. In the remainder, an atomic item stored within the ORAM is called a block. Let B denote an upper bound on the block size. Unlike traditional ORAMs, blocks can take any size in [1, B]. We will sometimes call the size of a block its weight. Let w i ∈ [1, B] denote the weight of the i-th block. Let m be the total number of blocks. Let N be an upper bound on the total weight i≤m w i . We want to build an ORAM that can accommodate any vector w = (w i ) i≤m of weights, as long as the following two conditions are fulfilled.

Condition 1. Every block w i has weight at most B;

Condition 2. The total weight w i is at most N .

For ease of exposition, we will assume that the number of blocks m is fixed, but our constructions can be easily adapted to a variable number of blocks, so long as the previous two conditions continue to hold. The parameters of our ORAM constructions will depend only on B and N ; crucially, they do not depend on the distribution of the weight vector w.

The interface of our weighted ORAMs is identical to standard ORAM: to retrieve a block, the client queries an identifier of the block (e.g. a virtual memory address). When writing a block, the client also inputs new data for the block. This data need not be of the same size as the data originally associated to the block identifier. The client can freely change the size of a block with every access, as long as Conditions 1 and 2 remain true.

As our main contribution, we build a weighted ORAM in the sense given above. In fact, we show a significantly stronger result. Many standard Tree-based ORAM algorithms admit a natural extension to handle blocks of variable size: at setup, the ORAM is dimensioned as if to accommodate N/B blocks of size B, but instead receives an arbitrary number of blocks of variable size bounded by B, with total size N . These blocks are read and written through the ORAM in essentially the same way as in the original, fixed-block size Tree ORAM, except for minor alterations to reflect the fact that blocks do not have the same size.

The main obstacle with that approach is technical. While Path ORAM is one of the most attractive solutions for practical Tree ORAM [SvS + 13b], its correctness proof is notoriously difficult-prompting the introduction of Simple ORAM as a less efficient variant that allows for a simpler correctness proof [START_REF] Chung | A simple ORAM[END_REF]. Our main result is to show that the natural weighted extensions of several existing Tree ORAM schemes, including Path ORAM and Simple ORAM, are in fact correct. For that purpose, we introduce a general framework: we prove that as long as a Tree ORAM fulfills a certain structural property, its weighted extension preserves correctness. The centerpiece of the proof is a Schur-convexity argument, which ultimately reduces the correctness of the weighted extension to that of the original ORAM. (An overview of the proof argument is given in Section 4.4.3, before the formal proof.) Practical experiments show that our weighted ORAM construction behaves in line with the analysis.

As an application of weighted ORAM, we build two SSE schemes, ZeroSSE and BlockSSE. Unlike most of SSE literature, both constructions completely hide access patterns. To our knowledge, ZeroSSE is the only construction that leaks neither the access pattern nor the size of retrieved objects, with full correctness. (The only other construction that we are aware of, in [START_REF] Kamara | Structured encryption and leakage suppression[END_REF], pays the price of having a non-negligible correctness failure probability.) BlockSSE hides access pattern, but not the size of retrieved objects. To our knowledge, it is the only ORAM-based SSE with worst-case server storage O(N ), rather than O(BN ), where B is the ORAM block size.

Our main result builds on Tree ORAMs, because of their higher practical efficiency compared to hierarchical ORAMs. This makes tree-based construction currently more attractive for applications such as SSE. Nevertheless, it is worth remarking that the position map of a weighted Tree-based ORAM, as we have built, has blocks of fixed size. Hence, it can be stored using any standard ORAM scheme, not necessarily tree-based. In particular, from a more theoretical perspective, the position map can be stored using an optimal ORAM with logarithmic overhead, following the groundbreaking result of Asharov et al. [AKL + 20]. This results in a weighted ORAM with logarithmic overhead. The question of building weighted hierarchical ORAM schemes is briefly discussed in Appendix B.4.

As another direct application of our construction, setting the block size B of our weighted ORAM to be equal to an upper-bound bound U on the size of the largest item to be stored in the ORAM, we immediately deduce from our construction weighted Path ORAM a length-hiding ORAM with communication overhead O(log 2 (N/U )). If we use an optimal (standard) ORAM for the position map, as indicated above, we obtain a lengthhiding ORAM with communication overhead log(N/U ). This overhead is optimal, since such a goal includes as a special case the setting where all blocks have size U , and is thus subject to known ORAM lower bounds for an ORAM storing N/U blocks [GO96, LN18].

Related work

While there is a rich literature on ORAM, surprisingly little of it deals with objects of variable size. To the best of our knowledge, only two articles mention this subdomain of ORAM.

In [START_REF] Daniel | A practical oblivious map data structure with secure deletion and history independence[END_REF], Roche et al. present the first ORAM that stores objects of variable size. Their goal is to build a remote data structure that satisfies the security requirements of ORAM, and in addition allows for secure deletion of items and history independence. In other words, in the case of a total leakage of the structure (such an event is referred to as a catastrophic attack):

• Items that have been deleted by the client can never be recovered through leaked data.

GENERAL PRELIMINARIES

• The internal structure does not reveal information about which elements were last accessed.

The data structure is built on top of a weighted ORAM. However, their construction for such an ORAM is limited: obliviousness and correctness (i.e. the client-side stash overflows with negligible probability) can be proven only if the size of the blocks follow a geometric probability distribution. In comparison, although we assume that block sizes are bounded by B, we do not need to assume anything on the distribution of block sizes. In more detail, there are two limitations to the assumptions of [START_REF] Daniel | A practical oblivious map data structure with secure deletion and history independence[END_REF]. First, many common distributions are not upper-bounded by a geometric distribution, for instance Zipf distributions. Second and more fundamentally, the ORAM user has no reason in general to pick item sizes independently, or to pick them from the same distribution. The construction of [START_REF] Daniel | A practical oblivious map data structure with secure deletion and history independence[END_REF] was designed with a specific use case in mind; its applicability beyond that use case is limited. Another construction of ORAM for objects of variable size may be found in [LHL + 18]. Their construction is also based on Tree ORAMs. The idea is to allow block size to be equal to a multiple of some value s (padding up to a multiple if needed), and to store all "splinters" of size s of a block along the same path from root to leaf. This construction has the strong requirement of a trusted proxy that shuffles blocks during certain operations. Moreover, the construction is flawed: cf. Appendix B.3.

Organization of the chapter

In Section 4.3 we recall the definitions of ORAM, SSE, and Schur convexity, a tool we will use in our proof. Section 4.4 is where we state our generic criterion for converting a standard ORAM into one that supports objects of variable size, and prove our main result. Concrete examples of known ORAM schemes that we can turn into weighted ORAM are presented in Section 4.5. An alternative generic construction that converts any ORAM into a weighted ORAM at the cost of a small blowup is presented in Appendix B.2. We discuss applications to the field of SSE in Section 4.6.

General Preliminaries

Throughout this work, memory size will be counted as a number of memory words. It is assumed that a memory word is large enough to store any address in memory. In practical applications, one may think of 64-bit or 128-bit words. Algorithms will be considered in the RAM model, where accessing an arbitrary memory word costs O(1) operations.

The security parameter is denoted by λ. A quantity is said to be negligible, denoted negl(λ), if it is O(λ -c ) for every constant c. A probability is said to be overwhelming if it is 1 -negl(λ). It is always assumed that the number of blocks n stored in the ORAM satisfies n ≥ λ, so that any quantity that is negl(n) is also negl(λ).

When an algorithm A with input x is probabilistic, we may sometimes explicitly write the random coins used by A as an input of A, separated by a semicolon, as in A(x; r).

Majorization and Schur Convexity

Given a vector v in R m , we denote by v ↓ ∈ R m the vector with the same components, sorted in decreasing order. Definition 3 (Majorization order). Let v, w be two vectors in R m such that m i=1 v i = m i=1 w i . The vector w is said to majorize v, written v ≺ w, if:

∀k ∈ [1, m], k i=1 v ↓ i ≤ k i=1 w ↓ i .
Definition 4 (Schur convexity). Let f : R m → R. The map f is said to be Schur-convex if it is non-decreasing for the majorization order. That is, for any two vectors v, w with

m i=1 v i = m i=1 w i , v ≺ w ⇒ f (v) ≤ f (w).
Definition 5 (Convexity). Let f : R m → R. The map f is said to be convex if for any two vectors v, w in R m , and any α in [0, 1] ⊂ R, it holds that:

f (αv + (1 -α)w) ≤ αf (v) + (1 -α)f (w).
Definition 6 (Symmetry). Let f : R m → R. The map f is said to be symmetric if for any vector v ∈ R m , and any permutation matrix P over m elements, f (v) = f (P v).

The link between convexity and Schur convexity is visible in the next lemma.

Lemma 4.2.1. Let f : R m → R. If f is symmetric and convex, then it is Schur-convex.

We refer the reader to [START_REF] Albert W Marshall | Inequalities: theory of majorization and its applications[END_REF] for a detailed presentation of the theory of majorization, including a proof of Lemma 4.2.1.

ORAM Preliminaries

Weighted Oblivious RAM

A weighted ORAM, also written wORAM, is a pair of client-server protocols (Setup, Access), defined as follows.

• Setup(N, B, D) takes as input an upper bound N on the total amount of data, a block size B, and a set D of pairs of the form (a i , data i ), where the a i 's are pairwise distinct addresses, and data i is arbitrary data of size

|data i | ∈ [1, B].
Setup outputs an initial client state and initial server state.

• Access(op, a, data) takes as input an operation op ∈ {read, write}, an address a, and some data data of size |data| ∈ [1, B]. If op = read, Access outputs to the client the data last written to address a. If op = write, Access replaces the data written at address a by data. Access may also update the client and server states.

We say that Setup(N, B, D) is legal if the total amount of data in D (i.e. the sum of the sizes of the data i 's) is at most N . Likewise, we say that Access(op, a, data) is legal if address a was defined during setup, and in the case that op = write, if |data| ∈ [1, B], and the total amount of data contained in the database after replacing the data at address a by data remains of size at most N . On the other hand, it is not required that the size of data matches the size of the data previously written at a.

ORAM PRELIMINARIES

Definition 7 (Correctness). A wORAM scheme is said to be correct if, given a legal setup and any sequence of legal access operations, a read access at address a outputs the data last written to address a, except with negligible probability. Definition 8 (Security). A wORAM scheme is said to be secure if, given any two legal sequences of operations of the same length (Setup(N, B, D), Access(op 1 , a 1 , data 1 ), . . . ,

Access(op k , a k , data k )) and (Setup(N, B, D ′ ), Access(op ′ 1 , a ′ 1 , data ′ 1 ), . . . , Access(op ′ k , a ′ k , data ′ k )
), the views of the server arising from each sequence are computationally indistinguishable.

A few remarks are in order. First, although we have defined Setup and Access as general client-server protocols, it is common in ORAM to require that the server behave like a passive memory, allowing only read and write accesses. That is, the client only ever asks the server to read or write specific data at a specific address. The server performs no computation of its own. Although this is not required in the previous definition, the wORAM schemes in this work are in that model.

Second, it is assumed that the contents of all memory locations on the server are encrypted using IND-CCA encryption, with a key known only to the client. Whenever the client accesses a memory location, they can reencrypt the data at that location, so that the server cannot learn the contents of any memory location, or whether it was changed during the access. As a result, the only way the server can infer information is by observing which locations the client queries in server memory. That is why the security definition of wORAM (following that of ORAM) focuses only on memory locations.

Finally, note that standard ORAM is the special case of wORAM where all addresses store data of the same size B. If the total amount of data is N , then such a scheme contains n = N/B blocks. Throughout this chapter, the letter N is reserved for the total amount of data. In the case of standard ORAM, the letter n is used for the number of blocks, with n = N/B.

Tree ORAM

We build wORAM by altering standard ORAM schemes following the Tree ORAM paradigm. In this section, we provide a high-level algorithmic view of that paradigm. That view is purposefully designed to accomodate several existing Tree ORAM schemes. It will also lay the groundwork for the construction of wORAM in the next section.

Existing Tree ORAM schemes are standard ORAMs, designed to store items of fixed size. In a Tree ORAM, to store n items of size B, the server creates a full binary tree with n leaves. (From now on, we assume n is a power of 2, increasing to the next power of 2 if necessary.) Throughout the chapter, the root of the tree is viewed as being at the top, and leaves as being at the bottom of the tree. Given a leaf l of the tree, the path from the root to the leaf l is denoted by P(l).

Each node of the tree, also called a bucket, can store up to Z data blocks of size B. Nodes are always padded to be of size ZB before being stored (encrypted) on the server.

In addition to the tree, the server may also store a stash, which may contain additional data blocks that could not fit in the tree. In the remainder, we view the stash as a special node directly above the root. This is relevant in two situations. First, there may be cases where a node is full (i.e it contains Z items), and where additional items need to be pushed to the parent node; if this happens at the root level, overflowing items are pushed to the stash. Second, whenever we consider the path P(l) from some leaf l to the root in the tree, we implicitly (and slightly abusively) also consider the stash to be part of the path. The stash is always padded to some upper bound R, before being stored (encrypted) on the server.

To each item with address a is associated a leaf of the tree pos(a). The array mapping each address a to the corresponding leaf pos(a) is called a position map. For now, we will assume the position map is stored by the client. By design, Tree ORAMs maintain the following invariant at all times: the item at address a is stored in one of the nodes on the path P(pos(a)) from the root to the leaf pos(a) (including the stash, as noted earlier).

During setup, each item with address a is stored in the leaf pos(a); or if it is full, in the lowest parent of pos(a) that is not yet full. To access item a, the client retrieves pos(a) from the position map, then reads the path P(pos(a)) on the server. Thanks to the invariant, that path contains the item a. Item a is then assigned a new uniformly random leaf. Finally, a special eviction procedure is called, which re-inserts item a somewhere on the path to its newly assigned leaf, and may also move other items.

Pseudo-code for the Access procedure is given in Algorithm 1, with additional parameters Z (the number of blocks per bucket, specifided by the Tree ORAM scheme; to reflect the fact that Z is an internal parameter of the ORAM construction, and not part of its interface, it is written between brackets), and random coins r. It makes use of the following subroutines:

• ReadBucket(bucket) retrieves a set of pairs (a i , data i ) from the tree node bucket.

• RemoveBlock(bucket, a) removes the item with address a from the tree node bucket.

• ChooseEvictionPath outputs a path for eviction, which differs depending on the specific Tree ORAM scheme. data = newdata 8: stash ← stash ∪ {(a, data)} 9: path ← ChooseEvictionPath(leaf ) 10: Evict[Z; r](path) 11: return data Pseudo-code for the Evict procedure is given in Algorithm 2, with additional parameters Z (the number of blocks per bucket, specifided by the Tree ORAM scheme), and random coins r. It makes use of the following subroutines:

• Size(X) returns the number of items |X| in X.

• ChooseNextBlock(stash, bucket, path) pops an item from the stash, to be stored in the bucket, or outputs ⊥.

ORAM PRELIMINARIES

Algorithm 2 Generic eviction algorithm.

Evict[Z; r](path):

1: Move all blocks in path to the stash 2: for bucket in path do 3:

X ← ∅ 4:
while Size(X) < Z do 5:

block ← ChooseNextBlock(stash, bucket, path)

6: if block = ⊥ then 7: break 8: else 9:
X ← X ∪ {block} 10:

WriteBucket(bucket, X, Z)

11: return

• WriteBucket(bucket,X,Z) writes the items in X to the node bucket, padding the node to size Z if needed.

We will discuss in Section 4.5 how several existing Tree ORAM schemes are captured by the above paradigm.

Correctness of Tree ORAM

Since Tree ORAM is a special case of ORAM, the correctness definition remains the same (Definition 7). However, because of the specificities of Tree ORAM, it can be reformulated in a more convenient manner. That is, the only correctness failure that can occur in a Tree ORAM scheme is that the stash overflows. (The reader familiar with Tree ORAM may object that some Tree ORAM schemes do not use a stash; that case will be handled in Section 4.5.)

Recall that the stash is always padded to size RB, i.e. it can store up to R items. Hence, correctness amounts to the following statement: at the outcome of any sequence of legal accesses (Setup, Access 1 , . . . , Access k ), it holds that Pr[Size(stash) > R] = negl(λ).

The ∞-ORAM Model

Consider a Tree ORAM instantiation ORAM Z ← Setup[Z](N, B, D), with bucket capacity Z. If s is a sequence of accesses, we call st(ORAM Z [s]) the stash usage, that is, the number of items in the stash at the outcome of the accesses.

In Path ORAM and many Tree ORAM schemes derived from it, the proof of correctness follows similar steps:

• Consider an infinite ORAM structure ORAM ∞ , which is the same protocol, except buckets have infinite capacity (that is, Z = ∞).

• Define a post-processing algorithm G Z that moves items in the tree produced by running ORAM ∞ (arranging in particular that each tree node contains at most Z items). Denote the stash usage of the post-processed ∞-ORAM by st Z (ORAM ∞ [s]).

• Prove that st(ORAM Z [s]) = st Z (ORAM ∞ [s]) when using the same random coins on both sides.

• Prove that Pr

[st Z (ORAM ∞ [s]) > R] = negl(N ).
The last two points imply that Pr[st(ORAM Z [s]) > R] = negl(N ), i.e. the original ORAM scheme is correct. We say that such a protocol admits a proof via infinite ORAM.

Generic Construction of wORAM from Tree ORAM

Our goal is to give a generic way to transform an existing standard Tree ORAM design into one that supports blocks of variable size. The transformation presented in this section is perhaps the most natural transformation one could imagine for that purpose. The main challenge is not the transformation itself, but rather proving that it preserves correctness.

Still, there is one aspect of the transformation whose necessity may not be immediately apparent. Namely, if the original ORAM has bucket capacity Z, then its weighted version will have bucket capacity Z + 1. This change is not necessary for the main theorem of this section to hold. However, it will be necessary when applying the main theorem to specific ORAMs, notably Path ORAM: see the discussion at the end of Section 4.5.2. In practice, experiments in Section 4.4.4 suggest that this increase in bucket capacity can be heuristically dispensed with.

The Weighted Transform

We define a general transform Weighted that takes as input a standard Tree ORAM scheme ORAM Z = (Setup, Access) following the framework of Section 4.3.2, and outputs a weighted ORAM scheme Weighted(ORAM Z ) = ORAM * Z = (Setup * , Access * ).

Let us first consider the setup. We say that the starting scheme ORAM Z has a regular setup if its setup procedure is equivalent to creating an empty tree with all items in the stash, then doing repeated evictions towards every leaf in the tree from left to right. Here, by "equivalent" we mean that the output of this process and the output of the normal setup process are identically distributed. In our main theorem, we will require that the starting Tree ORAM ORAM Z has a regular setup. Although that notion of regularity is non-standard, it has the benefit that the behavior of the setup process can be deduced from that of the eviction process. For our purpose, this means it will be enough to explain how to transform the eviction process to handle blocks of variable size.

ORAM * Z is defined in the following way, making only minimal modifications to ORAM Z to handle items of variable size.

• Setup * (N, B, D) initializes a tree with N leaves, whose nodes can each hold data of size (Z + 1)B, and a stash of the same size RB as the standard instance ORAM Z . It initializes a position map where each address a in D is mapped to a uniformly random leaf. Finally, it performs a regular setup: that is, all items in D are placed in the stash, and the Evict * procedure is called on the path from the root to each leaf, from left to right.

• Access * is identical to Access, except that it calls the modified subroutine Evict * .

• Evict * is identical to Evict, except that it calls the modified subroutines Size * and WriteBucket * .

GENERIC CONSTRUCTION OF WORAM FROM TREE ORAM

• Size * (X) returns the sum of the sizes of all items in X divided by B, instead of the number of items in X.

• WriteBucket * (bucket, X , Z ) still writes the items in X to node bucket, the only difference is that it pads the bucket to size Z + 1 instead of Z.

Suitable Tree ORAM Schemes

For the Weighted transform to preserve correctness, the original standard ORAM scheme must satisfy certain conditions. This section serves to define those conditions. Given a sequence of accesses s, some fixed random coins r used during those accesses, and a subset S of nodes in an ∞-ORAM scheme ORAM * , define the usage of S, written u S (ORAM * ∞ [s; r]), to be the total number of items assigned to the nodes in S. For a wORAM scheme, the usage of S is defined to be the total size of the items assigned to nodes in S, divided by the block size B.

As discussed in Section 4.3.2, a correctness failure for a Tree ORAM scheme ORAM occurs if and only if, at the outcome of a series of accesses s with random coins r, the stash receives strictly more than R elements. Using the notation from Section 4.3.3, this translates to st(ORAM Z [s; r]) > R. We say that a subset S of nodes witnesses the failure if, in the corresponding ∞-ORAM scheme ORAM * when performing the same sequence of accesses using the same random coins (viz. the choices of fresh uniformly random leaves for the position of each accessed item remain the same),

u S (ORAM * ∞ [s; r]) > |S| • Z + R.
Intuitively, since the nodes in S can store at most |S| • Z items, it is clear that more than R items must be reassigned to the stash in the original ORAM, which breaks correctness: that is why we say that S witnesses the failure. Definition 9 (F ⇒ W, W ⇒ F). We say that ORAM satisfies the F ⇒ W property (read: "failure implies witness") with respect to a set S of subset of nodes, iff for all access sequences s and all choices of random coins r, st(ORAM Z [s; r]) > R implies ∃S ∈ S , u S (ORAM * ∞ [s; r]) > |S| • Z + R. We say that ORAM satisfies the W ⇒ F (read: "witness implies failure") property if the converse is true.

Moreover, we say that ORAM satisfies the F ⇒ W (resp. W ⇒ F) property via union bound if the scheme also satisfies that

S ∈S Pr[u S (ORAM * ∞ L [s]) > |S| • Z + R] = negl(λ).
Informally, this means the statement "the probability that a failure witness exists is negligible" can be proved via a union bound over all possible witnesses S ∈ S .

The definitions remain the same for a wORAM scheme. In particular, for a wORAM scheme ORAM * , a subset S witnesses a failure if u S (ORAM * ∞ L [s]) > |S| • Z + R (and not |S| • (Z + 1) + R, even though our construction of wORAM uses buckets of size (Z + 1)B).

Definition 10 (Suitable Tree ORAM). We say that a Tree ORAM scheme is suitable if it satisfies the following conditions.

1. It admits a proof via infinite ORAM. That is, for all access sequence s and random coins r, st(ORAM

Z [s; r]) > R iff st Z (ORAM ∞ [s; r]) > R.
2. ORAM satisfies the W ⇒ F property with respect to some set S , via union bound.

3. Weighted(ORAM) satisfies the F ⇒ W property with respect to the same S .

4. ORAM allows free evictions. That is, if the client is allowed to trigger evictions on uniformly random leaves at will during a sequence of accesses, correctness still holds.

Requiring all those properties may seem demanding, but they naturally hold for several existing Tree ORAM schemes, including Path ORAM and Simple ORAM. This will be shown in more detail in Section 4.5. Intuitively, this is because many schemes admit a proof via infinite ORAM, either explicitly (in the case of Path ORAM), or trivially (in the case of Simple ORAM, where the ORAM and its infinite variant are identical up to correctness failures). Similarly, the F ⇒ W property is either already known, or trivial; and the free eviction property is immediate. The only property that requires some care is to show that Weighted(ORAM) satisfies the F ⇒ W property. However, it is much more tractable than trying to analyze the correctness of a wORAM scheme directly.

Main Result

Theorem 4.4.1 (Main Theorem). Let ORAM be any suitable Tree ORAM scheme. If ORAM is a correct ORAM scheme, then Weighted(ORAM) is a correct wORAM scheme.

Before diving into the proof proper, we sketch the underlying approach. Because of the F ⇒ W and W ⇒ F properties required by the suitability assumption, showing the wORAM scheme is correct essentially amounts to showing that no set S ∈ S witnesses a failure (except with negligible probability). We wish to analyze the function that maps the sizes of items to the usage of S (i.e. the sum of sizes of all items in S). Ultimately, we want to show that the probability that the usage of S exceeds |S| • Z + R is negligible, regardless of item sizes.

The proof strategy is to upper-bound the previous probability by a Schur-convex function (Section 4.2.1), and show that this function is negligible. The idea behind this strategy is that if a function of item sizes is Schur-convex, then in order to upper bound the function for all possible vectors of item sizes, it is enough to upper-bound it for a set of maximal vectors for the majorization order. Luckily, due to the requirement that item are of size at most B, and that the sum of items sizes is at most N B, a single weight vector majorizes all others, namely the vector (B, . . . , B, 0, . . . , 0). Hence, it is enough to upper-bound the function for that specific vector. This is quite convenient, because that weight vector essentially amounts to having all items be of the same size, which reduces to the correctness of the original (unweighted) ORAM instance.

To instantiate the proof idea outlined above, the core argument is to show that there exists a suitable Schur-convex function. This is done via a first-moment argument (Lemma 4.4.2), which allows us to work with expectations instead of probabilities. Expectations are much better behaved with respect to convexity (due to the linearity of expectation). Eventually, we get the upper bound to metamorphosize into a suitable Schur-convex function (in the proof, this is the map w → E[X s,L,S (w)]), and show it is convex essentially by showing that it is structured as a composition of convex maps. Using Lemma 4.2.1, we deduce that it is Schur-convex.

Proof. We start with a small self-contained lemma.

Lemma 4.4.2. Let X be an integral random variable defined over [0, t] ⊂ N, with t ∈ Poly(λ). Then Pr[X > R] = negl(λ) if and only if E(max(0, X -R)) = negl(λ).

GENERIC CONSTRUCTION OF WORAM FROM TREE ORAM

Proof. Recall that the expectation of a positive integral variable Y can be written as:

E(Y ) = i≥0 Pr[X > i].
As a corollary, for any integral variable Y satisfying 0 ≤ Y ≤ t:

Pr[Y > 0] ≤ E(Y ) ≤ t Pr[Y > 0]. (4.1)
Observe that the event X > R is equivalent to max(0, X -R) > 0. Using that observation, and applying (4.1) to the variable Y = max(0, X -R), we get:

Pr[X > R] ≤ E(max(0, X -R)) ≤ t Pr[X > R].
Since t ∈ Poly(λ), we are done. ■

Let ORAM be a suitable and correct Tree ORAM scheme. Let ORAM * ← Weighted(ORAM). Let s be a legal sequence of accesses for ORAM * . We need to show that Pr[st(ORAM

* [s]) > R] = negl(λ).
Since ORAM satisfies the F ⇒ W property with respect to some set S , it suffices to show that the probability that there exists S ∈ S witnessing the failure is negligible, i.e.

Pr[∃S ∈ S , u S (ORAM * ∞ L [s]) > |S| • Z + R] is negligible. Let us fix S ∈ S . We want to show that Pr[u S (ORAM * ∞ L [s]) > |S|•Z +R] is negligible.
(This is not enough to imply that the probability that there exists such an S is negligible, since S may have superpolynomial cardinality; we will come back to this point later.) A crucial observation is that in ORAM * ∞ L , the sizes of data items plays no role. In particular, given an access sequence s and associated random coins r, the location of each item in the tree is entirely determined independently of the size of the data items.

Given an access sequence s with m items in total, and a size allocation vector w = (w i ) i≤m ∈ [0, 1] m , define s(w) to be the access sequence s, modified such that at the outcome of the sequence the i-th item has size w i . Let Π be the set of permutation matrices of size m. Let X s,L,S (w) = max P∈Π (max(0, u S (ORAM * ∞ L [s(P w)]) -

(|S| • Z + R))). By Lemma 4.4.2, E[X s,L,S (w)] is an upper bound on Pr[u S (ORAM * ∞ L [s]) > |S| • Z + R],
so it is enough to show that E[X s,L,S (w)] is negligible. This will follow from the next lemma. Proof. First, we show that X s,L,S is convex when the random coins used in the ORAM construction are fixed. Until further notice, we assume that all random coins are fixed. Only w varies. Let λ ∈ [0, 1], and let v, w be two size allocation vectors. Observe that the map g : w → u S (ORAM * ∞ L [s(P w)]) is linear. This is because, as already noted, whether an item is stored in a node from S or not is independent of the weight of the items. As a consequence, g(w) is equal to the sum of the weights of items stored in S, i.e. it is a fixed linear combination of w i 's (with binary coefficients). Since g is linear, it is trivially convex.

Also observe that for any constant C, the map h : x → max(0, x-C) is increasing and convex. Since the composition of an increasing convex function with a convex function is convex, we deduce that the map h • g is convex. Since X s,L,S (w) = max P∈Π h • g(Pw), it is a maximum of convex maps, so it is also convex.

On the other hand, X s,L,S (w) is symmetric by construction, since it takes the maximum over all permutations of w. By Lemma 4.2.1, since X s,L,S (w) is both symmetric and convex, it is Schur-convex.

It remains to show that Schur convexity still holds when considering the expectation of X s,L,S (w). (From now on, we no longer assume that random coins are fixed.) However, it is straightforward to show that if a probabilistic map is Schur-convex for every fixed choice of random coins (sometimes called stochastical Schur-convexity), then its expectation is also Schur-convex [START_REF] Albert W Marshall | Inequalities: theory of majorization and its applications[END_REF]. We conclude that w → E[X s,L,S (w)] is Schur-convex. ■ Corollary 4.4.4. Let s be a legal sequence of accesses with weight vector w, and let S ∈ S . Then E[X s,L,S (w)] is negligible.

Proof. For an access sequence to be legal, its weight vector w must satisfy that w i ≤ B for all i, and w i ≤ N B. Observe that all such vectors are majorized by the vector v = (B, . . . , B, 0, . . . , 0) containing (v)]: in order to upper bound E[X s,L,S (w)], it suffices to focus on the weight vector v. (This is the point of using a Schur-convexity argument.) But in the case of the vector v, all items are of the same size B, or of size 0.1 In that case, ORAM * behaves exactly like ORAM, except that accesses to items of size 0 translate to evictions without any prior item access. In particular, the usage of S is the same for ORAM * and ORAM. Since we assume that ORAM has the free eviction property, it remains correct when allowing eviction queries by the client. Since it is also assumed to be correct and to satisfy W ⇒ F, it follows that the usage of S cannot exceed |S| • Z + R except with negligible probability, hence the same holds for ORAM * , and we are done. ■ So far, we have shown that the probability that any given S witnesses a failure in ORAM * is negligible. To conclude the proof, it remains to show that the probability that there exists an S ∈ S witnessing a failure is negligible. This does not follow immediately from the previous statement, because |S | may be superpolynomial. However, looking at the proof of Lemma 4.4.2, we see that when switching from expectation to probability and back, we only lose a factor t. In our case, the stash size is a random variable bounded by N B, so we have that for every S,

N initial B's. Since E[X s,L,S (w)] is Schur-convex, it follows that E[X s,L,S (w)] ≤ E[X s,L,S
Pr[u S (ORAM * ∞ L [s(v)]) > |S| • Z + R] ≤ N B Pr[u S (ORAM ∞ L [s]) > |S| • Z + R].
Since ORAM is assumed to satisfy W ⇒ F via union bound, and N B ∈ poly(λ), we know that the sum of the latter quantity over all S ∈ S is negligible, hence ORAM * inherits the same union bound property. It follows that the probability that there exists a failure witness S for ORAM * is negligible. Since ORAM * satisfies the F ⇒ W property, we conclude that ORAM * is correct.

Experimental Results

To test empirically the correctness of our weighted ORAM, we implemented a Path ORAM structure and performed simulated accesses. We did two experiments: one with N objects 4.5. APPLICATION TO EXISTING TREE ORAMS of the same size (which simulates the standard case) and one with objects of variable sizes (the sizes are uniformly random, but sum to N ). Our results are presented as graphs in Figure 4.1. We took inspiration from the experiment in Section 7 of [SvS + 13b]. The experiment went as follows:

• We generated ORAM structures for N objects, with N = 2 L and L ∈ {10, 11, . . . , 22}.

The bucket size is Z ∈ {3, 4}

• We chose the maximum block size to be B = 512.

• For the standard ORAM simulation, all blocks were of size B. For the wrighted ORAM simulation, blocks were taken uniformly at random in [B], with the total sum of the sizes being N • B. The number m of blocks generated is roughly 2 • N .

• We start with the Path ORAM loaded randomly with the objects at its leaves, and perform between 10 • m and 50 • m accesses in the order {1, 2, . . . , m, 1, 2, . . .}.

Figure 4.1 suggests that objects of variable size are even less prone to stash overflows than the standard case. Regarding bucket size, we make an observation similar to that of [SvS + 13b]: even though the correctness of the ORAM was proved for Z + 1 = 6, the construction appears resilient enough to work correctly even when Z + 1 = 4. In [SvS + 13b], the empirical results suggest that Path ORAM can be used with Z as low as 4.

Application to Existing Tree ORAMs

In this section we present several concrete constructions: a weighted Simple ORAM, based on Chung and Pass's Simple ORAM [START_REF] Chung | A simple ORAM[END_REF], and a weighted Path ORAM, based on the seminal work by Shi et al.

[SvS + 13b].
The construction for Path ORAM can be easily adapted to build a weighted Random-Index ORAM from the one presented in [HK22], as the block-holding structure is virtually the same. We also sketch the application to Circuit ORAM [START_REF] Wang | Circuit ORAM: On tightness of the Goldreich-Ostrovsky lower bound[END_REF] and OPRAM [START_REF] Hubert Chan | On the depth of oblivious parallel RAM[END_REF]. By Theorem 4.4.1, in each case, it suffices to show that the scheme is suitable. The weighted variant is then obtained by applying the Weighted transformation.

Weighted Simple ORAM [CP13]

In SimpleOram, each bucket has a capacity of Z = O(log N ), and the ORAM overflows if and only if there is a bucket with more than Z items: there is no stash. From the perspective of the Tree ORAM framework from Section 4.3.2, a stash does exist, however, it is required that it is empty at the outcome of any (legal) sequence of accesses. That is, we set the stash bound R to 0.

In SimpleOram:

• The ChooseEvictionPath(leaf ) method is implemented by choosing a path uniformly at random (the leaf argument is ignored). • The ChooseNextBlock(stash, bucket, path) method is implemented by returning the first item among items whose position is such that its meet with the current path is exactly bucket. (In other words, all items are stored as low as possible along the eviction path, while preserving the invariant that they are stored above their associated leaf.) The correctness of SimpleOram relies on the fact that all such items will fit in the current bucket; items are never pushed somewhere else in case a bucket is full.

We want to show that SimpleOram is suitable. Define S to be the set containing the singleton {bucket} for each tree node bucket. The fact that the correctness of SimpleOram is equivalent to the fact that no element of S witnesses a failure is immediate, since the correctness of SimpleOram requires precisely that no node overflows. Hence, SimpleOram satisfies W ⇒ F (and F ⇒ W) with respect to S . The fact that Weighted(SimpleOram) satisfies F ⇒ W is immediate for the same reason. SimpleOram also satisfies the union bound requirement, because its analysis in [START_REF] Chung | A simple ORAM[END_REF] relies on just such a union bound. The fact that it supports free evictions also follows directly the analysis in [START_REF] Chung | A simple ORAM[END_REF] (additional evictions translate to more success chances in the dart game argument at the center of the analysis). We conclude that SimpleOram is suitable.

Theorem 4.5.1. Weighted(SimpleOram) is a correct wORAM scheme.

Weighted Path ORAM [SvS + 13b]

Let ORAM Z ← PathOram.Setup(N, Z) be an instance of Path ORAM. The bucket capacity Z for Path ORAM is a small constant; the scheme is proven correct for Z = 5, we shall use this value. The stash capacity is R = O(log N ).

In PathOram:

• ChooseEvictionPath(leaf ) simply returns P(leaf ).

• ChooseNextBlock(stash, bucket, path) returns an item from the buffer such that its associated leaf is below bucket, and the meet between the position of the item and path is lowest among such items.

Theorem 4.5.2. Weighted(PathOram) is a correct wORAM scheme.

Proof. Define S to be the set of all subtrees of the ORAM tree, where a subtree is defined to be a subset of nodes closed for the parent relation (i.e. if the set contains a node, it also contains its parent). The analysis of [SvS + 13b] proves that PathOram satisfies both F ⇒ W and W ⇒ F with respect to S , via a union bound. The fact that PathOram supports free evictions also follows from the analysis. In the remainder, we focus on showing that PathOram * ← Weighted(PathOram) satisfies F ⇒ W. We follow a similar approach to the initial part of the analysis in [SvS + 13b]. Let us define a post-processing algorithm G Z , which is applied to ORAM * ∞ after a sequence of accesses. Like in the original analysis of Path ORAM, the G Z algorithm is a "thought experiment": that is, the algorithm is used within the proof, but never actually run by any party in the ORAM protocol. As a consequence, we can allow G Z to perform operations that are not normally allowed within the wORAM framework. In particular, we let G Z "split" any object of size w in two objects of sizes w 1 and w 2 such that w 1 + w 2 = w, storing the two chunks at distinct locations. G Z repeats the following process, as long as there are overfull buckets (i.e. whose size is strictly more than Z-to avoid cluttering the notation, all sizes are implicitly divided by the block size B):

1. Select a bucket b that has load strictly more than Z. Remove blocks from the bucket (splitting if needed) so that it ends up having load exactly Z. Removed blocks are stored in a temporary buffer.

2. Find the nearest ancestor of b that has load strictly less than Z. Store items from the buffer into this ancestor, until its load is exactly Z (or the buffer is empty), splitting if needed.

3. As long as the buffer is not empty, repeat the previous step, working our way up the path P(b), until reaching the stash. At that point, any remaining items in the buffer is stored in the stash.

First, let us prove that the stash usage (i.e. the cumulated size of all items in the stash) of the post-processed ∞-ORAM is greater than the stash usage of ORAM * Z :

st Z (ORAM * ∞ [s]) ≥ st(ORAM * Z [s]). (4.2)
First, notice that the order in which overfull blocks are processed by G Z has no bearing on the final occupancy of the nodes and stash. In particular, st Z (ORAM * ∞ [s]) is welldefined, even though we put no restriction on the order in which G Z processes overfull buckets. To show this, we can generalize the argument from [SvS + 13b]: assume that G Z processes blocks from the bucket β 1 at level l 1 on path p 1 , then blocks from the bucket β 2 at level l 2 on path p 2 . We want to show that the loads in the buckets in p 1 ∪ p 2 do not change if we let G Z process β 2 before β 1 . Without loss of generality, we can assume that those buckets are siblings (i.e. l 1 = l 2 = l), since only p 1 ∩ p 2 will be affected by a change in the order. Assume that the post-processed blocks from β 1 (resp. β 2 ) are of total size W 1 (resp. W 2 ). G Z first distributes a "mass" of size W 1 in the buckets from level l -1 to -1 in p 1 ∩ p 2 , and then a mass of size W 2 in those same buckets. Before the distribution, let us call V i the available space in the bucket at level i ∈ {-1, 0, . . . , l -1} on path p 1 ∩ p 2 . When distributing a mass W , G Z performs Algorithm 3 (we assume that V -1 = ∞): The {V i } are the same after a successive application of Algorithm 3 on W 1 Algorithm 3 Distribution of mass of blocks Distribution(W ):

1: i ← l 2: while W > 0 do 3: i ← i -1 4: if V i ≥ W then 5: V i ← V i -W 6: W ← 0 7: else 8: V i ← 0 9: W ← W -V i
then W 2 or after its application on W 2 then W 1 .

Remark. We wish to draw the reader's attention to one point: in what precedes, we consider for simplicity that blocks are taken in bulk from the buckets, whereas in what follows it is more convenient to assume that G Z processes them individually. It doesn't make a difference for the same reason that the order doesn't matter.

APPLICATION TO EXISTING TREE ORAMS

We can finally prove (4.2). Informally, we can see that during the accesses, ORAM * Z stores blocks in buckets and in the stash in a more lenient way than G Z , since it allows blocks to "stick out" of the buckets. More precisely, after the accesses of s in ORAM * ∞ [s], there exists a way to move blocks from the buckets they reside in to their final destination from ORAM * Z [s] (in another bucket or the stash). Since the order in which we postprocess blocks from the buckets does not matter, we can assume that this particular order is accessed by G Z . If that is the case, after the processing of each block, G Z puts that block in the bucket where it belongs according to ORAM * Z [s]. However, should a part of the block (or its entirety) stick out of the bucket (i.e. causes the load to become ≥ Z), this part will be moved to a higher block or the stash. Thus the processing of each block by G Z causes the stash size to either stay the same or to increase. Thus at the end of the processing,

st Z (ORAM * ∞ [s]) ≥ st(ORAM * Z [s]).
We are now ready to show that Weighted(PathOram) satisfies F ⇒ W. By (4.2), if correctness fails for Weighted(PathOram), then it also fails (with the same random coins) for the post-processed ∞-ORAM variant. That is, st Z (ORAM * ∞ [s]) > R. Let us define T to be the maximal subtree that only contains buckets of size at least Z after the postprocessing. If a bucket b is not in T , it has an ancestor b ′ that has usage strictly less than Z, so the blocks of b cannot go to the stash. Thus all blocks in the stash came from buckets in T , and thus u T (ORAM * ∞ [s]) > n(T ) • Z + R. This shows that T is a failure witness.

Discussion. In the proof above, a "splitting" variant of wORAM was introduced. In that splitting variant, items can be split into pieces of arbitrary sizes, and each piece can be stored at a different tree node (still maintaining the invariant that all pieces belonging to the same item are stored somewhere along the path from the root to the leaf associated with the item). Splitting is a convenient intermediate abstraction, because of its "continuous" behavior, which avoids rounding issues.

It is worth noting that splitting is not just a proof abstraction, but could also be used in actual tree-based wORAM algorithms. In fact, we could have defined our weighted transformation to allow splitting. In that case, the proof above shows that the weighted variant of Path ORAM would have the same bucket capacity Z as the original Path ORAM.

By contrast, our actual construction, which does not use splitting, needs to increase the bucket capacity to Z + 1 to avoid "rounding" issues. Intuitively, without splitting, if a bucket of capacity ZB words contains data of total size (Z -1)B + 1, and the client wants to insert a block of maximum size B, it cannot fit in that bucket. This means each bucket can have up to B -1 words of "wasted" space. Note that this cannot happen in standard ORAM, where all items have size B: it is an issue specific to weighted ORAM (and weighted allocation mechanisms in general). Splitting solves the issue without the need to increase bucket capacity: the ability to split avoids any wasted space.

Our construction solves the issue differently, without splitting, by increasing bucket capacity to (Z + 1)B words (or Z + 1 full blocks). This guarantees that if a bucket cannot receive a new block, then it already contains at least ZB words. In short, the reason we increase bucket capacity to Z + 1 in our constructions is to resolve rounding issues inherent to fitting weighted items into buckets of fixed capacity.

As noted, we could have chosen to define our Weighted transformation to allow splitting. We avoided that option, because it complicates implementation in practice, and may require significantly more metadata (each piece needs an identifier tag). Nevertheless, it CHAPTER 4. WEIGHTED ORAM WITH APPLICATIONS TO SSE is a valid option, and may be preferable if a slightly lower Z is desirable.

Weighted Oblivious Parallel RAM [BCP16]

Boyle, Chung, and Pass's protocol [START_REF] Boyle | Oblivious parallel RAM and applications[END_REF] is based on Simple ORAM. Their framework present ORAM protocols for parallel algorithms, i.e. with multiple processors (clients). The Weighted function is not impacted by the fact that there are several clients: The modifications to the subroutines still capture this case, and the correctness analysis holds. The only new component is the broadcast routine, where one of the CPUs broadcasts information about a certain block to the other CPUs. These messages are bounded by the size of the block. That could lead to a leakage however: we need to index every block, in the weighted case there are m objects and log m ≥ log N . Thus, we can lower bound the size of the messages by O(log N ): their size will not leak information on the block. This yields a correct weighted OPRAM.

Weighted Circuit ORAM [WCS14]

Circuit ORAM is a variant of Path ORAM, where the client only needs local space to hold one block. To achieve this, the eviction algorithm is slightly different and the stash is stored by the server (as the parent of the root node) instead of locally. The correctness analysis of this scheme is based on the same principles as the one for Path ORAM. The function Weighted yields a correct ORAM here too. To prove this, we only need to show how we can adapt for the fact that the stash is stored on top of the tree. Figuring out which way to do this is not obvious since, because of the varying block size, the client cannot simply stream the content of the stash block by block: it would leak block size information. We propose a simple fix, which we also use when dealing with Trivial ORAM:

Object Chunks

• We allow the client to store an additional space of size B (the maximal size of a block). This gives the client a local space of at least 2 • B.

• Whenever the client needs to access the stash, the client streams the content of the stash chunk by chunk, where each chunk is of size B. That way, since a block must always reside inside at most 2 chunks (see Figure 4.2), the client will read every object at the end of the stash stream.

SEARCHABLE ENCRYPTION FROM WEIGHTED ORAM

• When the client wishes to write back a block, it is done locally among two chunks.

This way, the scheme stays correct and secure even with objects of variable size. The application of the suitability criterion shows that Circuit ORAM is compatible with blocks of variable size.

Searchable Encryption from Weighted ORAM

With Searchable Symmetric Encryption (SSE), a client can delegate the storage of a database to a honest-but-curious server. The client is then able to perform searches on the database by issuing Search queries to the server. In the case of dynamic SSE, the client may also update the database by issuing Update queries to the server. The security goal is that the information leaked to the server during these operations should be limited, in a sense that will be defined soon.

Here, we focus on the case of single-keyword search. In that setting, the client's database consists of a collection of documents, and Search queries ask to retrieve all documents that contain a given keyword. In modern SSE schemes, this functionality is realized efficiently by building a reverse index: For each keyword w, a list of the identifiers of documents matching the keyword, written DB(w), is maintained on the server side in some encrypted form. Response-revealing SSE allows the server to learn the list of document identifiers, while response-hiding SSE does not: they are sent back to the client in encrypted form. Once having retrieved the desired document identifiers, the client may perform some additional computation, such as intersecting the results with other queries, or may fetch the documents on the same or a different server. In the case of responserevealing SSE, if the same server stores the reverse index and the documents, the server can immediately send back the documents without the need of an additional roundtrip, at the cost of possibly leaking additional information to the server. We note that the documents could be stored in an ORAM to avoid additional leakage, and that a weighted ORAM would reduce the performance cost of this approach. However, as in most SSE literature, we focus on the reverse index.

For efficiency reasons, SSE typically does not seek to have minimum leakage, but rather to strike a compromise between security and performance by allowing a controlled amount of leakage. In the security model, the leakage allowed by the scheme is expressed by a leakage function L = {L Setup , L Search , L Update }. The security model asks that during a Setup operation (resp. Search, Update) with input x, the information leaked to the server is included in L Setup (x) (resp. L Search (x), L Update (x)). More formally, it is required that there must exist a simulator S such that the view of the server during Setup(x) (resp.

Search(x), Update(x)) should be indistinguishable from S(L Setup (x)) (resp. S(L Search (x)), S(L Update (x))).
Response-revealing SSE schemes leak the access pattern: That is, the server learns the identifiers of all documents matched by a query. In some use cases, access pattern leakage can be quite damaging, and allow the server to infer a sizable amount of information about the database [START_REF] Cash | Leakageabuse attacks against searchable encryption[END_REF][START_REF] Grubbs | Learning to reconstruct: Statistical learning theory and encrypted database attacks[END_REF]. Even in the case of response-hiding SSE, the server can typically learn the query pattern: that is, the server can learn whenever the client repeats the same query. In many cases, the server can learn the volume of the answer: that is, the number of documents matched by the query.

In some use cases, these different types of information leakage can be quite damaging, as shown by so-called leakage-abuse attacks [CGPR15, GSB + 17]. To thwart those Scheme client storage bandwidth overhead TWORAM attacks, recent works have developed various protections, such as volume-hiding SSE [KM19, PPYY19], and the line of work on leakage suppression [START_REF] Kamara | Structured encryption and leakage suppression[END_REF]. The strongest form of protection, considered for instance in [GMP16, MM17, KMO18], involves the use of ORAM, or specialized variants of ORAM. This raises some questions about how to optimize the use of ORAM, in order to preserve the high efficiency goal of SSE. In particular, as discussed e.g. in [START_REF] Garg | TWORAM: Efficient oblivious RAM in two rounds with applications to searchable encryption[END_REF], since reverse indexes contain lists that can greatly vary in size, it is not obvious how to fit them into a (fixed-block size) ORAM. Our main point in this section is that the weighted construction introduced here fits this setting perfectly. Concretely, we propose two SSE constructions based on weighted ORAM: ZeroSSE and BlockSSE. A brief overview is given Figure 4.3. We note that the main point of TWORAM, not reflected in the table, is to reduce the number of roundtrips in the iterative version of Path ORAM, thanks to a clever use of garbled circuits. However garbled circuits add a considerable overhead in practice.

[GMP16] O(1) O(λ log 2 N ) ZeroSSE O(W ) O(log(N/U )) ZeroSSE ′ O(1) O(log 2 W + log(N/U )) BlockSSE O(W ) O(log(N/B)) BlockSSE ′ O(1) O(log 2 W + log(N/B))

Preliminaries

We follow the standard definition of SSE. A dynamic SSE scheme Σ consists of four protocols, defined as follows.

• Σ.KeyGen(1 λ ): Takes as input the security parameter λ. Outputs the master secret key K.

• Σ.Setup(K, N, DB): Takes as input the client secret key K, an upper bound on the database size N , and a database DB. Outputs an encrypted database EDB.

• Σ.Search(K, w, st; EDB): The client receives as input the secret key K, and keyword w. The server receives as input the encrypted database EDB. Outputs the list of document identifiers associated with the keyword w

• Σ.Update(K, (w, e); EDB): The client receives as input the secret key K, and a pair (w, e) of keyword w and document identifier e. The server receives as input the encrypted database EDB. Outputs updated encrypted database EDB ′ for the server, where the list of documents identifiers associeted with w has e appended to it.

The security model expresses that the view of the server can be simulated by an efficient simulator, receiving as input only the output of the leakage function. In more detail, we define two games, SSEReal and SSEIdeal. First, the adversary chooses a database DB. In SSEReal, the encrypted database EDB is generated by Setup(K, N, DB), whereas in SSEIdeal, the encrypted database is simulated by a (stateful) simulator S on input 4.6. SEARCHABLE ENCRYPTION FROM WEIGHTED ORAM L Setup (DB, N ). After receiving EDB, the adversary can issue search and update queries. In SSEReal, queries are answered using the real-world protocol. In SSEIdeal, the Search queries (resp. Update, Setup) on input x are simulated by S on input L Search (x) (resp. L Update (x), L Setup (x)). Finally, the adversary outputs a bit b.

The scheme is said to be L-secure (i.e. secure with respect to the leakage function L) if for all PPT adversaries, there exists a PPT simulator such that the transcripts in the real and ideal world are computationally indistinguishable.

ZeroSSE

A line of recent works has aimed to hide volume leakage: that is, to hide the number of identifiers matching a given query [START_REF] Kamara | Computationally volume-hiding structured encryption[END_REF][START_REF] Patel | Mitigating leakage in secure cloud-hosted data structures: Volume-hiding for multimaps via hashing[END_REF]. Hiding volume leakage seems sensible when using ORAM techniques to hide the query pattern, since volume leakage reveals information about the repetition of queries. This leads to the question of building an ORAM that also hides volume. For that purpose, an upper bound U is assumed on the volume of the longest list (that is, the longest query answer). As discussed in [START_REF] Garg | TWORAM: Efficient oblivious RAM in two rounds with applications to searchable encryption[END_REF], the first approach one may think of is to use an ORAM with block size U ; however, this would require padding all lists to U , which would be prohibitive in many use cases, since the longest list may be several orders of magnitude larger than the average list size. In the worst case, the blowup in storage is Ω(U ), even before considering ORAM overheads. Another approach would be to use a smaller block size, at the cost of a larger ORAM overhead.

The idea of ZeroSSE is simply to use the weighted variant of Path-ORAM, Weighted(PathOram) with B = U as the block size upper bound. Relative to the previous two approaches, this minimizes both the overhead due to padding, which is nonexistent since no padding is necessary, and the overhead due to ORAM, since we use the largest block size possible. In fact, since our main result is that Path ORAM can handle items of variable size at essentially no overhead, we contend that this is both the most natural and most efficient solution to building SSE with minimum leakage.

We define ZeroSSE in more details as follows. We note that Setup takes as input additional parameters U , which is an upper bound on the longest list size, and W , an upper bound on the number of keywords.

• ZeroSSE.Setup(K, N, DB, U ): Initializes Weighted(PathOram) with block size U and number of leaves ⌈N/U ⌉, containing as (variable-size) blocks DB(w) for each keyword w. The position map, of size O(W ) memory words, is stored on the client side.

• ZeroSSE.Search(K, w; EDB): The client queries the ORAM for keyword w to retrieve DB(w).

• ZeroSSE.Update(K, (w, e); EDB): The client queries the ORAM for keyword w to retrieve DB(w), and simply writes back DB(w) ∪ {e}. (Recall that our weighted construction allows modifying the size of blocks on the fly.)

ZeroSSE uses the non-iterative variant of Path-ORAM. This is because a client storage of O(W ), while undesirable in general, is often accepted in forward-secure SSE [START_REF] Bost | Security-efficiency tradeoffs in searchable encryption[END_REF]. Alternatively, we define ZeroSSE ′ to use the fully iterative version of Path-ORAM, which reduces the client storage to O(1) memory words, at the cost of additional roundtrips, and an additional O(log 2 W ) bandwidth overhead. (In theory, this could be reduced to O(log W ) using an optimal ORAM for the position map, but current constructions of optimal ORAM are not practical.) Theorem 4.6.1 (Security of ZeroSSE). Assuming Path-ORAM is a correct and secure ORAM scheme, ZeroSSE is L-secure with respect to the leakage function

L = {L Setup , L Search , L Update }, with L Setup = {N, U } and L Search = L Update = ∅.
A proof of Theorem 4.6.1 is given in Appendix B.1.

BlockSSE

An interesting peroperty of ZeroSSE is that updates are indistinguishable from searches. In fact, addition and deletion of an arbitrary number of documents in a list can be performed in a single interaction at no additional cost. However, this also means that adding a single document to a keyword incurs an O(U log 2 U ) bandwidth cost. If cheaper updates for single documents are desirable, an alternative solution is to use a smaller block size. A smaller block size (linearly) reduces the cost of updates, while (logarithmically) increasing the cost of searches.

BlockSSE offers that trade-off, by storing the reverse index in a wORAM with parametrizable maximum block size B. An interesting feature of BlockSSE is that we can choose the block size B such that the size of a Path-ORAM tree node ZB is one memory page (or an integral number of memory pages). This optimizes the IO-efficiency of the resulting SSE, as discussed e.g. in [BBF + 21]. This results in the first SSE with both high memory efficiency and no access pattern leakage.

While BlockSSE may perform significantly better than ZeroSSE in update-heavy workloads, the fact that searches and updates are indistinguishable, regardless of the number of documents added or deleted during an update, is lost. BlockSSE also does not support deletions by default, although they can be added generically at some additional cost, as in [Bos16].

To reduce the size of the position map, we borrow the pointer idea introduced in [WNL + 14]. Namely, each block belonging to the same list DB(w) contains the position of the previous block. This allows the position map, stored on the client, to only store the position of the last block, resulting in O(W ) storage.

We define BlockSSE in more details as follows. Note that Setup takes as input additional parameters B, which is the desired block size, and W , and upper bound on the number of keywords. Update takes as additional parameter U , which is an upper bound on the longest list size.

• BlockSSE.Setup(K, N, DB, U ): Initializes Weighted(PathOram) with block size B and number of leaves n = ⌈N/B⌉. For each keyword w, the list DB(w) is split into ⌈DB(w)/B⌉ chunks of size at most B -⌈log n⌉, with no padding. The i-th chunk for keyword w is inserted into the ORAM at a random position, together with the position of the (i -1)-th chunk. The position l w of the last chunk is stored on the client side.

• BlockSSE.Search(K, w, U ; EDB): The client queries the ORAM at position l w , retrieves the last chunk DB(w), together with the position of the penultimate chunk. The client iteratively retrieves the position of each previous chunk in the same manner. Each chunk i is assigned a new position uniformly at random, updating the position stored within the next chunk accordingly.

Introduction

The promise of white-box cryptography is to hide key material from an adversary who has full access to the implementation of a cipher. Using the implementation, the adversary can compute the cipher on any given input, she may observe all intermediate variables, and she may even modify them at will to inject faults. Still, the implementation should be obfuscated in such a way that the adversary cannot infer the encryption key. In this manner, a white-box implementation of a cipher offers a functionality similar to running the encryption algorithm within a trusted enclave in hardware: it allows the user to execute the algorithm, without leaking sensitive key material contained in the code. The difference is that white-box cryptography aims to hide information in software. This goal is quite attractive within industry. Historically, the concept was introduced by Chow et al. in two seminal articles, proposing white-box implementations of AES and DES [START_REF] Chow | White-box cryptography and an AES implementation[END_REF][START_REF] Chow | A white-box DES implementation for DRM applications[END_REF]. Since then, white-box cryptography has been instrumental in Digital Rights Management solutions (e.g. for iTunes, or pay TV services), and payment applications. It also offers an alternative solution for third parties who often cannot access proprietary trusted computing units (e.g. in iOS).

While the demand for secure white-box cryptography is high within industry, all public white-box constructions have so far been proven insecure (see Section 5.1.2). In some cases, short-term security may be enough, as the goal of practical deployments may be to dissuade or slow down attackers, in conjunction with frequent rekeying of sensitive white-box implementations. Nevertheless, a secure white-box implementation of a block cipher would be a major breakthrough.

Towards that end, an innovative approach was proposed at Crypto 2022 by Ranea, Vandersmissen, and Preneel [START_REF] Ranea | Implicit whitebox implementations: White-boxing ARX ciphers[END_REF]. The authors of [START_REF] Ranea | Implicit whitebox implementations: White-boxing ARX ciphers[END_REF] show that by using socalled implicit representations of round functions, it is possible to realize white-box implementations of SPN and ARX ciphers with rich non-linear encodings. The use of nonlinear encodings in white-box cryptography is not new, but previous uses of non-linear encodings were very restricted, while the approach of Ranea et al. allows for a much wider range of encodings. As an illustration of that point, Ranea et al. introduce the first white-box implementation technique suitable for ARX ciphers. To our knowledge, no prior technique applied to that setting.

To understand why non-linear encodings matter, it is helpful to look back to existing attacks on white-box cryptography. Roughly, published attacks fit into three families: 5.1. INTRODUCTION ad-hoc attacks, structural attacks, and gray-box attacks.

Ad-hoc attacks. Ad-hoc attacks target a specific white-box construction. The earliest attacks on white-box cryptography were of that type [BGE04, GMQ07, WMGP07]. While they show that the targeted design is insecure, they are restricted to that design.

Structural attacks.

Structural cryptanalysis was introduced by Biryukov and Shamir, before the invention of white-box cryptography [START_REF] Biryukov | Structural cryptanalysis of SASAS[END_REF]. In brief, given black-box access to a function with some hidden structure, the goal of structural cryptanalysis is to recover that structure. In their original work, Biryukov and Shamir consider the so-called SASAS structure, where the function of composed of three S-box layers, interleaved with affine layers A. Because existing white-box approaches for white-box cryptography rely on hiding intermediate components of a block ciphers (typically, its round functions) behind low-degree (typically affine) encodings, it is naturally amenable to structural cryptanalysis. Indeed, structural attacks allow the attacker to peel off the encodings, and recover the original round function.

Structural cryptanalysis provides considerable insight: for instance the structural cryptanalysis of ASA contained in [START_REF] Biryukov | Structural cryptanalysis of SASAS[END_REF] implies that it is essentially impossible to hide the round function of an SPN cipher behind affine encodings. In fact, the authors of [START_REF] Derbez | On recovering affine encodings in white-box implementations[END_REF] argue that many ad-hoc attacks on white-box constructions can be recast as special cases of the structural attack on ASA. It is worth noting that structural attacks are also interesting outside of white-box cryptography-the notion even predates white-box cryptography. The work of [START_REF] Biryukov | Structural cryptanalysis of SASAS[END_REF] was meant to provide insight on SPN ciphers, and the structural attack of [START_REF] Minaud | Key-recovery attacks on ASASA[END_REF] applies to a multivariate public-key encryption scheme. (Some other attacks on multivariate cryptography are also naturally viewed as structural attacks, even if they do not use the terminology, such as [START_REF] Ding-Feng | Cryptanalysis of "2R" schemes[END_REF].) Gray-box attacks. Gray-box attacks use techniques inspired by side-channel cryptanalysis to break the security of white-box encryption [START_REF] Sasdrich | White-box cryptography in the gray box[END_REF][START_REF] Goubin | Defeating stateof-the-art white-box countermeasures with advanced gray-box attacks[END_REF]. After all, whitebox security is intended to be a stronger requirement than resisting side channels: the attacker has full access to the implementation. This approach has been quite effective in automatically breaking constructions such as in the WhiBox challenge [BDG + 22, BBD + 22]. Nevertheless, it does not suffice to break the most secure variants, and is experimental in nature. Compared to structural attacks, it has the advantage of being more easily automatable for real-world deployment, but it does not provide the same kind of insight as structural attacks, which can be understood as general impossibility results.

Our Contributions

At Crypto 2022, Ranea, Vandersmissen, and Preneel have proposed a new technique for white-box cryptography: implicit encodings [START_REF] Ranea | Implicit whitebox implementations: White-boxing ARX ciphers[END_REF]. A compelling aspect of their proposal is that it enables rich non-linear input encodings. This circumvents the structural cryptanalysis results of [START_REF] Biryukov | Structural cryptanalysis of SASAS[END_REF][START_REF] Derbez | On recovering affine encodings in white-box implementations[END_REF], which show that it is generically impossible to hide the round function of an SPN cipher behind affine or linear encodings. A limitation of [START_REF] Ranea | Implicit whitebox implementations: White-boxing ARX ciphers[END_REF] is that output encodings must still be affine, and input encodings must be of low degree. This raises the question of a structural cryptanalysis of the ISA structure, where a layer of S-boxes is composed with a low-degree layer I at its input, and an affine CHAPTER 5. STRUCTURAL CRYPTANALYSIS OF IMPLICIT WHITE-BOX IMPLEMENTATIONS layer A at its output. That is, given black-box access to a function F of the form ISA, is it generically possible to recover the three inner layers I, S, A, such that F = A • S • I? Since the work of [RVP22] also applies to ARX ciphers, the same question applies to the IMA structure, where the S-box layer S is replaced with modular addition.

As our main result, we give a structural cryptanalysis of both ISA and IMA. In particular, this breaks the white-box proposal of [START_REF] Ranea | Implicit whitebox implementations: White-boxing ARX ciphers[END_REF]. Beyond that, it shows that it is generically impossible to hide an S-box layer (or modular addition) behind encodings, if only the input encoding is non-linear. Because the implicit function technique of [START_REF] Ranea | Implicit whitebox implementations: White-boxing ARX ciphers[END_REF] inherently requires affine output encodings, our work implies that it does not suffice to build secure white-box cryptography.

In terms of techniques, our structural cryptanalysis of ISA is similar in essence to the structural cryptanalysis of ASASA in [START_REF] Minaud | Key-recovery attacks on ASASA[END_REF]. Our structural cryptanalysis of IMA introduces interesting new techniques, which can be viewed as a generalization of linearization attacks. A practical validation of the attack is presented in Section 5.6.

Related Work

In 2002, Chow, Eisen, Johnson and van Oorschot introduced a white-box implementation of the Advanced Encryption Standard (AES) [START_REF] Chow | White-box cryptography and an AES implementation[END_REF], and the Data Encryption Standard (DES) [START_REF] Chow | A white-box DES implementation for DRM applications[END_REF]. Those seminal contributions introduced the idea of white-box cryptography, but quickly proved insecure. In 2004, Billet et al. [START_REF] Billet | Cryptanalysis of a white box AES implementation[END_REF] proposed an algebraic attack against the AES white-box implementation of [START_REF] Chow | White-box cryptography and an AES implementation[END_REF]. Further attacks were proposed in [MGH09, LRdM + 13]. Using differential cryptanalysis, [START_REF] Wyseur | Cryptanalysis of white-box des implementations with arbitrary external encodings[END_REF] and [START_REF] Goubin | Cryptanalysis of white box DES implementations[END_REF] broke the DES S-box of the white-box implementation from [START_REF] Chow | A white-box DES implementation for DRM applications[END_REF] and [START_REF] Link | Clarifying obfuscation: Improving the security of white-box encoding[END_REF]. These attacks led to a new proposal of white-box design in [START_REF] Xiao | A secure implementation of white-box aes[END_REF], but their attempt was thwarted by the attack from [MRP12]. In 2014, [START_REF] Biryukov | Cryptographic schemes based on the ASASA structure: Black-box, white-box, and public-key[END_REF] presented a new AES white-box implementation based on an Affine -S-box -Affine (ASASA) structure, which was broken by [START_REF] Minaud | Key-recovery attacks on ASASA[END_REF], using structural cryptanalysis. In [START_REF] Vandersmissen | A white-box Speck implementation using self-equivalence encodings[END_REF], the authors break a white-box implementation of the cipher Speck based on self-equivalence encodings, using a Gröbner basis approach. So-called gray-box attacks have also been proposed, including Differential Fault Analysis (DFA), and Differential Computer Analysis (DCA). These attacks offered new ways of attacking white-boxes, especially suited for automatic tools. Those techniques were repurposed from Side-Channel Attacks [START_REF] Joppe W Bos | Differential computation analysis: Hiding your white-box designs is not enough[END_REF]. Enhancements of the DCA attacks were proposed in [START_REF] Bogdanov | Higher-order DCA against standard side-channel countermeasures[END_REF].

Beyond symmetric cryptography, the ability to hide a secret symmetric key from the users of a program is related to general obfuscation [DLPR13]. The most demanding form of program obfuscation, called virtual black-box obfuscation, has been proven to be impossible in [BGI + 01]. This does not preclude the possibility that secure white-box cryptography may be possible, because white-box cryptography attemps to obfuscate a specific class of functions, namely symmetric ciphers. The diagonalization argument from [BGI + 01] does not apply to that class of function. Nevertheless, obfuscating specific programs remains a hard task: all publicly available white-box schemes have been broken so far.

In a work published in TCHES 2023, Biryukov, Lambin and Udovenko present a cryptanalysis of the same white-box system we are studying in this chapter [START_REF] Biryukov | Cryptanalysis of arx-based white-box implementations[END_REF]. Their attack is of a more practical nature than ours: their paper targets key recovery on the specific white-box construction of Ranea et al., only in the case of ARX ciphers. To our understanding, it does not contain a general structural cryptanalysis of ISA or IMA 5.2. TECHNICAL OVERVIEW (Section 5 of their work comes the closest, but it leaves many details to later sections, and those later sections use specificities of the construction of Ranea et al.). By contrast, our work is a general structural cryptanalysis of ISA and IMA. It applies to the framework of Ranea et al., by showing that the non-linear input encodings are not enough for security. It is not limited to their specific construction.

Technical Overview

At a high level, structural attacks in the literature follow the same general steps (including those in [START_REF] Biryukov | Structural cryptanalysis of SASAS[END_REF][START_REF] Biryukov | Cryptographic schemes based on the ASASA structure: Black-box, white-box, and public-key[END_REF][START_REF] Derbez | On recovering affine encodings in white-box implementations[END_REF]). We begin by outlining those steps. Then we will explain how our own technique proceeds. For now, we purposefully remain at a high level of abstraction.

Recall that the attacker has black-box access to a function with a known structure (such as ASA or SASAS). The goal is to recover the inner components.

Step 1: Model some part of the target structure as polynomial unknowns in a judicious manner. Then find a way to use the black-box oracle to derive low-degree equations over those unknowns. This is typically the "clever" part of the attack. The cryptanalyst needs to find a way to exploit the properties of the target structure to derive equations.

Examples: In the first stage of the SASAS attack [START_REF] Biryukov | Structural cryptanalysis of SASAS[END_REF], unknowns are entries in the table of the inverse S-box (from the last S-box layer). Equations are derived using ideas from integral cryptanalysis. In the first stage of the ASASA attack [START_REF] Derbez | On recovering affine encodings in white-box implementations[END_REF], unknowns are entries in the matrix representing the last linear layer. Equations are derived via a modified cube attack.

Step 2: Solve the equation system by linearization.

In general, the equations from Step 1 may not be linear. On the other hand, in existing attacks, it is easy to derive new equations by repeating Step 1 as needed. The point is that, while solving even quadratic systems is NP-hard when the number of equations is limited, the problem becomes easy if the attacker has access to as many (random enough) equations as they want. Indeed, in that case, the linearization technique can be applied [START_REF] Biryukov | Structural cryptanalysis of SASAS[END_REF][START_REF] Arora | New algorithms for learning in presence of errors[END_REF]. We refer the reader to Section 5.3.5 for more information on linearization, and do not discuss it here to continue focusing on the overall structure of the attack.

Step 3: Repeat the same general process to recover each one of the other components of the target structure. (Each time a component is recovered, the process of recovering the other components typically becomes easier, as the attacker has access to more and more information.)

In a typical attack, Step 1 and 2 recover the first or last layer of the structure. For example, Step 1 and 2 of the ASASA attack in [START_REF] Derbez | On recovering affine encodings in white-box implementations[END_REF] recover the last A layer. By composing the inverse of that layer with the black-box oracle, the attacker now has oracle access to an ASAS structure. Since it is a "simpler" structure, recovering the next layer is expected to be easier. (This is indeed the case in all structural attacks to our knowledge: peeling layers becomes progressively easier.) CHAPTER 5. STRUCTURAL CRYPTANALYSIS OF IMPLICIT WHITE-BOX IMPLEMENTATIONS This chapter contains two structural attacks: one on each of the new structures proposed for white-box protection in [START_REF] Ranea | Implicit whitebox implementations: White-boxing ARX ciphers[END_REF]. Namely, the ISA structure ("low degree-S box-affine"), and the IMA structure ("low degree-modular addition-affine").

ISA attack.

For the ISA structure (unlike the IMA structure later on), our attack follows the blueprint presented earlier. In fact, our ISA attack is a direct generalization of the structural cryptanalysis of ASASA in [START_REF] Minaud | Key-recovery attacks on ASASA[END_REF], and shares much of the same main ideas. For that reason, we only sketch it here, and refer to the full description in Section 5.4 for more information.

In an IS structure, where the first layer has degree d, and the S-box is over s bits, a bit of the output has degree (at most) d(s -1) over the input variables (see [START_REF] Minaud | Key-recovery attacks on ASASA[END_REF] Lemma 2]). A key observation is that the product of two output bits arising from the same S-box still has degree d(s -1), whereas if the two bits arise from distinct S-boxes, the degree rises to 2d(s -1). The other key observation is that such a disparity in the behavior of the degree can be exploited by a cube attack. In more details, notice that in the ISA structure, the value of one bit at the output of the first two IS layers is a linear combination of output bits of the ISA function. Defining the coefficients of that linear combination as unknowns, it is possible to obtain (via a cube attack) a quadratic equation over those unknowns. From there, the general strategy outlined at the start of the section can be implemented.

IMA attack.

In prior work that followed the general steps outlined at the start of the section [BS01, BBK14, DFLM18], as well as in our own ISA attack, a crucial fact the attacks implicitly rely on is that the overall function has low algebraic degree1 . Indeed, they rely on the key lemma of cube attacks, namely that the sum of a Boolean function of algebraic degree d over an affine space of dimension d + 1 is zero (cf. Lemma 5.3.1)2 . The number of summands is exponential in the degree d of the function, so this approach is only viable for low-degree functions.

An immediate problem when tackling the IMA structure is that modular addition over n bits has algebraic degree n. In particular, the IMA structure does not have low algebraic degree. For that reason, we do not directly use the cube attack approach of previous work. Instead, we rely on the iterative structure of modular addition: if modular addition is computed in the "elementary school" way by using carries, each output of the addition can be expressed as a quadratic polynomial in the input and in the value of the carry. That is, if we compute the modular addition z = x ⊞ y in Z 2 n , then denoting by z i the i-th bit of z (likewise for x and y), we have:

z i = x i + y i + c i ,
where c i denotes the carry coming from the addition of the first i -1 bits, and "+" is addition in Z 2 . From there, a straightforward computation yields:

z i = x i + y i + x i-1 y i-1 + c i-1 (x i-1 + y i-1 ).

PRELIMINARIES

What is interesting about this equation is that if the attacker has recovered the expression of the first i -1 bits of x, y, then the attacker can compute c i-1 . The attacker can then look for a linear relation between z i (linear combination of output bits of the black-box function with unknown coefficients), c i-1 (x i-1 + y i-1 ) (a known quantity times a linear combination of input bits with unknown coefficients), and the vector of pairwise products of the bits of x i-1 and y i-1 (again with unknown coefficients). To do so, the attacker creates a matrix whose rows are the concatenation of : input bits, input bits times c i-1 , output bits, and finally pairwise products of input bits-for random input bits. Because the previous relation, the kernel of the matrix must be non-trivial, and essentially reveals the unknown coefficients of x i-1 and y i-1 (we refer to Section 5.5 for more details).

To sum up, the attacker finds the coefficients of x i-1 and y i-1 iteratively, by using the recursive structure of modular addition. At each step, we note that there exist several possible solutions, forcing the attacker to guess. However, our experiments show that when the attacker makes a wrong guess, the very next step of the iteration always fails, meaning that wrong guesses are corrected immediately. We have validated the attack with a full implementation in the Sage programming language, discussed in Section 5.6. The implementation is available as supplementary material.

Structure of the chapter

We present our notation, the white-box framework, and structural cryptanalysis in Section 5.3. In Section 5.4, we show an attack on protocols white-boxing ciphers based on Sboxes using implicit implementations. Our main result is in Section 5.5, where we show an attack on implicit white-box implementations of ciphers based on modular additions. The techniques of polynomial factorization used as a subroutine of our attacks are detailed in Section 5.7.

Preliminaries

Notation

Boolean vectors. F 2 denotes the field with two elements. Given a vector v ∈ F n 2 , its i-th coordinate is denoted by v

[i], for 1 ≤ i ≤ n. We may write v = (v[1], . . . , v[n]). The dot product between two vectors v, w ∈ F n 2 is denoted by ⟨v|w⟩ = n i=1 v[i]w[i]. The concatentation of two vectors x, y ∈ F n 2 is written x ∥ y ∈ F 2n 2 .
Let e 1 , . . . , e n denote the canonical basis of F n 2 ; that is, e i [i] = 1 and e i [j] = 0 for j ̸ = i. The vector space spanned by a set of vectors v 1 , . . . , v k ∈ F n 2 is called the span of those vectors, written span(v 1 , . . . , v k ). Addition over F n 2 will simply denoted by +. Modular addition over Z/kZ will be written as ⊞.

Affine subspaces. An affine subspace of F n

2 is a subset of F n 2 of the form v +S = {v +s : s ∈ S}, where v ∈ F n 2 is an arbitrary vector, and S ⊆ F n 2 is a linear subspace. An affine map F m → F n is a map of the form x → f (x) + v, where v ∈ F n 2 is an arbitrary vector, and f : F m → F n is linear. We will sometimes say that certain objects are affine: for example, affine layers, affine encodings. This means that the relevant object is an affine map. WHITE-BOX IMPLEMENTATIONS Boolean functions. A Boolean function is a map F : F n 2 → F 2 . Recall that any Boolean function is functionally equivalent to a polynomial P in F 2 [X 1 , . . . , X n ]. That is, for all x ∈ F n 2 , F (x) is equal to the evaluation of P where X i is substituted with x[i]. The polynomial P can be chosen to be square-free: that is, it is a linear combination of monomials of the form

X ε 1 1 • • • • • X εn n with ε i ∈ {0, 1}.
In the remainder, in accordance with the literature on algebraic attacks, we only consider square-free polynomials, which are identified with their class in F 2 [X 1 , . . . , X n ]/⟨X 2 i -X i ⟩. Note that the square-free polynomial associated with F is unique, i.e. the space of Boolean functions F n 2 → F 2 is isomorphic to the space of square-free polynomials F 2 [X 1 , . . . , X n ]/⟨X 2 i -X i ⟩.

Algebraic degree. The algebraic degree of a function F is the degree of the associated (square-free) polynomial. For a k-bit function F : F n 2 → F k 2 , the algebraic degree of F is by convention the maximum of the algebraic degrees of the bit functions

F [i] : F n 2 → F 2 , 1 ≤ i ≤ k.
Throughout this chapter, the term degree exclusively refers to the algebraic degree. The degree of F will be denoted by deg(F ).

Round encodings

Consider a block cipher E composed of r rounds:

E = E r • • • • • E 1 .
In most block ciphers, the round key is added to the inner state. In that case, given black-box access to a round function E i , it is trivial to recover the round key. Indeed, all round operations are public and invertible, save for key addition. For that reason, white-box compilers typically attempt to obfuscate each round function by composing E i with a so-called input encoding I i , and output encoding O i . The encoded round function can be expressed as:

E i = O i • E i • I i .
In a typical white-box scheme, consecutive encodings cancel out, that is:

I i+1 • O i = Id.
The white-box implementation of the block cipher E only gives access to the encoded round functions E 1 , . . . , E r . Taking advantage of the cancellation property I i+1 • O i = Id, a honest user can compute:

E r • • • • • E 1 (x) = O r • E r • E r-1 • • • • • E 1 • I 1 (x) = O r • E • I 1 (x).
If O r and I r are not the identity, the previous computation is not equivalent to an encryption of x. In most white-box schemes, it is accepted that the input x is encoded as

x = I -1 1 (p)
, where p is the plaintext the user wishes to encrypt. Likewise, the output of the encryption is encoded with O r . Non-trivial I 1 and O r are called external encodings.

Implicit representations.

In the actual implementation of the white-box block cipher, the round function may be represented in various ways. In the original CEJO framework, the white-box implementation of E i consists of a series of lookup tables. Given an input x to the encoded round function, the user can compute its output E i (x) directly using those tables (combining them in a predefined way). The recent work of Ranea et al. introduces a different representation of the round function, which they call implicit representations.

PRELIMINARIES

Implicit representations of the round function provide a series of equations that the user can solve to compute the round function in the forward direction. That is, given an input x, the user computes its output y = E i (x) by solving an equation system f (x, y) in y. The description of the round function consists of a description of the equation system f . The point of implicit representations is that it allows Ranea et al. to build, for the first time: (1) white-box implementations with complex non-linear input encodings; and (2) white-box implementations of ARX ciphers.

Nevertheless, all attacks in this chapter are oblivious to how the encoded round function is represented-whether it is an implicit representation or otherwise. This is because our attacks will only require black-box access to the encoded round function. That is, given x and some arbitrary representation of E i , the only thing we need is that it is possible to efficiently compute E i (x). Note that it is necessary for the honest user to be able to perform those computations, so this requirement is essentially free. All white-box implementations that we know of satisfy it. To stress this point once more: attacks in this chapter do not depend on the type of representation. For that reason, we omit a full description of implicit representations, and refer the curious reader to [START_REF] Ranea | Implicit whitebox implementations: White-boxing ARX ciphers[END_REF].

Structural Cryptanalysis

Structural cryptanalysis was introduced by Biryukov and Shamir [START_REF] Biryukov | Structural cryptanalysis of SASAS[END_REF]. In the setting of structural cryptanalysis, an attacker is given oracle access to a function F . The attacker is able to query the oracle on input x, and gets as output F (x).

Assume the function F has some known structure, but the components of that structure are unknown. For example, F : F n 2 → F n 2 is known to be composed of an n-bit affine layer A 1 , followed by a layer S of k parallel s-bit S-boxes with n = ks, followed again by an n-bit affine layer A 2 . We can write F = A 2 •S •A 1 : this is the so-called ASA structure.

Given only black-box access to F (x) via the oracle, the goal of the attacker is to find the hidden components A 1 , S, A 2 . More precisely, since F may not uniquely define A 1 , S, A 2 , the goal of the attacker is to find k s-bit S-boxes forming a layer S ′ , and two affine layers

A ′ 1 , A ′ 2 , such that F = A ′ 2 • S ′ • A ′ 1 .
The previous example corresponds to the ASA structure, which stands for "Affine → S-box layer → Affine". The original article by Biryukov and Shamir presents the structural cryptanalysis of the SASAS structure, including as a sub-component, the structural cryptanalysis of SAS [START_REF] Biryukov | Structural cryptanalysis of SASAS[END_REF]. Later on, the ASASA structure was introduced in [BBK14], and a structural cryptanalysis of ASASA was given in [START_REF] Minaud | Key-recovery attacks on ASASA[END_REF]. Intuitively, the structural cryptanalysis of SAS, SASAS and ASASA show that it is exceedingly difficult to "hide" a layer of S-boxes using linear or affine encodings. In fact, even though many of the earlier attempts to build white-box schemes were originally broken in an ad-hoc fashion, it was noted in [START_REF] Derbez | On recovering affine encodings in white-box implementations[END_REF] that they can be broken generically via the structural cryptanalysis of ASA.

In this work, we extend structural cryptanalysis to non-linear encodings. Non-linear encodings will be represented by the letter I, for higher-order layer. (We have favored a vowel, for ease of pronunciation.) If arbitrary non-linear encodings are allowed, structural cryptanalysis becomes vacuous. To illustrate that point, consider any specific structure Σ followed by an arbitrary non-linear encoding I. Then the mapping F = I • Σ contains no information about Σ. Indeed, I can be equal to F ′ • Σ -1 for any arbitrary F ′ . In practice, existing white-box proposals only use low-degree non-linear encodings. Accordingly, in this work, the letter I should be understood as standing for a low-degree nonlinear layer. WHITE-BOX IMPLEMENTATIONS In practice, we will often assume that any non-linear layer I is of lower degree than its surrounding layers.

Another subtlety worth noting is that we only assume that I is low-degree in the forward direction. That is, x → I(x) is of low algebraic degree. The inverse x → I -1 (x) may be of high degree.

Since our attacks also target ARX ciphers, we introduce the letter M to stand for modular addition. The map M : (F 2 n ) 2 → (F 2 n ) 2 is defined by M : (x, y) → (x, x ⊞ y), where ⊞ denotes modular addition. Since surrounding layers are defined over F 2n 2 , a standard little-endian conversion between F 2 n and F n 2 will implicitly be assumed throughout this work: we will treat quantities in F 2 n and F n 2 as if they belong to the same space. The authors of [RVP22] use the "permuted addition" mapping M ′ : (x, y) → (x ⊞ y, y) instead of M . This makes no difference, because the two mappings M and M ′ are equivalent up to permutations of their inputs and outputs, and permutations are linear maps: the structural cryptanalysis of IMA is equivalent to that of IM ′ A.

Remark. In this work, all mappings within a structure are implicitly assumed to be invertible. This is because we target block ciphers, which are invertible by definition. Nevertheless, the invertibility assumption is mainly for convenience: most attacks can be adapted to dispense with it.

Cube attacks

Cube attacks were introduced by Dinur and Shamir [DS09]. We briefly recall the key lemma behind cube attacks, which will be useful in this work.

A starting observation is that for any non-zero F :

F n 2 → F 2 and any non-zero constant δ ∈ F n 2 : deg(x → F (x) + F (x + δ)) = deg(F ) -1,
with the convention deg(0) = -1. Intuitively, the operation x → F (x) + F (x + δ) may be thought of as a differential of F along δ, and affects the degree similarly. Differentiating F along multiple linearly independent vectors δ 1 , . . . , δ k amounts to summing F over the space spanned by the δ i 's. Since differentiating along each new δ i decreases the degree by one, we obtain the key lemma of cube attacks (see [DS09] for a more detailed proof). In line with the literature on cube attacks, an affine subspace of F n 2 will sometimes be called a cube. Lemma 5.3.1 states that any function of degree d sums to zero over a cube of dimension d + 1.

Linearization

In the course of this chapter, we will be repeatedly confronted with the problem of solving non-linear equation systems over F 2 . This is an NP-complete problem even for quadratic systems, and average-case instances are believed to be intractable. Generic algorithms 5.4. STRUCTURAL CRYPTANALYSIS OF ISA (such as Gröbner bases [START_REF] Faugère | Polynomial equivalence problems: Algorithmic and theoretical aspects[END_REF], or approaches based on the polynomial method [START_REF] Dinur | Improved algorithms for solving polynomial systems over GF(2) by multiple parity-counting[END_REF]) yield exponential-time algorithms for the average case.

Nevertheless, when the equations are of degree bounded by d over n unknowns, and the number of available equations is Ω(n d ), the system can be solved in polynomial time O(n 3d ) using the linearization technique. In effect, solving non-linear systems is only difficult when the number of available equations is limited. Throughout this work, we will use the strategy of reducing algorithmic problems to solving non-linear systems, but always in settings where we can freely sample a number of equations exponential in n; in particular, linearization will be applicable.

For the sake of completeness, we briefly sketch the linearization process. A more detailed treatment may be found in [START_REF] Arora | New algorithms for learning in presence of errors[END_REF][START_REF] Minaud | Key-recovery attacks on ASASA[END_REF]. Assume we have a system of m independent equations of degree (at most) d over n unknowns x 1 , . . . , x n . As discussed in Section 5.3.1, without loss of generality, we can restrict our attention to equations with square-free monomials, i.e. all monomials are of the form

x ε 1 1 • • • • • x εn n with ε ∈ F n 2 .
The fact that the monomials are of degree at most d translates to the fact that at most d of the ε i 's are non-zero. Hence, the number of possible monomials is bounded by:

d i=0 n i ≤ ne d d = O(n d ).
For each ε, replace all occurrences of the monomial x ε 1 1 • • • • • x εn n in the equation system by a new unknown t ε . There are O(n d ) such unknowns t ε , and the equation system is now linear in the t ε 's. Hence, we can solve the system using any linear system solving algorithm. If we use Gaussian elimination, the time complexity of this step is O(n 3d ). We obtain the values of all t ε 's.

It remains to deduce the values of the original variables x i 's from the t ε 's. Recall that e i ∈ F n 2 is defined by e i [i] = 1 and e i [j] = 0 for j ̸ = i. If all t e i appear in the equation system, recovering the x i 's is trivial, because x i = t e i . If the equation system has specific properties such that the t e i 's do not appear in the equations (for example, if the equations are homogeneous of degree d), some extra work is needed. Nonetheless, in practice, this step incurs a negligible cost in time complexity compared to linear system solving in the previous step. The reader is referred to [AG11, MDFK18] for detailed algorithms.

Structural cryptanalysis of ISA

In [START_REF] Ranea | Implicit whitebox implementations: White-boxing ARX ciphers[END_REF], the authors introduce implicit representations of encoded round functions. This allows the authors the freedom to use non-linear input encodings, but for technical reasons, output encodings must be affine (see [START_REF] Ranea | Implicit whitebox implementations: White-boxing ARX ciphers[END_REF] for the reasoning). In this section, we show that this approach cannot hide an inner S-box layer. To that end, we give a structural cryptanalysis of the ISA structure.

Problem statement

Let I : F n 2 → F n 2 be a non-linear map of degree d. Let S be a layer of k (not necessarily identical) s-bit S-boxes, with n = ks. For simplicity, S-boxes are assumed to be of maximal degree s -1. (The attack can easily be adapted otherwise, but the cost of the attack grows with s, so s -1 is the worst case.) Let A : F n 2 → F n 2 be an affine mapping. Let F = A • S • I. The goal of the attacker is to find a non-linear layer I ′ , an affine layer A ′ , and a layer S ′ of k parallel s-bit S-boxes such that F = A ′ • S ′ • I ′ . CHAPTER 5. STRUCTURAL CRYPTANALYSIS OF IMPLICIT WHITE-BOX IMPLEMENTATIONS solving a linear system in O(n 2 ) unknowns over F 2 . This costs roughly O(n 6 ) operations (using Gaussian elimination for simplicity; the exponent can be reduced using more advanced matrix inversion algorithms). In practice, note that this quantity counts the number of bit operations, whereas linear algebra over F 2 can naturally take advantage of word-level operations, resulting in a lower complexity. A secondary bottleneck is to collect O(n 2 ) cubes to derive the equations of the previous system. Each cube is of dimension d(s -1), resulting in a total of 2 d(s-1) calls to the encoded round function. Both computation must be performed for each bit. In the end, the total complexity is O(n 7 + n 2 2 d(s-1) ). Observe that for AES parameters and reasonable d (say, d < 5), the first term O(n 7 ) dominates: linear system solving is the bottleneck.

Application to white-box key recovery

The attacks presented in previous sections belong to the family of structural attacks. The output of the attack is an equivalent key, in the sense of structural attacks: that is, for an ISA structure, suitable non-linear layer I ′ , S-box layer S ′ , and affine layer A ′ , such that the function F under attack satisfies F = A ′ • S ′ • I ′ . When applying this technique to attack a white-box encoded round function with the appropriate structure (e.g. ISA), a white-box attacker (as opposed to a structural attacker) would like to go one step further, and recover the encryption key.

That goal is made possible by the fact that the white-box attacker knows more information than the structural attacker. Contrary to the structural attacker, the white-box attacker knows the full description of the round function, including specific descriptions of the S-boxes and linear layer. The only information the white-box attacker does not have are the round encodings, and the round keys. Compared to the structural attacker, the white-box attacker also has a more specific goal, which is to recover the round keys (and from there the overall encryption key).

This section is to bridge the gap between the two models, and show how a key-recovery attack in the white-box model can be deduced from a structural attack.

Reduction to a simple problem

At the outcome of the structural attacks from Section 5.4.4, the attacker has access to the input and output of every S-box, up to affine equivalence. More precisely, for each S-box S appearing in a round function of the underlying block cipher, the attacker can read the input and output of the S-box up to fixed affine encodings (fixed in the sense that they are always the same for a given S-box; they need not be the same between different S-boxes). Note that S-boxes belonging to the same round may also be permuted, in the sense that the structural attack may not present the S-boxes in the same order that they would be presented in a traditional description of the underlying cipher. In addition to reading the input and output of S-boxes up to affine equivalence, the attacker may also choose to modify those values at will, and observe the effect on later encryption rounds.

Thus, building a white-box attacker from a structural attacker can be neatly reduced to a stand-alone problem: given full read and write access to the input and output of every S-box in a particular SPN cipher, up to affine equivalence for each S-box, and up to permutation of the S-boxes in a given round, recover the round keys. (If the key schedule is invertible, recovering the round keys is equivalent to recovering the encryption key.)

STRUCTURAL CRYPTANALYSIS OF IMA

Solving the problem

We now explain how to solve the problem outlined just above. We note that it is not particularly difficult. Intuitively, this is because the "heavy lifting" was done by the structural attack: deducing a white-box key-recovery attack from the structural attack is relatively straightforward.

Let S i be a particular S-box recovered by the structural attack. The white-box attacker knows the actual S-box S orig in the original SPN block cipher (assuming for simplicity that all S-boxes are the same). Hence, S i and S orig are affine-equivalent: there exist affine maps A i , B i such that S i = B i • S orig • A i . Given as input S i and S orig , recovering suitable A i , B i is the so-called affine equivalence problem. Efficient algorithms for typical S-box sizes are given in [START_REF] Biryukov | A toolbox for cryptanalysis: Linear and affine equivalence algorithms[END_REF][START_REF] Dinur | An improved affine equivalence algorithm for random permutations[END_REF].

The affine equivalence problem may have more than one solution: there may exist

(A i , B i ) ̸ = (A ′ i , B ′ i ) such that S i = B i • S orig • A i = B ′ i • S orig • A ′ i .
In that case, we have:

S orig = (B -1 i • B ′ i ) • S orig • (A ′ i • A -1 i ). The pair (B -1 i • B ′ i , A ′ i • A -1 i
) is said to be an affine self-equivalence of S orig . If S orig admits only the trivial self-equivalence (Id, Id), the affine equivalence problem has a single solution. After computing that solution for each S-box using the efficient algorithms from [START_REF] Biryukov | A toolbox for cryptanalysis: Linear and affine equivalence algorithms[END_REF][START_REF] Dinur | An improved affine equivalence algorithm for random permutations[END_REF], the attacker has (read and write) access to the plaintext input and output of every S-box. The only remaining unknown is the permutation of the S-boxes in a given round. At this stage, recovering the round key for any real-world cipher is trivial. 4For an S-box sampled uniformly from permutations on a given number of bits, with high probability, there is no self-equivalence beside the trivial one, and we are done. However, we note that specific ciphers may use S-boxes with special non-random features, whose self-equivalence group may be non-trivial. This is in particular the case of the AES S-box, which is affine-equivalent to modular inversion in F 2 8 , hence has as many self-equivalences as modular inversion. Concretely, the AES S-box has 2040 ≈ 2 11 self-equivalences [START_REF] Biryukov | A toolbox for cryptanalysis: Linear and affine equivalence algorithms[END_REF]. Nevertheless, recovering the encryption key from read-write access to all S-boxes up to self-equivalence is still an easy problem. An algorithm for that purpose is given in [DFLM18, Section 4.2].

Structural cryptanalysis of IMA

As we have seen in the previous section, the introduction of implicit representations of round functions in [START_REF] Ranea | Implicit whitebox implementations: White-boxing ARX ciphers[END_REF] makes it possible to create non-linear input encodings for SPN cipher: the ISA structure. Another benefit of implicit representations, and their most novel application, is that they make it possible to apply white-box techniques to ARX ciphers, which was not possible before. More precisely, the authors show how to hide one layer of modular addition, which is the non-linear building brick of ARX ciphers. (For clarity, "linearity" here should be understood as linearity over F n 2 ; modular addition in Z/kZ is of course Z/kZ-linear.)

CHAPTER 5. STRUCTURAL CRYPTANALYSIS OF IMPLICIT WHITE-BOX IMPLEMENTATIONS

As earlier, the main limitation remains that only input encodings can be non-linear; the techniques of [START_REF] Ranea | Implicit whitebox implementations: White-boxing ARX ciphers[END_REF] do not support non-linear output encodings. The construction of [START_REF] Ranea | Implicit whitebox implementations: White-boxing ARX ciphers[END_REF] thus amount to an IMA structure. In this section, we give a structural cryptanalysis of IMA. The attack we present also applies to AMA. This shows that the use of a low-degree input encoding is not enough to hide an inner modular addition. At the end of the section, we discuss how the structural cryptanalysis result translates to a white-box key-recovery attack on white-box ARX ciphers.

Problem statement

Let I : F n 2 → F n 2 be a non-linear map of degree d. We allow the case d = 1 in the attack, i.e. the attack also applies to affine input layers. Let M : (x, y) → (x, x ⊞ y) be the modular addition addition, as discussed in Section 5.3.3.

Let A : F n 2 → F n 2 be an affine mapping. Let F = A • M • I. The goal of the attacker is to find a non-linear layer I ′ of degree at most d, and an affine layer A ′ , such that

F = A ′ • M • I ′ .

Equivalent keys

Our algorithm for the structural cryptanalysis of IMA will sometimes make guesses. For instance, at the end of Section 5.5.3, the algorithm will identify a few possible candidates for the map I[2n -1]. In those cases, the algorithm will simply guess that one of the candidates is the correct one. The attack continues as if the guess was correct. At some later points in the attack, the algorithm will test that certain vector spaces have the right dimension. If that is not the case, it reveals that one of the previous guesses was wrong. The algorithm then simply backtracks to the latest guess for which not all possibilities have been exhausted, and takes a different guess.

It is important to note that whenever the algorithm reaches a branching point (i.e. a guess), it is often the case that multiple choices will be correct. This is because the solution to the structural analysis problem is not unique: modular addition admits many affine self-equivalences [START_REF] Ranea | Implicit whitebox implementations: White-boxing ARX ciphers[END_REF]. Thus, our algorithm has two types of branching points. Some branching points will arise from the fact that there are multiple solutions: all choice are equally correct, and will not lead to any backtracking. Other branching points will only have one correct choice, and will lead to backtracking if the guess was incorrect. Our experiments show that the same branching point in the algorithm can be of either type, depending on the problem instance and previous choices. This is because equivalent keys for modular addition have a rather complex structure: see [RVP22, Section 5.2]. Interestingly however, our algorithm does not care about the exact structure of equivalent keys, or about which branching point is of which type: it simply makes guesses when necessary, and backtracks when it encounters an inconsistency. In practical experiments, incorrect choices lead to inconsistencies quickly (typically at the next consistency check), so the performance cost of wrong choices is low.

Peeling off the I layer: from IMA to MA

Step 1: recovering affine bits A starting point is that most bits at the output of the modular addition M : (x, y) → (x, x ⊞ y) are affine in the input of M : namely, the bits of x, and the last bit (x ⊞ y)[n] of 5.5. STRUCTURAL CRYPTANALYSIS OF IMA x ⊞ y, which is equal to x[n] + y [n]. (Recall that modular addition is denoted by ⊞, while + denotes addition over F 2 .) The image of the space of affine bits through the outer affine layer A can be detected using the fact that those bits have degree d in F = A • M • I, whereas other bits have higher degree.

To do so, take any cube C of degree d + 1 over the input of F . Suppose λ 0 ∈ F 2n 2 is such that ⟨λ 0 |F ⟩ is equal to a linear combination of affine bits before the last affine layer (formally: ⟨λ 0 |F ⟩ = ⟨µ 0 |M • I⟩ + γ 0 where γ 0 is a constant and µ 0 [i] = 0 for i ∈ [n + 1, . . . , 2n -1]). Then the following equation holds:

c∈C ⟨λ 0 |F (c)⟩ = 0 whenever dim(C) = 2.
(5.2) Equation (5.2) yields a linear constraint on λ 0 , viewed as a vector of binary unknowns λ 0 [1], . . . , λ 0 [2n]. Each choice of C yields an equation. Sampling sufficiently many C's allows us to solve the system and recover λ 0 . More exactly, since λ 0 is not unique, we recover the space S 0 of dimension n + 1 of all λ 0 's that correspond to affine bits of M , in the sense given earlier.

Step 2: recovering

(x ⊞ y)[n -1]
The only bit of degree 2 in M is M [2n-1], i.e. the n-1-th bit of x⊞y. Hence the only bit of degree 2d in

M • I is (M • I)[2n -1]. If λ 1 now denotes the linear mask corresponding to M [2n -1] through the last affine layer A (that is: ⟨λ 1 |F ⟩ = (M • I)[2n -1] + γ 1 where γ 1 is a constant), then λ 1 satisfies the following equation: c∈C ⟨λ 1 |F (c)⟩ = 0 whenever dim(C) = 2d + 1.
(5.3)

As before, each C yields an equation. By sampling sufficiently many C's, we can solve the system. However, the system is not satisfied only by λ 1 : all masks λ 0 recovered in Section 5.5.3 also satisfy it. Solving (5.3) yields a solution space S 1 of dimension n + 2, spanned by S 0 and λ 1 . (This, and other steps of the attacks, has been confirmed experimentally). For now, to recover λ 1 , we simply sample an element of S 1 \S 0 . This can be done by taking the non-zero element of the quotient S 1 /S 0 ∼ F 2 , and lifting it back to S 1 . (Alternatively, because half of the elements of S 1 are in S 0 , sampling a uniformly random element of S 1 , and testing that it does not belong to S 0 , succeeds within two tries in expectation.)

Note that the previous computation does not "truly" recover λ 1 ; rather, it recovers λ ′ 1 = λ 1 + λ 0 for some λ 0 ∈ S 0 . This is good enough for our next computation. We have:

⟨λ ′ 1 |F ⟩ = ⟨λ 1 |F ⟩ + ⟨λ 0 |F ⟩ = (M • I)[2n -1] + ⟨µ 0 |M • I⟩ + γ 1
where ⟨µ 0 |M ⟩ is linear, while M [2n -1] has degree two. On the other hand, observe that:

M (x, y)[2n -1] = (x ⊞ y)[n -1] = x[n]y[n] + x[n -1] + y[n -1]
where the first term is the carry of the modular addition. Reinjecting into the previous computation, we get:

⟨λ ′ 1 |F ⟩ = I[n]I[2n] + I[n -1] + I[2n -1] + ⟨µ 0 |M • I⟩ + γ 1 .
(5.4) CHAPTER 5. STRUCTURAL CRYPTANALYSIS OF IMPLICIT WHITE-BOX IMPLEMENTATIONS 2, even for valid solution, which requires a guess. On the other hand, if the solution space has dimension 0, it reveals that one of our previous guesses was wrong, and we backtrack to a previous guess, as discussed in Section 5.5. Remark. Taking a step back, the use of the inductive definition of modular addition via carries allows the attack to only have to consider equations of degree at most 2d = O(d), as opposed to O(nd) for a naive approach. The technique we use involving the vectors v ≤k can be viewed as a variant of the linearization technique from Section 5.3.5.

In essence, what we show is that if we have equations that are of low degree with respect to some input v, except for some term in the equation (here, c i-1 (v)) that may be of high degree, but whose value can be computed by the attacker, then it is still possible to solve the equation system with a linearization-like approach. Generalizing this idea, while normal linearization techniques allow an attacker to solve a system of low degree, given enough equations, our variant allows to solve a system of equations that are low degree in v and in other quantities f i (v), as long as the f i 's are known-even if the equations may be of arbitrarily high degree when expressed using only v.

Step 4: wrapping up the attack At the outcome of the previous step, we have removed the initial non-linear layer I, and are left with the structural cryptanalysis of MA. Contrary to the case of SA, the cryptanalysis of MA is trivial, since M is a fixed function. To recover A, it suffices to compose the function with M -1 .

Attack complexity

The complexity of the attack is determined by the number of bits n of the cipher's internal state, and the degree d of the input encoding. Similar to Section 5.4.5, the complexity bottleneck comes from solving Equation (5.9). This amounts to solving a linear system in n 2d ≤ n 2d unknowns over F 2 . Using Gaussian elimination for simplicity, this costs O(n 6d ) bit operations. Since this must be repeated for each of the n/2 bits targeted by the attack, the total complexity is O(n 6d+1 ). To provide some perspective, note that simply representing an arbitrary input layer of degree d requires O(n d ) bits. (Implicit representations in [START_REF] Ranea | Implicit whitebox implementations: White-boxing ARX ciphers[END_REF] are also of size O(n d ).)

Application to white-box key recovery

In a white-box key-recovery scenario, two aspects of the attack differ.

First, it is usually the case that the round function of an ARX cipher involves several modular additions. Our technique targets the case of a single modular addition. The Speck cipher contains a single modular addition, and our structural cryptanalysis directly applies. More generally, it is not clear how the implicit encoding technique of [START_REF] Ranea | Implicit whitebox implementations: White-boxing ARX ciphers[END_REF] would perform for more complex round functions. It would likely be implemented 5.6. PRACTICAL VALIDATION separately for each modular addition, which would again enable our attack. Even if it did not, we suspect that very similar techniques would apply. In any case, our structural cryptanalysis problem focuses on the simplest and cleanest case of a single modular addition. This also avoids becoming dependent on a specific round function.

A second point where the structural cryptanalysis approach differs from white-box key-recovery is that, as in Section 5.5.5, a white-box attack aims to recover a secret key, not just equivalent descriptions of inner encryption layers. In the case of modular addition, at the outcome of structural cryptanalysis, we recover an equivalent key. In practice, our attack recover the input and output of the modular addition layer up to self-equivalences of the modular addition. An (affine) self-equivalence of modular addition is a pair of affine layers (A, B) such that M = B • M • A. By executing the cipher on a given input, and using the output of our structurcal cryptanalysis, we can observe the values of bits after the modular addition layer, for every round, up to self-equivalence. If it was not up to self-equivalence, recovering round keys would be trivial, since all operations other than key addition are public and invertible.

Similar to the treatment in Section 5.5.5, applying the structural cryptanalysis result to white-box key recovery comes down to solving the following problem. Assume we have access to the full inner state of the cipher after every modular addition layer, but those inner states may be modified by an affine map arising from a self-equivalence (always the same for a given round). The goal is to recover the encryption key. The problem may appear difficult, because modular addition has many self-equivalences. But in fact, those self-equivalences mainly differ in the values of the first few and last few bits of the modular addition output (x ⊞ y). For the vast majority of bits, namely (x ⊞ y)[i] for 2 < i < n -2, the self-equivalent encodings behave like the identity matrix, up to the addition of a vector confined to a space of dimension 4 (see [RVP22, Section 5.2]). Recall that this information is available at every round. Recovering the secret key from there is not amenable to a general analysis, since it depends on the specific key schedule of a cipher. Nevertheless, we believe that for any concrete block cipher, it is not difficult to recover the round keys given that much leakage.

Practical validation

As noted in Section 5.4.3, our attacks on ISA are similar in spirit to the attack on ASASA in [START_REF] Minaud | Key-recovery attacks on ASASA[END_REF]. On the other hand, the attack on IMA is quite new, and relies on a backtracking mechanism whose practical behavior is not obvious. For that reason, we have decided to fully implement the IMA attack in the case d = 1, aiming especially to observe the behavior of the backtracking process. Our implementation is available in the appendix.

The implementation is in the Sage language (release 9.8), an open-source Python variant suited to formal computation. The implementation can be run simply with the command sage full.sage. It generates a random instance of the problem for n bits, where n can be specified in the full.sage file. We have run the program up to n = 64 bits. The attack always succeeds, and does so on a laptop in 95 minutes on inputs of size n = 64 bits.

Our main observation is that (to our surprise), the attack never needs to backtrack more than one step. To elaborate on that point, recall that the algorithm from Section 5.5 needs to make some choices when recovering each bit of the input layer, due to the fact that if P i,j,k,l,g,h = 1 then 5:

return False 6: return True such that (B j,k,l , C j,k,l ) ̸ = (0, 0) but B x = C x = 0 for all other triples x in {i, j, k, l}. This is analogous to the algorithm "FindGood" in [START_REF] Minaud | Key-recovery attacks on ASASA[END_REF]: if not ZeroOracle(j, k, l) and ZeroOracle(x) for all other triples in {i, j, k, l} then 8: return (j, k, l) With such a triple (j, k, l) for some i ∈ [n], let (µ, λ) = (B j,k,l , C j,k,l ). Then, ∀g, h, we have P i,j,k,l,g,h = λB i,g,h + µC i,g,h . Without loss of generality, we can assume that (µ, λ) = (0, 1), since we are looking for span(B, C).

We gain knowledge of B i,g,h by evaluating P i,j,k,l,g,h , thus for every i ∈ [n], we can recover span(B i, * , * , C i, * , * ) by evaluating P i,j,k,l,g,h for all g, h. This step is analogous to the algorithm "GetSpace" in [START_REF] Minaud | Key-recovery attacks on ASASA[END_REF]. (j, k, l) ← FindGood(i)

7:
for g, h ∈ [n] do 8:

v g,h ← P i,j,k,l,g,h 9:

E ← E + span(v)

10: return E

We can now build span(B, C) step by step: we first build span(B i, * , * , C i, * , * ), and we create a basis by selecting a random pair of vectors from this space. For i > 1, we check that the i-th vector space is consistent with the spaces from steps i -1 and i -2. If there is an inconsistency at some point, we backtrack and select a fresh random pair of vectors.

In the end, we obtain span(B, C). Let B ′ , C ′ be two linearly independent vectors in CHAPTER 5. STRUCTURAL CRYPTANALYSIS OF IMPLICIT WHITE-BOX IMPLEMENTATIONS span(B, C), and let A ′ = P -B ′ C ′ . Then A ′ , B ′ , C ′ is a solution to the factorization problem.

Conclusion

Our results show that any function of the form "low-degree layer, S-box layer, affine layer" can be efficiently decomposed into its inner components (up to equivalence) using only black-box access to the function. Moreover, the same is true of functions of the form "low-degree layer, modular addition, affine layer". An immediate consequence is that the white-box encryption framework of [START_REF] Ranea | Implicit whitebox implementations: White-boxing ARX ciphers[END_REF] is insecure, both for SPN and ARX ciphers. A broader consequence is that low-degree input encodings cannot hide a structured inner round function. If the round-encoding-based approach to white-box cryptography initiated by [START_REF] Chow | White-box cryptography and an AES implementation[END_REF][START_REF] Chow | A white-box DES implementation for DRM applications[END_REF] is to ever succeed in producing cryptographically secure schemes (as opposed to schemes meant to heuristically slow down real-world attackers), it must use non-trivial non-linear encodings for both input and output encodings.

Unfortunately, we are not aware of a general framework to embed non-linear encodings in both the input and output of the round. Simple non-linear encodings have been used in the past on specific schemes, but were severely restricted (operating over a few bits only, in the manner of S-boxes) [START_REF] Chow | White-box cryptography and an AES implementation[END_REF][START_REF] Chow | A white-box DES implementation for DRM applications[END_REF]. A more flexible way to embed non-linear encodings is a compelling goal for white-box cryptography. It might lead to cryptographically secure designs, which would be a major breakthrough. Indeed, having to structurally recover non-linear layers at both the input and output of a cipher relates to polynomial decomposition problems, which is NP-hard in the multivariate case [START_REF] Matthew T Dickerson | General polynomial decomposition and the s-1decomposition are np-hard[END_REF][START_REF] Faugère | An efficient algorithm for decomposing multivariate polynomials and its applications to cryptography[END_REF] (polynomial-time algorithms are known in the univariate case [START_REF] Blankertz | A polynomial time algorithm for computing all minimal decompositions of a polynomial[END_REF]).

Chapter

Conclusion

In this thesis, we have studied different problems related to computing in association with untrusted agents. Cryptography is a great tool because it spares us the faith and time needed to build trust: we build protocols and prove that they are secure: this is enough to ensure that our information is protected. This is of course in theory: in practice the implementation of a cryptosystem is a potential liability, a small oversight can prove catastrophic. Nevertheless, even when dealing with theoretical designs of cryptosystems, security might not be proven to the highest degree of certainty, save for perfect secrecy, also called information theoretical security. Cryptanalysis can be devastating to a cipher with no solid security ground to stand on.

In Chapter 3, we present new constructions of PSM protocols, that achieve information theoretical security. In our model however, no party (except the referee) can become corrupted. We can use such protocols to achieve a variant where parties collude with the referee, called non-interactive MPC [START_REF] Beimel | The complexity of multiparty PSM protocols and related models[END_REF]. By expanding the cube approach of [START_REF] Beimel | The complexity of multiparty PSM protocols and related models[END_REF], we create a framework where we see functions and inputs as tensors. With it, we get a better view the information that the parties can securely send to the referee. Some of this information contains the output we want the referee to learn. When the right conditions are met, the garbling around this output can be cancelled, and the referee learns the cleartext value. This framework yields PSM protocols for all functions, however not for any number k of parties: only prime powers for now. An interesting question is: can we expand this construction to handle k as a composite of two primes, then eventually as any composite number (and thus all of N)? Other techniques exist: in [SESN23], Shinagawa et al build PSM procotols based on quadratic residues. Not all functions fit this framework, but for k parties and any symmetric function f : {0, 1} k → {0, 1}, they achieve a communication cost of O(k 2 ), improving on the O(k 2 • log(k)) upper bound of [START_REF] Beimel | On the cryptographic complexity of the worst functions[END_REF].

In Chapter 4, we show how to build weighted-ORAM protocols: ORAM for objects of variable sizes. This is done by modifying existing ORAM protocols to make them handle weighted items. In our construction, no added cost in bandwidth is needed when done on a large subset of tree-ORAM protocols, including Path-ORAM which is used in practical applications [SvS + 13a]. In other ORAMs however, a small blowup is needed. An interesting direction to explore would be to search for a natural way to expand the hierarchical method to handle weighted items. Then no blowup would be needed. We also present new single-keyword SSE protocols based on weighted tree-ORAMs. This method is more efficient than previous attempts at constructing SSE using ORAM. This work is part of a broader wish for secure encrypted databases, although improvements are being made, it remains an open problem to achieve functionalities on par with plaintext databases while retaining some notion of security.

In Chapter 5, we cryptanalyze white-box constructions based on implicit implementa-tions from [START_REF] Ranea | Implicit whitebox implementations: White-boxing ARX ciphers[END_REF]. We show that the attack on the ASASA structure from [START_REF] Minaud | Key-recovery attacks on ASASA[END_REF] still applies when the first affine layer is replaced by a low-degree nonlinear layer. We also attack the structure behind the white-box based on an ARX cipher. [START_REF] Biryukov | Cryptanalysis of arx-based white-box implementations[END_REF] shows a decomposition-based key recovery attack on the same white-box, however without the structural aspect. Because of a flaw in the structure, we do not have suggestions to repair the system. The search for provably secure white-box cryptography continues. An open question is to analyze an ISI or an IM I construction: we prove that having a low-degree non-linear input layer is not enough, but while it is not clear how one could build a white-box where that layer is combined with a low-degree non-linear output layer, it is not clear either if one could find a (structural) attack. If we can keep building whitebox schemes based on polynomial decomposition, we can hope to base them off of hard problems [START_REF] Matthew T Dickerson | General polynomial decomposition and the s-1decomposition are np-hard[END_REF][START_REF] Faugère | An efficient algorithm for decomposing multivariate polynomials and its applications to cryptography[END_REF]. where ( * ) denotes "for all unordered E = {S 1 , .

A.2.1 The Multi-party Variant

In this section, we present an auxiliary PSM protocol that is used as a subroutine by our multi-party PSM in Section 3.3. The functionality is ⟨x 1 ⊗ . . . ⊗ x k , Y⟩ + s. It is a (k + 1)-party functionality where the i-th party has as input x i ∈ F N for i ∈ [k], and the (k + 1)-th party has as inputs Y ∈ F N ו••×N k times and s ∈ F. We will present a PSM protocol for this functionality with a communication complexity of O(poly(k) • N k ) field elements. This protocol is implicitly used in [START_REF] Beimel | The complexity of multiparty PSM protocols and related models[END_REF].

First, we consider the special case when k = 1. That is, there are only two parties. Say we call them Alice and Bob. Alice has x ∈ F N , Bob has y ∈ F N , s ∈ F. The functionality output is ⟨x, y⟩ + s. The PSM protocol works as follows:

• Random a, b ∈ F N , c ∈ F are sampled from the common random string, which is known by both Alice and Bob.

• Alice sends x := x + a, z := c -⟨b, x⟩ to the referee.

• Bob sends ȳ := y + b, w := s -c -⟨a, y⟩ -⟨a, b⟩ to the referee.

• The referee outputs ⟨x, ȳ⟩ + z + w.

For the case k ≥ 2, the first k parties need to jointly emulate Alice. The protocol works as follows: Due to the randomness of C, we know W is a randomized encoding of w. Thus, it is equivalent for the first k parties to jointly reveal W to the referee. Since every coordinate of W can be computed by an arithmetic formula of size O(k), each of them can be revealed by using the Ishai-Kushilevitz PSM protocol [START_REF] Ishai | Randomizing polynomials: A new representation with applications to round-efficient secure computation[END_REF], which has a communication complexity of O(poly(k)) field elements. The referee learns w after receiving O(poly(k) • N k ) field elements.

• The referee outputs ⟨ X, Ȳ⟩ + z + w.

The correctness of the protocol can be verified in the following equation: The privacy is guaranteed by the following simulator:

• Simulate X, Ȳ, W as uniform random, since they are one-time-padded by A, B, C.

• Given X, Ȳ, W and the function output, w, z are uniquely determined since w = (W) and ⟨ X, Ȳ⟩ + z + w = output.

• Simulate the transcripts of the inner Ishai-Kushilevitz PSM protocols using its own simulator, which takes X, W as input.

A.2.2 The 2-party Variant

In this section, we present an auxiliary PSM protocol that is used as a subroutine by our unbalanced 2-party PSM in Section 3.4. The functionality is ⟨x 1 ⊗ . . . ⊗ x k , Y⟩ + s. It is a 2-party functionality where the first party, namely Alice, has as inputs x 1 , . . . , x k ∈ F N and the second party, namely Bob, has as inputs Y ∈ F N ו••×N k times and s ∈ F. We will present a PSM protocol for this functionality with unbalanced communication complexity, where Alice sends O(kN ) field elements and Bob sends (N + 1) k field elements.

As the first step, we consider a harder problem instead. Bob's input is replaced by a multi-affine function f :

F N × • • • × F N → F.
Corresponding, the functionality is replaced by f (x 1 , . . . , x k ). Every multi-affine function f can be uniquely represented by its coefficient tensor F ∈ F (N +1)ו••×(N +1) such that for any z 1 , . . . ,

z k ∈ F N , f (z 1 , . . . , z k ) = ⟨z 1 ∥1 ⊗ • • • ⊗ z k ∥1, F⟩.
Here z i ∥1 denotes the concatenation of z i and 1, which is a dimension-(N + 1) vector. Notice that, if we let the "first" N × • • • × N subtensor of F equal Y, let its "last" entry F[N + 1, . . . , N + 1] = s, and let all other entries in F be 0, we have f (x 1 , . . . , x k ) = ⟨x 1 ∥1 ⊗ • • • ⊗ x k ∥1, F⟩ = ⟨x 1 ⊗ . . . ⊗ x k , Y⟩ + s.

The protocol works as follows:

A.2. AUXILIARY PSM PROTOCOLS FOR ⟨x 1 ⊗ . . . ⊗ x k , Y⟩ + s • Random r 1 , . . . , r k ∈ F N and a random multi-affine function g are sampled from the common random string.

• Alice sends xi = x i + r i to the referee, for all i ∈ [k].

• Bob computes the multi-affine function g, such that g(z 1 , . . . , z k ) := f (z 1r 1 , . . . , z kr k ).

Bob sends ḡ = g + h to the referee.

• Alice additionally sends s = h(x 1 , . . . , xk ) to the referee.

• The referee outputs ḡ(x 1 , . . . , xk ) -s.

The correctness follows directly from the following equation: The privacy is guaranteed by the following simulator:

• Simulate x1 , . . . , xk , ḡ as uniform random, since they are one-time padded by r 1 , . . . , r k , h.

• Given x1 , . . . , xk , ḡ and the function output, simulate s by computing s from the equation ḡ(x 1 , . . . , xk ) -s = output.

B.4. WEIGHTED HIERARCHICAL ORAM of log N splinters, cannot be stored in the tree: all splinters are then moved to the stash. The stash capacity is 2 log(N ) -1. To avoid overflows, the content of the stash is written back into the tree whenever its size exceeds log N . Such a behavior reveals to the server when the stash size passes the log N threshold. Unfortunately, leaking when the stash size passes a threshold breaks Path ORAM security, because certain access patterns fill the stash faster than others. For more information, we refer the reader to [RYF + 13, Section 3.1.1], where this exact point is discussed. Because of this leakage, the DivORAM construction of [LHL + 18] is insecure.

B.4 Weighted Hierarchical ORAM

Our work focuses on Tree ORAMs, mainly because of their higher practical efficiency. It is natural to ask whether similar results can be obtained for hierarchical ORAM. We briefly discuss this question here.

As shown in chapter 4, there is a natural way to adapt Tree ORAM algorithms to handle weighted items. The problem of building weighted Tree ORAM is not so much an algorithmic problem as a combinatorial one: we need to prove that the "natural" weighted variant of Tree ORAM creates no overflow.

With hierarchical ORAMs, this first step is already a challenge. There is no obvious natural algorithmic modification of hierarchical ORAMs that handles weighted items. Indeed, we would first need weighted oblivious hash tables. That is, we need oblivious hash tables that can handle items of variable size. We also need those tables to support oblivious sorting, or at least oblivious compaction, in a way that is compatible with variable-size items. Building such a data structure looks quite challenging, and we do not know of a natural candidate.

In more details, we know of two constructions that come close to that goal in the literature, but neither quite reaches it. The first is two-choice hashing for weighted items [START_REF] Talwar | Balanced allocations: the weighted case[END_REF][START_REF] Minaud | Dynamic local searchable symmetric encryption[END_REF]. Two-choice hashing is easy to realize obliviously. The problem is that we would have to pay (at least) a log log overhead, and efficient oblivious compaction seems difficult. An alternative approach is to use the "Data-Independent Packing" primitive from [BBF + 21]. But the only known instantiation requires computing a maximum flow algorithm. It is not clear how to compute that algorithm in quasilinear time, let alone in an oblivious manner.

CHAPTER 1 .

 1 INTRODUCTION EN FRANÇAIS bornes supérieures et présentons des protocoles PSM avec communication déséquilibrée pour deux parties. Notre résultat principal est un protocole PSM pour une infinité de k (tous les k ≤ 20 et toutes les puissances premières) avec un coût de O(poly(k) • N k-1

Figure 3

 3 Figure 3.1: Illustration of a multi-party PSM protocol

  R() ⊗ S()⟩ + easy terms. CHAPTER 3. NEW TECHNIQUES FOR MULTI-PARTY PSM Thus, by setting F to be any finite field where 2 ̸ = 0, the above equation induces a 2-party PSM protocol with unbalanced communication complexity O(N 1 3 ), O(N 2 3

The 2 -

 2 party PSM for f works as the follows: For each Ω ⊆ [k] such that 0 < |Ω| ≤ d, Alice sends XΩ to the referee. Symmetrically, for Ω ⊆ [k] such that 0 < |Ω| ≤ k -d, Bob sends ȲΩ to the referee. Use the PSM guaranteed by Fact II to reveal s j=1 b j T (j) to the referee. Then Fact I allows the referee to compute the output from Equation (3.15). Proof of Fact I. (Similar to the proof of Fact I in Section 3.3.2.) Equation (3.15) shows that ⟨F, x 1 ⊗ • • • ⊗ x k ⊗ y 1 ⊗ • • • ⊗ y k ⟩ can be computed from the encoding. Moreover, the distribution of the encoding is perfectly simulatable: The joint distribution of tensors XΩ for 0 < |Ω| ≤ d and ȲΩ for 0 < |Ω| ≤ k -d is uniform, as they are independently one-time padded. Then the value of s j=1 b j T (j) is uniquely determined by Equation (3.15).

  Lemma 4.4.3. Let s be a legal sequence of accesses, and let S ∈ S . Then the map f : w → E[X s,L,S (w)] is Schur-convex.

Figure 4 . 1 :

 41 Figure 4.1: Experimental results for Z ∈ {3, 4}

Figure 4

 4 Figure 4.2: A block of size < B in 2 chunks

Figure 4 . 3 :

 43 Figure 4.3: Overhead of ORAM-based SSE constructions. U is an upper bound on the longest list size, W ≤ N is the number of keywords, B is the ORAM block size.

4. 6 .

 6 SEARCHABLE ENCRYPTION FROM WEIGHTED ORAM • BlockSSE.Update(K, (w, e); EDB): If l w is not a multiple of B -⌈log n⌉, the client accesses the ORAM at position p w , adds e to the data, replaces p w by a new uniformly random position, and updates the ORAM according to this new data and position. If l w is a multiple of B -⌈log n⌉, a new block is inserted at a new uniformly random position, containing as data {e} together with the position p w of the previous last block. On the client side, p w is updated to the position of the newly inserted block. Theorem 4.6.2 (Security of BlockSSE). BlockSSE is L-secure with respect to the leakage function L = {L Setup , L Search , L Update }, with L Setup = {N, B}, L Search (w) = ⌈|DB(w)|/B⌉, and L Update = ∅. A proof of Theorem 4.6.2 is given in Appendix B.1. BlockSSE ′ is the same as BlockSSE, except the iterative variant of Path-ORAM is used.

Lemma 5.3. 1 .

 1 Let F : F n 2 → F 2 , and let E be an affine subspace of F n 2 of dimension deg(F ) + 1. Then: x∈E F (x) = 0.

  2. At the outcome of this computation, we recover λ B•C , which reveals the coefficients of B • C + D. Recovering the coefficients of B and C from there is a new instance of the factorization problem from Section 5.5.3, for the same degree d. Solving the problem yields the coefficients of B and C, i.e it reveals the polynomial expressions of I[n -i] and I[2n -i]. This sets us up for the next stage of the induction. Eventually, all I[i] are recovered: we have peeled off the initial I layer.

  ZeroOracle 1: Input: distinct i, j, k, l, g ∈ [n] 2: Output: True if B x = C x =0 for all possible triples x in {i, j, k, l, g}. 3: for h ∈ [n]\{i, j, k, l, g} do 4:

Algorithm 5

 5 FindGood 1: Input: i ∈ [n] 2: Output: j, k, l ∈ [n] such that (B j,k,l , C j,k,l ) ̸ = (0, 0) and B x = C x =0 for all other triples x in {i, j, k, l}. 3: while True do n]\{i, j, k} 7:

Algorithm 6 2 4 :2 5 :

 645 GetSpace 1: Input: i ∈ [n] 2: Output: span(B i, * , * , C i, * , * ) 3: Let v ∈ F n 2 Let E = {0} ⊆ F n 2 while dim(E) < 2 do 6:

•

  Random A, B, C ∈ F N ו••×N are sampled from the common random string. Define c ∈ F as the sum of entries in C. • The (k + 1)-th party sends Ȳ := Y + B, z := s -c -⟨A, Y⟩ -⟨A, B⟩ to the referee.• The first k parties jointly reveal X :=x 1 ⊗ . . . ⊗ x k + A, w := c -⟨B, x 1 ⊗ . . . ⊗ x k ⟩to the referee.Since every coordinate of X can be computed by an arithmetic formula of size O(k), each of these coordinates can be computed by the referee by using a PSM protocol with communication complexity of O(poly(k)) field elements[START_REF] Ishai | Randomizing polynomials: A new representation with applications to round-efficient secure computation[END_REF]. The referee learns X after receiving O(poly(k) • N k ) field elements. APPENDIX A. SUPPLEMENTARY MATERIAL ON PSM The term w := c -⟨B, x 1 ⊗ . . . ⊗ x k ⟩ equals the sum of all entries in W := C -B • p.w. (x 1 ⊗ . . . ⊗ x k ), where • p.w. denotes the point-wise product. In other words, we defines W ∈ F N ו••×N as W[i 1 , . . . , i k ] = C[i 1 , . . . , i k ] -B[i 1 , . . . , i k ]x 1 [i 1 ] . . . x k [i k ].

⟨

  X, Ȳ⟩ + z + w = ⟨x 1 ⊗ . . . ⊗ x k + A, Y + B⟩ + s -c -⟨A, Y⟩ -⟨A, B⟩ + c -⟨B, x 1 ⊗ . . . ⊗ x k ⟩ = ⟨x 1 ⊗ . . . ⊗ x k , Y⟩ + s.

ḡ(x 1

 1 , . . . , xk ) -s = g(x 1 , . . . , xk ) + h(x 1 , . . . , xk ) -h(x 1 , . . . , xk ) = g(x 1 , . . . , xk ) = f (x 1r 1 + r 1 , . . . , x kr k + r k ) = f (x 1 , . . . , x k ).

.2 Protocoles d'Oblivious RAM pour des objets de tailles variables

  Le modèle d'Oblivious RAM (ORAM) sert à dissimuler le motif d'accès qu'un client produit lorsqu'il émet des requêtes à un serveur pour obtenir les données chiffrées qui y sont stockées. En supposant que le client a stocké N objets, chacun de taille B bits, nous souhaitons pouvoir effectuer des requêtes de lecture/écriture avec une complexité de communication inférieure à celle de l'ORAM trivial, où le client télécharge l'intégralité de la base de données. Les protocoles ORAM ont été présentés pour la première fois par Goldreich et Ostrovsky dans[START_REF] Goldreich | Software protection and simulation on oblivious RAMs[END_REF]. Ils y présentent le premier ORAM non trivial, appelé square-root ORAM (nommé d'après son coût de bande passante de O(

	1.4. RÉSUMÉ DES RÉSULTATS
	1.4√ Dans le square-root ORAM, le serveur détient un tableau de taille N + 2 • √ N , composé N • B)). (initialement) des N éléments que l'ORAM doit stocker, suivis de √ N objets factices (par exemple, des chiffrements de mots aléatoires) et √ N objets protégés (dans le refuge). Le
	refuge servira de stockage temporaire, utile lors des requêtes. L'idée générale derrière ce
	système est la suivante :

Le coût de la communication de ce protocole est de l'ordre de O( √ N ) pour Alice et Bob. Au Chapitre 3.4, nous présentons des protocoles PSM avec une communication déséquilibrée : Alice envoie O(N η ) bits et Bob envoie O(N 1-η ) bits, avec η ∈ [0, 1].

Table 3

 3

	.1: The communication complexity of computing general f : [N ] k → {0, 1} in multi-party
	PSM model
	Communication complexity	Communication complexity
	of one party	of the other party
	[FKN94]

  Aux k N implies a PSM for f : [N ] k → {0, 1} with the same communication complexity. The reduction consists of having F be the truth table of f . We will present a framework of constructing k-party PSM for Aux k N , whose communication complexity is O k

where F is public and fixed CHAPTER 3. NEW TECHNIQUES FOR MULTI-PARTY PSM As shown in the beginning of Section 3.3.1, a PSM protocol for

  x iw is called an easy tensor if at most k + 1 out of the 2k dimensions are contributed by vector x

i 's (i.e., w ≤ k + 1). The corresponding term is called an easy term. Every easy term admits a PSM protocol with communication complexity no more than

O(poly(k) • N k-1

2 ) field elements (more details in Section 3.3.2). CHAPTER 3. NEW TECHNIQUES FOR MULTI-PARTY PSM Hard terms (hard tensors) The rest.

  For any prime p and positive integer e, binomial coefficient p e +t p e -2 is a multiple of p for all 0 ≤ t ≤ p e -3, while binomial coefficient 2p e -2 p e -2 ≡ 1 mod p. Proof. For every 0 ≤ t ≤ p e -3, The two parties in 2-party PSM are conventionally called Alice and Bob. Let x ∈ [N ] denote Alice's and y ∈ [N ] denote Bob's input. In this section, we show that every functionality f : [N ] × [N ] → {0, 1} admits a 2-party PSM protocol, where Alice sends O(N η ) bits and Bob sends O(N 1-η ) bits.

	3.4 Unbalanced 2-party PSM Protocols
	Proof.
				p e t	=	p e t	•	p e -1 t -1	.
	Lemma 3.3.3. p e + t p e -2	=	t j=0	t j		p e p e -2 -j
										multiple of p
	is a multiple of p. While
	2p e -2 p e -2	=	p e -3 j=0	p e -2 j	p e p e -2 -j	+	p e -2 p e -2	p e 0	≡ 1 mod p.
					multiple of p

easy terms mod p, which induces a k-party PSM protocol with c.c. O k (N k-1 2 ). Lemma 3.3.2. For any prime p and positive integer e, p e t is a multiple of p for all 0 < t < p e . Theorem 3.4.1. For any functionality f : [N ] × [N ] → {0, 1}, and any η = d/k such that d, k are integers and 0 < d < k ≤ 20, there is a 2-party PSM protocol for f with unbalanced communication complexity O

  Ω t are disjoint and their union equals [k]. The shape of an Alice-side masked tensor R Ω 1 ⊗. . .⊗R Ωt ⊗x i 1 ⊗. . .⊗x iw is the multiset {|Ω 1 |, . . . , |Ω t |}. Bob-side pure tensors are defined symmetrically.

  . . , S t } being a partition of [2k] such that {|S 1 |, . . . , |S t |} = P ". Thus, ⟨F, X(P )⟩ = Q⊆P G={S 1 ,...,St} s.t. {|S 1 |,...,|St|}=P \Q Q⊆P G={S 1 ,...,St} s.t. {|S 1 |,...,|St|}=P \Q Proof of Equation (3.10). Let n = sum(Q). By definition, α(Q) is the number of unsorted partitions E = {S 1 , . . . , S t } of [n] such that the multiset {|S 1 |, . . . , |S t |} (i.e. the shape of E) equals Q. .2. AUXILIARY PSM PROTOCOLS FOR ⟨x 1 ⊗ . . . ⊗ x k , Y⟩ + s • Then, sort the sets in the partion E = {S 1 , . . . , S t }. Sort them by their sizes, i.e. |S 1 | ≤ |S 2 | ≤ • • • ≤ |S t |. For any m, if several sets are of the size m, their order has to be specified, the number of such choices is (number of m's in Q)!. • Finally, arrange the elements in each S i into a sub-sequence, the number of possible sequences is |S i |!. Concatenate these sub-sequences in order. Auxiliary PSM Protocols for ⟨x 1 ⊗ . . . ⊗ x k , Y⟩ + s

	α(Q) •	(number of m's in Q)! •	i! = n!
		m∈Z +		i∈Q
	A.2
	F,	(R S i +	x j )
	( * )	i∈[t]	j∈S i
	=	F,
	( * ) G⊆E		j / ∈
			i∈[t] x α(Q) • F, R S i ⊗ j / ∈ i∈[t] S i R S i ⊗ x j
				i∈[t]	j / ∈	S i
				i∈[t]
	=

S∈G R S ⊗ S∈G S x j = β(P, G) • F, j , where β(P, G) accounts for the redundancy: define β(P, G) as the number of unordered partitions E of [2k] such that G ⊆ E and P is the shape of E. It is equivalent to count the number of F := E \ G. That is, β(P, G) also equals the number of unordered partitions F of [2k] \ S∈G S such that Q is the shape of F . Thus by definition, β(P, G) = α(Q). The proof is concluded by ⟨F, X(P )⟩ = Q⊆P α(Q) • ⟨F, R(P \ Q)⟩. To compute α(Q), we count the number of ways to arranging 1, . . . , n into a sequence. • First, pick an unsorted partitions E of [n] s.t. the shape of E equals Q. The number of choices is α(Q).

A

L'Informatique est une science jeune, par conséquent beaucoup de termes sont introduits pour nommer des concepts récents. Il est préférable d'employer la terminologie en français quand nous parlons de cryptologie dans cette langue, cependant certains domaines sont peu connus et le vocabulaire associé n'existe pour l'instant qu'en anglais. Plutôt que de proposer une traduction qui ne ferait pas consensus, ce manuscrit fait le choix de garder les termes en anglais dans ces cas là. D'une façon analogue, on parle de "travelling" au cinéma.

A note on the randomness complexity: The final protocol uses R Ω only if |Ω| ≤ k -1.

We implicitly exchange the order of indices in tensor product. E.g. when k = 2, the masked tensor X{1,4} ⊗ X{2,3} is defined by ( X{1,4} ⊗ X{2,3} )[j 1 , j 2 , j

, j

] = X{1,4} [j 1 , j 4 ] • X{2,3} [j 2 , j 3 ].

The source code can be downloaded from https://github.com/tianren/psm.

The source code can be downloaded from https://github.com/tianren/psm.

3.5. OPEN PROBLEMS

The reader may observe that items of size 0 are not technically legal per the earlier definition of wORAM, which asks that items are of size at least 1; however, Weighted(ORAM) remains well-defined even for items of size 0, so nothing stops us from using them within the proof -the reason we forbade items of size 0 is that they would allow for an unbounded number of items, which would require a position map of unbounded size, but this is irrelevant for the current line of reasoning.

More exactly, the attack of[START_REF] Biryukov | Structural cryptanalysis of SASAS[END_REF] relies on the SASAS function minus the last layer having low degree, while the attacks in[START_REF] Biryukov | Cryptographic schemes based on the ASASA structure: Black-box, white-box, and public-key[END_REF][START_REF] Derbez | On recovering affine encodings in white-box implementations[END_REF]rely on the whole function having low degree.

This analysis is done differently in[START_REF] Biryukov | Structural cryptanalysis of SASAS[END_REF], but in retrospect, it could also have been done via a cube attack-except they did not exist yet [DS09].

of the form S 1 • B for affine B is a solution. One may wonder if the attack might recover other solutions, but in practical experiments, this does not appear to be the case[START_REF] Biryukov | Structural cryptanalysis of SASAS[END_REF].

We do not propose a way to do so generically here. This is because the permutation symmetry between S-boxes might be broken only by the key schedule. Since the key schedule of a block cipher can take an arbitrary form, it does not lend itself to a generic structural analysis. On the other hand, for any concrete block cipher, if the cipher leaks plaintext values at the outcome of every S-boxes layer in every round, up to permutation of S-boxes, we contend that breaking the cipher is quite easy.

Remerciements

Remerciements v

Publication

This work was in an article published at the Theory of Cryptography Conference 2021, under the following title [START_REF] Assouline | Multi-party psm, revisited: Improved communication and unbalanced communication[END_REF]:

Multi-party PSM, revisited: Improved communication and unbalanced communication.

by Léonard Assouline and Tianren Liu

Equivalent keys

Since F does not uniquely define the triple (I, S, A), the goal of the attacker is to find a triple (I ′ , S ′ , A ′ ) such that F = A ′ •S ′ •I ′ , as stated above. Such a triple is called an equivalent key. A few remarks about equivalent keys will prove helpful for the cryptanalysis of ISA.

First, we can freely assume that A ′ is a linear layer, rather than an affine layer. To see this, take an arbitrary equivalent key (I, S, A) with an affine layer A(x) = L(x) + c, for some linear map L : F n 2 → F n 2 and constant c ∈ F n 2 . Then the triple (I, S ′ , L) with S ′ (x) = S(x) + L -1 (c) is also an equivalent key. This follows from the fact that both triple compute the same function, and that S ′ can still be represented as k parallel s-bit S-boxes. In the remainder, we assume without loss of generality that A is linear.

In fact, the last linear layer A is only defined as far as determining the output space of each S-box. More precisely, let V i = span(e s(i-1)+1 , . . . , e s(i-1)+s ) be the vector space spanned by the bits of the i-th S-box. Let L i be an arbitrary invertible linear map V i → V i . Given an equivalent key (I, S, A), we can freely compose the output of the i-th S-box with L i , and compose A with L -1 i , to obtain another equivalent key. Thus, we cannot hope to recover more information from A than the output space A(V i ) of each S-box through A.

Conversely, if we know the spaces A(V i ), then for each A(V i ), we can arbitrarily pick a basis of the space, then assign the k-th bit of the i-th S-box to the k-th element of that basis. Letting L ′ be the map computed in that manner, L -1 • F = (L -1 A) • S • I has the IS structure, so we have effectively peeled off the linear layer A. Indeed, L -1 A operates independently on each V i , and hence can be folded into the S-box layer.

In conclusion, in order to peel off the A layer, it is necessary and sufficient to recover the output spaces A(V i ) of each S-box through A. Note that the spaces A(V i ) can be recovered in any order. Indeed, given an equivalent key (I, S, A), we are free to permute the S-boxes, up to applying the inverse permutation to I and A (which does not affect their degree).

Peeling off the A layer: from ISA to IS

Our approach is similar to [START_REF] Minaud | Key-recovery attacks on ASASA[END_REF]. Consider two bits b 1 and b 2 at the output of two distinct S-boxes in the mapping S • I. When viewed as a function of the input x of S • I, each of those bits is of degree at most d(s -1). Hence their product b 1 b 2 is of degree at most 2d(s -1). On the other hand, let b 1 ′ denote a bit at the output of the same S-box as b 1 . Then by [MDFK18, Lemma 2], the product b 1 b 1 ′ is of degree only at most d(s -1).

The idea of the attack is to detect this difference in degree through the last affine layer A. For that purpose, for i = 1, 2, define λ i ∈ F n 2 such that:

Such λ i 's necessarily exist, because b 1 and b 2 are bits at the output of S • I = A -1 • F , and A -1 is linear (because we have assumed that A is linear). By Lemma 5.3.1, the fact that b 1 b 2 is of degree at most d(s -1) implies that b 1 b 2 sums to zero over any cube of dimension d(s -1) + 1. Let C be such a cube. We obtain the equation:

(5.1)

Note that C can be freely chosen by the attacker. Hence, all quantities F (x)'s in (5.1) can be computed by querying the F oracle. The only unknowns in the equation are the λ i [j]'s.

Observe that (5.1) is an equation of degree 2 over the λ i [j]'s. We can sample one new equation for each choice of cube C of dimension d(s -1). Provided d(s -1) < n, there are many more choices of cubes than quadratic monomials, hence the system can be solved by linearization (cf. Section 5.3.5).

Solving the system yields pairs of linear masks λ ′ 1 , λ ′ 2 such that ⟨λ ′ 1 |F (x)⟩ and ⟨λ ′ 2 |F (x)⟩ are equal to two bits (or linear combination of bits) at the output of the same S-box. Taking one such solution λ ′ 1 , λ ′ 2 , fixing λ 1 = λ ′ 1 in (5.1), and solving for λ 2 , we can recover the linear space spanned by all other bits at the output of the same S-box. In the notation of Section 5.4.2, we recover the output space A(V i ) of one S-box.

By repeating the same process, we eventually recover the outputs spaces A(V i ) for 1 ≤ i ≤ k, i.e. we obtain the output space of all S-boxes. Following the discussion in Section 5.4.2, this is enough to peel off the last linear A of F . We are left with a new structural cryptanalysis problem of the form F ′ = S • I.

Recovering the remaining layers: structural cryptanalysis of IS

In this section, we are given F = S • I, with the promise that S is a layer of k parallel s-bit S-boxes, and

The goal is to find S ′ , I ′ with the same features as S, I, such that F = S ′ • I ′ .

Let S i denote the i-th S-box in the layer S. Since we are able to observe separately the outputs of each S-box S i , let F i denote the restriction of F to the bits at the output of the i-th S-box. That is, F i = (F [(s -1)i + 1], . . . , F [(s -1)i + s]). Likewise, let I i denote restriction of I to the i-th S-box. Then F i = S i • I i . Observe that recovering an equivalent key S ′ , I ′ for F is exactly equivalent to recovering S ′ i :

for each S-box separately. As a consequence, from now on, we restrict our attention to finding S ′ 1 , I ′ 1 given black-box access to F 1 . To do so, we borrow an idea from [START_REF] Biryukov | Structural cryptanalysis of SASAS[END_REF].

For each x ∈ F s 2 , let t x = S -1 (x). We view the t x 's as unknown. Since I is of degree at most d, by Lemma 5.3.1, for any cube C of dimension d + 1, we get an equation:

Thus, by sampling sufficiently many cubes, we obtain a linear system of equations on the t x 's, which we can solve to obtain S ′ 1 3 . We can then let

Attack complexity

The complexity of the attack is determined by the number of bits n of the cipher's internal state, the number of bits s of the S-boxes, and the degree d of the input encoding. In parameter regimes that correspond to typical real-world scenarios (e.g. AES parameters), the complexity bottleneck is to solve Equation (5.1) (Section 5.4.3). This amounts to CHAPTER 5. STRUCTURAL CRYPTANALYSIS OF IMPLICIT WHITE-BOX IMPLEMENTATIONS Let P denote the polynomial of degree 2d in

1 is known to the attacker, and d is small (typically, in [START_REF] Ranea | Implicit whitebox implementations: White-boxing ARX ciphers[END_REF], d = 2), P can be computed explicitly by the attacker. Looking at the right-hand side of Equation (5.4), the only term of degree 2d is I[n]I[2n]: other terms are of degree at most d. Let B and C denote the polynomials of degree d corresponding to I[n] and I[2n] respectively. Let A denote the polynomial of degree d corresponding to the other terms of the expression. Then Equation (5.4) can be rewritten as:

where A, B, C are of degree d. This leads to the following problem.

Factorization Problem.

In other words, we want to solve a particular kind of structural cryptanalysis problem, for the structure P = A + B • C. As is often the case with structural cryptanalysis, the solution is not unique: if (A, B, C) is a solution, then so is (A + B, B, B + C), for instance. In general, any two linearly independent vectors in the linear span of B, C, 1 can be chosen for B ′ and C ′ . Unless P has a special structure, there are no other solutions (confirmed by experiments).

In fact, the factorization problem above was already considered in [START_REF] Minaud | Key-recovery attacks on ASASA[END_REF], in the special case d = 2. The authors of [START_REF] Minaud | Key-recovery attacks on ASASA[END_REF] give an efficient algorithm for that case. A polynomial-time algorithm for the case of arbitrary constant d can be found in [START_REF] Barak | On the (im)possibility of obfuscating programs[END_REF]. In fact, the work of [START_REF] Barak | On the (im)possibility of obfuscating programs[END_REF] applies to a much more general class of problems, and is quite complex as a result, and less efficient in practice. In Section 5.7, we generalize the algorithm from [START_REF] Minaud | Key-recovery attacks on ASASA[END_REF] for d > 2, which suffices for our purpose.

At the outcome of running either one of the previous algorithms on ⟨λ ′ 1 |F ⟩, we recover the linear span of I[n], I[2n], 1, viewed as polynomials in their inputs. Up to the contribution of 1 in that span, which only affects the constant in the polynomial, I[n] can be recovered by observing that it also lies in the span of polynomials generated by elements of S 0 . For I[2n], we simply take one of the other two non-zero elements in the span of

I[n], I[2n], which can be either I[2n] or I[2n] + I[n] (again, up to the constant 1). If we happened to pick I[2n] + I[n]

, our guess was wrong. Nevertheless, we continue with the rest of the attack. As discussed in Section 5.5.2, the algorithm will backtrack to this point if it detects an inconsistency later on.

Step 3: recovering the (x ⊞ y)[i]'s

In the previous step, we isolated the penultimate bit of the modular addition (x⊞y)[n-1], by using the fact that it is the only bit of degree two in M . This required using cubes of dimension 2d + 1.

We then factorized the polynomial expression of that bit to obtain the polynomial expressions

of I[n] and I[2n].

A simple approach would be to repeat this process: starting from the observation that (x ⊞ y)[n -i] is the only bit of degree i + 1 in M , for i > 1, we could isolate each bit and somehow factorize it, as before. This runs into two issues. First, to isolate a bit of degree i + 1, we would need to sum over cubes of dimension i + 2. The number of summands grows exponentially with i, and i goes up to n, so this is not feasible. Second, 5.5. STRUCTURAL CRYPTANALYSIS OF IMA the polynomial expression of (x ⊞ y)[n -1] is simple, which led to a simple factorization problem; but for (x ⊞ y)[n -i], the polynomial expression becomes increasingly complex as i grows, and so would the associated factorization problem.

We use a different approach, based on the following observation. Consider for a moment the expression x ⊞ y = z over F n 2 . Let c i denote the value of the carry coming into the (n -i)-th bit of x ⊞ y, that is:

The a straightforward computation shows that the following recursive relation holds:

Hence, if we know c i-1 , then we have:

Going back to our problem, we proceed by induction. For the i-th inductive stage, assume we have recovered I[n-j] and I[2n-j] for j ≤ i. Note that Step 2 in Section 5.5.3 initialized that induction for i = 0. Then using our knowledge of I[n -j] and I[2n -j] for j ≤ i, we know the inputs of the last i + 1 inputs of the modular addition M in F . This means that for any given input v of F , we can compute the value of the carry

. Using (5.6), we can thus write:

where A, B, C, D have algebraic degree d. Equation (5.7) may seem difficult to exploit, since it depends on c i-1 , which may be of high degree. For that reason, we no longer rely on cubes, and propose a different technique. For v ∈ F n 2 and S = {s 1 , . . . ,

For k ≤ n, let v ≤k denote the vector of length k i=0 n i whose coordinates are equal to v S for each S ⊆ [1, n] of cardinality at most ℓ (with the convention v ∅ = 1). Observe that a map f (v) is of algebraic degree at most k if and only if f (v) is a linear combination of elements of v ≤k . (Algebraically, we are moving into the tensor space T ≤k (F n 2 ), but we prefer to describe our algorithm in more concrete terms.) Applying this observation to A in (5.7), there exists λ A such that A(v) = ⟨λ|v ≤d ⟩, and likewise for D, and for the product B • C. Reinjecting into (5.7), we have:

(5.8)

Given v, the attacker can compute all elements v ≤2d , v ≤d , and c i-1 (v) • v ≤d on the right-hand side of (5.8). Here, we use the fact that c i-1 (v) can be computed for any v by induction hypothesis, discussed earlier. Letting λ i be such that

we have

(5.9)

Each choice of v yields a new equation of this form. We obtain a linear system in the λ * 's, viewed as vectors of binary unknowns. Without loss of generality, we set λ D = 0, since its coefficients can be folded in λ B•C . Solving the system, and discarding the subspaces where either λ A is zero, or the coefficients of degree higher than d in λ B•C are zero, yields a solution. In fact, experiments show that the solution space is sometimes of dimension WHITE-BOX IMPLEMENTATIONS the Factorization problem (in Section 5.5.3) has multiple solutions. What our experiments observe is that any time a choice is incorrect (i.e., the choice will not lead to a correct solution for the overall problem), an inconsistency is detected at the very next step of the computation. That is, the computation of the next bit immediately fails. As a consequence, the algorithm essentially follows a linear path, recovering the expression of one bit after the other. It never needs to revisit choices made for bits before the current one.

Because affine self-equivalences of the modular addition have a complex structure (see [RVP22, Section 5]), one might have expected that a non-trivial amount of backtracking may be necessary. It turns out that this is not the case. As a consequence, recovering the input (and output) encodings is much simpler than one might have expected. The main computational cost is to solve the linear system in each step, as discussed in Section 5.5.4.

Polynomial factorization

In this section, we focus on the factorization problem identified in Section 5.5.3. To solve the problem efficiently, we sketch a generalization of the polynomial factorization algorithms from [MDFK18, Section 5.3].

The problem is: given a polynomial P = A + B • C, where P is known and A, B, C are of degree d, find A ′ , B ′ , C ′ of degree d such that

In [START_REF] Minaud | Key-recovery attacks on ASASA[END_REF], the problem is solved when d = 2. The solution can be generalized as long as d remains small, as we discuss in what follows. For simplicity, we first present the algorithm in the case d = 3, and discuss its generalization to d > 3 later on.

Notation

Let D be a degree-

Let D i,j, * denote the vector (D i,j,0 , D i,j,1 , . . . , D i,j,n-1 ) ∈ F n 2 , and let D i, * , * denote the n × n matrix whose j-th row is D i,j, * , for j ∈ [n].

Algorithms to recover the polynomials

We focus on homogeneous monomials of P degree 2 * d = 6. Lower-degree monomials can be recovered in a similar way, as in [START_REF] Minaud | Key-recovery attacks on ASASA[END_REF]. The value of A can be deduced from the values of P , B, C using the equation A = P -B • C. Thus, we focus on recovering B, C. More precisely, following the approach of [START_REF] Minaud | Key-recovery attacks on ASASA[END_REF], we recover span(B, C). For polynomials of degree d = 2, span(B, C) is computed from the knowledge of span(B i, * , C i, * ) for all i ∈ [n]. In our case, it is likewise possible to compute span(B, C) from the knowledge of span(B i, * , * , C i, * , * ).

We first need an algorithm that will decide if, given (i, j, k), B i,j,k = C i,j,k = 0. This can be done in instant time with a low probability of failure: we use Algorithm 4, then recursively use variants that take a smaller number of indices as inputs.

Algorithm 4 may output an incorrect answer, with (very) low probability. If this happens, the factorization algorithm will fail at a later stage. Since this happens with low probability, in the event of a failure, the algorithm can simply be run again. Using Algorithm 4, we can build an algorithm that takes as input i ∈ [n] and returns (j, k, l)

Publication

This work has been submitted for publication at the time of writing this thesis.

Appendix

A Supplementary material on PSM

A.1 Proof of Equation (3.9) and (3.10)

Proof of Equation (3.9). By definition:

⟨F, X(P )⟩ = ( * )

Appendix

B Additional proofs for weighted ORAM B.1 SSE Proofs

B.1.1 Proof of ZeroSSE

The simulator S for ZeroSSE behaves as follows.

• Setup: on input L Setup = (N, U ), S creates a wORAM instance Weighted(PathOram) instance with block size U and number of blocks ⌈N/U ⌉, initialized with ⌈N/U ⌉ items containing dummy data of size B. Let a denote the address of one of these items.

• Search and Update: in both cases, S queries the wORAM instance on item a with op = read.

We claim that the resulting transcript is indistinguishable from the real transcript. In fact, this follows immediately from the security of Weighted(PathOram), since the guarantees of a wORAM scheme is that any two sequence of accesses of the same length are indistinguishable, and the simulator makes the same number of accesses as the client in the real game. Moreover, Theorem 4.4.1 implies that Weighted(PathOram) is a correct wORAM scheme.

Note that the analysis relies on the fact that Path ORAM is correct for the given parameters, which in turn implies that we require N/U = Ω(λ). If N/U < λ, it may not be worth using an elaborate ORAM scheme, since the overhead of trivial ORAM is less than λ.

B.1.2 Proof of BlockSSE

The simulator S for BlockSSE behaves as follows.

• Setup: on input L Setup = (N, B), S creates a wORAM instance Weighted(PathOram) instance with block size B and number of blocks ⌈N/B⌉, initialized with ⌈N/B⌉ items containing dummy data of size B. Let a denote the address of one of these items.

• Update: S queries the wORAM instance on item a with op = read.

• Search: on input L Search = x, S queries the wORAM instance x times on item a with op = read.

B.2. A GENERAL TRANSFORMATION

We claim that the resulting transcript is indistinguishable from the real transcript. Again, this follows immediately from the security of Weighted(PathOram), since the guarantees of a wORAM scheme is that any two sequence of accesses of the same length are indistinguishable, and the simulator makes the same number of accesses as the client in the real game. Moreover, Theorem 4.4.1 implies that Weighted(PathOram) is a correct wORAM scheme. As with ZeroSSE, that last point assumes that N/B = Ω(λ).

B.2 A General Transformation

In this section we present a way to transform any standard ORAM into a variable ORAM, at the cost of some blowup in the overhead. We have m objects, of individual size w i ∈ [0, B] for i ∈ [k] such that the sum of the sizes is N . The idea is:

• We create a standard ORAM structure for N objects, each of the same size higher than B (we discuss the size we need later). Let us call these N objects in the standard ORAM super objects.

• We want to store our m objects of varying sizes inside of the super objects. To do so, we map every object i ∈ [m] to a super object

• When we wish to access the object i, we make a standard ORAM access to the super object H(i), and read the object from the super object.

This technique yields the same computational, storage and bandwidth metrics as the ORAM we are modifying, with the caveat that the object size must be bigger.

The crucial part here is the function H. We must choose a way of hashing the m objects into the N super objects while having the following properties:

• A super object cannot overflow, except with negligible probability.

• The hash table should be modified as little as possible, so as to save bandwidth.

• The super objects should be as small as possible.

We present two hash algorithms based on the balls-in-bins problem that can be used to achieve this type of weighted ORAM.

B.2.1 One-Choice Process: O(log N ) blowup

We let each object be associated with a super object uniformly at random. In other words, H : [m] → [N ] is a random function. At each access, to get object i we call the access algorithm of the ORAM on super object H(i), modify object i in it, re-encrypt the super-object with fresh randomness, and write back the super object. It suffices to have each super object be of size B • log N .

Proof. Let m balls, each of weight w i ∈ [0, 1] such that m i=1 w i = N , be stored in N bins, which we associate uniformly at random. Let us call S the bin with the highest load. Let us call w the current weight distribution of the balls, and u be the weight distribution when we have only N balls of size 1, that is:

).

APPENDIX B. ADDITIONAL PROOFS FOR WEIGHTED ORAM

From the majorization argument in [START_REF] Berenbrink | On weighted balls-into-bins games[END_REF], we know that for any w, E( i∈S w i ) ≤ E( i∈S u i ). Since the max function is convex and the expectancy is linear, we have E(max(0, ( i∈S w i ) -log N )) ≤ E(max(0, ( i∈S u i ) -log N )). From now on, we will let the random variable X(v) denote max(0, ( i∈S u i ) -log(N )).

We have P(X(w) > 0) ≤ E(X(w)). The event X(w) > 0 is exactly the event of having at least one overflow in a given bin, so to prove that it happens with negligeable probability, it suffices to prove that E(X(u)) is negligeable. We have:

B.2.2 Layered Two-Choice Process: O(log log N ) blowup

The Layered 2-choice method of hashing m balls into N bins was introduced in [MR22, Section 4]. The idea is to split the m objects into "layers" according to their sizes. Then we can store them in the super objects by running standard (unweighted) 2-choice ballsin-bins allocation separately for each layer. Such an allocation is achievable with overhead O(log log N ).

However this algorithm does not support offline modification of the bins. This means that after an access for object i, we must update the ORAM by selecting 2 new super objects uniformly at random and write i in one of those super objects. The first consequence is that we double the bandwidth. Another problem is that the hash table has to be modified. To prevent client side spatial blowup, we must store the hash table (effectively a position map) on the server. This may be realized using a second ORAM (which need not use the same ORAM protocol).

Overall, while this approach is generic, it is significantly less efficient in practice than our main construction, which incurs almost no overhead relative to standard Tree ORAM.

B.3 A Flaw in DivORAM

DivORAM was introduced in [LHL + 18]. The DivORAM construction is (essentially) a weighted ORAM following a Tree ORAM structure: blocks are stored in buckets, and each bucket is located at the node of a binary tree. The blocks are decomposed into so-called splinters, which are stored in the buckets. A bucket at level i ∈ [log N ] can store up to 2 i splinters.

Stash analysis is given in [LHL + 18, Section 5.3]. Whenever a splinter cannot be stored in a tree bucket, it ends up in the stash. The worst case is when an entire block, composed

ABSTRACT

In this thesis, we study different methods of computing on hidden information. We present new constructions of protocols, which either improve on their state-of-the-art complexities or enable them to do more. We also analyse the security of other protocols and give attacks on them. The first subject we consider is that of Private Simultaneous Messages, where a group of individuals wish to have an external entity learn the output of a computation on their private data. Using a new framework, we show new constructions with a smaller communication cost than existing ones. We then study Oblivious RAM protocols, that hide the access pattern that a client makes when accessing private data stored on an untrusted server. We give the first constructions that allow the client to store data items of arbitrarily different sizes. We also show how using these constructions yield new protocols for Searchable Encryption. We finish by studying white-box cryptography, where the goal is to give an untrusted device unrestricted access to an encrytpion algorithm, while preventing the secret key from leaking. We present a cryptanalysis of Ranea et al's construction from CRYPTO 2022, where they give white-box ciphers from SPN and ARX based symmetric cryptosystems. We show that this scheme is insecure by providing a structural key-recovery attack. KEYWORDS PSM, MPC, White-Box, ORAM, SSE, Cryptanalysis