В общем, если вы спрашиваете о конкретном определении, хорошо включить ссылку на определение, о котором идет речь.
Однако в целом известно, что PKE требует рандомизированное шифрование (или неповторяющиеся одноразовые номера, я проигнорирую это).
Это означает, что (за исключением специальных настроек) функция:
$$\mathsf{Enc} : \mathcal{PK}\times\mathcal{M}\to\mathcal{C}$$
это рандомизированный алгоритм (где $\mathcal{ПК}$ пространство всех открытых ключей).
Вы всегда можете [1] написать рандомизированный алгоритм как детерминированный алгоритм, который принимает на вход некоторую случайную строку, т.е. пишет:
$$\mathsf{Enc}^{det} : \mathcal{PK}\times\mathcal{M}\times\mathcal{R}\to\mathcal{C}$$
куда $\mathsf{Enc}^{det}(pk, m;r)$ имитирует алгоритм $\mathsf{Enc}(pk,m)$, а когда алгоритм запрашивает случайные биты, он использует (фиксированную) строку $г$ как источник «случайных» битов.
Это относится к преобразованию FO, поскольку его можно «разбить» на два шага (переход $Т$-трансформировать и $U$-трансформировать см. Эта бумага).
$Т$-преобразование изменяет $\mathsf{Enc}$ двумя способами:
Дерандомизация: Вместо использования случайности $г$, используется случайный оракул $G$ установить $г := G(м)$, т.е. выбирает $\mathsf{Enc}^{det}(pk,m):= \mathsf{Enc}(pk,m; G(m))$
Повторное шифрование: Расшифровка также изменена, а именно проверяется, что для $m'\gets\mathsf{Dec}(sk, c)$ отношение $c = \mathsf{Enc}^{det}(pk, m')$ держит. Чтобы эта проверка имела смысл, шифрование должно (конечно) быть детерминированным.
Во всяком случае, чтобы быть в состоянии сделать первый шаг $Т$-преобразование, нужно знать $\mathcal{R}$, так как вам нужно иметь возможность выбрать случайный оракул $G : \mathcal{M}\to\mathcal{R}$. Обычно $\mathcal{R}$ можно записать в виде $\{0,1\}^к$ для некоторых $к$ [2].
[1] Здесь могут быть некоторые патологии, если рандомизированный алгоритм имеет «ожидаемое полиномиальное» время работы, а не завершается за некоторое полиномиальное время работы.Я проигнорирую это, это не имеет отношения к шифрованию.
[2] Обратите внимание, что есть схемы, для которых вы можете опасаться, что $\mathcal{R} \neq \{0,1\}^k$, или даже $\mathcal{R} = \{0,1\}^k$ но распространение шума, которое $\mathsf{Enc}$ потребности неравномерны по $\{0,1\}^к$. В частности, я имею в виду схемы на основе решетки, где случайность часто является «гауссовской» (или, скажем, центрированной биномиальной), хотя это также происходит и для схем на основе кода, где часто случайность имеет фиксированный вес Хэмминга iirc. Случайный оракул обычно выдает $G(м)$ который является равномерно случайным по $\{0,1\}$. Хотя это не проблема --- можно использовать алгоритм выборки $\mathsf{Samp} : \{0,1\}^k \to \mathcal{R}$ для преобразования вывода случайного оракула в желаемое распределение. Это происходит даже для рандомизированного шифрования, где вместо использования RO для случайности алгоритм использует некоторую форму системной случайности (которая считается вычислительно неотличимой от однородных случайных битов).
