Во-первых, после BPR была проведена дополнительная работа, включая практическое ЧПИ и ПРГ. Здесь «практичный» означает очень быстро --- ~5 циклов на байт (и всего ~3 для PRG iirc). Это находится в 10 раз по сравнению с AES, использующим AES-NI. Однако есть несколько предостережений по этому поводу:
- Клавиши очень большие
- Я считаю, что используются инструкции AVX, поэтому некоторый используется аппаратное ускорение
- Очень маленький выбираются параметры.
Эти малые параметры таковы, что больше не известно, что эквивалентность LWR/LWE соблюдается [1], и, кроме того, на самом деле нет никакого значимого сведения к проблеме жесткой решетки. Поэтому безопасность/параметры выбираются конкретно путем анализа нескольких известных атак. Похоже, это будет вам интересно.
- Какова связь между k, n и m? Насколько большими должны быть p и q?
Это зависит от того, хотите ли вы, чтобы это было доказуемо безопасный или же эвристически безопасный. Для доказуемой безопасности теорема 5.2 статьи, на которую вы ссылаетесь, кажется, дает вам именно то соотношение, которое вы хотите. Для эвристической безопасности (с использованием меньших параметров) следует обратить внимание на следующие моменты:
- раздел 4 документа PRF, и
- раздел 3 документа PRG.
но они не дают хороших неравенств, которые вам могут понадобиться, потому что такие неравенства неизвестны.
Вместо этого они оценивают несколько известных атак по определенному выбору параметров.
- Как масштабируется время, затрачиваемое самым известным алгоритмом на взлом безопасности этой функции, с k, n и m?
См. раздел 4 документа PRF и раздел 3 документа PRG, где выполняется несколько соответствующих вычислений.
3.a Выходом F является матрица. Что означает энтропия матрицы?
Строго говоря, ничего. Энтропия – это свойство распределение вероятностей, поэтому утверждение будет иметь смысл, только если рассматривать $F$ не как матрица, а как распределение по матрицам. Чтобы получить некоторое представление о том, что имеют в виду авторы, давайте $q = p_0 p_1$ быть полупростым.
Тогда, если $A, S_1,\dots S_k$ распределяются так, что (с вероятностью 1):
- $A\bmod p_0 \экв 0$, и
- $S_i\bmod p_1\экв 0$ для всех $я$,
тогда $F(A, S_1,\dots, S_k) \equiv 0\bmod q$ постоянно, поэтому PRF будет предсказуемым. Ограничение на $А, S_i$ быть обратимым $\bmod q$ останавливает эту конкретную (потенциальную) проблему (и, возможно, больше).
3.b И указывает ли это утверждение на то, что F является взаимно однозначной функцией?
Нет, но и не ожидается.Мы хотим $F$ быть неотличимым от случайная функция. Обратите внимание, что случайные функции не являются 1-1 (вы можете количественно определить это с помощью метода, называемого «переключение PRP-PRF», но это не имеет особого значения).
[1] Обратите внимание, что для большинства «практичных» примитивов на основе решетки это уже имеет место — например, SABRE основывается на конкретной безопасности MLWR с малыми модулями, хотя его модули $2^{13}\приблизительно 8 тыс.$ является много больше, чем модули $q = 257$ которые используют эти PRF/PRG. Это в некоторой степени актуально, поскольку недавно обсуждалось, что LWR с малыми модулями не подвергались особенно хорошему криптоанализу. Видеть этот поток группы Google NIST PQC. Начиная с этой ветки в декабре, люди проводили некоторые эксперименты (и не обнаружили ничего неожиданного), но из ветки кажется, что люди не пытались напрямую криптоанализировать LWR с малыми модулями до месяца или двух назад.
Есть несколько ситуаций, в которых можно использовать практические примитивы на основе LWR и получить доказуемую безопасность на основе проблем с решеткой, но единственная известная мне «стандартная» ситуация — это пример Сэма Кима. (Ключевой гомоморфный) PRF на основе решетки. У Харта Монтгомери также есть Нестандартная версия LWR он может оказаться безопасным для.
