195
H(x) является истинно универсальным для наблюдателя, посколько наблюдатель
не запрашивал x. Это истинно, даже если x является известным, или если x не
является универсальным, но является трудноугадываемым. Например, если x -
это n-битная строка, где первая половина x известна и вторая половина случайна,
тогда tt(x) должно быть
легко отличить от случайного, а H(x) - нет.)
Оставшиеся два свойства относятся непосредственно к доказательствам по-
средством редукции в модели со случайным оракулом. (Возможно, полезно бу-
дет обратиться к Разделу 3.3.2.) В качестве части сведения случайный оракул,
с которым взаимодействует злоумышленник A , должен быть симулирован. То
есть: A будет подавать запросы и получать ответы от того, что он будет пред-
ставлять как оракула, но редукция сама по себе должна теперь отвечать на дан-
ные запросы.
Оказывается, это дает много возможностей. Прежде всего:
Если A запрашивает x у H, редукция видит этот запрос и узнает x.
Это иногда называется «экстрагируемость». (Это не противоречит факту, упо-
мянутому ранее, что запросы случайному оракулу являются «частными».) Хотя
это является истинным в самой модели со случайным оракулом, здесь мы ис-
пользуем A как подпрограммувнутри редукции, которая симулирует случайно-
го оракула для A.) Наконец:
Редукция может устанавливать значение H(x) (то есть ответ
на запрос x) до значения своего выбора, поскольку это значение
правильно распределено, то есть является универсальным.
Это называется «программируемость». Не существует аналога экстрагируе-
мости или программируемости, как только There is no counterpart to extractability
or programmability once H is instantiated with any concrete function .
Достарыңызбен бөлісу: