Заявленная атака не «ломает» криптографию на основе решетки, а просто еще больше улучшает известные атаки.
Попробую кратко описать ситуацию.
Асимптотика:
Асимптотически нашим лучшим показателем является то, что LWE требует времени. $2^{сп}$ решить для некоторой константы $с$.
Это должно быть противопоставлено RSA $ 2 ^ {(\ журнал N) ^ {1/3}} $ (это очень неточно, и следует правильно использовать L-обозначение), и Эллиптическая кривая DLog $ 2 ^ {\ гидроразрыва {1} {2} \ log_2 | \ mathbb {G} |} $.
Это означает, что даже с улучшениями атак на варианты LWE мы считаем, что он имеет «лучшее масштабирование», чем предположения, такие как RSA (о которых вы специально упомянули), хотя он похож на ECDlog.
Текущие оценки $с$ может варьироваться, но это $< 1/2$ (думаю, возможно $\около 0,28$ актуален, но не проверял), поэтому ECDlog является лучшим по этой метрике, а затем LWE, а затем (далеко на расстоянии) RSA/DH с конечным полем.
Также неясно, насколько полезно это понятие на практике --- оно говорит, что некоторый набор параметров может быть безопасным, но не помогает выбрать, какой из них.
конкретно:
Даже если LWE делает брать $2^{сп}$ время решать, это не поможет нам, если мы не знаем $с$.
Улучшенные атаки (теоретически) улучшились $с$ со временем.
Это может привести к тому, что различные наборы параметров будут "сломаны" (хотя и не в том смысле, что мы можем проводить против них практические атаки --- в том смысле, что они не соответствуют минимальным стандартам NIST для определенного "уровня безопасности").
Эта ситуация, пожалуй, лучше чем ситуация, через которую прошел факторинг с развитием методов «индексного исчисления».
Для ECDlog лучшими атаками по-прежнему являются (варианты) алгоритма Полларда Ро, и так было на протяжении длинный время.
Все это говорит о том, что ECDlog конкретно имеет наиболее понятную безопасность, хотя я бы сказал, что LWE по-прежнему превосходит RSA и другие вещи, уязвимые для методов индексного исчисления.
Хотя NFS была создана около 30 лет назад, вполне вероятно, что она улучшена.
Например, путь (малой характеристики) конечного поля DLog был от примерно той же сложности, что и RSA, к (примерно) $ 2 ^ {(\ журнал р ^ п) ^ {1/4}} $, а затем к квазиполиномиальному времени (см. Надя Хенингер, через Мэтью Грина).
Это не означает, что что-то подобное произойдет с факторингом (такого не было около 30 лет), но, возможно, это все еще неудобная возможность.
Практически:
Последний способ понять безопасность предположения о твердости — это решить действительно большие экземпляры.
Это приводит к вопросам
- каков наибольший набор параметров, которые были нарушены в реальных вычислениях?
- сколько времени было потрачено на это вычисление?
Для RSA такие вещи, как RSA-240 (768-битное полупростое число), были сломаны за 1000 основных лет (или 6 месяцев iirc).
В этом смысле RSA (и DH с конечным полем для немалых характеристик) является нашим наиболее проверенным (и, возможно, наиболее понятным) предположением о твердости.
Эллиптические кривые также требовали длительных вычислений.
страница записей перечисляет количество разрывов в диапазоне групп размера $2^{110}$ к $2^{120}$, а время настенных часов снова составляет до 6 месяцев на верхнем уровне.
По этому показателю LWE действительно отстает.
Есть несколько хорошо известных «решетчатых задач» (а-ля вызовы RSA), например Технический университет Дармштадта бросает вызов.
Они предназначены для простого LWE (Пейкерт сделал несколько для RLWE, но я не вижу общедоступной таблицы лидеров для них).
В любом случае, для простых задач LWE самая высокая размерность, которую кто-либо когда-либо решал, равна 85, а размерности 500+ (хотя 700+ более распространены) используются в практических схемах.
Все записи, которые я просматривал, использовали менее 200 часов настенных часов (обычно на нескольких процессорах), поэтому вычисления действительно много меньший масштаб, чем вычисления RSA/ECDlog.
Это означает, что «большие атаки» на LWE, по крайней мере, на порядок меньше, чем аналогичные атаки на RSA/ECDlog, хотя это, вероятно, значительно занижает размер современных академических атак на RSA.
Таким образом, самый большой экземпляр LWE, который был взломан, имеет небольшой размер (что является хорошим признаком безопасности), и против него еще не было предпринято «по-настоящему крупных атак» (что плохо).
Приведенное выше игнорирует многие тонкости предположений о твердости, такие как
- устойчивость к утечкам,
- простота реализации,
- простота подавления побочных каналов.
LWE на самом деле неплохо справляется со всеми этими показателями (пока вы не делаете подписи), определенно лучше, чем RSA, хотя я лично не знаю ECDlog.
При всем при этом лично я рассматриваю LWE как
- а массивный улучшение по сравнению с RSA/(finite field)DLog и
- возможно, хуже, чем ECDlog.
Определенно, если бы квантовые компьютеры не представляли опасности, не было бы причин отказываться от ECDlog (за исключением специальных приложений, таких как FHE).
Но они есть, значит надо.
С этой точки зрения не следует сравнивать LWE и RSA/ECDlog, так как, к сожалению, мир, в котором они имеют смысл, быстро покидает нас.
Вместо этого следует сравнивать с другими постквантовыми предположениями.
Но среди постквантовых предположений LWE действительно находится на вершине.
Существуют допущения с большей безопасностью (например, McElice), но их эффективность слишком плоха, чтобы их можно было использовать, за исключением особых случаев.
Основными другими возможными предположениями являются
- NTRU, который также основан на решетке и, следовательно, не совсем «независим» от атак на LWE, и
- СИДХ.
Сам SIDH по-прежнему на порядок медленнее, чем конструкции на основе решетки iirc (хотя и более компактный).
Есть несколько причин утверждать, что его безопасность «выдержала испытание временем лучше», чем предположения, основанные на решетке (см. Дело для SIKE), но также ему всего ~ 10 лет iirc, поэтому он сам по себе все еще является новым предположением (и тем более в 2016 году, когда NIST начал процесс отбора).
Это также довольно сложно математически, что может затруднить реализацию (но я не пробовал).
Это довольно длинно (и игнорирует многие технические темы, скажем, твердость «малых модулей» LWR или утверждения о влиянии размеров группы Галуа на твердость RLWE, которые не были решены в течение многих лет.
Это те темы, которые кажутся наиболее вероятными для «больших прорывов», но пока ничего не произошло), но я надеюсь, что вы начнете хотя бы отвечать на ваш вопрос.
