この質問は言語に依存しないので、知的プログラマーの皆さんに何らかの形で助けていただきたいと思います。
|M| を持つ要素 "M" の集合が与えられます。= 2^128 要素。各要素「m」のビット長は 128 ビットです。
128 ビット長のメッセージを送信したい。このメッセージでは、M の要素の 1 つといくつかの情報 "n" を組み込みたいと考えています。つまり、「m」と「n」の長さは 128 ビット (メッセージの長さ) 未満でなければなりません。
相手はすべての要素を含む完全なセット「M」を持っていますが、どの要素を使用する必要があるかを伝える必要があります。この命令は 1 つのメッセージに収まる必要があり、複数のメッセージに分割することはできません。
したがって、アルゴリズム f() を使用して要素にインデックスを付けたいので、f(m)=index_of_m で index_of_m<128 ビットとなります。
つまり、アルゴリズムは、要素の長さ (128 ビット) よりも少ないビットで表されるインデックスに、長さ 128 ビットの 2^128 要素をマップする必要があります。
再びフォーマル：
セット:
M=(m1,m2,...mn) with n = 2^128
すべての長さm1...mn: 128 bits.
メッセージ"n" < 128 bit。メッセージの長さは可変で、1 ビットの場合もあります。
索引付け/マッピング関数: f()
f(m1)=i1 Index 1 of element m1 with the length of i1 < 128 bit., so i1+n=128bit
Wanted: Function f().
アイデア:
- 64 ビット出力のハッシュは 2^128 要素をエンコードできるため、要素をハッシュする単純な方法ではハッシュは機能しません。128 ビット出力のハッシュはメッセージ全体を使い果たし、"n" の場所はありません。
- 1 から 2^128 へのインデックス付けは機能しません。たとえば、2^128 ではメッセージ全体が使い果たされます。