とても滑らかなハッシュ

ベリースムースハッシュ（VSH）
一般的な
デザイナー	スコット・コンティーニ、アリエン・K・レンストラ、ロン・スタインフェルド
初版	2005
後継者	VSH*
詳細
ダイジェストサイズ	1024ビット以上

暗号学において、Very Smooth Hash (VSH)は、2005 年に Scott Contini、Arjen Lenstra、Ron Steinfeld によって発明された、証明可能に安全な暗号ハッシュ関数です。 ^[1] 証明可能に安全とは、衝突を見つけることが、既知の難しい数学的問題と同じくらい難しいことを意味します。他の証明可能に安全な衝突耐性ハッシュとは異なり、VSH は効率的で、実際に使用できます。漸近的には、 $log(n)$ メッセージビットごとに 1 回の乗算のみが必要で、RSA タイプの演算を使用します。そのため、VSH は、コード領域が限られている組み込み環境で役立ちます。

VSH には 2 つの主要なバリエーションが提案されています。1 つは、衝突を見つけることが、 $n$ を法とする非常に滑らかな数の非自明なモジュラー平方根を見つけることと同じくらい難しいことが証明されているものです。もう 1 つは素数 $p を法とする ($ トラップドアなし) もので、そのセキュリティ証明は $p$ を法とする非常に滑らかな数の離散対数を見つけることの難しさに依存しています。どちらのバージョンも効率は同様です。

VSH はランダムオラクルの代替としては適していませんが、証明可能で安全なランダム化トラップドアハッシュ関数の構築に使用できます。この関数は、Cramer-Shoup 署名方式で使用されるトラップドア関数を置き換えることができ、証明可能なセキュリティを維持しながら検証時間を約 50% 高速化します。

VSN と VSSR

^{現在[いつ? ]}広く使用されているすべての暗号ハッシュ関数は、難しい数学の問題に基づいているわけではありません。難しい数学の問題に基づいて構築されたいくつかの関数は、証明可能に安全であると呼ばれます。衝突を見つけることは、難しい数学の問題を解くのと同じくらい難しいことが知られています。Very Smooth Hash の基本バージョンでは、この難しい問題は、特定の特殊数 (VSN) のモジュラー平方根(VSSR)を見つけることです。 ^{[1]これは、}整数を因数分解するのと同じくらい難しいと想定されています。

固定定数 $c$ と $n$ に対して、整数 $m$ の最大素因数が最大で $log($ $n$ $)$ $c$ $である場合、その整数mは$ 非常に滑らかな数(VSN)です。

整数 $b が$ $n を$ 法とした非常に滑らかな二次剰余 であるとは、 $bを因数分解した際の最大の素数が$ $log($ $n$ $)$ $c$ 以下であり、 $b$ $\equiv$ $x$ $2$ $(mod$ $n$ $)$ となる整数 $x が$ 存在する場合を指します。このとき、整数 $x は$ $b$ のモジュラー平方根であるといわれます。

$ここで注目するのは、 x 2 \geq n$ である非自明な平方根だけです。 $x 2 < n$ の場合、実数体などの特性0の体からのアルゴリズムを使用して、簡単に平方根を計算できます。したがって、これらは暗号プリミティブには適していません。

非常に滑らかな数の非自明なモジュラー平方根(VSSR) は次の問題です。 $n を$ ほぼ同じ大きさの 2 つの未知の素数の積とし、 $k \leq (log(n)) c$ とし、 $(p 1 、 p 2 、 p 3 、\dots) = (2,3,5,\dots)$ を素数のシーケンスとします。 $nが与えられた場合、$ $n$ と互いに素で、 $e$ $0$ $、\dots、$ $e$ $k$ の少なくとも 1 つが奇数である整数 $x を見つけます。$ $\textstyle x^{2}\equiv \prod _{i=0}^{k}p_{i}^{e_{i}}{\pmod {n}}$

VSSR仮定は、無視できない確率で VSSR を解く確率多項式( $log(n)$ 単位) 時間アルゴリズムは存在しないというものです。これは、どのサイズのモジュラスに対して VSSR が計算上困難であるかを示さないため、実際には役に立たない仮定であると考えられています。代わりに、計算 VSSR 仮定が使用されます。これは、VSSR を解くことは、因数分解が困難な $s$ ビットモジュラス ( $sは$ $n$ のサイズよりいくらか小さい)を因数分解するのと同じくらい難しいと仮定するものです。

VSN と VSSR の例

パラメータを $c = 5$ および $n = 31$ に固定します。

すると、 $log(31)$ $5$ $\approx 7.37は$ $m$ $1$ のすべての素因数より大きいため、 $m 1 = 35 = 5 \cdot 7$ はこれらのパラメータに関して非常に滑らかな数になります。一方、 $m$ $2$ $= 55 = 5 \cdot 11$ はこれらのパラメータの下では VSN ではありません。

整数 $9は$ $、$ 非常に滑らかな数 ( $c 、 n$ の下で) であり、 $32 \equiv 9 (mod n)であるため、 n を法とする非常に滑らかな二次剰余です。これは、$ $9 < n$ であり、平方するときに係数が関係しないため、単純なモジュラー平方根です。

この整数はを法とする非常に滑らかな二乗剰余でもあります。すべての素因数は 7.37 より小さく、モジュラー平方根は(mod )なのでです。したがって、これは自明でない根です。VSSR 問題は、与えられたおよびを見つけることです。そして、これはを因数分解するのと同じくらい計算的に難しいと仮定します。 $b_{2}=15$ $n$ $x_{2}=20$ $20^{2}=400\equiv 15$ $n$ $x_{2}$ $b_{2}$ $n$ $n$

整数 $b = 15も$ $n を$ 法とする非常に滑らかな二次剰余です。その素因数はすべて 7.37 より小さく、モジュラー平方根は $x = 20です。これは、$ $202 = 400 \equiv 15 (mod n)$ です。したがって、これは非自明な平方根です。VSSR 問題は、 $b$ と $n$ が与えられたときに $x を見つけることです。これは、計算上、$ $n を$ 因数分解するのと同じくらい難しいと考えられています。

VSHアルゴリズム、基本バージョン

$n を$ 大きな RSA 複合値とし、( $p 1, p 2, p 3, \dots) = (2,3,5,\dots) を$ 素数列とします。ブロック長 $kを、となる最大の整数とします。m$ $を、ビット$ $($ $m$ $1$ $,\dots,$ $m$ $ℓ$ $)$ で構成されるハッシュ対象の $ℓ$ ビットメッセージとし、 $ℓ < 2$ $k$ と仮定します $。m$ のハッシュを計算するには、次のようにします。 $\textstyle \prod _{i=1}^{k}p_{i}<n$

$x 0 = 1$ と設定します。
$ℓ/$ $k$ 以上の最小の整数 $L$ をブロックの数とします。
$ℓ <$ $i$ $<$ $Lk$ （パディング）の場合、 $m i = 0$ とします。
$ℓ$ $i$ $\in {0,1}$ をメッセージ長 $ℓ$ の2進表現とし、 $1 \leq$ $i$ $\leq$ $k$ に対して $m$ $Lk$ $+$ $i$ $= ℓ$ $i$ と定義します。 $\textstyle \ell =\sum _{i=1}^{k}l_{i}2^{i-1}$
$j = 0, 1, \dots, L$ について順に計算する。 $x_{j+1}=x_{j}^{2}\prod _{i=1}^{k}p_{i}^{m_{jk+i}}\mod n$
$x L +1$ を返します。

ステップ 5 の機能は圧縮機能と呼ばれます。

VSHの特性

メッセージの長さを事前に知る必要はありません。
VSH で衝突を見つけることは、VSSR を解くのと同じくらい困難です。したがって、VSH は (強く)衝突耐性があり、これは第 2 原像衝突耐性も意味します。VSH が原像衝突耐性であることは証明されていません。
圧縮関数は衝突耐性がありません。ただし、ハッシュ関数 VSH は VSSR 仮定に基づいて衝突耐性があります。VSH の修正バージョンである VSH* は衝突耐性のある圧縮関数を使用し、短いメッセージをハッシュするときに約 5 倍高速になります。
VSH の出力長は安全な RSA 係数の長さであるため、VSH は実際には任意の長さのメッセージに対する「ハッシュしてから署名する」RSA 署名を構築するのに非常に適していると思われます。ただし、このような署名は、セキュリティを確保するために慎重に設計する必要があります。この単純なアプローチは、選択平文攻撃によって簡単に破られる可能性があります。
各反復のコストは、3 回のモジュラー乗算のコストよりも低くなります。VSH の基本バージョンでは、合計で $Ω(log(n) / log(log(n)))$ メッセージビットごとに 1 回の乗算が必要です。

VSHの変種

VSHの改良、高速化、より効率的な変種がいくつか提案されている。^[1]いずれも関数の基本的な概念を変えるものではない。これらの改良は次のように呼ばれる。

VSH の立方体化 (平方化の代わりに)
小さな素数の数を増やしたVSH
素数の積を事前に計算したVSH
高速VSH
ブロック長を増加した高速VSH

VSDL および VSH-DL バリアント

VSH-DLは、トラップドアを持たないVSHの離散対数版であり、その安全性は素数 $p$ を法とする離散対数を見つけることの難しさに依存します。^[1]

非常に滑らかな数離散対数(VSDL) は、非常に滑らかな数が与えられたときに、ある数 $n を法とするその$ 離散対数を求める問題です。

前のセクションと同様に、 $p i は$ $i$ 番目の素数を表します。さらに、 $c は$ 固定定数、 $p 、 q は$ $p$ $= 2 q + 1$ となる素数、 $k \leq (log p) c$ とします。 VSDL は次の問題です。 $pが与えられたとき、$ $i$ $= 1,$ $\dots$ $,$ $k$ に対して $|$ $e$ $i$ $| <$ $q$ となり、 $e 1 ,\dots, e$ $k$ の少なくとも 1 つが0 以外となるような整数 $e$ $1$ $,\dots,$ $e$ $k を$ 見つけます。 $2^{e_{1}}\equiv \prod _{i=2}^{k}p_{i}^{e_{i}}{\pmod {p}}$

VSDLの仮定は、無視できない確率で VSDL を解く確率多項式( $log(p)$ 単位) 時間アルゴリズムは存在しないというものです。VSDL の難しさと $p を$ 法とする離散対数の計算の難しさの間には強い関係があり、これは VSSR と整数因数分解の関係を彷彿とさせますが、それよりもいくぶん弱いものです。

VSHのセキュリティ

強い衝突耐性は、VSH で証明された唯一の特性です。これは原像耐性やその他の重要なハッシュ関数の特性を意味するものではなく、著者は「VSH はランダムオラクルのモデル化に使用すべきではない」と述べており、それらに依存する構造 ( RSA 署名、一部のMAC ) に代用することはできません。^{[1] VSH は、}セキュリティエンジニアリングで通常理解されているような汎用ハッシュ関数とは見なされません。

乗法性

VSH は乗法的です。 $x$ 、 $y$ 、 $z を$ 同じ長さの 3 つのビット文字列とします。ここで、 $z は$ ゼロビットのみで構成され、文字列は $x AND y = z を$ 満たします。このとき、 $H (z) H (x OR y) \equiv H (x) H (y) (mod n)$ となります。その結果、VSH は乗法ハッシュと加法ハッシュに適用される古典的な時間とメモリのトレードオフ攻撃に屈します。

$この事実は、予想される2$ $ℓ$ ではなく $2$ $ℓ/2 の$ $複雑度を持つℓ$ ビットの VSH に対する原像攻撃を構築するために使用できます。

短縮版に対する攻撃

VSH は非常に長いハッシュ (通常 1024 ビット) を生成します。切り捨てられた VSH ハッシュがハッシュの長さに見合ったセキュリティを提供するという兆候はありません。

$ℓ$ 最下位ビットに切り捨てられたVSHに対する部分衝突攻撃が存在する。 ^[2]

VSH に対するこの攻撃の複雑さは次のとおりです。

オフラインでテーブルを事前計算: $2 ℓ/3 の$ 時間とスペース。
衝突の検出: $2 ℓ/3$ 反復。
総コスト:良好な疑似乱数特性を持つハッシュ関数から予想される $2$ $ℓ/2$ ではなく、およそ $2 ℓ/3$ です。

これはおそらく^{[誰によると? ]、}楕円曲線署名方式など、VSH ハッシュ結果よりも短い署名を生成するデジタル署名方式での VSH の適用を排除します。

参照

参考文献

^ abcde Contini, S.; Lenstra, A.; Steinfeld, R. (2005-06-23)、VSH、効率的で証明可能な衝突耐性ハッシュ関数。
^ Saarinen, M.-JO (2006)、「現実世界における VSH のセキュリティ」(PDF)、Progress in Cryptology - INDOCRYPT 2006、Lecture Notes in Computer Science、vol. 4329、pp. 95–103、doi :10.1007/11941378_8、ISBN 978-3-540-49767-7^{[リンク切れ‍ ]}

[main-1] Contini, S.; Lenstra, A.; Steinfeld, R. (2005-06-23)、VSH、効率的で証明可能な衝突耐性ハッシュ関数。

[attack-2] Saarinen, M.-JO (2006)、「現実世界における VSH のセキュリティ」(PDF)、Progress in Cryptology - INDOCRYPT 2006、Lecture Notes in Computer Science、vol. 4329、pp. 95–103、doi :10.1007/11941378_8、ISBN 978-3-540-49767-7^{[リンク切れ‍ ]}