Ваш профессор говорит о следующей относительно распространенной оптимизации
Позволять $\mathcal{К}$ быть набором, и пусть $\mathsf{Образец} : \{0,1\}^r\to\mathcal{K}$ алгоритм, который на входе $г$ равномерно случайные биты, выводит элемент $k\in \mathcal{K}$.
Если $\mathsf{PRG} : \{0,1\}^s\to\{0,1\}^r$ является PRG, то для $s\стрелка влево\{0,1\}^s, г\стрелка влево\{0,1\}^r$, распределения
$$\mathsf{Образец}(\mathsf{PRG}(s))\ приблизительно_c \mathsf{Образец}(r)$$
вычислительно неразличимы.
Доказательство этого примерно тривиально. По безопасности PRG, $\mathsf{PRG}(s) \ приблизительно_c r$. Применение (эффективного) алгоритма $\mathsf{Образец}$ сохраняет вычислительную неразличимость (иначе $\mathsf{Образец}$ был бы эффективным противником против PRG).
По сути, если ваша окончательная конструкция нуждается в $s$-битный ключ, часто бывает достаточно, чтобы ключ был $г$-bit PRG seed, а затем растянуть его до $s$ биты с помощью PRG.
В вышеизложенном следует отметить ряд конкретных деталей:
Окончательный ключ, сгенерированный из $\mathsf{Образец}(r)$ сам по себе не обязательно должен быть равномерно случайным (хотя это, безусловно, наиболее распространенный случай).
Можно еще больше ослабить предположения относительно приведенного выше результата --- обратившись к экстракторам случайности, входные данные $г$ сам по себе не обязательно должен быть однородным, но вместо этого требует «достаточной минимальной энтропии» таким образом, чтобы его можно было сделать точным.
Вам все еще нужен обмен ключами. Игра безопасности PRG требует, чтобы семя PRG держалось в секрете для обеспечения безопасности, поэтому вам все равно нужно убедиться, что Ева не получит доступ к семени (как вы упомянули).
Вся эта оптимизация говорит о том, что «полезную нагрузку» обмена ключами можно уменьшить с помощью PRG (в частности, ее можно $г$ биты, а не $s$ биты).
Существует связанная оптимизация (которая немного отличается), которую также стоит обсудить.
Часто в криптографии (в частности, в решетчатой и основанной на кодировании криптографии) приходится передавать большой равномерно случайный элемент.
В частности, предположение об обучении с ошибками касается «выборок» LWE:
$$ (А, Ас+е)$$
Я не буду утруждать себя определением всего в этом примере, а вместо этого скажу, что $А$ обычно представляет собой равномерно случайную матрицу размера $\примерно 1-10кб$в зависимости от конкретной схемы.
У вас может возникнуть соблазн заменить этот равномерно случайный объект начальным числом PRG. $s$, который затем можно детерминировано расширить до случайного значения $А$ позже. Поскольку семена PRG имеют порядок $\около 128$ бит, это значительный (потенциальный) выигрыш.
Однако это недопустимая оптимизация из-за третьего пункта выше --- вы не можете использовать PRG для "сжатия" равномерно случайного значения до короткого начального числа таким образом, если ваша схема позже сделает это равномерно случайное значение общедоступным. Или вы можете, но для определенных PRG это может полностью нарушить безопасность.
Есть еще подобные вещи, которые вы можете делать с вещами, называемыми расширяемыми функциями вывода (по какой-то причине, аббревиатура XOF). Это примитивы на основе хеширования, которые (примерно) предназначены для использования, когда кому-то нужны свойства, подобные PRG, но с общедоступным начальным числом.
В любом случае, использование XOF для сжатия большого равномерно случайного значения является невероятно распространенной оптимизацией. Я почти уверен, что оба финалиста NIST PQC на основе LPR (Saber/Kyber) используют эту оптимизацию, хотя любая конкретная реализация может слегка отклоняться от спецификации и включать или не включать оптимизацию.
