Премия CSS "Испытание временем" 2023

Премия ACM CCS Test-of-Time Award присуждается исследованиям с длительным влиянием, которые оказали значительное воздействие на безопасность и конфиденциальность систем. Награда 2023 года за работу Мартина ван Дейка и других авторов о Path ORAM была вручена на недавней конференции ACM по компьютерной и коммуникационной безопасности, прошедшей в Копенгагене, Дания.

Лауреатами премии "Испытание временем" за CCS 2023 стали:
Эмиль Стефанов, Мартен ван Дийк, Элейн Ши, Т-Х. Hubert Chan, Christopher Fletcher, Ling Ren, Xiangyao Yu и Srinivas Devadas:
Path ORAM: Чрезвычайно простой Oblivious. Страницы 299-310, В материалах 20-й конференции ACM по компьютерной и коммуникационной безопасности, CCS 2013, Берлин, Германия. ACM 2013, ISBN: 978-1-4503-2477-9

Первоначально представленная на конференции ACM 2013 по компьютерной и коммуникационной безопасности, проходившей в Берлине, Германия, эта работа получила награду за лучший студенческий доклад.

Ведущий автор статьи Эмиль Стефанов, аспирант кафедры электротехники и компьютерных наук Калифорнийского университета в Беркли, умер в 2014 году, до того как статья была выбрана в 2018 году как лучший доклад в журнале Hardware and Embedded Security. В 2023 году эта работа стала одной из двух, за которые Мартену ван Дейку была присуждена премия IEEE CS Edward J. McCluskey Technical Achievement Award:

вклад в забывчивые и зашифрованные вычисления

Что же представляет собой алгоритм Path ORAM? Зачем он нужен, как он развивался и почему называется "Path ORAM"?

На сайте, посвященном Эмилю Стефанову, написано следующее:

Эмиль известен своими инновационными разработками в области обфускации шаблонов доступа к конфиденциальным данным. Среди многочисленных новаторских изобретений он предложил алгоритм Path Oblivious RAM, который, безусловно, является одним из самых простых, элегантных и эффективных решений, известных на сегодняшний день. Path ORAM позволил создать первые прототипы защищенных процессоров с поддержкой ORAM, включая Ascend и Phantom.

Решаемая проблема заключается в том, что одного шифрования данных часто недостаточно для защиты конфиденциальности пользователей в приложениях аутсорсингового хранения. Последовательность мест хранения, к которым обращается клиент (шаблон доступа), может привести к утечке значительного количества конфиденциальной информации о незашифрованных данных путем статистических выводов.

Алгоритмы Oblivious RAM, впервые предложенные Голдрейхом и Островским, позволяют клиенту скрыть эту модель доступа к удаленному хранилищу, постоянно перемешивая и перешифровывая данные по мере их поступления. Противник может наблюдать за физическими местами хранения данных, но алгоритм ORAM гарантирует, что вероятность того, что противник узнает что-либо об истинном (логическом) шаблоне доступа, ничтожно мала.

Алгоритм Path ORAM на тот момент был самой практичной конструкцией ORAM для небольших клиентских хранилищ. Стефанов вместе с ван Дейком, который сейчас возглавляет исследовательскую группу Computer Secuiruty в CWI, Нидерланды, и еще пятью исследователями доказали теоретические границы его производительности, а также представили соответствующие экспериментальные результаты.

Ядро их конструкции получило название Path ORAM, поскольку доступ к данным на сервере всегда осуществляется в виде древовидных путей.