Сьогодні на RobertoFest, присвяченому 40-річчю внеску Роберто Тамассії в аутентифіковані структури даних (і не тільки!) Надходження оновлень! 👇

Майкл Гудріч, показуючи нам, як люди ставилися до його книг про алгоритми та алгоритми Роберто:

До цього @chbpap продемонструвати, як класична робота Роберто над постійними автентифікованими словниками забезпечує роботу сучасних блокчейнів, таких як @ethereum. (Зачекайте, поки я розповім вам про дерева Веркле, звідки прийшли...)

@chbpap @ethereum Джузеппе Ді Баттіста, розповідаючи всім про те, як вони використовували цю нову річ під назвою «Інтернет» для подання наукової роботи, тому що було вже занадто пізно надіслати друкований примірник поштою. (HotCRP ще 😄 не був винайдений)

@chbpap @ethereum Іоанніс Толліс, нагадуючи нам, як виглядали слайди в 1986 році 👌 Запитання від аудиторії: «Що це був за шрифт?» 😅

@chbpap @ethereum Найприємніше в дослідженнях – це люди! ❤️

@chbpap @ethereum @chbpap, як молодий аспірант!

@chbpap @ethereum Важливо правильно розставити пріоритети в академічному житті!

@chbpap @ethereum Дерева, про які я ніколи раніше не чув...

@chbpap @ethereum

@chbpap @ethereum Спіймати ніч (для роботи з алгоритмами графів та аутентифікованими структурами даних)

@chbpap @ethereum Колегія колишніх аспірантів Роберто.

@chbpap @ethereum @motiyung розповідаючи нам про свої своєрідні дослідницькі звички...

@chbpap @ethereum @motiyung ... і приблизно в той час, коли він познайомився з Роберто: коли їм довелося об'єднати свої два подання в одне.

@chbpap @ethereum @motiyung Судячи з усього, один з їх співавторів, Джефф Вестбрук, є одним з авторів «Сімпсонів»! 🤯 Ось чому ви бачите так багато математики в шоу (наприклад, P != NP)

@chbpap @ethereum @motiyung Анна Лисянська, яка розповідає нам про регулювання EUDI (страшно) і про те, як анонімні облікові дані допоможуть забезпечити таку необхідну конфіденційність початковій, сильно недосконалій пропозиції ЄС!

@chbpap @ethereum @motiyung (Мені довелося зробити перерву в публікації: доповіді були дуже цікавими. І в повітрі витало особливе відчуття: кожен, хто виголошував промову, робив це від щирого серця, переказуючи спогади, показуючи картини та іноді крадучись трохи технічного контенту.)

@chbpap @ethereum @motiyung @ElaineRShi, починаючи свою промову.

@chbpap @ethereum @motiyung @ElaineRShi Елейн розповіла нам про роботу Роберто над ORAM. (Ця модель зовнішньої пам'яті постійно з'являлася протягом усіх переговорів. Можливо, захочеться в ньому розібратися!)

@chbpap @ethereum @motiyung @ElaineRShi 1. Зобов'язання Папаманту-Ши-Тамассія (PST): перша (AFAIK) _багатовимірна_ схема поліноміальних зобов'язань!

@chbpap @ethereum @motiyung @ElaineRShi Одна з моїх улюблених речей у цій схемі полягає в тому, як лема її розкладання дає доказ відкриття PCS.

@chbpap @ethereum @motiyung @ElaineRShi (Детальніше про це читайте на , буде оновлено найближчим часом!)

@chbpap @ethereum @motiyung @ElaineRShi 2. Акумуляційні дерева (вони ж дерева Веркле)

@chbpap @ethereum @motiyung @ElaineRShi Дерева накопичення - це просто k-ary дерева Меркла, де хеш-функція є криптографічним акумулятором (наприклад, RSA або білінійним) Вони були розроблені для перевірки автентичності наборів. Дерева Веркле є невеликою варіацією, введеною в [Kusz18].

@chbpap @ethereum @motiyung @ElaineRShi [Kusz18]: Дерева Веркле, Джон Кушмаул, 2018, Але, насправді, парадигма Веркла з префіксом k-арі дерев Меркла, де хеш-функція є векторним зобов'язанням, вперше з'явилася в [LY10; розд. 4], хоча і в контексті побудови множин ZK.

@chbpap @ethereum @motiyung @ElaineRShi [LY10] стислі зобов'язання меркуріального вектора та незалежні множини з нульовим знанням з короткими доведеннями; Ліберт, Бенуа і Юнг, Моті; у ТСС'10; 2010

@chbpap @ethereum @motiyung @ElaineRShi 3. Узагальнені хеш-дерева (або дерева Херкла: ) Дерево Меркла з приємними "гомоморфними" властивостями, дуже корисне для перевірки без стану.

@chbpap @ethereum @motiyung @ElaineRShi У [PSTY13] Роберто та його співавтори дають дерево Херкла на основі решітки з хеш-функції Ajtai. ⚠️ ( Малюнок нижче є надмірним спрощенням!)

@chbpap @ethereum @motiyung @ElaineRShi [PSTY13] потокові аутентифіковані структури даних; Папаманту, Харалампос і Ши, Елейн і Тамассія, Роберто і І, Ке; у програмі EUROCRYPT 2013; На жаль, цей [PSTY13] Herkle має деякі зміни масштабованості: поки глибина дерева не обмежена, гомоморфізм обмежений.

@chbpap @ethereum @motiyung @ElaineRShi Це означає, що гомоморфна операція може бути застосована лише фіксоване число часу, визначене під час налаштування схеми. Крім того, чим більше операцій ви хочете, тим менш ефективною стає схема. Це трохи дратує: ми хотіли б *ефективний*, необмежений гомоморфізм!

@chbpap @ethereum @motiyung @ElaineRShi (Є й інші дерева Херкла, такі як AMT і Hyperpoofs, вони просто перемикають проблему: вони мають необмежений гомоморфізм, але обмежену глибину. Все ще дратує.) Яка велика дослідницька проблема! Я закликаю всіх спробувати її вирішити.

@chbpap @ethereum @motiyung @ElaineRShi (Є й інші дерева Херкла: АМТ і Гіперпуфс . Але вони просто переключають проблему: у них необмежений гомоморфізм, але обмежена глибина. Все ще дратує.) Яка велика дослідницька проблема! Я закликаю всіх спробувати її вирішити.

@chbpap @ethereum @motiyung @ElaineRShi Гаразд: досить про дерева від людей, які одержимі ними. Настав час для заключного слова Роберто! Вони починалися з пояснення того, як він використовував змагальне машинне навчання (атаки з отруєнням), щоб уникнути нагляду своєї матері та втекти на відкриту дорогу на своєму 🚲 😆

@chbpap @ethereum @motiyung @ElaineRShi Хитрість полягала в тому, щоб «(не))звикнути» його матір до думки, що щоразу, коли він бере велосипед на прогулянку по маленькій дорозі перед своїм будинком, він завжди швидко повернеться, залишаючись на виду. Поки одного разу він не знайшов можливість, і замість цього вирушив прямо на 🛣️

@chbpap @ethereum @motiyung @ElaineRShi перший автомобіль Роберто, на якому насправді було написано «Brown», хоча ви не можете побачити його на цій картині, що майже передбачає, де Роберто проведе більшу частину свого академічного життя: Університет Брауна

@chbpap @ethereum @motiyung @ElaineRShi Вечір закінчився вечерею, де люди продовжували розповідати анекдоти та історії.

@chbpap @ethereum @motiyung @ElaineRShi Майк Гудріч розповідає нам, у чому полягає ключове вчення Роберто: «Завжди оптимізуйте подорожі»,

@chbpap @ethereum @motiyung @ElaineRShi Яка ж це була чудова ніч! ❤️