hash.tex

\chapter{認証}\index{にんしょう@認証}
\label{chap:authentication}
公開鍵基盤では、公開鍵の証明書が必要でした。
与えられた公開鍵が正しいこと示すにはなんらかの認証機構が必要です。
認証には、あるメッセージ（データ）が書き換えられていないことを検証するメッセージ認証や、メッセージを作った人が当人であることを検証するデジタル署名などがあります。

この章ではそれらの技術で使われるハッシュ関数を紹介します。
その後、ハッシュ関数や乱数を共通鍵暗号や公開鍵暗号と組み合わせることで認証や署名を作る方法を紹介します。
ブラインド署名という一風変わった署名も紹介します。

\section{ハッシュ関数}
\label{hash}
公開鍵暗号などを使うときには、その通信データが途中で改竄されていないことを確認する必要があります。
送信したデータのどこか一カ所でも変更されれば検出できるようにしたいのです。
そのために必要な技術の一つがハッシュ関数です。

一般にハッシュ関数とは任意のサイズのメッセージ$m$に対して、ある決まった手順にしたがってサイズが固定の値$H(m)$を出力する関数$H$です。
どんなに大きいメッセージであっても同じサイズ（たとえば20バイト）の値です。
そして同じ入力に対してはいつも同じ値になる決定的な関数です。

ハッシュ関数と聞くとプログラミング言語で使われる連想配列や辞書と呼ばれるデータ構造に使われるものを思い浮かべるかもしれません。
そのような用途のハッシュ関数は、高速に計算できて、ランダムな入力データに対して出力値がある程度一様に分布すれば十分です。
ただ2011年、Hashdosと呼ばれる攻撃が提案されました~\cite{hashdos}。
これはWebサーバにハッシュ値が同じ値になる多数のデータを与えることでCPUのリソースを奪う攻撃です。
したがって近年は与えられたハッシュ値になる多数のデータを求めにくいハッシュ関数が望まれています（別の手法でHashdosを回避することもできます）。
2012年に提案されたSipHash~\cite{SipHash}は、ある程度そのような性質を持ち、かつ短いメッセージを高速に計算できるので注目されています。

暗号プロトコルで使われるハッシュ関数は、そのようなハッシュ関数よりも更に強い性質が求められます。
普通のハッシュ関数と区別するために、暗号学的ハッシュ関数ということがあります。

たとえば1バイトごとの値を加算していき、最後に合計（チェックサムと呼ばれることがあります）を出力する関数を考えてみます。
どこか一カ所、値を変更するとチェックサムが変わるので変更されたと判断できます。
しかしデータのどこか二つの値を交換した場合、合計は変わらないのでチェックサムを確認するだけでは変更されたことを検知できません。
暗号学的ハッシュ関数はそんなことができないように設計されています。
詳しくいうと、暗号学的ハッシュ関数は次の性質を満たします。
\index{げんぞうけいさんこんなんせい@原像計算困難性}
\index{だいにげんぞうけいさんこんなんせい@第二原像計算困難性}
\index{しょうとつこんなんせい@衝突困難性}
\mydescription{
\item [原像計算困難性] 与えられた$h$に対して$H(m)=h$となる$m$を見つけることが困難である。
\item [第二原像計算困難性] $m_1$が与えられたときに$H(m_1)=H(m_2)$となる$m_2( \ne m_1)$を求めるのが困難である。
\item [衝突困難性] 相異なる$m_1$と$m_2$で、$H(m_1)=H(m_2)$となるメッセージを見つけることが困難である。
}
一つ目はハッシュの値から元のメッセージ（原像）を再現できないことを要求しています。
二つ目と三つ目は一見、同じように見えるかもしれませんが全然違います。
たとえるなら第二原像を求めるのは学校のクラスの中で自分と同じ誕生日の人を見つける問題です。
衝突（異なるメッセージが同じハッシュ値になること）を求めるのはクラスの中で誕生日が同じ人の組を見つける問題です。
\image{birthday.pdf}{第二原像と衝突の違い}
1年が365日で誕生日はどの日も等確率、クラスの人数が40人としましょう。
自分と同じ誕生日の人が見つかる確率$p_1$は、1から自分と同じ誕生日の人がいない確率を引けばよいので
\[
p_1=1-\left(\frac{364}{365}\right)^{40} \approx 0.10
\]
となります。
それに対してクラスの中に同じ誕生日の人の組がいる確率$p_2$は、1から全員の誕生日が異なる確率を引けばよいので
\[
p_2=1-\frac{364}{365} \cdot \frac{363}{365} \cdot \dots \cdot \frac{365-40+1}{365} \approx 0.89
\]
となります。
これは上の0.10に比べて非常に高い確率ですね。
この現象は誕生日のパラドックスと呼ばれます。

仮にある現象の確率が$1/2$を越えると「その現象が発生する」と定義することにします。
ハッシュ関数の出力のサイズが$n$ビットのときはクラスの人数が$2^n$であることに相当します。
すると第二原像が見つかる、つまりあるハッシュ値と同じ値になるメッセージが見つかる確率が$1/2$となるのは全体の半分近く集まったときです。
これは$O(2^n)$の計算量です。

それに対して衝突する2個の値を見つけるには、計算過程を省略しますが$O(2^{n/2})$個集めればよいです。
第二原像を求めることに比べてそのルートの計算量ですむのでずっと易しいのです。
誕生日のパラドックスと同じ現象です。
自分と同じ誕生日の人を探すより、同じ誕生日の人の組を探す方が易しいので、ハッシュ関数に要求される条件としては第二原像計算困難性よりも衝突困難性の方が強いです。
したがって出力が$n$ビットの理想のハッシュ関数の強度は$O(2^{n/2})$、$n/2$ビットセキュリティです。

2004年、ハッシュ関数MD5は衝突困難性を持っていないことが示されました。
現在は暗号学的ハッシュ関数の性質を満足していないため使ってはいけません。
またSHA-1も本来なら80ビットのセキュリティであるはずが、それよりもずっと小さい強度しかないことが判明しています。
そのため日本の暗号技術検討会及び関連委員会（CRYPTREC）では2013年にSHA-1を運用監視リストに移行しました。
今はSHA-2（SHA-256以上）を使うことが推奨されています。
その次の規格であるSHA-3は2012年に選定され、まもなく標準規格として登場するところです\footnote{2015年8月に正式に公開されました。}。

なおファイルをダウンロードするWebページでファイルへのリンクと同じページにSHA-1の値が書かれていることがあります。
しかし、これはセキュリティ的には何の安全も保証しないことに注意してください。
もし、サーバが乗っ取られてページを書き換えられたり、通信経路で改竄されたりしているなら、ファイルだけでなくSHA-1の値もいっしょに書き換えられるからです。
ダウンロード中にファイルが壊れていないかを確認する程度にしか意味はありません。
メッセージやデータが改竄されていないことを確認するには\ref{mac}節で紹介する技術を用います。

\section{ハッシュ関数の構成}
\label{cstr-hash}
ハッシュ関数は（ほとんど）任意のサイズのメッセージに対して固定長の値を出力します。
いきなり任意のサイズに対応したハッシュ関数を作るのは難しいので、まず固定長のメッセージの入力を少しだけ小さくする圧縮関数を用意します。
圧縮関数という名前ですが通常のデータの圧縮とは違い元のデータを復元できるわけではありません。

メッセージ$m$が与えられたとき、まず$m$をある固定のサイズ$l$のブロックに分割します。
分割するときはパディングと呼ばれる処理をします。
SHA-1, SHA-2では$m$にビット1とビット0を必要なだけ追加し、最後に$m$のサイズをくっつけて全体のサイズが丁度$l$の倍数になるように調節します。
\[
m=m_1 || m_2 || \dots || m_n.
\]
ここで$||$はメッセージをそのまま連結することを示します。
初期値$h_0$を固定し、圧縮関数$f$を用いて$h_1:=f(h_0, m_1)$を求めます。
次に$h_2:=f(h_1,m_2)$を求めます。これを繰り返し適用することで最終的に$h_n:=f(h_{n-1},m_n)$を求め、
$h_n$をハッシュ関数の値として出力します。
圧縮関数を繰り返し適用するので逐次的に処理する反復型ハッシュ関数（iterated hash function）と呼ばれます。
SHA-1、SHA-2などの現在よく使われるハッシュ関数はこの形をしています。
\image{iterated-hash.pdf}{反復型ハッシュ関数}

\section{メッセージ認証符号}
\label{mac}
メッセージ認証符号（MAC : Message Authentication Code）はメッセージが改竄されていないかどうかを確認する技術です。
MACは秘密鍵$k$と任意のメッセージ$m$に対してある値$t:=\MAC(k, m)$を出力するアルゴリズムです。
$\MAC$をMACを計算する関数、$t$をMAC値といいます。
AさんとBさんの間で秘密の鍵$k$を共有しておき、AがBにメッセージ$m$を送るとします。
そのときBには$(m,t:=\MAC(k, m))$を送ります。
Bは受け取った$(m,t)$から$\MAC(k,m)$を計算し、$t$と等しいかどうか
\[
t \eqq \MAC(k, m)
\]
を確認します。もし等号が成立しなければメッセージは改竄されています。
\image{mac.pdf}{MACによるメッセージの検証}
$k$を秘密に共有しておいて、異なる$m$に対して何度もMAC値を計算して使います。
ですから攻撃者は沢山の$\Set{(m_i,\MAC(k, m_i))}$を集められます。
この情報から$k$が漏洩すると困ります。
また仮に秘密鍵$k$が漏洩しなかったとしても、Aが作っていないメッセージに対するMAC値$t$を勝手に作られても困ります。
BはそのメッセージをAが作成したものと判断してしまうからです。
すなわちMACには

「攻撃者が好きに選んだメッセージに対する沢山のMAC値を取得できたとしても、
攻撃者が取得していないメッセージに対するMAC値を偽造できない。」\\
という性質が求められます。
これを適応的選択平文攻撃に対して存在的偽造困難（EUF : existentially unforgeable）であるといいます。

MACの構成法はいくつかあります。
一つは\ref{CBC}節で紹介したブロック暗号をCBCモードで使う方法です。
初期化ベクトルIVは0固定で利用します。メッセージ$m$の先頭に$m$のサイズを連結したものを秘密鍵$k$で暗号化します。
できた暗号文の最終ブロックをMAC値として出力します。
\[
\text{CBC-MAC}(k, m):=\text{CBC-Enc}(k, \text{IV}=0, m\text{のサイズ}||m)\text{の最終ブロック}.
\]
暗号化のときと違ってIVをランダムに選ぶべきではありません。
なぜなら0固定でないと、IVを送る必要があり、IVを改竄する攻撃が存在するからです。
またCBC-MACにはメッセージの先頭にサイズを付加しないと2組のメッセージとMAC値のペアから別のメッセージとMAC値のペアを生成する攻撃があることも知られています。
そのため可変長メッセージに対するCBC-MACは使うべきではありません。
固定長メッセージを扱う場合は安全ですが、2013年のCRYPTRECの運用監視リストに入っています。

2003年、岩田氏と黒澤氏はCBC-MACを改良してOMAC（One-Key CBC MAC）を開発しました~\cite{OMAC}。
これは2005年、CMACという名前でNISTのMACの標準となっています~\cite{CMAC}。

\section{HMACと伸長攻撃}
MACを実現するにはブロック暗号を使う方法の他にハッシュ関数を使う方法もあります。
ハッシュ関数を使ったMACをHMAC（Hash-based MAC）といいます。
HMACは$n$ビット出力のハッシュ関数$H(x)$と$n$ビットの鍵$k$に対して
\begin{align}
\label{hmac}
\HMAC(k, m):=H((k \oplus opad)||H((k \oplus ipad)||m))
\end{align}
と定義されます。
ここで$opad$や$ipad$はある定数、$||$はメッセージの連結を意味します。
このようにハッシュ関数を2回使うことで安全なMACを構成できることが知られています。

これを面倒だと思って
\[
\HMAC^\times(k,m):=H(k||m)
\]
としてしまいたくなるかもしれません。
しかしこれは可変長メッセージの場合に安全ではないのでやってはいけません。
SHA-1などの反復型ハッシュ関数に対して伸長攻撃（length-extension attack）と呼ばれる攻撃を受けます~\cite{hirose}。

どういう攻撃か少し紹介しましょう。
今秘密の$k$に対する、あるメッセージ$m$とそのHMACもどき$h:=H(k||m)$を手に入れたとします。
ハッシュ関数の内部の最終ブロック$m_n$は$k||m$の最後にパディング$p$をつけたものです。
$p$は$m$のサイズだけから決まる値です。
\[
m_n:=(k||m)\text{の最後の残り}||p.
\]
反復型ハッシュ関数の出力はこの$m_n$と、一つ前の圧縮関数の値$h_{n-1}$から圧縮関数$f$によって決まっていました。
\[
h=H(k||m)=f(h_{n-1},m_n).
\]
$m||p$の後ろに更に適当なメッセージ$c$（1バイトでいい）をつけてメッセージを作ります。
すると$m':=m||p||c$に対するHMACもどき$H(k||m')$は$h$と$c$から求められます。
\[
\HMAC^\times(k,m')=H(k||m||p||c)=f(h,c\text{にパディングしたもの})
\]
となって$k$の値を知らなくても$m$とは異なる$m'$に対するMACを構成できてしまいました。

したがってHMACもどき$H(k||m)$は安全ではないのです。
それなら$H(m||k)$だとよいのではと思われるかもしれませんが、この場合はまた別の攻撃方法が知られています。
したがって式（\ref{hmac}）で定義されたHMACを使うべきです。

SHA-3は\ref{cstr-hash}節で紹介した圧縮関数を使った反復型ハッシュ関数の構成は取っていません。
SHA-3は従来のハッシュ関数よりも大きな1600ビットの内部状態（スポンジといいます）を持ちます。
スポンジと入力の排他的論理和をとりながらかき混ぜます。
パディング処理は非常に簡単で、パディングにメッセージのサイズは含まれません。
そのため完全に任意のサイズのメッセージを扱え、伸長攻撃に対して耐性があります~\cite{sha3}。
\image{bad-hmac.pdf}{伸長攻撃}

\section{認証付き暗号}
メッセージを安全に秘密に通信するには暗号化と認証の両方が必要です。
暗号化とMACとの組み合わせは様々な方法が考えられます。
しかし組み合わせ方によっては安全性が損なわれることがあります。
\ref{CBC}節で触れたSSL3.0に対する攻撃POODLEもCBCモードの不適切な扱いをついた攻撃の一つです。
そのため、暗号化と認証を同時に行う認証付き暗号（AEAD : Authenticated Encryption with Associated Dataあるいは単にAE）が考えられています。

AEADの一つにGCM（Galois/Counter Mode）があります。
GCMは\ref{CTR}節で紹介したCTRモードに認証機構を組み込んでいます。
CBCモードよりも性能がよく安全なため広く使われています。
SSLの後継のTLS（Transport Layer Security）のバージョン1.2からはGCMをサポートしています。
2013年からよりよいAEADを目指した暗号方式のコンテストが始まっています
\footnote{\url{http://competitions.cr.yp.to/caesar.html}}。
\section{デジタル署名}
\label{dsa}
デジタル署名とは、あるメッセージがその作者によって作られたことを検証する仕組みです。
電子署名や単に署名ということも多いようです。
他人がその作者になりすまして署名を作ったり、別のメッセージに対する偽の署名を作ったりできないようになっています。
そのため署名したことを後で否認することができません。
またそのメッセージが改竄されていないことも確認できます。

基本アイデアは公開鍵暗号の原理を使う点にあります。
一般に公開鍵暗号はメッセージ$m$を公開鍵$K'$で暗号化して秘密鍵$K$で復号できるのでした。
\[
\Dec(K,\Enc(K',m)) = m.
\]
\ref{rsa}節のRSA暗号の暗号化$\Enc$と復号$\Dec$をよく見ると指数が違うだけで同じ形をしています。
$f(x,y):=x^y \mod{n}$とすると$\Enc(K',m)=f(m,K')$, $\Dec(K,m)=f(c,K)$。
RSA暗号はこの特殊性により$\Enc$に秘密鍵$K$を用い、$\Dec$に公開鍵$K'$を用いても等式が成り立ちます。
\begin{equation}
\label{enc_and_dec}
\Dec(K', \Enc(K,m))=m.
\end{equation}
いわば、$m$を秘密鍵$K$で暗号化して公開鍵$K'$で復号しています。
秘密鍵で暗号化されたメッセージは誰でも復号できるということです。
もちろんこれは暗号の意味をなしていません。
しかしそのメッセージを暗号化できるのはその秘密鍵を持っている人だけなのです。
つまりAさんがメッセージ$m$を自分の秘密鍵$K$によって暗号化し$(m, \Enc(K, m))$を公開したとします。
すると、Aさんの公開鍵$K'$を知っている人は誰でも式（\ref{enc_and_dec}）の等号成立を
確認することで$(m, \Enc(K, m))$はAさんが作成したと判断できます。

実際のところ、RSA暗号以外の公開鍵暗号はそのままデジタル署名として使えるわけではありません。
一般に公開鍵暗号の公開鍵と秘密鍵の形は違うので、両者を入れ換えることはできないからです。
そのため勝手なメッセージ$m$を秘密鍵で暗号化することはできません。
「秘密鍵で暗号化」「公開鍵で復号」もRSAの上式でのみいえる表現です。
後述しますが、署名に「暗号化」や「復号」アルゴリズムは存在しないので使わないようにしてください。

MACはメッセージが改竄されていないかを確認するために使われます。
MACは二人の間で秘密鍵を共有しなければなりません。
人が増えるとそれぞれの組の間で共有すべき秘密鍵が増え、管理する鍵の個数が膨大になってしまいます。
デジタル署名は秘密鍵を共有することなく公開鍵のみで誰でも署名を検証できます。
MACとデジタル署名の関係は、共通鍵暗号と公開鍵暗号の関係に似ています。

\subsection{RSA-FDH署名}
まずは式が比較的簡単なRSA暗号とハッシュ関数を組み合わせて作られたRSA-FDH（FDH : Full Domain Hash）署名を紹介しましょう~\cite{Bellare:1993}。

\mydescription{
\item[鍵生成]
RSA暗号の公開鍵を$(n,e)$、秘密鍵を$d$とします。
更にFull Domainハッシュ関数$H$を用意します。
Full Domainとはハッシュ値が公開鍵$n$と同じサイズとなるハッシュ関数のことです。
\item[署名]
メッセージ$m$に対して秘密鍵$d$を使って署名$s$を計算します。
\[
s:=H(m)^d \bmod{n}.
\]
\item[検証]
メッセージ$m$に対する署名$s$に対して
\[
H(m) \equiv s^e \pmod{n}
\]
が成立するとき署名を受理、そうでないとき\ruby{棄却}{き|きゃく}します。
}
ハッシュ関数を使うところ以外はRSA暗号とほぼ同じです。
この署名はRSA仮定とランダムオラクルモデルのもとで安全です。
ランダムオラクルモデルというのはハッシュ関数を出力が完全にランダムになる理想の関数であるという仮定を置いたモデルのことです。
$n$が2048ビットならハッシュ関数も2048ビット必要なのであまり効率がよいとはいえません。
この署名を構成したBellareとRogawayは確率的な要素を追加し、RSA-FDHよりも効率のよいRSA-PSS（Probabilistic Signature Scheme）も提案しています~\cite{Bellare:1996:ESD:1754495.1754541}。

\subsection{DSA}
次にElGamal署名の改良系であり、現在標準的に使われているDSA（Digital Signature Algorithm）~\cite{dsa}という署名を紹介しましょう。
\mydescription{
\item[鍵生成]
ハッシュ関数$H$とDHパラメータ$(p,q,g)$を決める（\ref{dh-param}節参照）。
$p$は大きな素数で、$q$はハッシュ関数の出力と同じサイズとする。
$g$は生成元で$g^q \equiv 1 \bmod{p}$。$p-1$は$q$で割り切れる。
最後に$0 < x < q$となる$x$をランダムに選び$y:=g^x \bmod{p}$とする。$(g, p, q, y)$が公開鍵で$x$が秘密鍵。

\item[署名] メッセージ$m$に対して
整数$k$をランダムに選び$r:=(g^k \bmod{p}) \bmod{q}$とする。
\[
s:=(H(m)+xr)/k\bmod{q}
\]
を計算し$(r,s)$を$m$に対する署名とする。
\item[検証] 署名$(r,s)$について
最初に$0 < r, s < q$を確認する。範囲外なら棄却する。メッセージ$m$に対して
\begin{align*}
& w:=s^{-1} \bmod{q}, \quad u_1:=H(m)w \bmod{q},\\
& u_2:=rw \bmod{q}, \quad v:= (g^{u_1} y^{u_2} \bmod{p}) \bmod{q}
\end{align*}
を求めて$v=r$なら署名を受理し、そうでないなら棄却する。
}
$p$と$q$の二種類の剰余を使います。
これは$p$が大きいので$q$で割ってよいところは$q$を使って効率化するためです。
正しいメッセージに対して署名が受理されることを確認しましょう。
上記手順にしたがって$m$に対する署名$(r,s)$を作ります。
すると、
\[
w = s^{-1}=k/(H(m)+xr), \quad g^{u_1} y^{u_2} = g^{H(m)w} (g^x)^{rw} = g^{(H(m)+xr)w}=g^k = r
\]
となって検証が通ります。

\section{ブラインド署名}
\label{blind_sig}
1982年、Chaumはブラインド署名~\cite{chaum83blindsign}という面白い概念を提案しました。
これは署名者がどんなメッセージに署名しているか知らないままで署名させるというものです。
実際にするならこんな感じでしょうか。
Aさんがメッセージ$m$をBさんに署名して欲しいとします。
まずAはメッセージを封筒に入れます。
封筒には署名欄のところだけ切り抜いて穴を空けておきます。
Bは封筒に入ったままメッセージを読まずに署名欄に署名します。
Aは封筒からBの署名が入ったメッセージをとりだします。

現実世界で何に署名しているか知らないまま署名するのはとても怖いことです。
詐欺にあうかもしれません。
しかし、ブラインド署名は電子投票や電子マネーなど匿名性を担保したままその内容を保証したいときの利用が考えられています。
選挙管理委員に投票内容を教えないまま投票用紙としての正当性を選挙管理委員に保証してもらったり、
電子マネーの紙幣の番号を教えずに銀行にそのマネーの保証をしてもらったりします。
電子投票については\ref{vote}節でもう少し詳しく考察します。
ブラインド署名の枠組みを考えます。
まずBが使う署名の公開鍵と秘密鍵を生成します。
Aはメッセージ$m$を他人が読めない形$x:=\Blind(m)$にしてBに渡します（ブラインド処理）。
Bは$x$に署名をして$y:=\Sign(x)$をAに返します（署名処理）。
Aは$y$から$\Unblind(y)$を求めます（アンブラインド処理）。
\[
\Unblind(y)=\Unblind(\Sign(\Blind(m)))=\Sign(m)
\]
となっているとAが$m$を公開すれば誰もが$(m,\Sign(m))$はBが署名したということを確認できます。
\image{blind.pdf}{ブラインド署名の概念処理}
RSA署名を使ったブラインド署名を紹介しましょう。
\mydescription{
\item[鍵生成]
BはRSA-FDH署名の署名鍵$d$と検証鍵$(n,e,H)$を用意する。
\item[ブラインド]
Aはメッセージ$m$に対して乱数$r$を選んで$x$を計算してBに渡す。
\[
x:=\Blind(m):=r^e H(m) \bmod{n}.
\]
\item[署名]
Bは$x$に対して署名$y$を計算してAに返す。
\[
y:=\Sign(x):=x^d \bmod{n}.
\]
\item[アンブラインド]
Aは$y$からメッセージ$m$に対するBの署名$s$を計算する。
\[
s:=\Unblind(y):= y/r \bmod{n}.
\]
}
この方法で正しく署名ができていることを確認します。
\[
y \equiv x^d \equiv (r^e H(m))^d = r^{ed} H(m)^d \equiv r H(m)^d \bmod{n}
\]
なので
\[
s \equiv y/r \equiv H(m)^d \bmod{n}
\]
となりAは$m$に対するBのRSA-FDH署名を取得できています。

\section{秘匿共通集合計算}
\label{sec:psi}
\ruby{秘匿}{ひ|とく}共通集合計算（PSI : Private Set Intersection）とは、あるデータの集合に対してAさんとBさんがそれぞれその部分集合を持っているとき、
お互いに何を持っているのか秘密にしたまま共通する要素を特定する技術です。

物騒な例ですが、政府が極秘でテロリストの容疑者の一覧を持っているとします。
飛行機会社は搭乗者の中にテロリストがいないか調べたいとします。
PSIを使うことによって搭乗者の情報を政府に知らせることなく、また政府はテロリストのリストを飛行機会社に知らせずにその要求を満たせます。
\image{psi.pdf}{PSI}

他にも通信情報、遺伝子情報など様々なプライベートな情報に対する操作でPSIが使える部分はあるでしょう。
\ref{chemical}節では化合物データベースの検索への応用例を紹介します。
PSIは様々な実現方法が提案されていますが、ここではブラインド署名を使った方法を紹介しましょう。

Aさんが$S_A:=\Set{a_i|i=1, \dots, N_A}$, Bさんが$S_B:=\Set{b_j|j=1, \dots, N_B}$を持っているとします。
AがBに問い合わせることでAは$S_A \cap S_B$を求めます。
\begin{itemize}
\item[1.] Bはブラインド署名の鍵生成を行う。ブラインド署名に使うハッシュ関数とは別のハッシュ関数$H$を用意する。
\item[2.] Aは各$a_i$に対してブラインド署名プロトコルを使って$s_i:=\Sign_B(a_i)$を取得する。
\item[3.] Bは各$b_j$に対して署名をしてからハッシュをとり$\Set{b'_j:=H(\Sign_B(b_j))}$をAに送る。
\item[4.] Aは$s_i$から$a'_i:=H(\Sign_B(a_i))$を求めて$\Set{a'_i}$と$\Set{b'_j}$を比較し、同じ値があるかを探す。
それが共通部分集合である。
\end{itemize}
この方式は演算量が要素の個数ですみます。
ただしこの方式だとBは共通部分の情報を得られないのでAとBの立場が対等ではありません。
またAは$H(\Sign_B(b_j))$の値をもらっています。
これから$b_j$の情報を引き出すのは無理ですが、この値は確定的です。
そのためこのプロトコルを複数回行った場合、もしBの集合$S_B$に変化があると「どの番号の要素が変わった」という情報がAに伝わってしまいます。
これらの欠点の改良案もいろいろ提案されています。

なお、ブラインド署名を使わずにBがAにハッシュ関数$\Set{b_j':=H(b_j)}$を渡してもよいのではと思われるかもしれません。
しかし、この方法では$b_j$の予想できる種類が多くないとき、Aは自分で手当たり次第に$H(b_k)$を計算して$b_j'$と比較できます。
そうするとどの$b_k$をもらったかわかってしまいます。ですからハッシュ関数だけでは駄目なのです。

\section{部分ブラインド署名}
ブラインド署名は大変有用な技術ですが問題点もあります。
それは署名者がどんなメッセージに署名をしているか全くわからない点にあります。
この性質がまさにブラインド署名の特長なのですが、署名をさせる人が悪意を持っている場合に対処できません。
そのため部分ブラインド署名という概念が提案されました。

これはメッセージの一部を両者が共有することで署名者が署名してよいかどうかを判断できるようにした方式です。
たとえば共有するメッセージの部分に有効期限を入れておく、署名要求者の名前を入れるなどが想定されます。
2000年に阿部氏、岡本氏により提案された方式~\cite{Abe:2000}を紹介しましょう。
これは離散対数問題を安全性の根拠に置くSchnorr署名の拡張になっています。
Aさんが署名をしてほしい人、Bさんが署名者です。メッセージを$m$、両者が共有するメッセージを$m'$とします。
\begin{enumerate}
%\myitemindent
\item $(p,q,g)$をDHパラメータ（\ref{dh-param}節参照）とする。
$p$と$q$は$p-1$が$q$の倍数となる素数で$g^q=1 \bmod{p}$である。
Bは秘密鍵$x$を決めて$y:=g^x \bmod{p}$を公開鍵とする。
更にハッシュ関数$H$を決める。
\item Bは$m'$を確認してブラインド署名することに決める。
整数$u$, $s$, $d$をランダムに選ぶ。$z:=H(m')$, $a:=g^u$, $b:=g^sz^d$を計算して$(a,b)$をAに送る。
\item Aは$z=H(m')$を確認し、整数$t_1$, $t_2$, $t_3$, $t_4$をランダムに選び
\[
\alpha:=ag^{t_1} y^{t_2}, \quad \beta:=bg^{t_3} z^{t_4}, \quad
\epsilon:=H(\alpha, \beta, z, m), \quad e:=\epsilon-t_2 - t_4
\]
を計算して$e$をBに送る。
\item Bは$c:=e-d$, $r:=u-cx$を計算しAに$(r,c,s,d)$を送る。
\item Aは$\rho:=r+t_1$, $\omega:=c+t_2$, $\sigma:=s+t_3$, $\delta:=d+t_4$を計算し$(\rho,\omega,\sigma,\delta)$を$m$に対する署名とする。
\item 署名の検証は
\[
\omega + \delta \eqq H(g^{\rho} y^{\omega}, g^{\sigma} z^{\delta}, z, m)
\]
が成立するかどうかで判定する。
\end{enumerate}
正しく計算しているなら
\begin{align*}
&\omega+\delta=c+t_2 + d+t_4=e-d+t_2+d+t_4=(\epsilon-t_2-t_4)+t_2+t_4=\epsilon,\\
&g^{\rho}y^{\omega}=g^{r+t_1}(g^x)^{\omega}=g^{(u-cx)+t_1+cx+t_2x}=g^{u+t_1+t_2x}=g^ug^{t_1}y^{t_2}=\alpha,\\
&g^{\sigma}z^{\delta}=g^{s+t_3}z^{d+t_4}=(g^sz^d)g^{t_3}z^{t_4}=\beta \text{より}\\
&H(g^{\rho} y^{\omega}, g^{\sigma} z^{\delta}, z, m)=H(\alpha, \beta, z, m)=\epsilon
\end{align*}
となることを確認できます。
この方式はDLP仮定のもとで安全と証明されています。

\section{この章のまとめ}
公開鍵基盤に必要な認証について説明しました。
ハッシュ関数は任意のメッセージを固定長の値（ハッシュ値）に変換する関数です。

ハッシュ関数はハッシュ値から元のメッセージを復元できるものであってはいけません。
より強く、同じハッシュ値になる異なる2個のメッセージが見つけられるものであってもいけません。
前者の性質を原像計算困難性、後者の性質を衝突困難性といいます。

認証には主に、メッセージが改竄されていないかを検証するメッセージ認証と、メッセージを書いた人が本人であることを検証するデジタル署名があります。
メッセージ認証は共通鍵暗号、デジタル署名は公開鍵暗号と関係が深いです。