この先の議論を展望するために、何のために計算量的安全性の議論をしているのか、今一度振り返ります。シャノンが導入した完全秘匿性にはその暗号文から平文の情報が全く漏れないという素晴らしい性質があります。同時に鍵と平文の長さは同じだけ必要、とか鍵を再利用してはいけない、という厳しい制約もあります。
完全秘匿性という性質を緩めることでこれらの制約を何とかしたい、というのが計算量的安全性の導入のモチベーションでした。そして意味的安全性という一つ暗号文からの情報漏洩に関する性質が、計算量的識別不可能性という性質と同値であることを前回見てきました。この計算量的識別不可能性は定義式も簡単ですし、なにより、完全秘匿性と等価な完全識別不可能性を計算量的に緩めた形になっていて理解しやすいものです。
この計算量的識別不可能性を持つ暗号はどうやって作ることができるのでしょうか。実はそのためにもう一つピースを加える必要があります。そのピースがあればOTP暗号に対して短い鍵を使っても（完全秘匿性は失いますが）計算量的識別不可能性を確保することができます。
ではそのピースとはなにかというと、「擬似ランダム」とか「擬似乱数」と呼ばれる概念です。それともう一つ、確率分布の計算量的識別（あるいは識別不可能）という概念も登場します（というか擬似ランダムの定義に必要な概念です）。これらを使ってものすごく雑にまとめるとこうなります。
一様ランダムな短い鍵から擬似ランダム生成器(PRG, Psudo Randome Generator)で長い鍵（擬似乱数）を作ります。この長い擬似乱数の分布は一様分布と計算量的に識別できません。そのためこの長い擬似乱数を使って平文を暗号化すると、暗号文の分布も一様分布と計算量的に識別できないことがわかります。ここからこの暗号方式は計算量的識別不可能性を持つことが示せます。
Genは長い鍵を一様分布に従って生成するとします。またGen'は短い鍵を一様分布に従って作るとします。またPRGとGen'の合成をPRG⚪︎Gen'と記すことにします。すると暗号方式(Enc, Gen)が完全秘匿である時、暗号方式(Enc, PRG⚪︎Gen')は計算量的安全性を持つことが示せます。
これから数回にわたってこの辺の話をしていきます。
