準備 - 暗号理論教室

準備

等式/不等式

• 1/2 + 1/4 + ・・・ + 1/2ⁿ = 1 - 1/2ⁿ.

• n^1/n → +1      (n → ∞).

• (n/k)^k ≦ _nC_k ≦ (ne/k)^k.

• ε > -1 　⇒ 　1/(1 +ε) ≧ 1 - ε.

• 任意の x ∈ R について、1+x ≦ e^x.
• 任意の x ≧ 1 について、(1 - 1/x)^x ≦ 1/e ≦ (1 - 1/(x+1))^x.
• 任意の x ≧ 1 について、1 - 1/x ≦ e^-1/x ≦ 1 - 1/(x+1).
• 任意の x > 1 について、1 + 1/x ≦ e^1/x ≦ 1 + 1/(x-1).

• 1 - 1/(x+1) ≧ e^-1/x (x > 0)

• q > 0 について、δ(∈[0,1])の関数δ・(1-δ)^q は δ=1/(q+1) のとき最大で、その値≧1/{e・(q+1)}.

• Pr[A|B] ≧ Pr[A∩B] ≧ Pr[A] - Pr[¬B].

• For every A, B \subset {0,1}ⁿ, Σ_{x \in A, y \in B} M_x,y = 1_A^T M 1_B.

• (a₁ + ... + a_N)² ≦ N (a₁² + ... + a_N²)

補題

確率

確率変数Xについて

• Var[X] =^def E[(X - E[X])²] = E[X²] - E[X]²
  • ※ Xがバイナリならば、Var[X] ≦ 1.
• 標準偏差σ[X] =^def (Var[X])^1/2

補題
確率変数X₁, ... , X_nが組ごとに独立ならば、

• Var[ Σ_i=1..n X_i ] = Σ_1=1..n Var[X_i].

補題(Markov)
Xを非負の確率変数とするとき、

• Pr[ X ≧ k E[X] ] ≦ 1/k.

補題(Chebyshev)
Xを標準偏差σの確率変数とするとき、任意の k > 0 について、

• Pr[ | X - E[X] | > kσ ] ≦ 1/k².

補題(Chernoff)
X₁, X₂, ..., X_nを互いに独立なバイナリ確率変数とし、
μ = Σ_i=1..n E[X_i] とするとき、任意の c > 0 について、

• Pr[ | Σ_i=1..n X_i - μ | ≧ cμ ] ≦ 2 e^{-min(c2/4, c/2) μ}.

補題(Chernoff)
X₁, X₂, ..., X_nを互いに独立なバイナリ確率変数とし、X = X₁ +・・・+ X_n、μ = E[X] とするとき、

• (lower tail) ∀δ∈ (0, 1] について、
  • Pr[ X < (1 - δ) μ] < exp( -μδ² / 2).
• (upper tail) 0 < δ < 2e - 1について、
  • Pr[ X > (1 + δ) μ] < exp( -μδ² / 4).

補題(Hoeffding)
X₁, X₂, ..., X_nを互いに独立な、区間 [a,b] 上の、平均μの確率変数とし、X = X₁ +・・・+ X_n とするとき、

• ∀ k > 0 について、
  • Pr[ |X - μ n| ≧ k] ≦ exp( - 2k² / (n(b-a)²) ).

補題(Leftover Hash Lemma, インフォーマル)
H が universal hash, H_∞(X|Z) が十分大
⇒ (Z, K, H(K,X))は(Z, K, U)に統計的に十分近い。

数論

補題(CS)
gcd(a,b) = 1 である整数x, y, a, bについて

• x^a ≡ y^b (mod N)

ならば、

• x'^a ≡ y (mod N)

となる整数 x' を効率的に計算できる。

証明

補題[CS 03]
素因数分解仮定のもとで、与えられた（強素数の積である）整数 n 、
およびランダムな g, h ∈ (Z_n^*)² について、

• 1 = g^a h^b, a≠0, b≠ 0

となる整数 a, b を求めることは困難である。

補題[CS 03]
強RSA仮定のもとで、与えられた（強素数の積である）整数 n 、
およびランダムな g, h ∈ (Z_n^*)² について、

• w^c = g^a h^b, ¬(c | a, c | b)

となる整数 a, b, c を求めることは困難である。

CRT係数
F1, F2, F3 : pairwise co-prime

• ((F2 F3)^-1 mod F1) F2 F3

基本概念

ネグリジブルな関数

関数ε： N →　R₊ が ネグリジブルであるとは、
任意の c > 0 について、ある K があって、

• ε(n) < 1 / n^c　     (n ≧ k)

であることをいう。

統計的距離

2つの確率変数 X, Yについて、

• Δ[X, Y] =^def 1/2 Σ_α | Pr[X = α] - Pr[Y = α] |

をXとYの間の統計的距離という。任意の変換φについて、

• Δ[φ(X), φ(Y)] ≦ Δ[X, Y].

識別不可能性

2つの確率変数族 X = {X_s}_s∈S, Y = {Y_s}_s∈Sが統計的に識別不可能であるとは、
あるネグリジブルな関数εがあって、任意の s∈S について、

• Δ[X_s, Y_s] < ε(|s|)

であることをいう。

• X ≡_s Y

とかく。

2つの確率変数族 X = {X_s}_s∈S, Y = {Y_s}_s∈Sが計算的に識別不可能であるとは、
任意の効率的なアルゴリズムDに対し、あるネグリジブルな関数εがあって、

• | Pr[α ← X_s ： D(s,α) = 1] - Pr[α ← Y_s ： D(s,α) = 1] | < ε(|s|)

であることをいう。

• X ≡_c Y

とかく。

ハッシュ関数

定義
ハッシュ関数 {H_k : {0,1}* → {0,1}^l}_k が 衝突困難 であるとは、
任意の効率的なアルゴリズムAについて、確率

• Pr[ k ← {0,1}ⁿ, (x₀, x₁) ← A(k) ：
  • x₀ ≠ x₁, H_k(x₀) = H_k(x₁) ]

がネグリジブルであることをいう。

定義
ハッシュ関数族 H = {H_k}_k∈N が division intractable であるとは、
任意の効率的な攻撃者Aに対し、

• Pr[ h ← H_k, (X₁,...,X_n, Y) ← A(h) :
  • Y ≠ X_i (for i=1..n) かつ h(Y)が積Π_i=1..nh(X_i) をわりきる ]

が（kについて）ネグリジブルであることをいう。

双線形群

双線形群の定義

素数位数pの3つの巡回群G₁, G₂, G_Tについて、
写像 e : G₁ x G₂ → G_Tが双線形写像であるとは、

• (双線形) u∈G₁, v ∈ G₂, a, b ∈ Z_pについて、e(u^a, v^b) = e(u, v)^{a b}.
• (非退化) u≠1, v≠1 ならば e(u, v)≠ 1.

であることをいう。

(G₁, G₂)が双線形群であるとは、

• G₁, G₂の群演算がそれぞれ効率的に計算可能で、
• ある群G_Tについて双線形写像 e: G₁ x G₂ → G_T も効率的に計算可能で、さらに
• ある効率的に計算可能な群準同型写像 Ψ:G₂ → G₁ が存在する

ことをいう。

Gが双線形群であるとは、

• Gの群演算が効率的に計算可能で、
• ある群G_Tについて双線形写像 e: G x G → G_T も効率的に計算可能

であることをいう。

双線形写像のインバート可能性

双線形群Gとその要素u（≠1）について、GからG_Tへの写像

• f_u(x) = e(u, x)

を考える。

写像f_uがインバート可能ならば、双線形群G上のBDHP問題

• Gの要素 u, u^a, u^b, u^c を与えられて、G_Tの要素e(u, u)^abcを求める

は容易である。実際、

• e(u^a, u^b) = e(u, u^ab)

のf_uに関する逆像u^abを求めて、

• e(u^ab, u^c) = e(u, u)^abc.

同様に、写像f_uがインバート可能ならば、G_T上の判定DH問題

• G_Tの要素 g, g^a, g^b, h を与えられて、h =^? g^ab を判定する

も容易である。実際、

• f_u(v) = e(u, v) = g
• f_u(v^a) = e(u, v^a) = g^a
• f_u(v^b) = e(u, v^b) = g^b
• f_u(w) = e(u, w) = h

となる v, v^a, v^b, w を求めて、

• e(v, w) =^? e(v^a, v^b).

上へ

---