# Computing with private information: Techniques from Cryptology

Léonard Assouline

► To cite this version:

Léonard Assouline. Computing with private information: Techniques from Cryptology. Cryptography and Security [cs.CR]. PSL University; Ecole normale supérieure, 2023. English. NNT: tel-04324824

HAL Id: tel-04324824

https://inria.hal.science/tel-04324824

Submitted on 5 Dec 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Computing with private information:
Techniques from Cryptology

Soutenue par

Léonard Assouline

Le 1er Décembre 2023

École doctorale n°386

Sciences Mathématiques de
Paris Centre

Spécialité

Informatique

Composition du jury :

Matthieu Rivain
CryptoExperts

Rapporteur

Damien Vergnaud
Sorbonne Université

Rapporteur

Cécile Delerablée
Leanear

Examinatrice

Louis Goubin
Université Versailles Saint-Quentin-
en-Yvelines
Pierre-Alain Fouque
Université Rennes 1

Examineur

Examineur

David Naccache
ENS

Examineur

Michel Abdalla
ENS

Directeur de thèse

Brice Minaud
ENS

Directeur de thèse

<figure><img src="image_2.png" /></figure>
<figure><img src="image_3.png" /></figure>
<figure><img src="image_4.png" /></figure>

# Résumé

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é.
<figure><img src="image_5.png" /></figure>

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.
Remerciements

Je souhaite commencer en remerciant mes directeurs de thèse : merci à Brice pour ses conseils, son savoir et sa gentillesse. Je remercie également Michel pour son guidage, son expérience et pour avoir mis cette thèse sur les rails. Un grand merci à Damien et Matthieu pour avoir accepté d'être les rapporteurs de ce manuscrit, et pour leurs commentaires.

L'équipe Cascade du DI de l'ENS est le laboratoire révé pour faire une thèse, je tiens
à remercier tous ses membres, en commençant par Lise-Marie, Valérie, Linda, Fanny,
Mohamed, Ludovic et Jacques. Merci à Céline, Phong et David pour les discussions.
Merci à Michael pour son avoir été un bro, à Lénaïck pour son enthousiasme, thank you
Huy for the ping-pong games. Je remmercie Antoine pour les ragots industriels, Henry
pour les démonstrations, Guirec pour chaque débat, merci Baptiste, Nicolas, merci à Ky
pour bzzzz. Merci Hugo pour les rigolades, Paola pour son esprit, thank you Robert for
your didactism, thank you Jianwei, merci Florette, Wissam, Yann.

Merci à Pierre, compère cryptologue depuis la L3, à mes camarades lyonnais, Ulysse et ceux du gslq, Ouassim, Gauthier, Morgane, Martin, Baptiste, Fënril, Solal, Côme, Thomas, Pierre et Jacquelin. Merci à Arnault pour nos reflexions sur le doctorat et le milieu académique, Antoine, Valentin, Emma, Baptiste, Pascal, Madeleine, Billy, Eve. Je remercie également Elie, Vladimir, Araxe, Louise, Roméo, Baptiste.

Merci à Igor, Françoise et Louise. Un grand merci également à ma grand-mère pour les histoires de Paris à travers les époques. Merci à mes parents, qui m'ont toujours aiguillé vers la bonne direction, et Gabriel de remarquer les choses. Merci à Ginza de me tenir compagnie pendant que je termine de rédiger ce manuscrit.

Enfin, merci Jeanne de me faire avancer depuis bien avant le début de cette thèse.
# Contents

Résumé i

Abstract iii

Remerciements v

1 Introduction en Français 1

1.1 Cryptographie symétrique et asymétrique 2

1.2 Laisser le calcul à un tiers 2

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

1.3.1 Calculer avec d'autres 3

1.3.2 Stocker ses données ailleurs 4

1.3.3 Laisser quelqu'un d'autre chiffrer 5

1.4 Résumé des résultats 6

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

1.4.2 Protocoles d'Oblivious RAM pour des objets de tailles variables 8

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

2 Introduction 11

2.1 Symmetric and asymmetric cryptography 12

2.2 Having someone else do the computing 12

2.3 Flavors of delegating computation 13

2.3.1 Computing with others 13

2.3.2 Storing data elsewhere 14

2.3.3 Letting someone else encrypt 15

2.4 Summary of results 15

2.4.1 New upper bounds on the complexity of PSM protocols 15

2.4.2 Oblivious RAM protocols for objects of variable sizes 17

2.4.3 Structural cryptanalysis of white-box schemes of ARX ciphers 18

3 New techniques for Multi-party PSM 21

3.1 Introduction 21

3.1.1 Our Contributions 22

3.1.2 Proof Overview 23

3.1.3 Related Works 26

3.2 Preliminaries 26

3.2.1 Tensor 27

3.2.2 Private Simultaneous Messages 27
<table>
  <tbody>
    <tr>
      <td>3.2.3 Randomized Encoding</td>
      <td>28</td>
    </tr>
    <tr>
      <td>3.3 New Multi-party PSM Protocols</td>
      <td>28</td>
    </tr>
    <tr>
      <td>3.3.1 A Framework for Multi-party PSM</td>
      <td>29</td>
    </tr>
    <tr>
      <td>3.3.2 The Induced PSM Protocol</td>
      <td>32</td>
    </tr>
    <tr>
      <td>3.3.3 When k is Small</td>
      <td>33</td>
    </tr>
    <tr>
      <td>3.3.4 When k + 1 is a Prime Power</td>
      <td>34</td>
    </tr>
    <tr>
      <td>3.4 Unbalanced 2-party PSM Protocols</td>
      <td>36</td>
    </tr>
    <tr>
      <td>3.4.1 A Framework for 2-party PSM</td>
      <td>36</td>
    </tr>
    <tr>
      <td>3.4.2 The Induced PSM Protocol</td>
      <td>40</td>
    </tr>
    <tr>
      <td>3.4.3 When η has a Small Denominator</td>
      <td>41</td>
    </tr>
    <tr>
      <td>3.5 Open Problems</td>
      <td>42</td>
    </tr>
    <tr>
      <td><b>4 Weighted ORAM with Applications to SSE</b></td>
      <td><b>45</b></td>
    </tr>
    <tr>
      <td>4.1 Introduction</td>
      <td>45</td>
    </tr>
    <tr>
      <td>4.1.1 Our Contributions</td>
      <td>48</td>
    </tr>
    <tr>
      <td>4.1.2 Related work</td>
      <td>49</td>
    </tr>
    <tr>
      <td>4.1.3 Organization of the chapter</td>
      <td>50</td>
    </tr>
    <tr>
      <td>4.2 General Preliminaries</td>
      <td>50</td>
    </tr>
    <tr>
      <td>4.2.1 Majorization and Schur Convexity</td>
      <td>50</td>
    </tr>
    <tr>
      <td>4.3 ORAM Preliminaries</td>
      <td>51</td>
    </tr>
    <tr>
      <td>4.3.1 Weighted Oblivious RAM</td>
      <td>51</td>
    </tr>
    <tr>
      <td>4.3.2 Tree ORAM</td>
      <td>52</td>
    </tr>
    <tr>
      <td>4.3.3 The ∞-ORAM Model</td>
      <td>54</td>
    </tr>
    <tr>
      <td>4.4 Generic Construction of wORAM from Tree ORAM</td>
      <td>55</td>
    </tr>
    <tr>
      <td>4.4.1 The Weighted Transform</td>
      <td>55</td>
    </tr>
    <tr>
      <td>4.4.2 Suitable Tree ORAM Schemes</td>
      <td>56</td>
    </tr>
    <tr>
      <td>4.4.3 Main Result</td>
      <td>57</td>
    </tr>
    <tr>
      <td>4.4.4 Experimental Results</td>
      <td>59</td>
    </tr>
    <tr>
      <td>4.5 Application to Existing Tree ORAMs</td>
      <td>60</td>
    </tr>
    <tr>
      <td>4.5.1 Weighted Simple ORAM [CP13]</td>
      <td>60</td>
    </tr>
    <tr>
      <td>4.5.2 Weighted Path ORAM [SvS<sup>+</sup>13b]</td>
      <td>62</td>
    </tr>
    <tr>
      <td>4.5.3 Weighted Oblivious Parallel RAM [BCP16]</td>
      <td>65</td>
    </tr>
    <tr>
      <td>4.5.4 Weighted Circuit ORAM [WCS14]</td>
      <td>65</td>
    </tr>
    <tr>
      <td>4.6 Searchable Encryption from Weighted ORAM</td>
      <td>66</td>
    </tr>
    <tr>
      <td>4.6.1 Preliminaries</td>
      <td>67</td>
    </tr>
    <tr>
      <td>4.6.2 ZeroSSE</td>
      <td>68</td>
    </tr>
    <tr>
      <td>4.6.3 BlockSSE</td>
      <td>69</td>
    </tr>
    <tr>
      <td><b>5 Structural Cryptanalysis of Implicit White-Box Implementations</b></td>
      <td><b>73</b></td>
    </tr>
    <tr>
      <td>5.1 Introduction</td>
      <td>73</td>
    </tr>
    <tr>
      <td>5.1.1 Our Contributions</td>
      <td>74</td>
    </tr>
    <tr>
      <td>5.1.2 Related Work</td>
      <td>75</td>
    </tr>
    <tr>
      <td>5.2 Technical Overview</td>
      <td>76</td>
    </tr>
    <tr>
      <td>5.2.1 Structure of the chapter</td>
      <td>78</td>
    </tr>
    <tr>
      <td>5.3 Preliminaries</td>
      <td>78</td>
    </tr>
    <tr>
      <td>5.3.1 Notation</td>
      <td>78</td>
    </tr>
    <tr>
      <td>5.3.2 Round encodings</td>
      <td>79</td>
    </tr>
  </tbody>
</table>
<table>
  <tbody>
    <tr>
      <td>5.3.3</td>
      <td>Structural Cryptanalysis</td>
      <td>80</td>
    </tr>
    <tr>
      <td>5.3.4</td>
      <td>Cube attacks</td>
      <td>81</td>
    </tr>
    <tr>
      <td>5.3.5</td>
      <td>Linearization</td>
      <td>81</td>
    </tr>
    <tr>
      <td>5.4</td>
      <td>Structural cryptanalysis of ISA</td>
      <td>82</td>
    </tr>
    <tr>
      <td>5.4.1</td>
      <td>Problem statement</td>
      <td>82</td>
    </tr>
    <tr>
      <td>5.4.2</td>
      <td>Equivalent keys</td>
      <td>83</td>
    </tr>
    <tr>
      <td>5.4.3</td>
      <td>Peeling off the A layer: from ISA to IS</td>
      <td>83</td>
    </tr>
    <tr>
      <td>5.4.4</td>
      <td>Recovering the remaining layers: structural cryptanalysis of IS</td>
      <td>84</td>
    </tr>
    <tr>
      <td>5.4.5</td>
      <td>Attack complexity</td>
      <td>84</td>
    </tr>
    <tr>
      <td>5.4.6</td>
      <td>Application to white-box key recovery</td>
      <td>85</td>
    </tr>
    <tr>
      <td>5.5</td>
      <td>Structural cryptanalysis of IMA</td>
      <td>86</td>
    </tr>
    <tr>
      <td>5.5.1</td>
      <td>Problem statement</td>
      <td>87</td>
    </tr>
    <tr>
      <td>5.5.2</td>
      <td>Equivalent keys</td>
      <td>87</td>
    </tr>
    <tr>
      <td>5.5.3</td>
      <td>Peeling off the I layer: from IMA to MA</td>
      <td>87</td>
    </tr>
    <tr>
      <td>5.5.4</td>
      <td>Attack complexity</td>
      <td>91</td>
    </tr>
    <tr>
      <td>5.5.5</td>
      <td>Application to white-box key recovery</td>
      <td>91</td>
    </tr>
    <tr>
      <td>5.6</td>
      <td>Practical validation</td>
      <td>92</td>
    </tr>
    <tr>
      <td>5.7</td>
      <td>Polynomial factorization</td>
      <td>93</td>
    </tr>
    <tr>
      <td>5.7.1</td>
      <td>Notation</td>
      <td>93</td>
    </tr>
    <tr>
      <td>5.7.2</td>
      <td>Algorithms to recover the polynomials</td>
      <td>93</td>
    </tr>
    <tr>
      <td>5.8</td>
      <td>Conclusion</td>
      <td>95</td>
    </tr>
    <tr>
      <td><b>6</b></td>
      <td><b>Conclusion</b></td>
      <td><b>97</b></td>
    </tr>
    <tr>
      <td><b>A</b></td>
      <td><b>Supplementary material on PSM</b></td>
      <td><b>99</b></td>
    </tr>
    <tr>
      <td>A.1</td>
      <td>Proof of Equation (3.9) and (3.10)</td>
      <td>99</td>
    </tr>
    <tr>
      <td>A.2</td>
      <td>Auxiliary PSM Protocols for &lt;x<sub>1</sub> &otimes; ... &otimes; x<sub>k</sub>, Y&gt; + s</td>
      <td>100</td>
    </tr>
    <tr>
      <td>A.2.1</td>
      <td>The Multi-party Variant</td>
      <td>100</td>
    </tr>
    <tr>
      <td>A.2.2</td>
      <td>The 2-party Variant</td>
      <td>101</td>
    </tr>
    <tr>
      <td><b>B</b></td>
      <td><b>Additional proofs for weighted ORAM</b></td>
      <td><b>103</b></td>
    </tr>
    <tr>
      <td>B.1</td>
      <td>SSE Proofs</td>
      <td>103</td>
    </tr>
    <tr>
      <td>B.1.1</td>
      <td>Proof of ZeroSSE</td>
      <td>103</td>
    </tr>
    <tr>
      <td>B.1.2</td>
      <td>Proof of BlockSSE</td>
      <td>103</td>
    </tr>
    <tr>
      <td>B.2</td>
      <td>A General Transformation</td>
      <td>104</td>
    </tr>
    <tr>
      <td>B.2.1</td>
      <td>One-Choice Process: O(log N) blowup</td>
      <td>104</td>
    </tr>
    <tr>
      <td>B.2.2</td>
      <td>Layered Two-Choice Process: O(log log N) blowup</td>
      <td>105</td>
    </tr>
    <tr>
      <td>B.3</td>
      <td>A Flaw in DivORAM</td>
      <td>105</td>
    </tr>
    <tr>
      <td>B.4</td>
      <td>Weighted Hierarchical ORAM</td>
      <td>106</td>
    </tr>
  </tbody>
</table>
# 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é.
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 ?"

## 1.1 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 *PK*, 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.

## 1.2 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 pour ç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.
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, résultant 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 de-meure une bonne solution prête à l'emploi. Alice pourraît aussi obfusquer un programme avec de l'obfuscation indistinguishable, 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 Messages*<fnref n="1" /> (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.

## 1.3 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.

### 1.3.1 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

<footnote n="1">¹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.</footnote>
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 [Yao82]. 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, \dots, P_k$ détiennent chacune une entrée secrète $x_1, \dots, 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, \dots, 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 [Lin20]. 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.

1.3.2 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
ç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 [Con22].

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.

### 1.3.3 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élécharger à 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éléchargement 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 pourrait 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 aujourd'hui [CFV19].
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.

1.4 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.

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

Dans un protocole PSM, il y a *k* parties *P*₁, ..., *P*ₖ et un arbitre *Ref*. Soit *N* ∈ N. Pour tout *i* ∈ [*k*], chaque partie *P*ᵢ détient une entrée secrète *x*ᵢ ∈ [*N*], et chacune envoie un message *m*ᵢ à l'arbitre, de façon à ce que ce dernier puisse faire un calcul sur les messages qui donne *f*(*x*₁, ..., *x*ₖ) 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
[FKN94] 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 [IK97]. Depuis,
de nouvelles bornes inférieures et supérieures ont été découvertes : dans le cas à deux
parties, [FKN94] présente un protocole avec une complexité de communication en *O(N)*,
puis [BIKK14] montre qu'une complexité en *O(√N)* est possible. Dans [BKN18], 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 [FKN94]. 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, [FKN94] montre une limite de 3k − O(1) bits, qui a
été étendue en une borne inférieure de 3k − O(log(k)) par [AHMS20]. Pour k = ω(log(n)),
cette borne inférieure de Ω(n) est améliorée en une borne de Ω(k²n/ log(kn)) par [BR22].

À l'issue d'une collaboration avec Tianren Liu [AL21], nous montrons de nouvelles
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 \le 20$ et toutes les puissances premières) avec un coût de $O(\text{poly}(k) \cdot N^{\frac{k-1}{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 $\hat{f} : \mathcal{X} \times \mathcal{R} \to \hat{\mathcal{Y}}$ d'une fonction $f : \{\mathcal{X} \to \mathcal{Y} \mid x \mapsto f(x)\}$ est tel que pour $r \in \mathcal{R}$ une valeur aléatoire, $\hat{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, \dots, x_k)$, les messages $m_1, \dots, m_k$ reçus par l'arbitre constituent un codage aléatoire (où $r$ est l'aléa partagé) de $f(x_1, \dots, x_k)$.

L'idée derrière ce nouveau cadre vient de [BIKK14] : chaque entrée $x_i$ est représentée par son vecteur identité $z_i$, où la $i$-ème coordonnée de $z_i$ est 1 et les autres sont 0. Ensuite, nous scindons ce vecteur en deux : $z_i = y_{2i} \otimes 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 : $\mathbf{a}_1, \mathbf{a}_2, \mathbf{b}_1, \mathbf{b}_2 \stackrel{\$}{\leftarrow} \{0, 1\}^{\sqrt{N}}$.

* L'entrée d'Alice $\mathbf{x}$ est telle que $\mathbf{x} = \mathbf{x}_1 \otimes \mathbf{x}_2$, avec $\mathbf{x}_1, \mathbf{x}_2 \in \{0, 1\}^{\sqrt{N}}$.

* De façon similaire, l'entrée de Bob est $\mathbf{y} = \mathbf{y}_1 \otimes \mathbf{y}_2$.

Maintenant, avant de voir comment le protocole fonctionne, Alice et Bob vont construire individuellement certains polynômes privés :

* Alice calcule $\mathbf{q}_1, \mathbf{q}_2$ de taille $O(\sqrt{N})$ tels que
  $$ \langle \mathbf{q}_1, \mathbf{z}_1 \rangle = \langle \mathbf{p}, (\mathbf{x}_1 + \mathbf{a}_1) \otimes (\mathbf{x}_2 + \mathbf{a}_2) \otimes (\mathbf{z}_1 \otimes \mathbf{b}_2 + \mathbf{b}_1 \otimes \mathbf{b}_2) \rangle \text{ et} $$
  $$ \langle \mathbf{q}_2, \mathbf{z}_2 \rangle = \langle \mathbf{p}, (\mathbf{x}_1 + \mathbf{a}_1) \otimes (\mathbf{x}_2 + \mathbf{a}_2) \otimes \mathbf{b}_1 \otimes \mathbf{z}_2 \rangle. $$

* Bob calcule $\mathbf{h}_1, \mathbf{h}_2$ de taille $O(\sqrt{N})$ tels que
  $$ \langle \mathbf{h}_1, \mathbf{z}_1 \rangle = \langle \mathbf{p}, (\mathbf{z}_1 \otimes \mathbf{a}_2 + \mathbf{a}_1 \otimes \mathbf{a}_2) \otimes \mathbf{y}_1 \otimes \mathbf{y}_2 \rangle \text{ et} $$
  $$ \langle \mathbf{h}_2, \mathbf{z}_2 \rangle = \langle \mathbf{p}, \mathbf{a}_1 \otimes \mathbf{z}_2 \otimes \mathbf{y}_1 \otimes \mathbf{y}_2 \rangle. $$

Le protocole fonctionne de la façon suivante :

* Alice envoie $(\mathbf{x}_1 + \mathbf{a}_1, \mathbf{x}_2 + \mathbf{a}_2)$ à Ref.

* Bob envoie $(\mathbf{y}_1 + \mathbf{b}_1, \mathbf{y}_2 + \mathbf{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 apprendre $\gamma = \langle \mathbf{q}_1, \mathbf{y}_1 \rangle + \langle \mathbf{q}_2, \mathbf{y}_2 \rangle + \langle \mathbf{h}_1, \mathbf{x}_1 \rangle + \langle \mathbf{h}_2, \mathbf{x}_2 \rangle$.

* Ref calcule $\langle \mathbf{F}, (\mathbf{x}_1 + \mathbf{a}_1) \otimes (\mathbf{x}_2 + \mathbf{a}_2) \otimes (\mathbf{y}_1 + \mathbf{b}_1) \otimes (\mathbf{y}_2 + \mathbf{b}_2) \rangle - \gamma$.

Le coût de la communication de ce protocole est de l'ordre de $O(\sqrt{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^\eta)$ bits et Bob envoie $O(N^{1-\eta})$ bits, avec $\eta \in [0, 1]$.
1.4.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 [GO96]. 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(\sqrt{N} \cdot B)$). Dans le square-root ORAM, le serveur détient un tableau de taille $N + 2 \cdot \sqrt{N}$, composé (initialement) des $N$ éléments que l'ORAM doit stocker, suivis de $\sqrt{N}$ objets factices (par exemple, des chiffrements de mots aléatoires) et $\sqrt{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 :

En premier lieu, le client permute de manière sécurisée (oblivious permutation dans la langue de Turing) les premiers $N + \sqrt{N}$ objets et garde une représentation de la permutation secrète $\pi$. Le client effectue ensuite plusieurs accès. Le $j$-ème accès à un objet (par exemple, le $i$-ème objet) consiste en :

• La lecture de tout le refuge de taille $\sqrt{N}$ pour trouver l'objet.

• Si trouvé : le client accède à l'objet factice suivant. Dans les premières $N + \sqrt{N}$ cellules, il est à l'index $\pi(N + j)$.

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

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

Après au plus $\sqrt{N}$ accès, le client met à jour les valeurs des objets réels dans les premières $N + \sqrt{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 $\omega(\log(N))$, s'appelle "Simple ORAM" [CP13]. Ici, le stockage du serveur est structuré sous forme d'arbre binaire complet de profondeur $L = \lceil \log(N) \rceil$, où chaque nœud, 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*
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 [AM23] 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 $\leq B$ bits, supposons que le serveur héberge un poids total d'au plus $N \cdot 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 \cdot B$ bits. Nous pouvons placer un objet dans un panier tant que la limite de $Z \cdot B$ n'est pas atteinte. Le panier est considéré comme plein si le poids total dépasse $Z \cdot B$ (il sera toujours en dessous de $(Z + 1) \cdot 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.

### 1.4.3 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 [Koc96]. 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$ [GMO01]. 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 [CEJv03], on parle de cadre *CEJO*. Ici, un chiffrement est décomposé en une série de tables de correspondance composées. Elles sont chacune
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 \circ \dots \circ E_n$. Le système en boîte blanche est composé d'une suite de couches $(E'_i)_{i \in [n]} = (O_i \circ E_i \circ I_i)_{i \in [n]}$ où $O_i = I_{i+1}^{-1}$ pour tout $i \in [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 \circ \dots \circ E'_n = I_1 \circ Enc_K \circ O_n$. Plusieurs implémentations de cette méthode ont été cryptanalysé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. [RVP22], 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 $\forall x, y, P(x, y) = 0 \iff F(x) = y$. $P$ doit être telle que pour tous les $x$, la fonction $y \mapsto 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 [MDFK18] 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 = (\mathbf{x}||\mathbf{y}) \in \{0,1\}^n$, où $\mathbf{x}, \mathbf{y} \in \{0,1\}^{n/2}$, et donne en sortie $(\mathbf{x}||\mathbf{x} \boxplus \mathbf{y})$ où $\boxplus$ est l'addition modulaire dans $\mathbb{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 $\mathbf{a}$ et obtient en sortie $\mathbf{b} = A \circ M \circ I(\mathbf{a})$. Notons $t = (\mathbf{x}||\mathbf{y})$ par $N(\mathbf{a})$ et $\mathbf{z} = \mathbf{x} \boxplus \mathbf{y}$. On remarque que, pour tout $i \in [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.
# Introduction

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 responsibility 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
football accross the field, without anyone tracing that back to me?”

### 2.1 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 $PK$, 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.

### 2.2 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
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 pro-
duce, 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 com-
putes 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 *Obliv-
ious 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.

## 2.3 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.

2.3.1 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 [Yao82]. 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, Swe00]. 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, \dots, P_k$ each hold a secret input $x_1, \dots, x_k$,
and they wish to compute the output of some (public) function $f$, such that each party
learns $f(x_1, \dots, 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 [Lin20]. In this thesis, we
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.

### 2.3.2 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 [Con22].

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.
### 2.3.3 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 download 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 aforementioned 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 [CFV19].

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 reverse-engineer 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.

## 2.4 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.

### 2.4.1 New upper bounds on the complexity of PSM protocols

In a PSM protocol, there are $k$ parties $P_1, \dots, P_k$ and a referee *Ref*. Let $N \in \mathbb{N}$. For all $i \in [k]$, each party $P_i$ holds a secret input $x_i \in [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, \dots, 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.
The PSM model was presented first in 1994 by Feige, Kilian and Naor [FKN94] 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 [IK97]. Since then, new upper and lower bounds have been found: in the 2-party case, [FKN94] showed a protocol with communication complexity $O(N)$, then it was shown that one can achieve a communication complexity of $O(\sqrt{N})$ [BIKK14]. In [BKN18], a cost of $O(\text{poly}(k) \cdot N^{k/2})$ was shown for all $k \ge 2$, improving on the $O(\text{poly}(k) \cdot N^{k-1})$ cost from [FKN94], along with better results for $k \le 5$. This work also proposed protocols with unbalanced complexity: some parties send more information than others.

Regarding lower bounds, [FKN94] showed a limit of $3k-O(1)$ bits, which was expanded into a $3k-O(\log(k))$ lower bound by [AHMS20]. For $k = \omega(\log(n))$, this $\Omega(n)$ lower bound is improved into a $\Omega(k^2n/\log(kn))$ one by [BR22].

In a work done in collaboration with Tianren Liu [AL21], 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 \le 20$ and all prime powers) with a cost of $O(\text{poly}(k) \cdot N^{\frac{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 $\hat{f}: \mathcal{X} \times \mathcal{R} \to \hat{\mathcal{Y}}$ of a function $f$: $\begin{cases} \mathcal{X} \to \mathcal{Y} \\ x \mapsto f(x) \end{cases}$ is such that for $r \in \mathcal{R}$ some random value, $\hat{f}(x, r)$ has enough information to recover $f(x)$ and nothing else about $x$. PSM are a special case of randomized encodings: seeing $x$ as $x = (x_1, \dots, x_k)$, the messages $\{m_1, \dots, m_k\}$ received by the referee are a randomized encoding (with $r$ being the shared randomness) of $f(x_1, \dots, x_k)$.

The idea behind this new framework comes from [BIKK14]: we represent each input $x_i$ with its *one-hot* encoding: $x_i$ is seen as an identity vector $\mathbf{z}_i$, where the $x_i$th coordinate of $\mathbf{z}_i$ is 1 and the others are 0. We then *split* this vector in two: $\mathbf{z}_i = \mathbf{y}_{2i} \otimes \mathbf{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 $\mathbf{p} \in \{0, 1\}^N$.

* Alice and Bob will share the following randomness: $\mathbf{a}_1, \mathbf{a}_2, \mathbf{b}_1, \mathbf{b}_2 \stackrel{\$}{\leftarrow} \{0, 1\}^{\sqrt{N}}$.

* Alice's input $\mathbf{x}$ is s.t. $\mathbf{x} = \mathbf{x}_1 \otimes \mathbf{x}_2$, with $\mathbf{x}_1, \mathbf{x}_2 \in \{0, 1\}^{\sqrt{N}}$.

* In the same way, Bob's input is $\mathbf{y} = \mathbf{y}_1 \otimes \mathbf{y}_2$.

Now, before we see how the protocol works, Alice and Bob will construct privately some polynomials:

* Alice computes $\mathbf{q}_1, \mathbf{q}_2$ of size $O(\sqrt{N})$ such that
  $$ \langle \mathbf{q}_1, \mathbf{z}_1 \rangle = \langle \mathbf{p}, (\mathbf{x}_1 + \mathbf{a}_1) \otimes (\mathbf{x}_2 + \mathbf{a}_2) \otimes (\mathbf{z}_1 \otimes \mathbf{b}_2 + \mathbf{b}_1 \otimes \mathbf{b}_2) \rangle \text{ and} $$
  $$ \langle \mathbf{q}_2, \mathbf{z}_2 \rangle = \langle \mathbf{p}, (\mathbf{x}_1 + \mathbf{a}_1) \otimes (\mathbf{x}_2 + \mathbf{a}_2) \otimes \mathbf{b}_1 \otimes \mathbf{z}_2 \rangle. $$

* Bob computes $\mathbf{h}_1, \mathbf{h}_2$ of size $O(\sqrt{N})$ such that
$$ \langle \mathbf{h}_1, \mathbf{z}_1 \rangle = \langle \mathbf{p}, (\mathbf{z}_1 \otimes \mathbf{a}_2 + \mathbf{a}_1 \otimes \mathbf{a}_2) \otimes \mathbf{y}_1 \otimes \mathbf{y}_2 \rangle \text{ and} $$

$$ \langle \mathbf{h}_2, \mathbf{z}_2 \rangle = \langle \mathbf{p}, \mathbf{a}_1 \otimes \mathbf{z}_2 \otimes \mathbf{y}_1 \otimes \mathbf{y}_2 \rangle. $$

The protocol works as follows:

* Alice sends $(\mathbf{x}_1 + \mathbf{a}_1, \mathbf{x}_2 + \mathbf{a}_2)$ to Ref.

* Bob sends $(\mathbf{y}_1 + \mathbf{b}_1, \mathbf{y}_2 + \mathbf{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 $\gamma = \langle \mathbf{q}_1, \mathbf{y}_1 \rangle + \langle \mathbf{q}_2, \mathbf{y}_2 \rangle + \langle \mathbf{h}_1, \mathbf{x}_1 \rangle + \langle \mathbf{h}_2, \mathbf{x}_2 \rangle$.

* Ref computes $\langle \mathbf{F}, (\mathbf{x}_1 + \mathbf{a}_1) \otimes (\mathbf{x}_2 + \mathbf{a}_2) \otimes (\mathbf{y}_1 + \mathbf{b}_1) \otimes (\mathbf{y}_2 + \mathbf{b}_2) \rangle - \gamma$.

The communication cost of that protocol is $O(\sqrt{N})$ for both Alice and Bob. In Chapter 3.4, we present PSM protocols with *unbalanced* communication: Alice sends $O(N^\eta)$ bits and Bob sends $O(N^{1-\eta})$ bits, with $\eta \in [0, 1]$.

### 2.4.2 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 [GO96]. They present the first non-trivial ORAM which is now called the square-root ORAM (named after its bandwidth cost of $O(\sqrt{N} \cdot B)$). In the square-root ORAM, the server holds an array of size $N + 2 \cdot \sqrt{N}$, composed (Initially) of the $N$ items the ORAM must store, followed by $\sqrt{N}$ dummy items (e.g. encryptions of random words) and $\sqrt{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+\sqrt{N}$ items and keeps a representation of the secret permutation $\pi$. The client then makes several accesses. The $j$th access to an object (e.g. the $i$th object) consists of:

* Reading the entire shelter of size $\sqrt{N}$ to find the object.

* If found: the client accesses the next dummy object. In the first $N + \sqrt{N}$ memory cells, it is at index $\pi(N + j)$.

* If not found: the client accesses the object at its true location at index $\pi(i)$.

* The client eventually updates the value of the $i$th item, reencrypts it and stores it in the shelter.

After at most $\sqrt{N}$ accesses, the client updates the values of the real objects in the first $N + \sqrt{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
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 $\omega(\log(N))$ client storage is aptly named “Simple ORAM” [CP13]. Here, the server storage is structured as a complete binary tree of depth $L = \lceil \log(N) \rceil$, 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 $i$th 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 [AM23] 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 $\le B$ bits, we will assume that the server will host a total weight of at most $N \cdot 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 \cdot B$ bits. We can put an object in a bucket as long as that bound of $Z \cdot B$ is not reached. The bucket is considered full if the total weight exceeds $Z \cdot B$ (it will always be less than $(Z+1) \cdot 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.

### 2.4.3 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 = \text{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 explanation 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 [Koc96]. A more elaborate attacker can study elec-
tromagnetic perturbations around the device performing the computing, or make measure
on the power lines to study the electrical consumption used to compute $\mathbf{Enc}_K$ [GMO01].
Here, the attacker is said to be given *side-channel* information. We also see this model
referred to as the *grey-box* model.

In the white-box model, the attacker has at its disposal an implementation of $\mathbf{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 $\mathbf{Enc}_K$ such that the adversary cannot learn any information on $K$.
The first white-box implementation of a cipher (AES) was introduced in [CEJv03], this is
referred 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 substitution-permutation network such as AES
is seen as a composition of non-linear layers: $\mathbf{Enc}_K = E_1 \circ \dots \circ E_n$. The white-box cipher
is made up of a sequence of layers $(E'_i)_{i \in [n]} = (O_i \circ E_i \circ I_i)_{i \in [n]}$ where $O_i = I_{i+1}^{-1}$ for all
$i \in [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 $\mathbf{Enc}'_K = E'_1 \circ \dots \circ E'_n =
I_1 \circ \mathbf{Enc}_K \circ 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 [RVP22], using *implicit implementations*. Here, the round function $F$ of a block cipher
is represented by a function $P$ such that $\forall x, y, P(x, y) = 0 \iff F(x) = y$. $P$ must
be such that for all $x$, the function $y \mapsto 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<sup>+</sup>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 [MDFK18] 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 $\mathbf{t} = (\mathbf{x}||\mathbf{y}) \in \{0,1\}^n$, where $\mathbf{x}, \mathbf{y} \in \{0,1\}^{n/2}$, and outputs $(\mathbf{x}||\mathbf{x} \oplus \mathbf{y})$ where $\oplus$ is the
modular addition in $\mathbb{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 $\mathbf{a}$ and gets an output $\mathbf{b} = A \circ M \circ I(\mathbf{a})$. Let us write $\mathbf{t} = (\mathbf{x}||\mathbf{y})$ as $N(\mathbf{a})$
and $\mathbf{z} = \mathbf{x} \oplus \mathbf{y}$. We can notice that, for all $i \in [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.
# New techniques for Multi-party PSM

## 3.1 Introduction

Private Simultaneous Messages (PSM) is a minimal model of secure multi-party computation. It was introduced by Feige, Kilian and Naor [FKN94], and was generalized to the multi-party setting by Ishai and Kushilevitz [IK97].

In a PSM protocol for evaluating a $k$-ary functionality $f : [N]^k \to \{0,1\}$, there are $k$ parties. They all share a common random string. For all $i \in [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, \dots, x_k)$, and should learn no other information about $x_1, \dots, x_k$.

<figure><img src="image_6.png" /><figcaption>Figure 3.1: Illustration of a multi-party PSM protocol</figcaption></figure>

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.

In the PSM model, there are relatively efficient PSM protocols for computing non-deterministic branching programs [FKN94] and modular branching programs [IK97]. 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)$ [AHMS20]. In $k$-party PSM where each party holds a 1-bit input, Ball et al. showed an $\Omega(k^2/\log k)$ lower bound [BHI+20]. This lower bound was then improved to be $\Omega(k^2n/\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$:
<table><caption>Table 3.1: The communication complexity of computing general $f : [N]^k \to \{0,1\}$ in multi-party PSM model</caption><thead><tr><th>Number of parties</th><th>[BIKK14]</th><th>[BKN18]</th><th>This work</th></tr></thead><tbody><tr><td>2</td><td>O(N<sup>1/2</sup>)</td><td>O(N<sup>1/2</sup>)</td><td>O(N<sup>1/2</sup>)</td></tr><tr><td>3</td><td></td><td>O(N)</td><td>O(N)</td></tr><tr><td>4</td><td></td><td>O(N<sup>5/3</sup>)</td><td>O(N<sup>3/2</sup>)</td></tr><tr><td>5</td><td></td><td>O(N<sup>7/3</sup>)</td><td>O(N<sup>2</sup>)</td></tr><tr><td>k &ge; 6</td><td></td><td>O(poly(k) &middot; N<sup>k/2</sup>)</td><td>2<sup>O(k)</sup> &middot; N<sup>k-1/2</sup><br>for infinitely many k<br>including all k &le; 20</td></tr></tbody></table>

<table><caption>Table 3.2: The unbalanced communication complexity of general $f : [N] \times [N] \to \{0,1\}$ in 2-party PSM model</caption><thead><tr><th></th><th>Communication complexity<br>of one party</th><th>Communication complexity<br>of the other party</th></tr></thead><tbody><tr><td>[FKN94]</td><td>O(log N)</td><td>N</td></tr><tr><td>[BIKK14]</td><td>O(N<sup>1/2</sup>)</td><td>O(N<sup>1/2</sup>)</td></tr><tr><td>This work</td><td>O(N<sup>η</sup>)</td><td>O(N<sup>1-η</sup>)</td></tr></tbody></table>

$[N]^k \to \{0,1\}$, a “naïve” $k$-party PSM requires $O(N^{k-1})$ communication (the 2-party version was presented in [FKN94]). The first novel upper bound is $O(\sqrt{N})$ for 2-party PSM [BIKK14], and it was recently generalized to an $O_k(N^{k/2})$ upper bound for $k$-party PSM [BKN18]. 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.

### 3.1.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 \to \{0,1\}$,

* For all $k \le 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})$.
**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] \times [N] \to \{0, 1\}$,

* For every rational $\eta \in (0, 1)$ whose denominator is no more than 20, our framework yields a 2-party PSM protocol, where one party sends $O(N^\eta)$ bits and the other sends $O(N^{1-\eta})$ bits.

* For every rational $\eta \in (0, 1)$, we conjecture that our framework will yield a 2-party PSM protocol, where one party sends $O_\eta(N^\eta)$ bits and the other sends $O_\eta(N^{1-\eta})$ bits.

To some extent, such a trade-off was known in the literature when $\eta = 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 [FKN94].

### 3.1.2 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 [BKN18]. 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 [BIKK14]. 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 \in [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 $\mathbb{F}$. Let the $i$-th party locally computes a unit vector $\mathbf{x}_i \in \mathbb{F}^N$. That is, all entries in $\mathbf{x}_i$ are zero except for $\mathbf{x}_i[x_i] = 1$. Let $\mathbf{F}$ be the truth table of $f$ represented as an $N \times N \times N$ array, we have $f(x_1, x_2, x_3) = \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{x}_3 \rangle$, where $\otimes$ denotes the tensor product and $\langle \cdot, \cdot \rangle$ denotes the inner product.

Therefore, it is sufficient to construct a 3-party PSM protocol, where the $i$-th party has input $\mathbf{x}_i \in \mathbb{F}^N$ (not necessarily being an unit vector) and the referee learns $\langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{x}_3 \rangle$ for some public $\mathbf{F} \in \mathbb{F}^{N \times N \times N}$.
We start by letting the i-th party sample random $\mathbf{r}_i \in \mathbb{F}^N$ from the common random string and send the one-time padded $\bar{\mathbf{x}}_i := \mathbf{x}_i + \mathbf{r}_i$ to the referee. Then the referee can compute $\langle \mathbf{F}, \bar{\mathbf{x}}_1 \otimes \bar{\mathbf{x}}_2 \otimes \bar{\mathbf{x}}_3 \rangle$. We call this term a “masked term”, because it is computed from the masked inputs $\bar{\mathbf{x}}_1, \bar{\mathbf{x}}_2, \bar{\mathbf{x}}_3$. This masked term can be decomposed as the sum of several “pure terms”

$$ \langle \mathbf{F}, \bar{\mathbf{x}}_1 \otimes \bar{\mathbf{x}}_2 \otimes \bar{\mathbf{x}}_3 \rangle = \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{x}_3 \rangle + \\ \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{r}_3 \rangle + \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{r}_2 \otimes \mathbf{x}_3 \rangle + \langle \mathbf{F}, \mathbf{r}_1 \otimes \mathbf{x}_2 \otimes \mathbf{x}_3 \rangle + \\ \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{r}_2 \otimes \mathbf{r}_3 \rangle + \langle \mathbf{F}, \mathbf{r}_1 \otimes \mathbf{x}_2 \otimes \mathbf{r}_3 \rangle + \langle \mathbf{F}, \mathbf{r}_1 \otimes \mathbf{r}_2 \otimes \mathbf{x}_3 \rangle + \\ \langle \mathbf{F}, \mathbf{r}_1 \otimes \mathbf{r}_2 \otimes \mathbf{r}_3 \rangle. \tag{3.1} $$

We classify the pure terms into two categories:

**Target Term** The term $\langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{x}_3 \rangle$. 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, \dots, r_7 \in \mathbb{F}$ from their common random string such that $r_1 + \dots + r_7 = 0$. There exist sub-protocols revealing each of

$$ \begin{aligned} r_1 + \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{r}_3 \rangle, & \quad r_2 + \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{r}_2 \otimes \mathbf{x}_3 \rangle, \quad r_3 + \langle \mathbf{F}, \mathbf{r}_1 \otimes \mathbf{x}_2 \otimes \mathbf{x}_3 \rangle, \\ r_4 + \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{r}_2 \otimes \mathbf{r}_3 \rangle, & \quad r_5 + \langle \mathbf{F}, \mathbf{r}_1 \otimes \mathbf{x}_2 \otimes \mathbf{r}_3 \rangle, \quad r_6 + \langle \mathbf{F}, \mathbf{r}_1 \otimes \mathbf{r}_2 \otimes \mathbf{x}_3 \rangle, \\ & \quad r_7 + \langle \mathbf{F}, \mathbf{r}_1 \otimes \mathbf{r}_2 \otimes \mathbf{r}_3 \rangle \end{aligned} \tag{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 $\bar{\mathbf{x}}_i := \mathbf{x}_i + \mathbf{r}_i$, they use 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 + \langle \mathbf{F}, \mathbf{r}_1 \otimes \mathbf{r}_2 \otimes \mathbf{r}_3 \rangle$, any party (e.g. the first party) can compute it and send it to the referee.

* For the term $r_4 + \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{r}_2 \otimes \mathbf{r}_3 \rangle$, the first party computes it and sends it to the referee. Similarly for $r_5 + \langle \mathbf{F}, \mathbf{r}_1 \otimes \mathbf{x}_2 \otimes \mathbf{r}_3 \rangle$ and $r_6 + \langle \mathbf{F}, \mathbf{r}_1 \otimes \mathbf{r}_2 \otimes \mathbf{x}_3 \rangle$.

* For the term $r_1 + \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{r}_3 \rangle$, both first and second party need to participate. Since the first party knows $\mathbf{F}, \mathbf{x}_1, \mathbf{r}_3$, it can locally compute a vector $\mathbf{g} \in \mathbb{F}^N$ such that

$$ r_1 + \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{r}_3 \rangle = r_1 + \langle \mathbf{g}, \mathbf{x}_2 \rangle. $$

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 + \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{r}_2 \otimes \mathbf{x}_3 \rangle$ and $r_3 + \langle \mathbf{F}, \mathbf{r}_1 \otimes \mathbf{x}_2 \otimes \mathbf{x}_3 \rangle$.
**Example: 5-Party PSM.** We will sketch a 5-party PSM protocol for any $f : [N]^5 \to \{0, 1\}$ with communication complexity $O(N^2)$.

Let $\mathbb{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 $(\mathbf{x}_1, \dots, \mathbf{x}_5) \mapsto \langle \mathbf{F}, \mathbf{x}_1 \otimes \dots \otimes \mathbf{x}_5 \rangle$, where $\otimes$ denotes the tensor product, the i-th party having input $\mathbf{x}_i \in \mathbb{F}^N$, $\mathbf{F}$ is public and fixed being the truth table of $f$.

For each $\Omega \subseteq \{1, 2, 3, 4, 5\}$, parties sample a dimension-$|\Omega|$ tensor $\mathbf{R}_{\Omega} \in \mathbb{F}^{N^{|\Omega|}}$ from the common random string. Define $\bar{\mathbf{X}}_{\Omega} := \mathbf{R}_{\Omega} + \otimes_{i \in \Omega} \mathbf{x}_i$. For example, $\bar{\mathbf{X}}_{\{2\}} := \mathbf{R}_{\{2\}} + \mathbf{x}_2$ and $\bar{\mathbf{X}}_{\{3,4\}} := \mathbf{R}_{\{3,4\}} + \mathbf{x}_3 \otimes \mathbf{x}_4$. Since the communication budget is $O(N^2)$, they can perform a PSM sub-protocol so that the referee learns $\bar{\mathbf{X}}_{\Omega}$ for all $\Omega$ such that $|\Omega| \le 2$.

Learning those tensors allows the referee to compute many terms, including $\langle \mathbf{F}, \bar{\mathbf{X}}_{\{1,2\}} \otimes \bar{\mathbf{X}}_{\{3,4\}} \otimes \bar{\mathbf{X}}_{\{5\}} \rangle$. This term can be decomposed into the sum of the following 8 terms:

$$ \begin{aligned} & \langle \mathbf{F}, \bar{\mathbf{X}}_{\{1,2\}} \otimes \bar{\mathbf{X}}_{\{3,4\}} \otimes \bar{\mathbf{X}}_{\{5\}} \rangle \\ &= \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{x}_3 \otimes \mathbf{x}_4 \otimes \mathbf{x}_5 \rangle + \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{x}_3 \otimes \mathbf{x}_4 \otimes \mathbf{R}_{\{5\}} \rangle \\ & \quad + \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{R}_{\{3,4\}} \otimes \mathbf{x}_5 \rangle + \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{R}_{\{3,4\}} \otimes \mathbf{R}_{\{5\}} \rangle \\ & \quad + \langle \mathbf{F}, \mathbf{R}_{\{1,2\}} \otimes \mathbf{x}_3 \otimes \mathbf{x}_4 \otimes \mathbf{x}_5 \rangle + \langle \mathbf{F}, \mathbf{R}_{\{1,2\}} \otimes \mathbf{x}_3 \otimes \mathbf{x}_4 \otimes \mathbf{R}_{\{5\}} \rangle \\ & \quad + \langle \mathbf{F}, \mathbf{R}_{\{1,2\}} \otimes \mathbf{R}_{\{3,4\}} \otimes \mathbf{x}_5 \rangle + \langle \mathbf{F}, \mathbf{R}_{\{1,2\}} \otimes \mathbf{R}_{\{3,4\}} \otimes \mathbf{R}_{\{5\}} \rangle. \end{aligned} \quad (3.3) $$

Any term that is formed in the same way as the left-hand side of (3.3), i.e. $\langle \mathbf{F}, \bar{\mathbf{X}}_{S_1} \otimes \dots \otimes \bar{\mathbf{X}}_{S_t} \rangle$ for some $S_1 + \dots + S_t = \{1, 2, 3, 4, 5\}$, is called a *masked term*. It can be computed by the referee if $|S_i| \le 2$ for all $i$.

Any term that is formed in the same way as the right-hand side of (3.3), i.e. $\langle \mathbf{F}, \mathbf{R}_{S_1} \otimes \dots \otimes \mathbf{R}_{S_t} \otimes \mathbf{x}_{i_1} \otimes \dots \otimes \mathbf{x}_{i_w} \rangle$ for some $S_1 + \dots + S_t + \{i_1, \dots, 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 $\langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{x}_3 \otimes \mathbf{x}_4 \otimes \mathbf{x}_5 \rangle$ is called the target term.

**Easy term** A pure term $\langle \mathbf{F}, \mathbf{R}_{S_1} \otimes \dots \otimes \mathbf{R}_{S_t} \otimes \mathbf{x}_{i_1} \otimes \dots \otimes \mathbf{x}_{i_w} \rangle$ is easy if $w \le 3$. Every easy term can be computed using a PSM protocol with communication complexity $O(N^2)$. For example, $\langle \mathbf{F}, \mathbf{R}_{\{1,2\}} \otimes \mathbf{x}_3 \otimes \mathbf{x}_4 \otimes \mathbf{x}_5 \rangle$ is an easy term. The 5th party, based on its view, can compute a tensor $\mathbf{G} \in \mathbb{F}^{N^2}$ such that $\langle \mathbf{F}, \mathbf{R}_{\{1,2\}} \otimes \mathbf{x}_3 \otimes \mathbf{x}_4 \otimes \mathbf{x}_5 \rangle = \langle \mathbf{G}, \mathbf{x}_3 \otimes \mathbf{x}_4 \rangle$. And $\langle \mathbf{G}, \mathbf{x}_3 \otimes \mathbf{x}_4 \rangle$ 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

$$ \begin{aligned} & \langle \mathbf{F}, \bar{\mathbf{X}}_{\{1,2\}} \otimes \bar{\mathbf{X}}_{\{3,4\}} \otimes \bar{\mathbf{X}}_{\{5\}} \rangle \\ &= \langle \mathbf{F}, \mathbf{x}_1 \otimes \dots \otimes \mathbf{x}_5 \rangle + \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{x}_3 \otimes \mathbf{x}_4 \otimes \mathbf{R}_{\{5\}} \rangle + \text{easy terms.} \end{aligned} $$

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: $\langle \mathbf{F}, \bar{\mathbf{X}}_{\{1,2\}} \otimes \bar{\mathbf{X}}_{\{3\}} \otimes \bar{\mathbf{X}}_{\{4,5\}} \rangle$, $\langle \mathbf{F}, \bar{\mathbf{X}}_{\{1,2\}} \otimes \bar{\mathbf{X}}_{\{3,5\}} \otimes \bar{\mathbf{X}}_{\{4\}} \rangle$ and $\langle \mathbf{F}, \bar{\mathbf{X}}_{\{1,2\}} \otimes \bar{\mathbf{X}}_{\{3\}} \otimes \bar{\mathbf{X}}_{\{4\}} \otimes \bar{\mathbf{X}}_{\{5\}} \rangle$.
$$
\begin{align*}
& \langle \mathbf{F}, \bar{\mathbf{X}}_{\{1,2\}} \otimes \bar{\mathbf{X}}_{\{3\}} \otimes \bar{\mathbf{X}}_{\{4,5\}} \rangle \\
&= \langle \mathbf{F}, \mathbf{x}_1 \otimes \cdots \otimes \mathbf{x}_5 \rangle + \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{R}_{\{3\}} \otimes \mathbf{x}_4 \otimes \mathbf{x}_5 \rangle + \text{easy terms}, \\
& \langle \mathbf{F}, \bar{\mathbf{X}}_{\{1,2\}} \otimes \bar{\mathbf{X}}_{\{3,5\}} \otimes \bar{\mathbf{X}}_{\{4\}} \rangle \\
&= \langle \mathbf{F}, \mathbf{x}_1 \otimes \cdots \otimes \mathbf{x}_5 \rangle + \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{x}_3 \otimes \mathbf{R}_{\{4\}} \otimes \mathbf{x}_5 \rangle + \text{easy terms}, \\
& \langle \mathbf{F}, \bar{\mathbf{X}}_{\{1,2\}} \otimes \bar{\mathbf{X}}_{\{3\}} \otimes \bar{\mathbf{X}}_{\{4\}} \otimes \bar{\mathbf{X}}_{\{5\}} \rangle \\
&= \langle \mathbf{F}, \mathbf{x}_1 \otimes \cdots \otimes \mathbf{x}_5 \rangle + \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{R}_{\{3\}} \otimes \mathbf{x}_4 \otimes \mathbf{x}_5 \rangle \\
&\quad + \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{x}_3 \otimes \mathbf{R}_{\{4\}} \otimes \mathbf{x}_5 \rangle + \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{x}_3 \otimes \mathbf{x}_4 \otimes \mathbf{R}_{\{5\}} \rangle \\
&\quad + \text{easy terms}.
\end{align*}
$$

By carefully combining these masked tensors, we have

$$
\begin{align}
& \langle \mathbf{F}, \bar{\mathbf{X}}_{\{1,2\}} \otimes \bar{\mathbf{X}}_{\{3,4\}} \otimes \bar{\mathbf{X}}_{\{5\}} \rangle + \langle \mathbf{F}, \bar{\mathbf{X}}_{\{1,2\}} \otimes \bar{\mathbf{X}}_{\{3\}} \otimes \bar{\mathbf{X}}_{\{4,5\}} \rangle \nonumber \\
& + \langle \mathbf{F}, \bar{\mathbf{X}}_{\{1,2\}} \otimes \bar{\mathbf{X}}_{\{3,5\}} \otimes \bar{\mathbf{X}}_{\{4\}} \rangle - \langle \mathbf{F}, \bar{\mathbf{X}}_{\{1,2\}} \otimes \bar{\mathbf{X}}_{\{3\}} \otimes \bar{\mathbf{X}}_{\{4\}} \otimes \bar{\mathbf{X}}_{\{5\}} \rangle \tag{3.4} \\
&= 2 \cdot \langle \mathbf{F}, \mathbf{x}_1 \otimes \cdots \otimes \mathbf{x}_5 \rangle + \text{easy terms.} \nonumber
\end{align}
$$

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 \cdot \langle \mathbf{F}, \mathbf{x}_1 \otimes \cdots \otimes \mathbf{x}_5 \rangle$.

As long as $\mathbb{F}$ is a finite field in which $2 \neq 0$, the referee has learned the target term. The protocol takes a communication cost of $O(N^2)$ field elements.

### 3.1.3 Related Works

Besides [BIKK14, BKN18], 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(\sqrt{N})$ is conserved [BIKK14, GKW15]. A similar lower bound of $\Omega(\log N)$ is known [GKW15, AARV17]. Recently, Liu, Vaikuntanathan and Wee improved the CDS upper bound for arbitrary function to $2^{\sqrt{\log N}}$ [LVW17]. In a slightly different setting, the amortized CDS upper bound per party is improved to $\Theta(1)$ [AARV17, AA18].

Gay, Kerenidis and Wee constructed 2-party CDS with smooth communication complexity trade-off between the two parties [GKW15]. In particular, for any $\eta \in [0, 1]$, they constructed a 2-party CDS protocol where one party sends $O(N^\eta)$ bits and the other sends $O(N^{1-\eta})$ 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 [BIK17], was shown to imply obfuscation.

## 3.2 Preliminaries

Let $\mathbb{N} := \{0, 1, \dots\}$ denote the set of all natural numbers, and let $[n] := \{1, \dots, n\}$. In this chapter, $\mathbb{F}$ denotes a field, $\mathcal{R}$ denotes a finite commutative ring. For some prime power
p, let $\mathbb{F}_p$ denote the unique finite field of order p. A vector will be denoted by a bold face lowercase letter. For a vector $\mathbf{v}$, let $\mathbf{v}[i]$ denote its i-th entry.

### 3.2.1 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 $\mathbf{T} \in \mathbb{F}^{n_1 \times n_2 \times \dots \times n_k}$ is essentially an array of size $n_1 \times n_2 \times \dots \times n_k$. The entries in $\mathbf{T}$ are indexed by $(i_1, \dots, i_k) \in [n_1] \times \dots \times [n_k]$, and denoted by $\mathbf{T}[i_1, \dots, i_k]$. A tensor can also be viewed as a representation of a multi-linear function: any k-linear function $f: \mathbb{F}^{n_1} \times \mathbb{F}^{n_2} \times \dots \times \mathbb{F}^{n_k} \to \mathbb{F}$ can be uniquely determined by its coefficient tensor $\mathbf{F} \in \mathbb{F}^{n_1 \times \dots \times n_k}$, such that

$$f(\mathbf{v}_1, \dots, \mathbf{v}_k) = \sum_{i_1 \in [n_1], \dots, i_k \in [n_k]} \mathbf{F}[i_1, \dots, i_k] \cdot \mathbf{v}_1[i_1] \cdots \mathbf{v}_k[i_k]. \quad (3.5)$$

The inner product of two tensors $\mathbf{S}, \mathbf{T} \in \mathbb{F}^{n_1 \times n_2 \times \dots \times n_k}$ is defined as

$$\langle \mathbf{S}, \mathbf{T} \rangle := \sum_{i_1 \in [n_1], \dots, i_k \in [n_k]} \mathbf{S}[i_1, \dots, i_k] \cdot \mathbf{T}[i_1, \dots, i_k].$$

Given two tensors $\mathbf{S} \in \mathbb{F}^{n_1 \times \dots \times n_k}$ and $\mathbf{T} \in \mathbb{F}^{m_1 \times \dots \times m_\ell}$, we define $\mathbf{S} \otimes \mathbf{T}$, their tensor product. It is a tensor in $\mathbb{F}^{n_1 \times \dots \times n_k \times m_1 \times \dots \times m_\ell}$ such that

$$(\mathbf{S} \otimes \mathbf{T})[i_1, \dots, i_k, j_1, \dots, j_\ell] = \mathbf{S}[i_1, \dots, i_k] \cdot \mathbf{T}[j_1, \dots, j_\ell].$$

Using the notation of inner product and tensor product, Equation (3.5) can also be written as $f(\mathbf{v}_1, \dots, \mathbf{v}_k) = \langle \mathbf{F}, \mathbf{v}_1 \otimes \dots \otimes \mathbf{v}_k \rangle$.

### 3.2.2 Private Simultaneous Messages

**Definition 1** (private simultaneous message). A k-party functionality is a mapping $f: \mathcal{X}_1 \times \dots \times \mathcal{X}_k \to \mathcal{Y}$, where $\mathcal{X}_1, \dots, \mathcal{X}_k$ are its input spaces and $\mathcal{Y}$ is its output space.

A private simultaneous message (PSM) protocol for a functionality $f$ consists of a randomness space $\mathcal{W}$ and a tuple of deterministic functions $(\mathbf{M}_1, \dots, \mathbf{M}_k, \mathbf{R})$

$$\begin{aligned} \mathbf{M}_i: \mathcal{X}_i \times \mathcal{W} &\to \{0, 1\}^{\mathcal{C}_i}, \quad \text{for all } i \in [k], \\ \mathbf{R}: \{0, 1\}^{\mathcal{C}_1} \times \dots \{0, 1\}^{\mathcal{C}_k} &\to \{0, 1\}, \end{aligned}$$

where $\mathcal{C}_i$ is the communication complexity of the i-th party, $\mathcal{C} := \mathcal{C}_1 + \dots + \mathcal{C}_k$ is the total communication complexity.

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

(correctness.) For all input tuple $(x_1, \dots, x_k) \in \mathcal{X}_1 \times \dots \times \mathcal{X}_k$ and randomness $w \in \mathcal{W}$,

$$\mathbf{R}(\mathbf{M}_1(x_1, w), \dots, \mathbf{M}_k(x_k, w)) = f(x_1, \dots, x_k)$$

(privacy.) There exists a randomized simulator $\mathbf{S}$, such that for any input $(x_1, \dots, x_k) \in \mathcal{X}_1 \times \dots \times \mathcal{X}_k$, the joint distribution of $\mathbf{M}_1(x_1, w), \dots, \mathbf{M}_k(x_k, w)$ is the same as the distributions of $\mathbf{S}(f(x_1, \dots, x_k))$, where the distributions are taken over $w \leftarrow \mathcal{W}$ and the coin tosses of $\mathbf{S}$.
### 3.2.3 Randomized Encoding

Randomized encoding is a primitive closely related to PSM. The randomized encoding of a function $f$ is a randomized function $\hat{f}$. The output $\hat{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: \mathcal{X} \to \mathcal{Y}$ consists of a randomized encoding function $\hat{f}: \mathcal{X} \times \mathcal{W} \to \hat{\mathcal{Y}}$ and a deterministic decoding function $R: \hat{\mathcal{Y}} \to \mathcal{Y}$, where $\mathcal{W}$ denotes the randomness space and $\hat{\mathcal{Y}}$ denotes the coding space.

A perfectly secure randomized encoding satisfies the following properties:

(correctness.) For all $x \in \mathcal{X}$ and randomness $w \in \mathcal{W}$,

$$R(\hat{f}(x, w)) = f(x)$$

(privacy.) There exists a randomized simulator $S$, such that for any input $x \in \mathcal{X}$, the distribution of $\hat{f}(x, w)$ is the same as the distributions of $S(f(x))$, where the distributions are taken over $w \leftarrow \mathcal{W}$ and the coin tosses of $S$.

Follows directly from the definitions, $(M_1, \dots, M_k, R)$ is a PSM protocol for $f$ if and only if $(\hat{f}, R)$ is a randomized encoding for $f$, where $\hat{f}(x_1, \dots, x_k, w) := (M_1(x_1, w), \dots, 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.

## 3.3 New Multi-party PSM Protocols

In this section, we present one of our main results: for many $k$, every functionality $f: [N]^k \to \{0, 1\}$ admits a PSM protocol of communication complexity $O_k(N^{\frac{k-1}{2}})$.

**Theorem 3.3.1.** Let $f: [N]^k \to \{0, 1\}$ be an arbitrary $k$-party functionality.

* There is a $k$-party PSM protocol for $f$ with communication and randomness complexity $O(N^{\frac{k-1}{2}})$, if $k \le 20$.

* There is a $k$-party PSM protocol for $f$ with communication and randomness complexity $O_k(N^{\frac{k-1}{2}})$, if $k+1$ is a prime or a prime power.

In this section, we prove a stronger statement. Let $\mathbb{F}$ be a finite field, consider the following auxiliary $k$-party functionality $\text{Aux}_N^k$:

k-party functionality $\text{Aux}_N^k$

* The $i$-th party has input $\mathbf{x}_{2i-1}, \mathbf{x}_{2i} \in \mathbb{F}^{\sqrt{N}}$

* The output is $\langle \mathbb{F}, \mathbf{x}_1 \otimes \dots \otimes \mathbf{x}_{2k} \rangle$, where $\mathbb{F}$ is public and fixed
As shown in the beginning of Section 3.3.1, a PSM protocol for $Aux_N^k$ implies a PSM for $f : [N]^k \to \{0, 1\}$ with the same communication complexity. The reduction consists of having $\mathbf{F}$ be the truth table of $f$.

We will present a framework of constructing $k$-party PSM for $Aux_N^k$, whose communication complexity is $O_k(N^{\frac{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 \le 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 \to \{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^{\frac{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.

### 3.3.1 A Framework for Multi-party PSM

As mentioned in the beginning of Section 3.3, the functionality $f : [N]^k \to \{0, 1\}$ can be reduced to functionality $Aux_N^k$. The reduction works as follows: Let $x_1, \dots, x_k$ be the input, the $j$-th party has input $x_j \in [N]$. We evenly divide $x_j$ into $x'_{2j-1}, x'_{2j} \in [\sqrt{N}]$. For each $i \in [2k]$, let $\mathbf{x}_i := \mathbf{e}_{x'_i} \in \mathbb{F}^{\sqrt{N}}$ be the $x'_i$-th standard unit vector. We reduce $f$ to $Aux_N^k$:

$$f(x_1, \dots, x_{2k}) = \langle \mathbf{F}, \mathbf{x}_1 \otimes \dots \otimes \mathbf{x}_{2k} \rangle$$

where $\mathbf{F}$ is the truth-table of $f$. For the remainder of the section, it is thus sufficient to construct a PSM protocol for $Aux_N^k$.

For each non-empty $\Omega \subseteq [2k]$, our protocol will sample a random dimension-$|\Omega|$ tensor $\mathbf{R}_\Omega \in \mathcal{R}(\sqrt{N})^{|\Omega|}$ from the common random string<fnref n="1" />. Define $\bar{\mathbf{X}}_\Omega := \mathbf{R}_\Omega + \otimes_{i \in \Omega} \mathbf{x}_i$. E.g., $\bar{\mathbf{X}}_{\{2\}} := \mathbf{R}_{\{2\}} + \mathbf{x}_2$, $\bar{\mathbf{X}}_{\{3,4\}} := \mathbf{R}_{\{3,4\}} + \mathbf{x}_3 \otimes \mathbf{x}_4$.

Within the communication complexity budget $O(N^{\frac{k-1}{2}})$, we can let the referee learn $\bar{\mathbf{X}}_\Omega$ for all $\Omega$ such that $|\Omega| \le k-1$ (more details in Section 3.3.2). The referee does not learn extra information as $\bar{\mathbf{X}}_\Omega$ is one-time padded by $\mathbf{R}_\Omega$. For example when $k = 4$, we can let the referee learn tensors $\bar{\mathbf{X}}_{\{1\}}, \bar{\mathbf{X}}_{\{2\}}, \dots, \bar{\mathbf{X}}_{\{8\}}, \bar{\mathbf{X}}_{\{1,2\}}, \bar{\mathbf{X}}_{\{1,3\}}, \dots, \bar{\mathbf{X}}_{\{7,8\}}, \bar{\mathbf{X}}_{\{1,2,3\}}, \bar{\mathbf{X}}_{\{1,2,4\}}, \dots, \bar{\mathbf{X}}_{\{6,7,8\}}$. The referee learns those tensors by having *subsets of the parties* recursively perform PSM

<footnote n="1">¹A note on the randomness complexity: The final protocol uses $\mathbf{R}_\Omega$ only if $|\Omega| \le k - 1$.</footnote>
protocols with a smaller number of parties, so that the referee learns the required in-
formation. Learning those tensors allows the referee to compute many terms including
$\langle \mathbf{F}, \bar{\mathbf{X}}_{\{1,2,3\}} \otimes \bar{\mathbf{X}}_{\{4,5,6\}} \otimes \bar{\mathbf{X}}_{\{7,8\}} \rangle$, which equals to the sum of the following 8 terms,

$$
\begin{align}
& \langle \mathbf{F}, \bar{\mathbf{X}}_{\{1,2,3\}} \otimes \bar{\mathbf{X}}_{\{4,5,6\}} \otimes \bar{\mathbf{X}}_{\{7,8\}} \rangle \nonumber \\
& = \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{x}_3 \otimes \mathbf{x}_4 \otimes \mathbf{x}_5 \otimes \mathbf{x}_6 \otimes \mathbf{x}_7 \otimes \mathbf{x}_8 \rangle \nonumber \\
& \quad + \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{x}_3 \otimes \mathbf{x}_4 \otimes \mathbf{x}_5 \otimes \mathbf{x}_6 \otimes \mathbf{R}_{\{7,8\}} \rangle \nonumber \\
& \quad + \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{x}_3 \otimes \mathbf{R}_{\{4,5,6\}} \otimes \mathbf{x}_7 \otimes \mathbf{x}_8 \rangle \nonumber \\
& \quad + \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{x}_3 \otimes \mathbf{R}_{\{4,5,6\}} \otimes \mathbf{R}_{\{7,8\}} \rangle \tag{3.6} \\
& \quad + \langle \mathbf{F}, \mathbf{R}_{\{1,2,3\}} \otimes \mathbf{x}_4 \otimes \mathbf{x}_5 \otimes \mathbf{x}_6 \otimes \mathbf{x}_7 \otimes \mathbf{x}_8 \rangle \nonumber \\
& \quad + \langle \mathbf{F}, \mathbf{R}_{\{1,2,3\}} \otimes \mathbf{x}_4 \otimes \mathbf{x}_5 \otimes \mathbf{x}_6 \otimes \mathbf{R}_{\{7,8\}} \rangle \nonumber \\
& \quad + \langle \mathbf{F}, \mathbf{R}_{\{1,2,3\}} \otimes \mathbf{R}_{\{4,5,6\}} \otimes \mathbf{x}_7 \otimes \mathbf{x}_8 \rangle \nonumber \\
& \quad + \langle \mathbf{F}, \mathbf{R}_{\{1,2,3\}} \otimes \mathbf{R}_{\{4,5,6\}} \otimes \mathbf{R}_{\{7,8\}} \rangle. \nonumber
\end{align}
$$

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 $\bar{\mathbf{X}}_{\Omega_1} \otimes \dots \otimes \bar{\mathbf{X}}_{\Omega_t}^2$ such that $\Omega_1, \dots, \Omega_t$ are disjoint and their union equals $[2k]$. The shape of a masked tensor $\bar{\mathbf{X}}_{\Omega_1} \otimes \dots \otimes \bar{\mathbf{X}}_{\Omega_t}$ is the multiset $\{|\Omega_1|, \dots, |\Omega_t|\}$. The inner product of a masked tensor and $\mathbf{F}$ is called a masked term.

For any multiset $P$ such that $\mathrm{sum}(P) = 2k$, let $\sum \bar{\mathbf{X}}(P)$ denote the sum of all masked tensors of shape $P$, let $\sum \langle \mathbf{F}, \bar{\mathbf{X}}(P) \rangle$ denote the sum of all masked terms of shape $P$. We thus have $\sum \langle \mathbf{F}, \bar{\mathbf{X}}(P) \rangle = \langle \mathbf{F}, \sum \bar{\mathbf{X}}(P) \rangle$.

**Definition (pure tensor & pure term).** A pure tensor is a tensor product $\mathbf{R}_{\Omega_1} \otimes \dots \otimes \mathbf{R}_{\Omega_t} \otimes \mathbf{x}_{i_1} \otimes \dots \otimes \mathbf{x}_{i_w}$ such that $\{i_1, \dots, i_w\}, \Omega_1, \dots, \Omega_t$ are disjoint and their union equals $[2k]$. The shape of a pure tensor $\mathbf{R}_{\Omega_1} \otimes \dots \otimes \mathbf{R}_{\Omega_t} \otimes \mathbf{x}_{i_1} \otimes \dots \otimes \mathbf{x}_{i_w}$ is the multiset $\{|\Omega_1|, \dots, |\Omega_t|\}$. The inner product of a pure tensor and $\mathbf{F}$ is called a pure term.

For any multiset $P$ such that $\mathrm{sum}(P) \le 2k$, let $\sum \mathbf{R}(P)$ denote the sum of all pure tensors of shape $P$, let $\sum \langle \mathbf{F}, \mathbf{R}(P) \rangle$ denote the sum of all pure terms of shape $P$. We thus have $\sum \langle \mathbf{F}, \mathbf{R}(P) \rangle = \langle \mathbf{F}, \sum \mathbf{R}(P) \rangle$.

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

**Target term (target tensor)** $\langle \mathbf{F}, \mathbf{x}_1 \otimes \dots \otimes \mathbf{x}_{2k} \rangle$ is called the target term as it is desired functionality output. The corresponding tensor $\mathbf{x}_1 \otimes \dots \otimes \mathbf{x}_{2k}$ is called the target tensor.

**Easy terms (easy tensors)** A pure tensor $\mathbf{R}_{\Omega_1} \otimes \dots \otimes \mathbf{R}_{\Omega_t} \otimes \mathbf{x}_{i_1} \otimes \dots \otimes \mathbf{x}_{i_w}$ is called an easy tensor if at most $k+1$ out of the $2k$ dimensions are contributed by vector $\mathbf{x}_i$'s (i.e., $w \le k+1$). The corresponding term is called an easy term. Every easy term admits a PSM protocol with communication complexity no more than $O(\mathrm{poly}(k) \cdot N^{\frac{k-1}{2}})$ field elements (more details in Section 3.3.2).

<footnote>$^2$We implicitly exchange the order of indices in tensor product. E.g. when $k=2$, the masked tensor $\bar{\mathbf{X}}_{\{1,4\}} \otimes \bar{\mathbf{X}}_{\{2,3\}}$ is defined by $(\bar{\mathbf{X}}_{\{1,4\}} \otimes \bar{\mathbf{X}}_{\{2,3\}})[j_1, j_2, j_3, j_4] = \bar{\mathbf{X}}_{\{1,4\}}[j_1, j_4] \cdot \bar{\mathbf{X}}_{\{2,3\}}[j_2, j_3]$.</footnote>
**Hard terms (hard tensors)** The rest.

With this terminology, we can give an overview of our PSM protocol. As the referee can learn $\bar{X}_{\Omega}$ for all $\Omega$ such that $|\Omega| \le k - 1$, the referee can compute any masked term of shape $P$ if $\max(P) \le 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:

$$ \textit{a linear combination of masked terms} = \textit{target term} + \textit{some easy terms.} \qquad (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 $\text{Aux}_N^k$. (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$, $\sum \bar{X}(3, 3, 2)$ is defined as the sum of all masked tensors $\bar{X}_{\Omega_1} \otimes \bar{X}_{\Omega_2} \otimes \bar{X}_{\Omega_3}$ such that the multiset $\{|\Omega_1|, |\Omega_2|, |\Omega_3|\}$ equals $\{3, 3, 2\}$, i.e.

$$ \sum \bar{X}(3, 3, 2) := \bar{X}_{\{1,2,3\}} \otimes \bar{X}_{\{4,5,6\}} \otimes \bar{X}_{\{7,8\}} + \bar{X}_{\{1,2,3\}} \otimes \bar{X}_{\{4,5,7\}} \otimes \bar{X}_{\{6,8\}} \\ + \bar{X}_{\{1,2,3\}} \otimes \bar{X}_{\{4,5,8\}} \otimes \bar{X}_{\{5,6\}} + \bar{X}_{\{1,2,3\}} \otimes \bar{X}_{\{4,6,7\}} \otimes \bar{X}_{\{5,8\}} \\ + \dots + \bar{X}_{\{3,4,5\}} \otimes \bar{X}_{\{6,7,8\}} \otimes \bar{X}_{\{1,2\}}. $$

Let's revisit Equation (3.6),

$$ \begin{aligned} & \underbrace{\langle \mathbf{F}, \bar{\mathbf{X}}_{\{1,2,3\}} \otimes \bar{\mathbf{X}}_{\{4,5,6\}} \otimes \bar{\mathbf{X}}_{\{7,8\}} \rangle}_{\text{a masked term of shape } \{3, 3, 2\}} \\ &= \underbrace{\langle \mathbf{F}, \mathbf{x}_1 \otimes \dots \otimes \mathbf{x}_8 \rangle}_{\text{a pure term of shape } \{\}} + \underbrace{\langle \mathbf{F}, \mathbf{x}_1 \otimes \dots \otimes \mathbf{x}_6 \otimes \mathbf{R}_{\{7,8\}} \rangle}_{\text{a pure term of shape } \{2\}} \\ &\quad + \underbrace{\langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{x}_3 \otimes \mathbf{R}_{\{4,5,6\}} \otimes \mathbf{x}_7 \otimes \mathbf{x}_8 \rangle}_{\text{pure terms of shape } \{3\}} + \langle \mathbf{F}, \mathbf{R}_{\{1,2,3\}} \otimes \mathbf{x}_4 \otimes \dots \otimes \mathbf{x}_8 \rangle \\ &\quad + \underbrace{\langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{x}_3 \otimes \mathbf{R}_{\{4,5,6\}} \otimes \mathbf{R}_{\{7,8\}} \rangle}_{\text{pure terms of shape } \{3, 2\}} + \langle \mathbf{F}, \mathbf{R}_{\{1,2,3\}} \otimes \mathbf{x}_4 \otimes \mathbf{x}_5 \otimes \mathbf{x}_6 \otimes \mathbf{R}_{\{7,8\}} \rangle \\ &\quad + \underbrace{\langle \mathbf{F}, \mathbf{R}_{\{1,2,3\}} \otimes \mathbf{R}_{\{4,5,6\}} \otimes \mathbf{x}_7 \otimes \mathbf{x}_8 \rangle}_{\text{a pure term of shape } \{3, 3\}} + \underbrace{\langle \mathbf{F}, \mathbf{R}_{\{1,2,3\}} \otimes \mathbf{R}_{\{4,5,6\}} \otimes \mathbf{R}_{\{7,8\}} \rangle}_{\text{a pure term of shape } \{3, 3, 2\}}. \end{aligned} $$

By applying a symmetric sum on both sides, we get

$$ \begin{aligned} \sum \langle \mathbf{F}, \bar{\mathbf{X}}(3, 3, 2) \rangle = & \underbrace{280 \cdot \sum \langle \mathbf{F}, \mathbf{R}(1) \rangle}_{\text{the target term}} + \underbrace{10 \cdot \sum \langle \mathbf{F}, \mathbf{R}(2) \rangle}_{\text{hard pure terms}} \\ & + \underbrace{10 \cdot \sum \langle \mathbf{F}, \mathbf{R}(3) \rangle + \sum \langle \mathbf{F}, \mathbf{R}(3, 2) \rangle + \sum \langle \mathbf{F}, \mathbf{R}(3, 3) \rangle + \sum \langle \mathbf{F}, \mathbf{R}(3, 3, 2) \rangle}_{\text{easy pure terms}}. \end{aligned} $$
As another example of the symmetric sum of masked term that the referee can compute,

$$ \begin{aligned} \sum \langle \mathbf{F}, \bar{\mathbf{X}}(2, 2, 2, 2) \rangle = & \underbrace{105 \cdot \sum \langle \mathbf{F}, \mathbf{R}(1) \rangle}_{\text{target term}} + \underbrace{15 \cdot \sum \langle \mathbf{F}, \mathbf{R}(2) \rangle}_{\text{hard pure terms}} \\ & + \underbrace{3 \cdot \sum \langle \mathbf{F}, \mathbf{R}(2, 2) \rangle + \sum \langle \mathbf{F}, \mathbf{R}(2, 2, 2) \rangle + \sum \langle \mathbf{F}, \mathbf{R}(2, 2, 2, 2) \rangle}_{\text{easy pure terms}} \end{aligned} $$

By carefully combining the above two equations, we get

$$ 3 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(3, 3, 2) \rangle - 2 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(2, 2, 2, 2) \rangle = 630 \cdot \sum \langle \mathbf{F}, \mathbf{R}(1) \rangle + \text{easy terms}, \quad (3.8) $$

which induces a 4-party PSM whose communication complexity is $O(N^{3/2})$, if we let $\mathbb{F}$ to be any field in which $630 \neq 0$. (Section 3.3.2 explains how Equation (3.8) implies a 4-party PSM with desired communication complexity.)

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 $\text{sum}(P) = 2k$),

$$ \sum \langle \mathbf{F}, \bar{\mathbf{X}}(P) \rangle = \sum_{Q \subseteq P} \alpha(Q) \cdot \sum \langle \mathbf{F}, \mathbf{R}(P \setminus Q) \rangle, \quad (3.9) $$

where $P \setminus Q$ is the multiset subtraction and

$$ \alpha(Q) := \frac{(\text{sum}(Q))!}{\prod_{i \in Q} i! \cdot \prod_{m \in \mathbb{Z}^{+}} (\text{number of } m\text{'s in } Q)!} \quad (3.10) $$

is the following combinatoric number: $\alpha(Q)$ is the number of ways to partition $\text{sum}(Q)$ distinct elements into some unordered subsets $S_1, \dots, S_t$ such that $Q = \{|S_1|, \dots, |S_t|\}$. Equations (3.9), (3.10) are proved in Appendix A.1.

### 3.3.2 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 $\bar{\mathbf{X}}^{(1)}, \dots, \bar{\mathbf{X}}^{(t)}$, easy pure terms $\mathbf{R}^{(1)}, \dots, \mathbf{R}^{(s)}$, and coefficients $a_1, \dots, a_t, b_1, \dots, b_s \in \mathbb{F}$ such that

$$ \langle \mathbf{F}, \mathbf{x}_1 \otimes \dots \otimes \mathbf{x}_{2k} \rangle = \sum_{j=1}^{t} a_j \bar{\mathbf{X}}^{(j)} + \sum_{j=1}^{s} b_j \mathbf{R}^{(j)}. \quad (3.11) $$

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

* Fact I: $\sum_{j=1}^{s} b_j \mathbf{R}^{(j)}$ and $\bar{\mathbf{X}}_{\Omega}$ for all $0 < |\Omega| \leq k-1$ form a randomized encoding of $\langle \mathbf{F}, \mathbf{x}_1 \otimes \dots \otimes \mathbf{x}_{2k} \rangle$. That is, they contain the sufficient information to recover $\langle \mathbf{F}, \mathbf{x}_1 \otimes \dots \otimes \mathbf{x}_{2k} \rangle$, and they are garbled with additional randomness so that no other information can be recovered.

* Fact II: For every $\Omega \subseteq [2k]$ such that $0 < |\Omega| \leq k-1$, there is a PSM protocol for $\bar{\mathbf{X}}_{\Omega}$ with communication complexity $\text{poly}(k) \cdot N^{\frac{k-1}{2}}$ field elements.
* Fact III: There is a PSM protocol for $\sum_{j=1}^{s} b_j \mathbf{R}^{(j)}$ with communication complexity $\text{poly}(k) \cdot s \cdot N^{\frac{k-1}{2}}$ field elements.

The k-party PSM for f works as the follows: For each $\Omega \subseteq [2k]$ such that $0 < |\Omega| \le k-1$, use the PSM guaranteed by Fact II to reveal $\bar{\mathbf{X}}_{\Omega}$ to the referee. Use the PSM guaranteed by Fact III to reveal $\sum_{j=1}^{s} b_j \mathbf{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 $\langle \mathbf{F}, \mathbf{x}_1 \otimes \dots \otimes \mathbf{x}_{2k} \rangle$ can be computed from the encoding. Moreover, the distribution of the encoding is perfectly simulatable: The joint distribution of tensors $\bar{\mathbf{X}}_{\Omega}$ for $0 < |\Omega| \le k-1$ is uniform distribution, as they are independently one-time padded. Then the value of $\sum_{j=1}^{s} b_j \mathbf{R}^{(j)}$ is uniquely determined by equation (3.11).

**Proof of Fact II.** Let $t = |\Omega|$. Each coordinate of $\bar{\mathbf{X}}_{\Omega}$ is defined as

$$ \bar{\mathbf{X}}_{\{j_1, \dots, j_t\}}[i_1, \dots, i_t] = \mathbf{R}_{\{j_1, \dots, j_t\}}[i_1, \dots, i_t] + \mathbf{x}_{j_1}[i_1] \cdots \mathbf{x}_{j_t}[i_t], $$

which is an arithmetic formula of size $O(k)$. Thus each coordinate has a PSM protocol with communication complexity $\text{poly}(k)$ field elements [IK00].

**Proof of Fact III.** Sample random $c_1, \dots, c_s \in \mathbb{F}$ from the common random string such that $c_1 + \dots + c_s = 0$. Then it's sufficient to construct a PSM protocol for computing $b_j \mathbf{R}^{(j)} + c_j$ for each $j$. Say this easy pure term $\mathbf{R}^{(j)}$ is $\langle \mathbf{F}, \mathbf{R}_{\Omega_1} \otimes \dots \otimes \mathbf{x}_{i_1} \otimes \dots \otimes \mathbf{x}_{i_w} \rangle$. By our definition of an easy term, $w \le k+1$. There exists a special party, such that the other parties hold at most $k-1$ of $\mathbf{x}_{i_1}, \dots, \mathbf{x}_{i_w}$. When $w = k+1$, the special party is the one who holds two of $\mathbf{x}_{i_1}, \dots, \mathbf{x}_{i_w}$ (the existence is guaranteed by the pigeonhole principle). W.l.o.g. assume that the other parties hold $\mathbf{x}_{i_1}, \dots, \mathbf{x}_{i_w}$, such that $w' \le k-1$. Then the special party knows a dimension-$w'$ tensor $\mathbf{G}$ (which is determined by its input and $b_j, \mathbf{R}_{\Omega_1}, \mathbf{R}_{\Omega_2}, \dots$) such that

$$ b_j \mathbf{R}^{(j)} + c_j = \langle \mathbf{G}, \mathbf{x}_{i_1} \otimes \dots \otimes \mathbf{x}_{i_{w'}} \rangle + c_j, $$

which admits a PSM protocol (presented in Section A.2.1) with communication complexity $O(\text{poly}(k) \cdot N^{w'/2})$ field elements.

### 3.3.3 When k is Small

As shown in Section 3.3.1, to construct PSM protocol for $\text{Aux}_N^k$ with communication complexity $O_k(N^{\frac{k-1}{2}})$, it is sufficient to prove the target term is spanned by the referee-computable masked terms and easy pure terms. In this section, we verify that the condition holds for all $k \le 20$, which proves the first bullet of Theorem 3.3.1. However, we do not have a general construction of such linear systems of equations for an arbitrary $k$.

The case when $k=2$ was solved by [BIKK14]. Our framework yields the same protocol from

$$ \sum \langle \mathbf{F}, \bar{\mathbf{X}}(1, 1, 1, 1) \rangle = \sum \langle \mathbf{F}, \mathbf{R}(\cdot) \rangle + \text{easy terms.} $$

The case when $k=3$ was solved by [BKN18]. Our framework yields a similar protocol from

$$ \sum \langle \mathbf{F}, \bar{\mathbf{X}}(2, 2, 2) \rangle = \sum \langle \mathbf{F}, \mathbf{R}(\cdot) \rangle + \text{easy terms.} $$
The case when $k = 4$ is solved in section 3.3.1.

For $k = 5$, consider the following two masked terms,

$$ \sum \langle \mathbf{F}, \bar{\mathbf{X}}(4, 4, 2) \rangle = 1575 \cdot \sum \langle \mathbf{F}, \mathbf{R}(1) \rangle + 35 \cdot \sum \langle \mathbf{F}, \mathbf{R}(2) \rangle + \text{easy terms}, $$

$$ \sum \langle \mathbf{F}, \bar{\mathbf{X}}(4, 2, 2, 2) \rangle = 3150 \cdot \sum \langle \mathbf{F}, \mathbf{R}(1) \rangle + 210 \cdot \sum \langle \mathbf{F}, \mathbf{R}(2) \rangle + \text{easy terms}. $$

We have $6 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(4, 4, 2) \rangle - \sum \langle \mathbf{F}, \bar{\mathbf{X}}(4, 2, 2, 2) \rangle = 6300 \cdot \sum \langle \mathbf{F}, \mathbf{R}(1) \rangle + \text{easy terms}$, which induces a 5-party PSM with communication complexity $O(N^2)$.

For $k = 6$, consider the following masked terms

$$ \left[ \begin{array}{c} \sum \langle \mathbf{F}, \bar{\mathbf{X}}(5, 4, 3) \rangle \\ \sum \langle \mathbf{F}, \bar{\mathbf{X}}(4, 4, 4) \rangle \\ \sum \langle \mathbf{F}, \bar{\mathbf{X}}(3, 3, 3, 3) \rangle \end{array} \right] = \left[ \begin{array}{ccc} 27720 & 126 & 56 \\ 5775 & 35 \\ 15400 & 280 \end{array} \right] \left[ \begin{array}{c} \sum \langle \mathbf{F}, \mathbf{R}(1) \rangle \\ \sum \langle \mathbf{F}, \mathbf{R}(3) \rangle \\ \sum \langle \mathbf{F}, \mathbf{R}(4) \rangle \end{array} \right] + \text{easy terms} $$

Therefore, $100 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(5, 4, 3) \rangle - 160 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(4, 4, 4) \rangle - 45 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(3, 3, 3, 3) \rangle = 1155000 \cdot \sum \langle \mathbf{F}, \mathbf{R}(1) \rangle + \text{easy terms}$, which induces a 6-party PSM with communication complexity $O(N^{2.5})$.

For $k = 7$, consider the following masked terms

$$ \left[ \begin{array}{c} \sum \langle \mathbf{F}, \bar{\mathbf{X}}(4, 4, 4, 2) \rangle \\ \sum \langle \mathbf{F}, \bar{\mathbf{X}}(6, 6, 2) \rangle \\ \sum \langle \mathbf{F}, \bar{\mathbf{X}}(6, 4, 4) \rangle \end{array} \right] = \left[ \begin{array}{ccc} 525525 & 5775 & 1575 \\ 42042 & 462 \\ 105105 & 210 \end{array} \right] \left[ \begin{array}{c} \sum \langle \mathbf{F}, \mathbf{R}(1) \rangle \\ \sum \langle \mathbf{F}, \mathbf{R}(2) \rangle \\ \sum \langle \mathbf{F}, \mathbf{R}(4) \rangle \end{array} \right] + \text{easy terms} $$

Therefore, $14 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(4, 4, 4, 2) \rangle - 175 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(6, 6, 2) \rangle - 105 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(6, 4, 4) \rangle = -11036025 \cdot \sum \langle \mathbf{F}, \mathbf{R}(1) \rangle + \text{easy terms}$, which induces a 7-party PSM with communication complexity $O(N^3)$.

For larger $k$, we wrote a simple program<fnref n="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^{\frac{k-1}{2}})$ for every $k \le 20$. For example when $k = 20$, our program found:

$$ \begin{aligned} \sum \langle \mathbf{F}, \mathbf{R}(1) \rangle = & 2895 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(19, 19, 2) \rangle + 1902 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(19, 17, 4) \rangle + 2843 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(19, 16, 5) \rangle + 1025 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(19, 16, 3, 2) \rangle + 691 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(19, 15, 6) \rangle \\ & + 2507 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(19, 15, 4, 2) \rangle + 1923 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(19, 14, 7) \rangle + 1836 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(19, 14, 5, 2) \rangle + 2385 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(19, 13, 8) \rangle + 2073 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(19, 13, 6, 2) \rangle + 1312 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(19, 12, 9) \rangle + 2963 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(19, 12, 7, 2) \rangle + 568 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(19, 11, 10) \rangle + 975 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(19, 11, 8, 2) \rangle + 2445 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(19, 10, 9, 2) \rangle + 2047 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(19, 9, 8, 4) \rangle + 318 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(19, 9, 8, 2, 2) \rangle + 2118 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(19, 9, 6, 6) \rangle + 2189 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(19, 9, 6, 4, 2) \rangle + 1271 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(19, 9, 6, 2, 2, 2) \rangle + 1557 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(19, 9, 4, 4, 4) \rangle + 2482 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(19, 9, 4, 4, 2, 2) \rangle + 173 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(19, 9, 4, 2, 2, 2, 2) \rangle + 1943 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(19, 9, 2, 2, 2, 2, 2, 2) \rangle + 29 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(18, 18, 4) \rangle \\ & + 1247 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(18, 17, 5) \rangle + 1768 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(18, 17, 3, 2) \rangle + 2735 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(18, 16, 6) \rangle + 416 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(18, 16, 4, 2) \rangle + 1009 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(18, 15, 7) \rangle + 130 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(18, 15, 5, 2) \rangle + 138 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(18, 14, 8) \rangle + 52 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(18, 14, 6, 2) \rangle + 2661 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(18, 13, 9) \rangle + 26 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(18, 13, 7, 2) \rangle + 731 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(18, 12, 10) \rangle \\ & + 16 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(18, 12, 8, 2) \rangle + 145 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(18, 11, 11) \rangle + 12 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(18, 11, 9, 2) \rangle + 818 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(18, 10, 8, 4) \rangle + 1728 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(18, 10, 8, 2, 2) \rangle + 2676 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(18, 10, 6, 6) \rangle + 1533 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(18, 10, 6, 4, 2) \rangle + 2490 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(18, 10, 6, 2, 2, 2) \rangle + 760 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(18, 10, 4, 4, 4) \rangle + 747 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(18, 10, 4, 4, 2, 2) \rangle \\ & + 2752 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(18, 10, 4, 2, 2, 2, 2, 2) \rangle + 83 \cdot \sum \langle \mathbf{F}, \bar{\mathbf{X}}(18, 10, 2, 2, 2, 2, 2, 2) \rangle + \text{easy terms} \mod 3001 \end{aligned} $$

which induces a PSM protocol with c.c. $O(N^{9.5})$.

### 3.3.4 When $k+1$ is a Prime Power

As shown in Section 3.3.1, to construct PSM protocol for $\text{Aux}_N^k$ with communication complexity $O_k(N^{\frac{k-1}{2}})$, it is sufficient to prove the target term is spanned by the referee-computable masked terms and easy 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 $\mathbb{F}_p$.

<footnote n="3">³The source code can be downloaded from https://github.com/tianren/psm.</footnote>
Proof. Consider the symmetric sum of all masked terms of shape {$k-1, 1, \dots, 1$}

$$
\begin{align}
& \sum \langle \mathbf{F}, \bar{\mathbf{X}}(k-1, \underbrace{1, \dots, 1}_{k+1 \text{ 1's}}) \rangle \nonumber \\
&= \sum_{i=0}^{k+1} \alpha(k-1, \underbrace{1, \dots, 1}_{k+1-i \text{ 1's}}) \cdot \sum \langle \mathbf{F}, \mathbf{R}(\underbrace{1, \dots, 1}_{i \text{ 1's}}) \rangle \nonumber \\
&\quad + \sum_{i=0}^{k+1} \alpha(\underbrace{1, \dots, 1}_{k+1-i \text{ 1's}}) \cdot \sum \langle \mathbf{F}, \mathbf{R}(k-1, \underbrace{1, \dots, 1}_{i \text{ 1's}}) \rangle \tag{3.12} \\
&= \alpha(k-1, \underbrace{1, \dots, 1}_{k+1 \text{ 1's}}) \cdot \sum \langle \mathbf{F}, \mathbf{R}(\underbrace{1, \dots, 1}_{i \text{ 1's}}) \rangle \nonumber \\
&\quad + \sum_{i=1}^{k-2} \alpha(k-1, \underbrace{1, \dots, 1}_{k+1-i \text{ 1's}}) \cdot \sum \langle \mathbf{F}, \mathbf{R}(\underbrace{1, \dots, 1}_{i \text{ 1's}}) \rangle + \text{easy terms.} \nonumber
\end{align}
$$

(Recall that a pure term of shape $P$ is easy iff $\sum(P) \ge k-1$.)

W.l.o.g. assume $k > 2$. By definition, $\alpha(k-1, \underbrace{1, \dots, 1}_{t \text{ 1's}}) = \binom{k-1+t}{k-1}$. Lemma 3.3.3 shows that $\alpha(k-1, \underbrace{1, \dots, 1}_{k+1 \text{ 1's}}) = \binom{2k}{k-1} \equiv 1 \mod p$, while $\alpha(k-1, \underbrace{1, \dots, 1}_{k+1-i \text{ 1's}}) = \binom{2k-i}{k-1}$ is a multiple of $p$ for all $1 \le i \le k-2$. Therefore,

$$
\sum \langle \mathbf{F}, \bar{\mathbf{X}}(k-1, \underbrace{1, \dots, 1}_{k+1 \text{ 1's}}) \rangle = \sum \langle \mathbf{F}, \mathbf{R}(\underbrace{1, \dots, 1}_{i \text{ 1's}}) \rangle + \text{easy terms} \mod p,
$$

which induces a $k$-party PSM protocol with c.c. $O_k(N^{\frac{k-1}{2}})$. $\square$

**Lemma 3.3.2.** For any prime $p$ and positive integer $e$, $\binom{p^e}{t}$ is a multiple of $p$ for all $0 < t < p^e$.

Proof.

$$
\binom{p^e}{t} = \frac{p^e}{t} \cdot \binom{p^e-1}{t-1}. \quad \square
$$

**Lemma 3.3.3.** For any prime $p$ and positive integer $e$, binomial coefficient $\binom{p^e+t}{p^e-2}$ is a multiple of $p$ for all $0 \le t \le p^e-3$, while binomial coefficient $\binom{2p^e-2}{p^e-2} \equiv 1 \mod p$.

Proof. For every $0 \le t \le p^e - 3$,

$$
\binom{p^e + t}{p^e - 2} = \sum_{j=0}^{t} \binom{t}{j} \underbrace{\binom{p^e}{p^e - 2 - j}}_{\text{multiple of } p}
$$

is a multiple of $p$. While

$$
\binom{2p^e - 2}{p^e - 2} = \sum_{j=0}^{p^e-3} \binom{p^e-2}{j} \underbrace{\binom{p^e}{p^e-2-j}}_{\text{multiple of } p} + \binom{p^e-2}{p^e-2} \binom{p^e}{0} \equiv 1 \quad \mod p. \quad \square
$$
## 3.4 Unbalanced 2-party PSM Protocols

The two parties in 2-party PSM are conventionally called Alice and Bob. Let $x \in [N]$ denote Alice's and $y \in [N]$ denote Bob's input. In this section, we show that every functionality $f : [N] \times [N] \to \{0, 1\}$ admits a 2-party PSM protocol, where Alice sends $O(N^\eta)$ bits and Bob sends $O(N^{1-\eta})$ bits.

**Theorem 3.4.1.** For any functionality $f : [N] \times [N] \to \{0, 1\}$, and any $\eta = d/k$ such that $d, k$ are integers and $0 < d < k \le 20$, there is a 2-party PSM protocol for $f$ with unbalanced communication complexity $O(N^\eta)$, $O(N^{1-\eta})$.

In this section, we prove a stronger statement. Let $\mathbb{F}$ be a finite field, consider the following auxiliary 2-party functionality $\text{Aux}_{k,N}^2$:

2-party functionality $\text{Aux}_{k,N}^2$

* Alice has input $\mathbf{x}_1, \dots, \mathbf{x}_k \in \mathbb{F}^{k/\sqrt{N}}$

* Bob has input $\mathbf{y}_1, \dots, \mathbf{y}_k \in \mathbb{F}^{k/\sqrt{N}}$

* The output is $\langle \mathbf{F}, \mathbf{x}_1 \otimes \dots \otimes \mathbf{x}_k \otimes \mathbf{y}_1 \otimes \dots \otimes \mathbf{y}_k \rangle$, where $\mathbf{F}$ is public and fixed

A PSM protocol for $\text{Aux}_{k,N}^2$ implies a PSM for $f : [N] \times [N] \to \{0, 1\}$ with the same communication complexity of each party. The reduction consists of having $\mathbf{F}$ be the truth table of $f$.

We present a framework for the construction of 2-party PSM protocols for $\text{Aux}_{k,N}^2$, where Alice sends $O_\eta(N^\eta)$ bits and Bob sends $O_\eta(N^{1-\eta})$ bits, for all $\eta \in \{\frac{1}{k}, \dots, \frac{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 $\eta$ whose denominator is no larger than 20. Backed by those observations, we believe that our framework allows for a smooth trade-off between the communication complexity of Alice and Bob:

**Conjecture 2.** For any functionality $f : [N] \times [N] \to \{0, 1\}$, and any $0 < \eta < 1$, there is a 2-party PSM protocol for $f$ with unbalanced communication complexity $O_\eta(N^\eta)$, $O_\eta(N^{1-\eta})$.

**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$.

### 3.4.1 A Framework for 2-party PSM

Consider a rational $\eta = \frac{d}{k} \in (0, 1)$. Let $\mathbb{F}$ be a finite commutative ring that we will fix later. All the operations are within ring $\mathbb{F}$ unless otherwise specified.
As mentioned in the beginning of Section 3.4, there is an non-interactive reduction from the functionality $f: [N] \times [N] \to \{0,1\}$ to functionality $\text{Aux}_{k,N}^2$. The reduction works as follows: Let $x, y \in [N]$ be the input of Alice and Bob respectively. Evenly divide $x$ into $x_1, \dots, x_k \in [\sqrt[k]{N}]$, similarly divide $y$ into $y_1, \dots, y_k \in [\sqrt[k]{N}]$. For each $j \in [k]$, let $\mathbf{x}_j := \mathbf{e}_{x_j} \in \mathbb{F}^{\sqrt[k]{N}}$ be the $x_j$-th standard unit vector. Similarly let $\mathbf{y}_i := \mathbf{e}_{y_i} \in \mathbb{F}^{\sqrt[k]{N}}$ for every $i \in [k]$. The functionality $f$ can be reduced to $\text{Aux}_{k,N}^2$ by doing:

$$f(x_1, \dots, x_k, y_1, \dots, y_k) = \langle \mathbf{F}, \mathbf{x}_1 \otimes \dots \otimes \mathbf{x}_k \otimes \mathbf{y}_1 \otimes \dots \otimes \mathbf{y}_k \rangle.$$

where $\mathbf{F}$ is the truth-table of $f$. For the remainder of the section, it is thus sufficient to construct a PSM protocol for $\text{Aux}_{k,N}^2$.

For every $\Omega \subseteq [k]$, our protocol will sample random $\mathbf{R}_\Omega, \mathbf{S}_\Omega \in \mathbb{F}^{(\sqrt[k]{N})^{|\Omega|}}$ from the common random string. Let $\bar{\mathbf{X}}_\Omega := \mathbf{R}_\Omega + \otimes_{i \in \Omega} \mathbf{x}_i$ and $\bar{\mathbf{Y}}_\Omega := \mathbf{S}_\Omega + \otimes_{i \in \Omega} \mathbf{y}_i$.

As the communication complexity of Alice is $O_\eta(N^{d/k})$, she can send $\bar{\mathbf{X}}_\Omega$ to the referee for every $\Omega$ that $|\Omega| \le d$. So far no information is leaked as $\bar{\mathbf{X}}_\Omega$ is one-time padded by $\mathbf{R}_\Omega$. Similarly, Bob can send $\bar{\mathbf{Y}}_\Omega$ for every $\Omega$ that $|\Omega| \le k-d$.

There are many meaningful terms that the referee can compute once he receives $(\bar{\mathbf{X}}_\Omega)|_{\Omega|\le d}$ and $(\bar{\mathbf{Y}}_\Omega)|_{\Omega|\le k-d}$. For example, when $\eta = d/k = 1/3$, the referee can compute:

$$ \begin{aligned} & \langle \mathbf{F}, \bar{\mathbf{X}}_{\{1\}} \otimes \bar{\mathbf{X}}_{\{2\}} \otimes \bar{\mathbf{X}}_{\{3\}} \otimes \bar{\mathbf{Y}}_{\{1,2\}} \otimes \bar{\mathbf{Y}}_{\{3\}} \rangle \\ &= \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{x}_3 \otimes \mathbf{y}_1 \otimes \mathbf{y}_2 \otimes \mathbf{y}_3 \rangle \\ & \quad + \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{x}_3 \otimes \mathbf{y}_1 \otimes \mathbf{y}_2 \otimes \mathbf{S}_{\{3\}} \rangle \\ & \quad + \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{x}_3 \otimes \mathbf{S}_{\{1,2\}} \otimes \mathbf{S}_{\{3\}} \rangle \\ & \quad + \dots \quad (28 \text{ other terms}) \\ & \quad + \langle \mathbf{F}, \mathbf{R}_{\{1\}} \otimes \mathbf{R}_{\{2\}} \otimes \mathbf{R}_{\{3\}} \otimes \mathbf{S}_{\{1,2\}} \otimes \mathbf{S}_{\{3\}} \rangle. \end{aligned} \quad (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 $\bar{\mathbf{X}}_{\Omega_1} \otimes \dots \otimes \bar{\mathbf{X}}_{\Omega_t}$ such that $\Omega_1, \dots, \Omega_t$ are disjoint and their union equals $[k]$. The shape of an Alice-side masked tensor $\bar{\mathbf{X}}_{\Omega_1} \otimes \dots \otimes \bar{\mathbf{X}}_{\Omega_t}$ is the multiset $\{|\Omega_1|, \dots, |\Omega_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 $\mathbf{F}$ and a masked tensor is called a *masked term*.

An Alice-side masked tensor of shape $P$ is referee-computable if $\max(P) \le d$. A Bob-side masked tensor of shape $Q$ is referee-computable if $\max(Q) \le 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 Bob-side masked tensor.

**Definition (pure tensor & pure term).** An Alice-side pure tensor is a tensor product $\mathbf{R}_{\Omega_1} \otimes \dots \otimes \mathbf{R}_{\Omega_t} \otimes \mathbf{x}_{i_1} \otimes \dots \otimes \mathbf{x}_{i_w}$ such that $\{i_1, \dots, i_w\}, \Omega_1, \dots, \Omega_t$ are disjoint and their union equals $[k]$. The shape of an Alice-side masked tensor $\mathbf{R}_{\Omega_1} \otimes \dots \otimes \mathbf{R}_{\Omega_t} \otimes \mathbf{x}_{i_1} \otimes \dots \otimes \mathbf{x}_{i_w}$ is the multiset $\{|\Omega_1|, \dots, |\Omega_t|\}$. Bob-side pure tensors are defined symmetrically.

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 $\mathbf{F}$ is called a *pure term*.
For any legit shape, let $\sum \mathbf{R}(P)$ denote the sum of all Alice-side pure tensor whose shape is $P$. Similarly, define Bob-side pure tensor sum $\sum \mathbf{S}(P)$.

Let's go back to the example when $\eta = 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 $\langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{x}_3 \otimes \mathbf{y}_1 \otimes \mathbf{y}_2 \otimes \mathbf{y}_3 \rangle$ is the desired functionality.

* The term $\langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{x}_3 \otimes \mathbf{S}_{\{1,2\}} \otimes \mathbf{y}_3 \rangle$ has a PSM protocol with communication complexity $O(N^{1/3})$. Because Alice knows a vector $\mathbf{g}$ (which is determined by $\mathbf{F}$, Alice's input and randomness $(\mathbf{R}_{\Omega})_{\Omega}$, $(\mathbf{S}_{\Omega})_{\Omega}$) such that $\langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{x}_3 \otimes \mathbf{S}_{\{1,2\}} \otimes \mathbf{y}_3 \rangle = \langle \mathbf{g}, \mathbf{y}_3 \rangle$.

* The term $\langle \mathbf{F}, \mathbf{S}_{\{1\}} \otimes \mathbf{x}_2 \otimes \mathbf{x}_3 \otimes \mathbf{y}_1 \otimes \mathbf{y}_2 \otimes \mathbf{y}_3 \rangle$ admits a PSM protocol with unbalanced communication complexity $O(N^{1/3})$, $O(N^{2/3})$. Because Bob knows a dimension-2 tensor $\mathbf{G}$ such that $\langle \mathbf{F}, \mathbf{S}_{\{1\}} \otimes \mathbf{x}_2 \otimes \mathbf{x}_3 \otimes \mathbf{y}_1 \otimes \mathbf{y}_2 \otimes \mathbf{y}_3 \rangle = \langle \mathbf{x}_2 \otimes \mathbf{x}_3, \mathbf{G} \rangle$. (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 $\mathbf{x}_1 \otimes \cdots \otimes \mathbf{x}_k$. The only Bob-side target tensor is $\mathbf{y}_1 \otimes \cdots \otimes \mathbf{y}_k$. The only target tensor is $\mathbf{x}_1 \otimes \cdots \otimes \mathbf{x}_k \otimes \mathbf{y}_1 \otimes \cdots \otimes \mathbf{y}_k$.

**easy tensor** An Alice-side pure tensor of shape $P$ is called easy if $\text{sum}(P) \ge d$. A Bob-side pure tensor of shape $Q$ is called easy if $\text{sum}(Q) \ge k-d$. A pure tensor $\mathbf{R} \otimes \mathbf{S}$ is called easy if either $\mathbf{R}$ or $\mathbf{S}$ is easy.

**hard tensor** The rest.

The inner product of $\mathbf{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:

$$ \begin{aligned} & \langle \mathbf{F}, \bar{\mathbf{X}}_{\{1\}} \otimes \bar{\mathbf{X}}_{\{2\}} \otimes \bar{\mathbf{X}}_{\{3\}} \otimes \bar{\mathbf{Y}}_{\{1,2\}} \otimes \bar{\mathbf{Y}}_{\{3\}} \rangle \\ & = \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{x}_3 \otimes \mathbf{y}_1 \otimes \mathbf{y}_2 \otimes \mathbf{y}_3 \rangle \\ & \quad + \langle \mathbf{F}, \mathbf{x}_1 \otimes \mathbf{x}_2 \otimes \mathbf{x}_3 \otimes \mathbf{y}_1 \otimes \mathbf{y}_2 \otimes \mathbf{S}_{\{3\}} \rangle + \text{easy terms} \end{aligned} $$

By a symmetric sum, we get

$$ \begin{aligned} & \langle \mathbf{F}, \sum \bar{\mathbf{X}}(1, 1, 1) \otimes \sum \bar{\mathbf{Y}}(2, 1) \rangle \\ & = 3 \cdot \underbrace{\langle \mathbf{F}, \sum \mathbf{R}(\cdot) \otimes \sum \mathbf{S}(\cdot) \rangle}_{\text{target}} + \langle \mathbf{F}, \sum \mathbf{R}(\cdot) \otimes \sum \mathbf{S}(1) \rangle + \text{easy terms.} \end{aligned} $$

Similarly, we have decomposed another referee-computable term

$$ \begin{aligned} & \langle \mathbf{F}, \sum \bar{\mathbf{X}}(1, 1, 1) \otimes \sum \bar{\mathbf{Y}}(1, 1, 1) \rangle \\ & = \underbrace{\langle \mathbf{F}, \sum \mathbf{R}(\cdot) \otimes \sum \mathbf{S}(\cdot) \rangle}_{\text{target}} + \langle \mathbf{F}, \sum \mathbf{R}(\cdot) \otimes \sum \mathbf{S}(1) \rangle + \text{easy terms.} \end{aligned} $$

Combine them to cancel out the hard terms:

$$ \begin{aligned} & \langle \mathbf{F}, \sum \bar{\mathbf{X}}(1, 1, 1) \otimes \sum \bar{\mathbf{Y}}(2, 1) \rangle - \langle \mathbf{F}, \sum \bar{\mathbf{X}}(1, 1, 1) \otimes \sum \bar{\mathbf{Y}}(1, 1, 1) \rangle \\ & = 2 \cdot \langle \mathbf{F}, \sum \mathbf{R}(\cdot) \otimes \sum \mathbf{S}(\cdot) \rangle + \text{easy terms.} \end{aligned} $$
Thus, by setting $\mathbb{F}$ to be any finite field where $2 \neq 0$, the above equation induces a 2-party PSM protocol with unbalanced communication complexity $O(N^{\frac{1}{3}})$, $O(N^{\frac{2}{3}})$.

In general, a masked term $\langle \mathbf{F}, \sum \bar{\mathbf{X}}(P) \otimes \sum \bar{\mathbf{Y}}(Q) \rangle$ can be decomposed into pure terms by

$$ \sum \bar{\mathbf{X}}(P) = \sum_{P' \subseteq P} \alpha(P') \sum \bar{\mathbf{X}}(P \setminus P'), $$

$$ \sum \bar{\mathbf{Y}}(Q) = \sum_{Q' \subseteq Q} \alpha(Q') \sum \bar{\mathbf{Y}}(Q \setminus Q'), $$

$$ \langle \mathbf{F}, \sum \bar{\mathbf{X}}(P) \otimes \sum \bar{\mathbf{Y}}(Q) \rangle = \sum_{\substack{P' \subseteq P \\ Q' \subseteq Q}} \alpha(P') \alpha(Q') \langle \mathbf{F}, \sum \bar{\mathbf{X}}(P \setminus P') \otimes \sum \bar{\mathbf{Y}}(Q \setminus Q') \rangle. $$

with the combinatoric number $\alpha$ 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,

$$ \textit{the target term} = \textit{a linear combination of referee-computable masked terms} + \textit{a linear combination of easy terms.} \qquad (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 $\eta$. 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,

$$ \textit{a linear combination of referee-computable Alice-side masked tensors} \\ = \sum \mathbf{R}(\cdot) + \textit{Alice-side easy tensors}, $$

$$ \textit{a linear combination of referee-computable Bob-side masked tensors} \\ = \sum \mathbf{S}(\cdot) + \textit{Bob-side easy tensors}. $$

The tensor product of the above two equations is

$$ \textit{a linear combination of referee-computable masked tensors} \\ = \sum \mathbf{R}(\cdot) \otimes \sum \mathbf{S}(\cdot) + \textit{a linear combination of easy tensors}. $$

Multiplying both sides of the above equation with $\mathbf{F}$ yields the desired sufficient condition of form (3.14).
### 3.4.2 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 $\bar{\mathbf{Z}}^{(1)}, \dots, \bar{\mathbf{Z}}^{(s)}$, easy pure terms $\mathbf{T}^{(1)}, \dots, \mathbf{T}^{(s)}$, and coefficients $a_1, \dots, a_t, b_1, \dots, b_s \in \mathbb{F}$ such that

$$ \langle \mathbf{F}, \mathbf{x}_1 \otimes \dots \otimes \mathbf{x}_k \otimes \mathbf{y}_1 \otimes \dots \otimes \mathbf{y}_k \rangle = \sum_{j=1}^{t} a_j \bar{\mathbf{Z}}^{(j)} + \sum_{j=1}^{s} b_j \mathbf{T}^{(j)}. \quad (3.15) $$

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

* Fact I: $\sum_{j=1}^{s} b_j \mathbf{T}^{(j)}$ together with $\bar{\mathbf{X}}_{\Omega}$ for all $0 < |\Omega| \le d$ and $\bar{\mathbf{Y}}_{\Omega}$ for all $0 < |\Omega| \le k-d$ form a randomized encoding of the functionality output.

* Fact II: There is a PSM protocol for $\sum_{j=1}^{s} b_j \mathbf{T}^{(j)}$, in which Alice sends $k \cdot s \cdot N^{\frac{d}{k}}$ field elements, Bob sends $k \cdot s \cdot N^{1-\frac{d}{k}}$ field elements.

The 2-party PSM for $f$ works as the follows: For each $\Omega \subseteq [k]$ such that $0 < |\Omega| \le d$, Alice sends $\bar{\mathbf{X}}_{\Omega}$ to the referee. Symmetrically, for $\Omega \subseteq [k]$ such that $0 < |\Omega| \le k-d$, Bob sends $\bar{\mathbf{Y}}_{\Omega}$ to the referee. Use the PSM guaranteed by Fact II to reveal $\sum_{j=1}^{s} b_j \mathbf{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 $\langle \mathbf{F}, \mathbf{x}_1 \otimes \dots \otimes \mathbf{x}_k \otimes \mathbf{y}_1 \otimes \dots \otimes \mathbf{y}_k \rangle$ can be computed from the encoding. Moreover, the distribution of the encoding is perfectly simulatable: The joint distribution of tensors $\bar{\mathbf{X}}_{\Omega}$ for $0 < |\Omega| \le d$ and $\bar{\mathbf{Y}}_{\Omega}$ for $0 < |\Omega| \le k-d$ is uniform, as they are independently one-time padded. Then the value of $\sum_{j=1}^{s} b_j \mathbf{T}^{(j)}$ is uniquely determined by Equation (3.15).

**Proof of Fact II.** Sample random $c_1, \dots, c_s \in \mathbb{F}$ from the common random string such that $c_1 + \dots + c_s = 0$. Then it's sufficient to construct a PSM protocol for computing $b_j \mathbf{T}^{(j)} + c_j$ for each $j$.

Because $\mathbf{T}^{(j)}$ is an easy term, we have $\mathbf{T}^{(j)} = \langle \mathbf{F}, \mathbf{R}^{(j)} \otimes \mathbf{S}^{(j)} \rangle$, where $\mathbf{R}^{(j)}$ is an Alice-side pure tensor, $\mathbf{S}^{(j)}$ is a Bob-side pure tensor, and either $\mathbf{R}^{(j)}$ is an Alice-side easy tensor, $\mathbf{S}^{(j)}$ is a Bob-side easy tensor. W.l.o.g., assume $\mathbf{R}^{(j)}$ is an Alice-side easy tensor.

Say this Alice-side easy pure term $\mathbf{R}^{(j)}$ is $\mathbf{R}_{\Omega_1} \otimes \dots \otimes \mathbf{x}_{i_1} \otimes \dots \otimes \mathbf{x}_{i_w}$. By the definition of an Alice-side easy term, $w \le k-d$. Then Bob knows a dimension-$w$ tensor $\mathbf{G}$ (which is determined by $\mathbf{S}^{(j)}, b_j, \mathbf{R}_{\Omega_1}, \mathbf{R}_{\Omega_2}, \dots$) such that

$$ b_j \mathbf{T}^{(j)} + c_j = \langle \mathbf{G}, \mathbf{x}_{i_1} \otimes \dots \otimes \mathbf{x}_{i_w} \rangle + c_j, $$

which admits a PSM protocol (presented in Section A.2.2) in which Alice sends $O(w \cdot N^{1/k})$ field elements, Bob sends $N^{w/k}$ field elements.
### 3.4.3 When $\eta$ 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 $\eta \in (0, 1)$ whose denominator is no larger than 20. Theorem 3.4.1 follows as a consequence.

For $\eta = 1/3$, the 2-party PSM protocol in Section 3.4.1 is also induced by

$$ \begin{aligned} \sum \bar{X}(1, 1, 1) &= \sum \mathbf{R}(1) + \text{Alice-side easy tensors,} \\ \sum \bar{Y}(2, 1) - \sum \bar{Y}(1, 1, 1) &= 2 \cdot \sum \mathbf{S}(1) + \text{Bob-side easy tensors.} \end{aligned} $$

For $\eta = 1/4$, a 2-party PSM protocol with c.c. $O(N^{1/4})$, $O(N^{3/4})$ is induced by

$$ \begin{aligned} \sum \bar{X}(1, 1, 1, 1) &= \sum \mathbf{R}(1) + \text{Alice-side easy tensors,} \\ \sum \bar{Y}(1, 1, 1, 1) + 2 \cdot \sum \bar{Y}(3, 1) \\ &\quad + \sum \bar{Y}(2, 2) - \sum \bar{Y}(2, 1, 1) = 6 \cdot \sum \mathbf{S}(1) + \text{Bob-side easy tensors.} \end{aligned} $$

For $\eta = 1/5$, a 2-party PSM protocol with desired c.c. is induced by

$$ \begin{aligned} \sum \bar{X}(1, 1, 1, 1) &= \sum \mathbf{R}(1) + \text{Alice-side easy tensors,} \\ 6 \cdot \sum \bar{Y}(4, 1) + 2 \cdot \sum \bar{Y}(3, 2) \\ &\quad - 2 \cdot \sum \bar{Y}(3, 1, 1) - \sum \bar{Y}(2, 2, 1) \\ &\quad + \sum \bar{Y}(2, 1, 1, 1) - \sum \bar{Y}(1, 1, 1, 1, 1) = 24 \cdot \sum \mathbf{S}(1) + \text{Bob-side easy tensors.} \end{aligned} $$

For $\eta = 2/5$, a 2-party PSM protocol with desired c.c. is induced by

$$ \begin{aligned} 2 \cdot \sum \bar{X}(2, 2, 1) - \sum \bar{X}(2, 1, 1, 1) &= 20 \cdot \sum \mathbf{R}(1) + \text{Alice-side easy tensors,} \\ 3 \cdot \sum \bar{Y}(3, 2) + \sum \bar{Y}(3, 1, 1) \\ &\quad - \sum \bar{Y}(2, 2, 1) - \sum \bar{Y}(1, 1, 1, 1, 1) = 24 \cdot \sum \mathbf{S}(1) + \text{Bob-side easy tensors.} \end{aligned} $$

For larger denominators, we wrote a computer program<fnref n="4" /> to assist us in the proof. For example, for $\eta = 7/20$, a 2-party PSM with desired c.c. is induced by

$\Sigma \mathbf{R}(1) = \text{Alice-side easy tensors} + 18 \cdot \Sigma \bar{X}(7, 7, 6) + 10 \cdot \Sigma \bar{X}(7, 7, 5, 1) + 14 \cdot \Sigma \bar{X}(7, 7, 4, 2) + 14 \cdot \Sigma \bar{X}(7, 7, 4, 1, 1) + 17 \cdot \Sigma \bar{X}(7, 7, 3, 3) + 20 \cdot \Sigma \bar{X}(7, 7, 3, 2, 1) + 20 \cdot \Sigma \bar{X}(7, 7, 3, 1, 1, 1) + 10 \cdot \Sigma \bar{X}(7, 7, 2, 2, 2) + 10 \cdot \Sigma \bar{X}(7, 7, 2, 2, 1, 1) + 10 \cdot \Sigma \bar{X}(7, 7, 1, 1, 1, 1, 1) + 6 \cdot \Sigma \bar{X}(7, 6, 6, 1) + 19 \cdot \Sigma \bar{X}(7, 6, 5, 2) + 19 \cdot \Sigma \bar{X}(7, 6, 5, 1, 1) + 21 \cdot \Sigma \bar{X}(7, 6, 4, 3) + 22 \cdot \Sigma \bar{X}(7, 6, 4, 2, 1) + 22 \cdot \Sigma \bar{X}(7, 6, 4, 1, 1, 1) + 7 \cdot \Sigma \bar{X}(7, 6, 3, 3, 1) + 15 \cdot \Sigma \bar{X}(7, 6, 3, 2, 2) + 15 \cdot \Sigma \bar{X}(7, 6, 3, 2, 1, 1) + 15 \cdot \Sigma \bar{X}(7, 6, 3, 1, 1, 1, 1) + 19 \cdot \Sigma \bar{X}(7, 6, 2, 2, 2, 1) + 19 \cdot \Sigma \bar{X}(7, 6, 2, 2, 1, 1, 1) + 19 \cdot \Sigma \bar{X}(7, 6, 2, 1, 1, 1, 1, 1) + 19 \cdot \Sigma \bar{X}(7, 6, 1, 1, 1, 1, 1, 1, 1) \mod 23 $$

$\Sigma \mathbf{S}(1) = \text{Bob-side easy tensors} + 13 \cdot \Sigma \bar{Y}(13, 7) + 20 \cdot \Sigma \bar{Y}(13, 6, 1) + 2 \cdot \Sigma \bar{Y}(13, 5, 2) + 22 \cdot \Sigma \bar{Y}(13, 5, 1, 1) + 1 \cdot \Sigma \bar{Y}(13, 4, 3) + 17 \cdot \Sigma \bar{Y}(13, 4, 2, 1) + 3 \cdot \Sigma \bar{Y}(13, 4, 1, 1, 1) + 19 \cdot \Sigma \bar{Y}(13, 3, 3, 1) + 21 \cdot \Sigma \bar{Y}(13, 3, 2, 2) + 1 \cdot \Sigma \bar{Y}(13, 3, 2, 1) + 11 \cdot \Sigma \bar{Y}(13, 3, 1, 1, 1, 1) + 12 \cdot \Sigma \bar{Y}(13, 2, 2, 2, 1) + 17 \cdot \Sigma \bar{Y}(13, 2, 2, 1, 1, 1) + 3 \cdot \Sigma \bar{Y}(13, 2, 1, 1, 1, 1) + 10 \cdot \Sigma \bar{Y}(13, 1, 1, 1, 1, 1, 1, 1) + 11 \cdot \Sigma \bar{Y}(12, 8) + 17 \cdot \Sigma \bar{Y}(12, 7, 1) + 1 \cdot \Sigma \bar{Y}(12, 6, 2) + 11 \cdot \Sigma \bar{Y}(12, 6, 1, 1) + 17 \cdot \Sigma \bar{Y}(11, 9) + 14 \cdot \Sigma \bar{Y}(11, 8, 1) + 6 \cdot \Sigma \bar{Y}(11, 7, 2) + 20 \cdot \Sigma \bar{Y}(11, 7, 1, 1) + 7 \cdot \Sigma \bar{Y}(11, 6, 3) + 4 \cdot \Sigma \bar{Y}(11, 6, 2, 1) + 21 \cdot \Sigma \bar{Y}(11, 6, 1, 1, 1) + 2 \cdot \Sigma \bar{Y}(10, 10) + 4 \cdot \Sigma \bar{Y}(10, 9, 1) + 15 \cdot \Sigma \bar{Y}(10, 8, 2) + 4 \cdot \Sigma \bar{Y}(10, 8, 1, 1) + 1 \cdot \Sigma \bar{Y}(10, 7, 3) + 17 \cdot \Sigma \bar{Y}(10, 7, 2, 1) + 3 \cdot \Sigma \bar{Y}(10, 7, 1, 1, 1) + 21 \cdot \Sigma \bar{Y}(10, 6, 4) + 8 \cdot \Sigma \bar{Y}(10, 6, 3, 1) + 4 \cdot \Sigma \bar{Y}(10, 6, 2, 2) + 21 \cdot \Sigma \bar{Y}(10, 6, 2, 1, 1) + 1 \cdot \Sigma \bar{Y}(10, 6, 1, 1, 1, 1) + 20 \cdot \Sigma \bar{Y}(9, 9, 2) + 13 \cdot \Sigma \bar{Y}(9, 9, 1, 1) + 4 \cdot \Sigma \bar{Y}(9, 8, 3) + 22 \cdot \Sigma \bar{Y}(9, 8, 2, 1) + 12 \cdot \Sigma \bar{Y}(9, 8, 1, 1, 1) + 14 \cdot \Sigma \bar{Y}(9, 7, 4) + 13 \cdot \Sigma \bar{Y}(9, 7, 3, 1) + 18 \cdot \Sigma \bar{Y}(9, 7, 2, 2) + 14 \cdot \Sigma \bar{Y}(9, 7, 2, 1, 1) + 16 \cdot \Sigma \bar{Y}(9, 7, 1, 1, 1, 1) + 11 \cdot \Sigma \bar{Y}(9, 6, 5) + 13 \cdot \Sigma \bar{Y}(9, 6, 4, 1) + 12 \cdot \Sigma \bar{Y}(9, 6, 3, 2) + 17 \cdot \Sigma \bar{Y}(9, 6, 3, 1, 1) + 20 \cdot \Sigma \bar{Y}(9, 6, 2, 2, 1) + 13 \cdot \Sigma \bar{Y}(9, 6, 2, 1, 1, 1) + 5 \cdot \Sigma \bar{Y}(9, 6, 1, 1, 1, 1, 1) + 19 \cdot \Sigma \bar{Y}(8, 8, 4) + 16 \cdot \Sigma \bar{Y}(8, 8, 3, 1) + 8 \cdot \Sigma \bar{Y}(8, 8, 2, 2) + 19 \cdot \Sigma \bar{Y}(8, 8, 2, 1, 1) + 2 \cdot \Sigma \bar{Y}(8, 8, 1, 1, 1, 1) + 17 \cdot \Sigma \bar{Y}(8, 7, 5) + 18 \cdot \Sigma \bar{Y}(8, 7, 4, 1) + 6 \cdot \Sigma \bar{Y}(8, 7, 3, 2) + 20 \cdot \Sigma \bar{Y}(8, 7, 3, 1, 1) + 10 \cdot \Sigma \bar{Y}(8, 7, 2, 2, 1) + 18 \cdot \Sigma \bar{Y}(8, 7, 2, 1, 1, 1) + 14 \cdot \Sigma \bar{Y}(8, 7, 1, 1, 1, 1, 1) + 18 \cdot \Sigma \bar{Y}(8, 6, 6) + 6 \cdot \Sigma \bar{Y}(8, 6, 5, 1) + 13 \cdot \Sigma \bar{Y}(8, 6, 4, 2) + 5 \cdot \Sigma \bar{Y}(8, 6, 4, 1, 1) + 1 \cdot \Sigma \bar{Y}(8, 6, 3, 3) + 17 \cdot \Sigma \bar{Y}(8, 6, 3, 2, 1) + 3 \cdot \Sigma \bar{Y}(8, 6, 3, 1, 1, 1) + 20 \cdot \Sigma \bar{Y}(8, 6, 2, 2, 2) + 13 \cdot \Sigma \bar{Y}(8, 6, 2, 2, 1, 1) + 5 \cdot \Sigma \bar{Y}(8, 6, 2, 1, 1, 1, 1) + 9 \cdot \Sigma \bar{Y}(8, 6, 1, 1, 1, 1, 1, 1) + 5 \cdot \Sigma \bar{Y}(7, 7, 6) + 1 \cdot \Sigma \bar{Y}(7, 7, 5, 1) + 6 \cdot \Sigma \bar{Y}(7, 7, 4, 2) + 20 \cdot \Sigma \bar{Y}(7, 7, 4, 1, 1) + 4 \cdot \Sigma \bar{Y}(7, 7, 3, 3) + 22 \cdot \Sigma \bar{Y}(7, 7, 3, 2, 1) + 12 \cdot \Sigma \bar{Y}(7, 7, 3, 1, 1, 1) + 11 \cdot \Sigma \bar{Y}(7, 7, 2, 2, 2) + 6 \cdot \Sigma \bar{Y}(7, 7, 2, 2, 1, 1, 1) + 20 \cdot \Sigma \bar{Y}(7, 7, 2, 1, 1, 1, 1) + 13 \cdot \Sigma \bar{Y}(7, 7, 1, 1, 1, 1, 1) + 15 \cdot \Sigma \bar{Y}(7, 6, 6, 1) + 13 \cdot \Sigma \bar{Y}(7, 6, 5, 2) + 5 \cdot \Sigma \bar{Y}(7, 6, 5, 1, 1) + 18 \cdot \Sigma \bar{Y}(7, 6, 4, 3) + 7 \cdot \Sigma \bar{Y}(7, 6, 4, 2, 1) + 8 \cdot \Sigma \bar{Y}(7, 6, 4, 1, 1, 1) + 20 \cdot \Sigma \bar{Y}(7, 6, 3, 3, 1) + 10 \cdot \Sigma \bar{Y}(7, 6, 3, 2, 2) + 18 \cdot \Sigma \bar{Y}(7, 6, 3, 2, 1, 1) + 14 \cdot \Sigma \bar{Y}(7, 6, 3, 1, 1, 1, 1) + 9 \cdot \Sigma \bar{Y}(7, 6, 2, 2, 2, 1) + 7 \cdot \Sigma \bar{Y}(7, 6, 2, 2, 1, 1, 1) + 8 \cdot \Sigma \bar{Y}(7, 6, 2, 1, 1, 1, 1, 1) + 19 \cdot \Sigma \bar{Y}(7, 6, 1, 1, 1, 1, 1, 1) \mod 23 $$

We checked every rational $\eta = d/k$ such that $k \le 20$, and verified that our framework does in fact yield a 2-party PSM protocol with unbalanced communication complexity $O(N^\eta)$, $O(N^{1-\eta})$.

<footnote n="4">⁴The source code can be downloaded from https://github.com/tianren/psm.</footnote>
**3.5 Open Problems**

This chapter presents two frameworks: a framework for constructing $k$-party PSM protocols for general $f : [N]^k \to \{0, 1\}$ with c.c. $O_k(N^{\frac{k-1}{2}})$, and a framework for constructing 2-party PSM protocols for general $f : [N] \times [N] \to \{0, 1\}$ where one party sends $O_\eta(N^\eta)$ bits and the other party sends $O_\eta(N^{1-\eta})$ bits. An immediate open problem is to prove our frameworks work for all integer $k$ and all rational $\eta$. Currently, we can only prove it works for some $k$ and $\eta$.

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) \cdot N^{\frac{k-1}{2}}$. While [BKN18] achieves communication complexity $\text{poly}(k) \cdot N^{\frac{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^{\frac{k}{2}-1})$, when $k$ is sufficiently large? Can our 2-party framework yield PSM protocol with communication $O_\eta(N^\eta)$ for some rational $\eta < \frac{1}{2}$? Our technique transfers such questions into some linear systems. Each question has an affirmative answer (for a given $k$ or $\eta$) 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^{\frac{k-1}{2}})$ bits. A variant of [FKN94] provides a $k$-party PSM protocol where the $i$-th party sends $\tilde{O}_k(N^{i-1})$ bits, whose geometric average is $\tilde{O}_k(N^{\frac{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.
Publication

This work was in an article published at the Theory of Cryptography Conference 2021,
under the following title [AL21]:

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

by Léonard Assouline and Tianren Liu.

In Kobbi Nissim and Brent Waters, editors, Theory of Cryptography, pages 194–223
# Weighted ORAM with Applications to SSE

## 4.1 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 [GLMP19]; 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 [GO96], 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,
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 Ω(*λ*²) bits, but its overhead
is O(log² *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 [CGPR15, GLMP19]. Those attacks
have in turn motivated SSE approaches that rely on ORAM [GMP16, KMO18].

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 [MR22]. 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 [CGPR15]. 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 [GLMP18]. Traffic analysis attacks are another
example of using length information to infer sensitive data [DCRS12]. 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
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 $\text{Polylog}(N/U)$, or optimally, $\log(N/U)$.

### 4.1.1 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 \in [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* $\sum_{i \le m} w_i$. We want to build an ORAM that can accommodate *any* vector $\mathbf{w} = (w_i)_{i \le 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 $\sum 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 $\mathbf{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 [CP13]. 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 [KMO18], 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 length-hiding 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].

### 4.1.2 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 [RAC16], 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.
* 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 [RAC16]. 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 [RAC16] 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.

### 4.1.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.

## 4.2 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 $\lambda$. A quantity is said to be *negligible*, denoted $\text{negl}(\lambda)$, if it is $O(\lambda^{-c})$ for every constant $c$. A probability is said to be *overwhelming* if it is $1 - \text{negl}(\lambda)$. It is always assumed that the number of blocks $n$ stored in the ORAM satisfies $n \ge \lambda$, so that any quantity that is $\text{negl}(n)$ is also $\text{negl}(\lambda)$.

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)$.

### 4.2.1 Majorization and Schur Convexity

Given a vector $v$ in $\mathbb{R}^m$, we denote by $v^\downarrow \in \mathbb{R}^m$ the vector with the same components, sorted in decreasing order.
**Definition 3 (Majorization order).** Let $\mathbf{v}$, $\mathbf{w}$ be two vectors in $\mathbb{R}^m$ such that $\sum_{i=1}^m v_i = \sum_{i=1}^m w_i$. The vector $\mathbf{w}$ is said to majorize $\mathbf{v}$, written $\mathbf{v} \prec \mathbf{w}$, if:

$$ \forall k \in [1, m], \quad \sum_{i=1}^{k} v_i^{\downarrow} \le \sum_{i=1}^{k} w_i^{\downarrow}. $$

**Definition 4 (Schur convexity).** Let $f: \mathbb{R}^m \to \mathbb{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 $\mathbf{v}, \mathbf{w}$ with $\sum_{i=1}^m v_i = \sum_{i=1}^m w_i$,

$$ \mathbf{v} \prec \mathbf{w} \Rightarrow f(\mathbf{v}) \le f(\mathbf{w}). $$

**Definition 5 (Convexity).** Let $f: \mathbb{R}^m \to \mathbb{R}$. The map $f$ is said to be *convex* if for any two vectors $\mathbf{v}, \mathbf{w}$ in $\mathbb{R}^m$, and any $\alpha \in [0, 1] \subset \mathbb{R}$, it holds that:

$$ f(\alpha \mathbf{v} + (1 - \alpha) \mathbf{w}) \le \alpha f(\mathbf{v}) + (1 - \alpha) f(\mathbf{w}). $$

**Definition 6 (Symmetry).** Let $f: \mathbb{R}^m \to \mathbb{R}$. The map $f$ is said to be *symmetric* if for any vector $\mathbf{v} \in \mathbb{R}^m$, and any permutation matrix $P$ over $m$ elements, $f(\mathbf{v}) = f(P\mathbf{v})$.

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

**Lemma 4.2.1.** Let $f: \mathbb{R}^m \to \mathbb{R}$. If $f$ is symmetric and convex, then it is Schur-convex.

We refer the reader to [MOA79] for a detailed presentation of the theory of majorization, including a proof of Lemma 4.2.1.

## 4.3 ORAM Preliminaries

### 4.3.1 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| \in [1, B]$. Setup outputs an initial client state and initial server state.

* Access(op, a, data) takes as input an operation $op \in \{\text{read, write}\}$, an address $a$, and some data $data$ of size $|data| \in [1, B]$. If $op = \text{read}$, Access outputs to the client the data last written to address $a$. If $op = \text{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 = \text{write}$, if $|data| \in [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$.