出てくるもの（3）：誤り訂正と秘匿性増幅

相対エントロピーから情報と物理を組み立てる　第3部 第10章 §3.10.5　★★ 誤り訂正で公開する分 $H(A\,|\,B)$ を引き、2-universal なハッシュで $S(A\,|\,E)$ まで縮める。漸近では Devetak–Winter の鍵率になる

誤り訂正：公開した分だけ Eve の不確かさが減る

ふるい分けと誤り率の見積もりの後、Alice は $n$ ビット $A^n$、Bob はそれと少し違う $B^n$ を持っている。Alice は $A^n$ の関数 $C=f(A^n)$（たとえば線形符号のシンドローム）を公開し、Bob は $B^n$ と $C$ から $A^n$ を復元する。Slepian と Wolf の定理¹1D. Slepian and J. K. Wolf (1973), IEEE Trans. Inf. Theory 19, 471.下の脚注へ閉じるによれば、$n\to\infty$ で必要な公開の量は1ビットあたり $H(A\,|\,B)$ で足りる。ビットの誤り率が $e_z$ の対称な誤りなら $H(A\,|\,B)=h_{\mathrm b}(e_z)$ である。

公開した $C$ は Eve も聞いている。Eve の不確かさがどれだけ減るかは、次の式で押さえられる。$C$ は $A^n$ の関数なので $S(A^nC\,|\,E)=S(A^n\,|\,E)$ で、条件付きエントロピーの連鎖律と $H(C\,|\,E)\le\ln\lvert \mathcal C\rvert$（$\lvert \mathcal C\rvert$ は $C$ のとりうる値の数）から

$$S(A^n\,|\,EC)=S(A^nC\,|\,E)-H(C\,|\,E)\ge S(A^n\,|\,E)-\ln\lvert \mathcal C\rvert\tag{3.10.16}$$

である。公開したビット数の分だけ、Eve の不確かさは最大で減る。誤り訂正の後に Eve に残る不確かさは、1ビットあたり $S(A\,|\,E)-H(A\,|\,B)$ 以上ある。

秘匿性増幅：ハッシュで縮める

誤り訂正の後、Alice と Bob は同じ $n$ ビットを持つが、Eve はそれについて部分的な情報を持っている。2人は公開の乱数で関数 $f$ を選び、$n$ ビットを $\ell$ ビットの $f(A^n)$ に縮める。$\ell$ が Eve の不確かさより十分小さければ、縮めた鍵は Eve からほとんど独立で一様になる。これを秘匿性増幅と呼ぶ²2C. H. Bennett, G. Brassard, C. Crépeau and U. M. Maurer (1995), IEEE Trans. Inf. Theory 41, 1915. Eve が量子の系を持つ場合は R. Renner (2005), 博士論文（ETH Zürich）, arXiv:quant-ph/0512258.下の脚注へ閉じる。

関数の選び方には次の性質を課す。$n$ ビットから $\ell$ ビットへの関数の集まり $\mathcal F$ が 2-universal であるとは、異なる $x\ne x'$ のどの組についても、$\mathcal F$ から一様に選んだ $f$ で $f(x)=f(x')$ となる確率が $2^{-\ell}$ 以下になることをいう。$\ell\times n$ の 0/1 行列 $\hat M$ 全体から一様に選び $f(x)=\hat Mx$（2を法とする積）とすると、$x\oplus x'\ne0$ に対して $\hat M(x\oplus x')$ は $\ell$ ビットの一様な乱数になるので、衝突の確率はちょうど $2^{-\ell}$ である。

Eve の不確かさの測り方として、Eve が $A$ を1回で当てる確率の最大値 $p_{\mathrm{guess}}(A\,|\,E)$ を使い、$H_{\min}(A\,|\,E)=-\ln p_{\mathrm{guess}}(A\,|\,E)$ を最小エントロピーと呼ぶ³3当てる確率による解釈は R. König, R. Renner and C. Schaffner (2009), IEEE Trans. Inf. Theory 55, 4337.下の脚注へ閉じる。秘匿性増幅の保証は次の形をとる（ハッシュの残り物の補題）。2-universal な $\mathcal F$ から一様に選んだ $f$ について

$$\frac12\bigl\|\hat\rho_{f(A)FE}-\tfrac{1}{2^\ell}\mathbf 1\otimes\hat\rho_{FE}\bigr\|_1\le\frac12\exp\Bigl(-\frac{H_{\min}(A\,|\,E)-\ell\ln2}{2}\Bigr)\tag{3.10.17}$$

が成り立つ（$F$ は選んだ関数を記録した古典の系で、Eve も知っている）。左辺は、実際の鍵と理想の鍵（一様で Eve と独立）のトレース距離である。3.10.1節では秘密の度合いを相対エントロピーで測ったが、Pinsker の不等式 $\frac12\|\hat\rho-\hat\sigma\|_1\le\sqrt{D(\hat\rho\,\|\,\hat\sigma)/2}$ により、相対エントロピーが小さければトレース距離も小さい。右辺を $\varepsilon$ 以下にするには、ビットで数えて

$$\ell\le\frac{H_{\min}(A\,|\,E)}{\ln2}-2\log_2\frac1{2\varepsilon }\tag{3.10.18}$$

にすればよい。

漸近の鍵の長さ

最小エントロピーは von Neumann エントロピー以下で、一般には小さい。しかし独立な写しが $n$ 個あるとき、小さな確率 $\varepsilon '$ の分だけ状態をならした最小エントロピー $H_{\min}^{\varepsilon '}$ について$\frac1nH_{\min}^{\varepsilon '}(A^n\,|\,E^n)\to S(A\,|\,E)$ が成り立つ（量子の漸近等分割性）⁴4M. Tomamichel, R. Colbeck and R. Renner (2009), IEEE Trans. Inf. Theory 55, 5840.下の脚注へ閉じる。これは第1部第2章（第1部第2章）の典型系列の量子版で、ほとんどの確率がエントロピーで決まる大きさの典型的な部分に集まるために成り立つ。これと式 (3.10.16) を合わせると、誤り訂正と秘匿性増幅の後に残る鍵は1ビットあたり

$$\frac{\ell}{n}\to S(A\,|\,E)-H(A\,|\,B)$$

で、Devetak–Winter の式 (3.10.7) と一致する。定理 3.10.4 の2つの項は、それぞれ「誤り訂正で公開した分」と「秘匿性増幅で残せる分」だった。

有限の $n$ では、誤り率を見積もるときの統計的なゆらぎと、漸近等分割性の $\sqrt n$ 程度の補正を差し引く必要がある。それらを無視した粗い見積もりは、BB84 で$\ell\approx n[1-2h_{\mathrm b}(Q)/\ln2]-2\log_2(1/\varepsilon )$ になる。$n=10^6$、$Q=0.02$、$\varepsilon =10^{-10}$ なら、誤り訂正で公開する量が $n\,h_{\mathrm b}(0.02)/\ln2\approx1.41\times10^5$ ビット、鍵は $\ell\approx7.17\times10^5$ ビットである。$\varepsilon$ の分の $2\log_2(10^{10})=66$ ビットは、この大きさの $n$ ではわずかである。

1　D. Slepian and J. K. Wolf (1973), IEEE Trans. Inf. Theory 19, 471.

2　C. H. Bennett, G. Brassard, C. Crépeau and U. M. Maurer (1995), IEEE Trans. Inf. Theory 41, 1915. Eve が量子の系を持つ場合は R. Renner (2005), 博士論文（ETH Zürich）, arXiv:quant-ph/0512258.

3　当てる確率による解釈は R. König, R. Renner and C. Schaffner (2009), IEEE Trans. Inf. Theory 55, 4337.

4　M. Tomamichel, R. Colbeck and R. Renner (2009), IEEE Trans. Inf. Theory 55, 5840.