Теория и практика защиты программ

       

Дополнения к базовой модели и вероятностные RAM-машины


Приводимые ниже результаты верны для RAM-машин, которые являются вероятностными в очень строгом смысле. А именно ЦП в этих машинах имеет доступ к случайным оракулам. Однако в предположении существования односторонних функций, случайные оракулы могут быть эффективно реализованы посредством псевдослучайных функций.

Определение 5.2. Для каждого kÎN определим оракульный

CPUk как CPUk с двумя дополнительными лентами, названными оракульными лентами. Одна из этих лент является «только-для-чтения», а другая «только-для-записи». Всякий раз, когда машина входит в специальное состояние вызова оракула, содержимое оракульной ленты «только-для-чтения» изменяется мгновенно (т.е., за единственный шаг) и машина переходит к другому специальному состоянию. Строка, записанная на оракульной ленте «только-для-записи» между двумя вызовами оракула называется запросом, соответствующим последнему вызову. Будем считать, что CPUk имеет доступ к функции f, если делается запрос q и оракул отвечает и изменяет содержимое оракульной ленты «только-для-чтения» на f(q). Вероятностная

машина CPUk – это оракульная машина CPUk  с доступом к однородно выбранной функции f:{0,1}O(k) ®{0,1}.

Определение 5.3. Для каждого kÎN определим оракульную RAMk-машину

как RAMk-машину, в которой машина CPUk

заменена на оракульную CPUk. Скажем, что эта RAMk-машина имеет доступ к функции f, если CPUk имеет доступ к функции f и будем обозначать как

. Вероятностная RAMk-машина – это RAMk-машина, в которой машина  CPUk заменена вероятностной CPUk. (Другими словами, вероятностная RAMk-машина – это оракульная RAMk-машина с доступом к однородно выбранной функции).



Содержание раздела