Notice bibliographique
Résumé
Finding the Minimum Spanning Tree or Forest (MSF) of a weighted graph is one of the most fundamental graph problems. It has many applications, and there are various algorithms to solve it in quasi-linear time. However, in a secure computation setting where the graph is shared between multiple parties, there are no fully satisfactory solutions. Any prior work on this problem either builds a circuit that is fed into a generic multi-party computation protocol, or is limited to graphs that have a unique MSF. In this work, we first identify privacy and fairness issues that arise when the MSF is not necessarily unique, i.e., there exist duplicate edge weights. Subsequently, we consider the notion of a Random Minimum Spanning Forest, which defines a distribution of the desired output in the case where multiple MSFs exist. We carefully design a protocol for this problem in the semi-honest security model. The main insight of our protocol is that we may reveal certain intermediate results over the entire course of the protocol execution (provably without impacting security), which are then used to make decisions that optimize efficiency. No party learns anything about the inputs of other parties except for the produced MSF, not even the number of input edges. Furthermore, the number of communication rounds is low for many typical graphs, which allows running the protocol even when the network latency is high. Our evaluation shows that, depending on the graph structure and its weight distribution, our protocol can outperform the previous baseline by Laud (PoPETs 2015) by up to 2-3 orders of magnitude in terms of running time. From another perspective, this work exposes some disadvantages of using generic compilers to obtain MPC protocols, as their efficiency always equal that of the worst-case input. Our techniques show that even within the context of MPC, it is possible to obtain a secure protocol whose running time is not fixed a-priori, but instead determined by the output that is not known in advance. By carefully studying the desired functionality, this allows for significant efficiency improvements for any realistic inputs.
Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.
Comment cette classification a été obtenuedéplier
Prédiction distillée sur la base complète
Imitation des enseignantsNi prévalence calibrée, ni vérité terrain. Validation humaine à venir. Apprise à partir de 10 348 étiquettes directes de Codex et de 10 348 étiquettes directes de Gemma. Le mode candidate est l'union des têtes enseignantes seuillées; le consensus est leur intersection. Ces sorties portent le statut machine_predicted_unvalidated et ne sont ni des étiquettes humaines ni des étiquettes directes de modèles de pointe.
Scores Codex et Gemma par catégorie
| Catégorie | Codex | Gemma |
|---|---|---|
| Métarecherche | 0,001 | 0,003 |
| Méta-épidémiologie (sens strict) | 0,000 | 0,000 |
| Méta-épidémiologie (sens large) | 0,000 | 0,000 |
| Bibliométrie | 0,001 | 0,002 |
| Études des sciences et des technologies | 0,000 | 0,000 |
| Communication savante | 0,001 | 0,001 |
| Science ouverte | 0,003 | 0,002 |
| Intégrité de la recherche | 0,000 | 0,000 |
| Charge utile insuffisante (le modèle a refusé de juger) | 0,000 | 0,000 |
Scores machine (provisoires)
Les deux têtes enseignantes du modèle étudiant, lues sur ce travail. Un score ordonne la base pour la relecture; il n'affirme jamais une catégorie, et le statut de validation accompagne chaque rangée tel quel.
Scores de référence d'un modèle non mature (critères de maturité non atteints, 7 itérations). Un score ordonne; il n'affirme jamais une catégorie.
score_only:v0-immature-baseline · tel quel depuis la passe de notation : score_only signifie que le nombre peut ordonner les travaux, et qu'aucune étiquette de catégorie n'en découleClassification
machine, non validéePrédiction automatique; un appel candidat d’une seule tête enseignante, pas un consensus.
Le détail, modèle par modèle et score par score, se trouve en fin de page sous « Comment cette classification a été obtenue ».