Регистрация Войти
Рейтинг:2
Sean avatar Crypto

Проблема суммы разреженных подмножеств

флаг yt
Sean

В основополагающих результатах Джентри по FHE (https://dl.acm.org/doi/10.1145/1536414.1536440), предполагается, что проблема разреженного подмножества это трудно. Похоже, что есть дополнительный документ по конкретному параметру размер подмножества (https://eprint.iacr.org/2011/567.pdf), в котором упоминается, что выбор размера подмножества Джентри слишком агрессивен (например, 15). Но в своем разделе 5 (Обсуждение) он также упомянул, что реальное предположение, использованное в статье Джентри, - это Скрытый Проблема разреженного подмножества и ее анализ не применяются.

Итак, что касается выбора размера подмножества, что сейчас считается «безопасным» параметром для проблемы скрытого разреженного подмножества (например, при условии, что размер всего набора весов равен 32k, используемому в статье Джентри)?

108
0 + 0
Рейтинг:1
Mark avatar Crypto
флаг ng
Mark

Были более сильные атаки на схему FHE Джентри, в частности, я считаю, что работа Biasse + Song 2016 года (квантово) ломает ее за полиномиальное время (и в классическом случае за субэкспоненциальное время). Учитывая эту относительную слабость по сравнению с другими схемами FHE, я не видел, чтобы люди пытались конкретно реализовать работу Джентри (скажем, за последние ~ 5 лет --- конечно, в этом направлении были ранние работы).

Обсуждение этого можно найти, например, в работе Бернштейна. это. В общем, если вы беспокоитесь о размерах конкретных параметров для реализаций FHE, я бы направил вас к Стандарт гомоморфного шифрования. Он не включает схему Джентри, вероятно, из-за вышеупомянутых атак. Это означает, что неясно, существует ли «безопасная» параметризация, с которой согласятся криптографы, — большинство из них теперь вместо этого пытаются работать со стандартными проблемами LWE / SIS (и их алгебраическими вариантами).

0 + 0
Sean avatar
флаг yt
Sean
Большое спасибо за информацию!
1
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.