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

Криптография на основе решеток: секрет гауссовского распределения чи

флаг pl
Karim

В лекции Криса Пейкерта (ссылка 40:20), он показал более эффективные криптосистемы, в которых секрет извлекается из распределения ошибок Гаусса. $\чи$. В лекции он сказал: «Некоторым приложениям действительно нужны секреты, полученные из распределения ошибок, и они действительно не работают так хорошо, если исходят из равномерного распределения», и добавил: «По какой-то странной причине именно эта форма получает вы продвигаетесь вперед с точки зрения создания приложений, таких как полное гомоморфное шифрование (FHE)».

  1. Знаем ли мы сегодня, почему это так?
  2. Какую эффективность приносит распределение ошибок по сравнению с равномерным?

Изменить: обновить информацию

95
0 + 0
Hilder Vitor Lima Pereira avatar
флаг us
Hilder Vitor Lima Pereira
Вы уверены, что он сказал, что приложение работает только с гауссовым секретом, или требование состоит в том, чтобы секрет имел небольшую норму? Возможно, вам следует проверить это, потому что некоторые схемы FHE хорошо работают, когда секрет короткий, но «короткий» может быть гауссовым, бинарным, троичным...
1
Ответить
Karim avatar
флаг pl
Karim
Извините за поздний ответ, я пытался найти, где я это услышал. Так что это был не Вадим Любашевский, а Крис Пейкерт во время Зимней школы. Я обновлю по вопросу со ссылкой на лекцию.
0
Ответить
Рейтинг:2
Chris Peikert avatar Crypto
флаг in
Chris Peikert

Для работы некоторых операций FHE, таких как «переключение/уменьшение модуля», требуется «маленький» секрет LWE. Точно так же некоторые криптосистемы, такие как Любашевского-Пейкерта-Регева-10 и Линднера-Пейкерта-11, имеют меньшие ключи и/или шифротексты (и, соответственно, более быстрые операции) благодаря использованию «малого» секрета.

Меньшие секреты обеспечивают более высокую эффективность в этих системах, но для безопасности существует предел того, насколько маленькими мы можем их считать. В работе Applebaum-Cash-Peikert-Sahai-09 было доказано, что получение секрета LWE из распределения ошибок (которое дает относительно небольшой секрет) не менее безопасно, чем использование равномерно случайного секрета.

0 + 0
Karim avatar
флаг pl
Karim
Так что, если я правильно понимаю, вытягивание секрета из раздачи ошибок убивает сразу двух зайцев. Он дает маленькие секреты, не жертвуя безопасностью, делая секрет слишком маленьким. Это верно?
0
Ответить
Chris Peikert avatar
флаг in
Chris Peikert
Да, это короткая версия.
1
Ответить
Hilder Vitor Lima Pereira avatar
флаг us
Hilder Vitor Lima Pereira
[Также доказано, что LWE с двоичными секретами безопасен] (https://theoryofcomputing.org/articles/v014a013/v014a013.pdf), вам просто нужно увеличить размерность $n$. Тем не менее, я думаю, что для RLWE с бинарными или троичными секретами нет приведения от худшего случая к среднему, но люди все равно используют его, как в HElib или TFHE, так как все еще можно оценить конкретную безопасность для таких секретов и они даже короче, чем при гауссовом распределении...
1
Ответить
Chris Peikert avatar
флаг in
Chris Peikert
@HilderVitorLimaPereira Все это правда. Однако использование двоичного/троичного секрета менее надежно (с точки зрения безопасности), чем использование распределения ошибок, поскольку оно основано только на известном криптоанализе, тогда как использование распределения ошибок имеет строгое доказательство надежности, основанное на исходной проблеме LWE. Таким образом, у нас есть типичный компромисс между тем, что кажется безопасным, и тем, что мы можем доказать.
2
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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