ヤオのテスト

暗号学と計算理論において、ヤオのテストは、 1982年にアンドリュー・チチ・ヤオ^{[ 1 ]}によって定義された擬似乱数列に対するテストである。ある単語列がヤオのテストに合格するのは、それなりの計算能力を持つ攻撃者が、それを一様ランダムに生成された列と区別できない場合である。

正式な声明

ブール回路

を多項式、をビット長のシーケンスの集合の集合とし、各 に対して、を 上の確率分布、を多項式とします。予測集合とは、未満のサイズのブール回路の集合です。を入力 に対して、 から確率でランダムに選択された文字列が となる確率とします。つまり 、${\displaystyle P}$ ${\displaystyle S=\{S_{k}\}_{k}}$ ${\displaystyle S_{k}}$ ${\displaystyle P(k)}$ ${\displaystyle k}$ ${\displaystyle \mu_{k}}$ ${\displaystyle S_{k}}$ ${\displaystyle P_{C}}$ ${\displaystyle C=\{C_{k}\}}$ ${\displaystyle P_{C}(k)}$ ${\displaystyle p_{k,S}^{C}}$ ${\displaystyle s}$ ${\displaystyle S_{k}}$ ${\displaystyle \mu (s)}$ ${\displaystyle C_{k}(s)=1}$

${\displaystyle p_{k,S}^{C}={\mathcal {P}}[C_{k}(s)=1|s\in S_{k}{\text{ 確率 }}\mu _{k}(s)]}$

さらに、をビット長のシーケンスを入力として、から一様にランダムに選択される確率とします。がヤオのテストに合格するのは、すべての予測コレクション、有限個を除くすべての、すべての多項式 に対してであるときです 。 ${\displaystyle p_{k,U}^{C}}$ ${\displaystyle C_{k}(s)=1}$ ${\displaystyle s}$ ${\displaystyle P(k)}$ ${\displaystyle \{0,1\}^{P(k)}}$ ${\displaystyle S}$ ${\displaystyle C}$ ${\displaystyle k}$ ${\displaystyle Q}$

${\displaystyle |p_{k,S}^{C}-p_{k,U}^{C}|<{\frac {1}{Q(k)}}}$

確率論的定式化

次ビットテストの場合と同様に、上記の定義で用いられた予測集合は、多項式時間で動作する確率的チューリングマシンに置き換えることができる。これにより、ヤオのテストのより厳密な定義も得られる（アドルマンの定理を参照）。実際、上述の非一様回路を用いて擬似乱数列の決定不可能な性質を決定できるのに対し、 BPPマシンは常に指数時間決定論的チューリングマシンによってシミュレートできる。

参考文献

1. Andrew Chi-Chih Yao .トラップドア関数の理論と応用. 第23回IEEEコンピュータサイエンス基礎シンポジウム論文集, 1982年.