EPOC (暗号)
EPOC（Efficient Probabilistic Public Key Encryption）は、1998年4月にNTT情報通信研究所の岡本龍明氏と内山成憲氏によって発表された公開鍵[[暗号]]方式です。この方式の最大の特徴は、同一の平文に対して異なる暗号文を生成できる確率的暗号であるという点です。これにより、暗号のセキュリティ強度を高めることが可能になります。
EPOCは、鍵生成、暗号化、復号という3つの主要なアルゴリズムで定義されます。
まず、秘密鍵として、同じサイズの2つの素数 \( p \) と \( q \) を選びます。次に、これらの素数を用いて合成数 \( n = p^2q \) を計算します。さらに、\( n \) と互いに素な剰余類群 \( (\mathbb{Z} / n\mathbb{Z})^ \) の元となる正整数 \( g \) を選びます。この \( n \) と \( g \) が公開鍵となります。
平文を \( m \) （ただし、\( 0 < m < p \)）、乱数を \( r \) （ただし、\( 0 < r < n \)）とします。このとき、暗号文 \( C \) は次の式で計算されます。
\( C = g^{m + nr} \mod n \)
復号には、まず \( C_p = C^{p-1} \mod p^2 \) と \( g_p = g^{p-1} \mod p^2 \) を計算します。次に、フェルマー商を求める関数 \( L(x) = \frac{x-1}{p} \) を用いて、平文 \( m \) を以下の式で復号します。
\( m = \frac{L(C_p)}{L(g_p)} \mod p \)
EPOCの安全性は、ランダムオラクルモデルに基づいています。このモデルでは、真にランダムなハッシュ関数を使用することで、EPOCの根幹をなす関数が安全な暗号化システムとして機能します。この結果、このシステムは選択暗号文攻撃に対しても意味的に安全であることが証明されています。
EPOCの基礎となるのは、岡本・内山（OU）関数です。OU関数を反転することは、公開鍵を素因数分解することと同程度の困難さを持つことが示されています。これは、EPOCのセキュリティの強固さを示す重要な根拠となっています。
EPOCには、以下の3つのバージョンが存在します。
EPOC-1: 一方向性トラップドア関数とランダム関数（ハッシュ関数）を使用します。主に鍵の配布を目的としています。
EPOC-2: 一方向性トラップドア関数、2つのランダム関数（ハッシュ関数）、および対称鍵暗号化（例: ワンタイムパッドやブロック[[暗号]]）を使用します。鍵の配布と暗号化されたデータ転送の両方に使用されます。
EPOC-3: 岡本内山一方向トラップドア関数、2つのランダム関数（ハッシュ関数）、および対称暗号化方式（ワンタイムパッドや従来のブロック[[暗号]]）を使用します。こちらも鍵の配布と暗号化されたデータ転送に使用されます。
EPOC-1は主に鍵配布に、EPOC-2とEPOC-3は鍵配布と暗号化されたデータ転送の両方を目的として設計されています。これらのバージョンは、それぞれのユースケースに応じて使い分けることができます。
* “公開鍵[[暗号]]方式EPOCについて” (PDF) 日本銀行金融研究所 (1998年8月). 2022年12月24日閲覧。
暗号方式の詳細
EPOCは、鍵生成、暗号化、復号という3つの主要なアルゴリズムで定義されます。
鍵生成
まず、秘密鍵として、同じサイズの2つの素数 \( p \) と \( q \) を選びます。次に、これらの素数を用いて合成数 \( n = p^2q \) を計算します。さらに、\( n \) と互いに素な剰余類群 \( (\mathbb{Z} / n\mathbb{Z})^ \) の元となる正整数 \( g \) を選びます。この \( n \) と \( g \) が公開鍵となります。
暗号化
平文を \( m \) （ただし、\( 0 < m < p \)）、乱数を \( r \) （ただし、\( 0 < r < n \)）とします。このとき、暗号文 \( C \) は次の式で計算されます。
\( C = g^{m + nr} \mod n \)
復号
復号には、まず \( C_p = C^{p-1} \mod p^2 \) と \( g_p = g^{p-1} \mod p^2 \) を計算します。次に、フェルマー商を求める関数 \( L(x) = \frac{x-1}{p} \) を用いて、平文 \( m \) を以下の式で復号します。
\( m = \frac{L(C_p)}{L(g_p)} \mod p \)
安全性について
EPOCの安全性は、ランダムオラクルモデルに基づいています。このモデルでは、真にランダムなハッシュ関数を使用することで、EPOCの根幹をなす関数が安全な暗号化システムとして機能します。この結果、このシステムは選択暗号文攻撃に対しても意味的に安全であることが証明されています。
EPOCの基礎となるのは、岡本・内山（OU）関数です。OU関数を反転することは、公開鍵を素因数分解することと同程度の困難さを持つことが示されています。これは、EPOCのセキュリティの強固さを示す重要な根拠となっています。
EPOCのバージョン
EPOCには、以下の3つのバージョンが存在します。
EPOC-1: 一方向性トラップドア関数とランダム関数（ハッシュ関数）を使用します。主に鍵の配布を目的としています。
EPOC-2: 一方向性トラップドア関数、2つのランダム関数（ハッシュ関数）、および対称鍵暗号化（例: ワンタイムパッドやブロック[[暗号]]）を使用します。鍵の配布と暗号化されたデータ転送の両方に使用されます。
EPOC-3: 岡本内山一方向トラップドア関数、2つのランダム関数（ハッシュ関数）、および対称暗号化方式（ワンタイムパッドや従来のブロック[[暗号]]）を使用します。こちらも鍵の配布と暗号化されたデータ転送に使用されます。
EPOC-1は主に鍵配布に、EPOC-2とEPOC-3は鍵配布と暗号化されたデータ転送の両方を目的として設計されています。これらのバージョンは、それぞれのユースケースに応じて使い分けることができます。
参考文献
* “公開鍵[[暗号]]方式EPOCについて” (PDF) 日本銀行金融研究所 (1998年8月). 2022年12月24日閲覧。
もう一度検索
【記事の利用について】
タイトルと記事文章は、記事のあるページにリンクを張っていただければ、無料で利用できます。
※画像は、利用できませんのでご注意ください。
【リンクついて】
リンクフリーです。