Ты можешь. Здесь следует упомянуть определенную оговорку: твердость задач LWE контролируется (частично) размером модуля $q$.
Два важных режима параметров: $q$ существование полиномиально большой в параметре безопасности и сверхполиномиально большой.
Меньший модуль лучше для эффективности и безопасности.
Я думаю, что только недавно у нас появились PRF с полиномиальным модулем от LWE, см., Например, это.
До этой статьи это приводило к забавной ситуации, когда мы могли построить такие вещи, как выровненный FHE, из предположения о более слабой решетке, чем то, что нам нужно для построения PRF.
Для супер-поли $q$ хотя есть и простые конструкции.
Эта бумага является хорошей ссылкой.
Основная идея заключается в том, что образец LWE $(a, \langle a,s\rangle + e)$ является псевдослучайным, поэтому, вероятно, является основой для PRF.
Если попытаться записать какого-нибудь естественного кандидата, например:
$$F_s(a) = \langle a,s\rangle + e\bmod q$$
есть две очевидные проблемы:
это только псевдослучайно, если $а$ является случайным (так что это скорее «слабый PRF», чем PRF --- просто немного другой криптографический примитив)
$F_s(а)$ является рандомизированной функцией --- ошибка $е$ должны быть выбраны случайным образом.
Вы можете решить эту вторую проблему, округлив ее до ближайшего кратного $р$, то есть писать $F_s'(a) = \lfloor \langle a,s\rangle + e\rceil_p$.
При условии, что $кв/р$ достаточно велик, случайный выбор $е$ лишь незначительно повлияет на конечный результат, поэтому мы можем также написать (детерминированную) функцию $F_s'(a) = \lfloor \langle a,s\rangle\rceil_p$.
В качестве альтернативы, это можно рассматривать как слабый PRF, построенный из Обучение с округлением предположение.
Чтобы «обновить» слабый PRF до стандартного PRF, можно сделать ключ $(А, S_1, \точки, S_k)$и определить
$$F_{A, S_1,\dots, S_k}(x_1,\dots,x_k) = \left\lfloor A\prod_{i =1}^k S_i^{x_i}\right\rceil_p.$$
Где $x_i\in\{0,1\}$, и $A, S_1,\dots, S_k$ являются либо кольцевыми элементами, либо матрицами соответствующих размеров, так что выражение имеет смысл.
Именно такая конструкция сделана во второй статье раздела 5.
В итоге:
- Да мы можем построить PRF из задач LWE/решетки
- Сделать это эффективно (из-за малого модуля) было на удивление сложно, но теперь известно, как это сделать (см. первую статью).
- Выполнение этого из проблемы LWR концептуально просто, но мы можем основывать безопасность проблемы LWR только на проблеме LWE для больших модулей.
