Aujourd'hui à RobertoFest, nous célébrons les 40 ans de contributions de Roberto Tamassia aux structures de données authentifiées (et plus encore !) Mises à jour à venir !👇

Michael Goodrich, nous montrant comment les gens se sentaient à propos de ses livres d'algorithmes et de ceux de Roberto :

Avant cela, @chbpap montre comment le travail classique de Roberto sur les dictionnaires authentifiés persistants alimente les blockchains modernes comme @ethereum. (Attendez que je vous parle d'où viennent les arbres Verkle…)

@chbpap @ethereum Giuseppe Di Battista, racontant à tout le monde comment ils ont utilisé cette nouvelle chose appelée "internet" pour soumettre un article académique parce qu'il était trop tard pour envoyer la copie imprimée. (HotCRP n'avait pas encore été inventé 😄)

@chbpap @ethereum Ioannis Tollis, nous rappelle à quoi ressemblaient les diapositives en 1986 👌 Question du public : « Quelle police c'était ? » 😅

@chbpap @ethereum La plus belle chose à propos de la recherche, ce sont les gens ! ❤️

@chbpap @ethereum @chbpap, en tant que jeune doctorant !

@chbpap @ethereum Il est important de définir correctement vos priorités dans la vie académique !

@chbpap @ethereum Des arbres dont je n'avais jamais entendu parler auparavant…

@chbpap @ethereum

@chbpap @ethereum Saisissez la nuit (pour travailler sur des algorithmes de graphes et des structures de données authentifiées)

@chbpap @ethereum Panel d'anciens étudiants en doctorat de Roberto.

@chbpap @ethereum @motiyung nous parle de ses habitudes de recherche particulières…

@chbpap @ethereum @motiyung …et à propos du moment où il a rencontré Roberto : quand les deux ont dû fusionner leurs deux soumissions en une seule.

@chbpap @ethereum @motiyung Apparemment, l'un de leurs co-auteurs, Jeff Westbrook, est l'un des scénaristes des Simpsons ! 🤯 C'est pourquoi vous voyez autant de mathématiques dans l'émission (comme P != NP)

@chbpap @ethereum @motiyung Anna Lysyanskaya, nous parle de la réglementation EUDI (effrayante) et de la manière dont des identifiants anonymes pourraient aider à donner la confidentialité tant nécessaire à la proposition initiale de l'UE, qui est fortement défaillante !

@chbpap @ethereum @motiyung (J'ai dû faire une pause dans mes publications : les discussions étaient très captivantes. Et il y avait une atmosphère particulière : tous ceux qui ont pris la parole l'ont fait de tout cœur, racontant des souvenirs, montrant des photos et parfois glissant un peu de contenu technique.)

@chbpap @ethereum @motiyung @ElaineRShi, commence sa présentation.

@chbpap @ethereum @motiyung @ElaineRShi Elaine nous a parlé du travail de Roberto sur les ORAMs. (Ce modèle de mémoire externe revenait souvent dans les discussions. Vous voudrez peut-être vous y intéresser !)

@chbpap @ethereum @motiyung @ElaineRShi 1. Engagements Papamanthou-Shi-Tamassia (PST) : le premier (à ma connaissance) schéma d'engagement polynomial _multivarié_ !

@chbpap @ethereum @motiyung @ElaineRShi L'une de mes choses préférées à propos de ce schéma est la façon dont son lemme de décomposition produit une preuve d'ouverture PCS.

@chbpap @ethereum @motiyung @ElaineRShi (Lisez-en plus à , à mettre à jour bientôt !)

@chbpap @ethereum @motiyung @ElaineRShi 2. Arbres d'accumulation (a.k.a., arbres Verkle)

@chbpap @ethereum @motiyung @ElaineRShi Les arbres d'accumulation sont simplement des arbres de Merkle k-aires où la fonction de hachage est un accumulateur cryptographique (par exemple, RSA ou bilinéaire). Ils ont été conçus pour authentifier des ensembles. Les arbres Verkle sont une petite variation introduite dans [Kusz18].

@chbpap @ethereum @motiyung @ElaineRShi [Kusz18] : Verkle Trees, John Kuszmaul, 2018, Mais, en réalité, le paradigme Verkle des arbres Merkle préfixes k-aires où la fonction de hachage est un engagement vectoriel est apparu pour la première fois dans [LY10 ; Sec. 4], bien que dans le contexte de la construction des ensembles ZK.

@chbpap @ethereum @motiyung @ElaineRShi [LY10] Engagements vectoriels mercuriels concis et ensembles indépendants à connaissance nulle avec preuves courtes ; par Libert, Benoît et Yung, Moti ; dans TCC'10 ; 2010

@chbpap @ethereum @motiyung @ElaineRShi 3. Arbres de hachage généralisés (ou arbres de Herkle : ) Un arbre de Merkle avec de belles propriétés "homomorphiques", très utile pour la validation sans état.

@chbpap @ethereum @motiyung @ElaineRShi Dans [PSTY13], Roberto et ses co-auteurs présentent un arbre Herkle basé sur un réseau à partir de la fonction de hachage Ajtai. (⚠️ La figure ci-dessous est une simplification excessive!)

@chbpap @ethereum @motiyung @ElaineRShi [PSTY13] Structures de données authentifiées en streaming ; par Papamanthou, Charalampos et Shi, Elaine et Tamassia, Roberto et Yi, Ke ; dans EUROCRYPT 2013 ; Malheureusement, ce [PSTY13] Herkle a quelques changements de scalabilité : bien que la profondeur de l'arbre soit illimitée, l'homomorphisme est limité.

@chbpap @ethereum @motiyung @ElaineRShi Cela signifie que l'opération homomorphe ne peut être appliquée qu'un nombre fixe de fois, déterminé au moment de la configuration du schéma. De plus, plus vous souhaitez d'opérations, moins le schéma devient efficace. C'est un peu ennuyeux : nous aimerions un homomorphisme *efficace* et sans limites !

@chbpap @ethereum @motiyung @ElaineRShi (Il existe d'autres arbres Herkle comme les AMTs et les Hyperpoofs, ils inversent simplement le problème : ils ont une homomorphie non bornée mais une profondeur bornée. C'est toujours ennuyeux.) Quel problème de recherche formidable ! J'encourage tout le monde à essayer de le résoudre.

@chbpap @ethereum @motiyung @ElaineRShi (Il existe d'autres arbres Herkle : AMTs et Hyperpoofs. Mais ils changent juste le problème : ils ont un homomorphisme non borné mais une profondeur bornée. C'est toujours agaçant.) Quel problème de recherche formidable ! J'encourage tout le monde à essayer de le résoudre.

@chbpap @ethereum @motiyung @ElaineRShi D'accord : assez parlé des arbres par des gens qui en sont obsédés. Il est temps pour les remarques finales de Roberto ! Celles-ci ont commencé par une explication de la façon dont il a utilisé l'apprentissage automatique adversarial (attaques de poisoning) pour échapper à la supervision de sa mère et s'enfuir sur la route ouverte avec son 🚲 😆

@chbpap @ethereum @motiyung @ElaineRShi Le truc était de "(dés)habituer" sa mère à croire que, chaque fois qu'il prend le vélo pour faire un tour sur la petite route devant chez lui, il reviendra toujours rapidement tout en restant à vue. Jusqu'à ce qu'un jour, il trouve une opportunité, et il est plutôt allé directement vers le 🛣️

@chbpap @ethereum @motiyung @ElaineRShi La première voiture de Roberto, qui avait en fait "Brown" écrit dessus, même si vous ne pouvez pas le voir sur cette photo, préfigurait presque où Roberto passerait la majeure partie de sa vie académique : l'Université Brown

@chbpap @ethereum @motiyung @ElaineRShi La nuit s'est terminée par un dîner, où les gens ont continué à raconter des blagues et des histoires.

@chbpap @ethereum @motiyung @ElaineRShi Mike Goodrich nous dit quel est l'enseignement clé de Roberto : « toujours optimiser les déplacements »,

@chbpap @ethereum @motiyung @ElaineRShi Quelle merveilleuse nuit c'était ! ❤️