(57)【要約】多入力多出力のｓボックスであって、ａ個の隣接番号の入力ビット（１０１，１０２，１０３，１０４，１０５）Ｉ１、Ｉ２乃至Ｉａを受信し、ここでａは少なくとも４であり、ｂ個の連続番号の出力ビット（１３１，１３２，１３３，１３４，１３５）Ｏ１、Ｏ２乃至Ｏｂを出力する。このｓボックスは、ｃ個の一次ｓボックス（１２１，１２２，１３）ｓｂ１、ｓｂ２乃至ｓｂｃを含む。各一次ｓボックス（１２１，１２２，１２３）は多入力単一出力のブール関数ｆ１、ｆ２乃至ｆｃを具え、これらが多入力と単一出力の関係を規定する。各一次ｓボックス（１２１，１２２，１２３）はそれぞれ入力ビットｓ１、ｓ２乃至ｓｃのセットを受信し、これらのセットがそれぞれ前記ｓボックスへのａ個の入力ビット（１０１，１０２，１０３，１０４，１０５）から選択され、それぞれｓｌ１、ｓｌ２乃至ｓｌｃビットを含む。前記ｓｌ１、ｓｌ２乃至ｓｌｃの数は３乃至（ａ−１）の範囲内にあり、前記ｓｌ１、ｓｌ２乃至ｓｌｃの数の合計がａより大きい。前記ｓボックスのｂ個の出力ビット（１３１，１３２，１３３，１３４，１３５）が、前記ｃ個のブール関数の出力を含む。【選択図】図１
2008514975.tif 000002
【特許請求の範囲】
【請求項１】
多入力多出力のｓボックスであって：
ａ個の隣接番号の（contiguously numbered）入力ビットＩ１、Ｉ２乃至Ｉａを受信し、ここでａは少なくとも４であり、
ｂ個の連続番号の出力ビットＯ１、Ｏ２乃至Ｏｂを出力するよう構成され、
このｓボックスが：
ｃ個の一次ｓボックスｓｂ１、ｓｂ２乃至ｓｂｃを含み、それぞれ：
多入力単一出力のブール関数ｆ１、ｆ２乃至ｆｃを含み、これらが多入力と単一出力の関係を規定しており、
入力ビットｓ１、ｓ２乃至ｓｃのセットをそれぞれ受信するよう構成され、これらのセットがそれぞれ前記ｓボックスへのａ個の入力ビットから選択され、それぞれｓｌ１、ｓｌ２乃至ｓｌｃビットを含み、これにより：
前記ｓｌ１、ｓｌ２乃至ｓｌｃの数が３乃至（ａ−１）の範囲内にあり；
前記ｓｌ１、ｓｌ２乃至ｓｌｃの数の合計がａより大きく、
前記ｓボックスのｂ個の出力ビットが、前記ｃ個のブール関数の出力を含むことを特徴とするｓボックス。
【請求項２】
請求項１の多入力多出力ｓボックスにおいて、前記ｓボックスのｂ個の出力ビットが前記ｃ個の一次ｓボックスの出力であることを特徴とするｓボックス。
【請求項３】
請求項１または２の多入力多出力ｓボックスにおいて、ａが１６以上であることを特徴とするｓボックス。
【請求項４】
請求項１乃至３のいずれか１項の多入力多出力ｓボックスにおいて、ｂが１６以上であることを特徴とするｓボックス。
【請求項５】
請求項１乃至４のいずれか１項の多入力多出力ｓボックスにおいて、ｃが１２以上ｂ以下であることを特徴とするｓボックス。
【請求項６】
請求項１乃至５のいずれか１項の多入力多出力ｓボックスにおいて、それぞれ１からａのｉとｊについて、ｓｉとｓｊの各セットがｍｉｎ（ｓｌｉ，ｓｌｊ）−１ビット以下を共有することを特徴とするｓボックス。
【請求項７】
請求項１乃至６のいずれか１項の多入力多出力ｓボックスにおいて、前記数ｓｌ１、ｓｌ２乃至ｓｌｃの合計がａの１．５倍より大または等しいことを特徴とするｓボックス。
【請求項８】
請求項１乃至７のいずれか１項の多入力多出力ｓボックスにおいて、ａ、ｂ、ｃの少なくとも１つが素数であることを特徴とするｓボックス。
【請求項９】
請求項１乃至８のいずれか１項の多入力多出力ｓボックスにおいて、前記数ａとｂが１より大きな公約数を持たないことを特徴とするｓボックス。
【請求項１０】
請求項１乃至９のいずれか１項の多入力多出力ｓボックスにおいて、前記数ｓｌ１、ｓｌ２乃至ｓｌｃの少なくとも２つが同じであることを特徴とするｓボックス。
【請求項１１】
請求項１０の多入力多出力ｓボックスにおいて、前記数ｓｌ１、ｓｌ２乃至ｓｌｃの全部が同じであることを特徴とするｓボックス。
【請求項１２】
請求項１乃至１１のいずれか１項の多入力多出力ｓボックスにおいて、入力ビットセットｓ１、ｓ２乃至ｓｃがそれぞれ、確率的プロセス（provabilistic）を用いて選択されることを特徴とするｓボックス。
【請求項１３】
請求項１乃至１２のいずれか１項の多入力多出力ｓボックスにおいて、前記入力ビットセットｓ１、ｓ２乃至ｓｃの少なくとも１つを選択するのに用いられるプロセスがキード（keyed）されていることを特徴とするｓボックス。
【請求項１４】
請求項１２または１３の多入力多出力ｓボックスにおいて、前記入力ビットセットｓ１、ｓ２乃至ｓｃの選択は、少なくとも１の基準（criterion）を満たすよう実践的に改良（heuristically refined）されていることを特徴とするｓボックス。
【請求項１５】
請求項１乃至１４のいずれか１項の多入力多出力ｓボックスにおいて、前記ブール関数ｆ１、ｆ２乃至ｆｃは確率的プロセス（provabilistic）を用いて生成されることを特徴とするｓボックス。
【請求項１６】
請求項１乃至１５のいずれか１項の多入力多出力ｓボックスにおいて、前記ブール関数ｆ１、ｆ２乃至ｆｃの少なくとも１つを生成するのに用いられるプロセスがキード（keyed）されていることを特徴とするｓボックス。
【請求項１７】
請求項１５または１６の多入力多出力ｓボックスにおいて、前記少なくとも１のブール関数ｆ１、ｆ２乃至ｆｃの選択は、少なくとも１の基準（criterion）を満たすよう実践的に改良（heuristically refined）されていることを特徴とするｓボックス。
【請求項１８】
請求項１乃至１７のいずれか１項の多入力多出力ｓボックスにおいて、前記ブール関数ｆ１、ｆ２乃至ｆｃの少なくとも１つは平衡したブール関数（ballanced Boolean function）であることを特徴とするｓボックス。
【請求項１９】
請求項１８の多入力多出力ｓボックスにおいて、前記ブール関数ｆ１、ｆ２乃至ｆｃがそれぞれ平衡したブール関数（ballanced Boolean function）であることを特徴とするｓボックス。
【請求項２０】
請求項１乃至１９のいずれか１項の多入力多出力ｓボックスにおいて、前記ブール関数ｆ１、ｆ２乃至ｆｃの少なくとも１つが、２対１マルチプレクサ関数（two-to-one multiplexer function）を具えることを特徴とするｓボックス。
【請求項２１】
請求項２０の多入力多出力ｓボックスにおいて、前記ブール関数ｆ１、ｆ２乃至ｆｃがそれぞれ２対１マルチプレクサ関数（two-to-one multiplexer function）を具えることを特徴とするｓボックス。
【請求項２２】
請求項１乃至２１のいずれか１項の多入力多出力ｓボックスにおいて、前記ブール関数ｆ１、ｆ２乃至ｆｃの少なくとも１つがユニークなブール関数であることを特徴とするｓボックス。
【請求項２３】
請求項２２の多入力多出力ｓボックスにおいて、前記ブール関数ｆ１、ｆ２乃至ｆｃがそれぞれユニークなブール関数であることを特徴とするｓボックス。
【請求項２４】
請求項２２または２３の多入力多出力ｓボックスにおいて、前記関数ｆ１、ｆ２乃至ｆｃ間の差（difference）がアフィン（affine）であることを特徴とするｓボックス。
【請求項２５】
請求項１乃至２４のいずれか１項の多入力多出力ｓボックスにおいて、実行時に再構成される（reconfigured）ことを特徴とするｓボックス。
【請求項２６】
請求項１乃至２５のいずれか１項の多入力多出力ｓボックスにおいて、前記入力ビットセットｓ１乃至ｓｃの少なくとも１つが実行時に変更されることを特徴とするｓボックス。
【請求項２７】
請求項１乃至２６のいずれか１項の多入力多出力ｓボックスにおいて、前記関数ｆ１、ｆ２乃至ｆｃの少なくとも１つが実行時に再構成されることを特徴とするｓボックス。
【請求項２８】
請求項１乃至２７のいずれか１項の多入力多出力ｓボックスにおいて、（ｃ−ａ）乃至ａのすべてのｉについて：
各一次ｓボックスｓｂｉへのｓｌｉの入力ビットのセットが、入力ビットＩ１乃至Ｉｉから選択され；
入力ビットＩｉと出力ビットの関係が線形であることを特徴とするｓボックス。
【請求項２９】
請求項２８の多入力多出力ｓボックスにおいて、Ｉ１乃至Ｉａのａ個のビットセットのＴ＝（ａ−ｃ）ビットのサブセットが、ビットＩ１乃至ＩＴのＴ×Ｔの全単射（bijective mapping）の入力であることを特徴とするｓボックス。
【請求項３０】
請求項１乃至２９のいずれか１項の多入力多出力ｓボックスにおいて、Ｗが一定である（Ｗ＋１）乃至ａのずべてのｉについて：
前記一次ｓボックスｓｂｉへのｓｌｉの入力ビットのセットが、入力ビットＩ（ｉ−Ｗ）乃至Ｉｉから選択され；
入力ビットＩｉと前記ｓボックスｓｂｉの出力ビットの関係が線形であることを特徴とするｓボックス。
【請求項３１】
請求項３０の多入力多出力ｓボックスにおいて、Ｗが２乃至（ａ−１）の範囲にあることを特徴とするｓボックス。
【請求項３２】
請求項３０または３１の多入力多出力ｓボックスにおいて、Ｉ１乃至ＩＷのＷビットが、Ｗ×Ｗの全単射の入力であることを特徴とするｓボックス。
【請求項３３】
請求項１乃至２７のいずれか１項の多入力多出力ｓボックスにおいて、入力ビットｓ１、ｓ２乃至ｓｃのセットの入力ビットのｓｌ１、ｓｌ２乃至ｓｌｃの選択は：
隣接番号の（contiguously numbered）入力ビットＩ１、Ｉ２乃至Ｉａでは、ビットＩａがビットＩ（ａ−１）と同様にビットＩ１と隣接（contiguous）するよう扱われ、これにより入力ビットＩ１、Ｉ２乃至Ｉａがビットの巡回収集（circular collection）とみなされ；
前記隣接番号の入力ビットＩ１、Ｉ２乃至Ｉａのセットは、ビットｗ１乃至ｗｄの領域（windows）のセットを含むとみなされ、ここでｄは３乃至（ｃ／３）の範囲にあり：
各領域（window）が最初と最後の領域境界を有し、各領域境界が、一次ｓボックスｓｂｉとｓｂｉ＋１間の同じ方向に１ビット位置ずつ増大し；
隣接番号の（contiguously numbered）出力ビットＯ１、Ｏ２乃至Ｏｂのセットでは、前記ビットＯｂがビットＯｂ−１と同様にビットＯ１と隣接するよう扱われ、これにより出力ビットＯ１、Ｏ２乃至Ｏｂがビットの巡回収集とみなされ；
セットｓｂ１乃至ｓｂｃ内の各一次ｓボックスｓｂｋについて：
一次ｓボックスｓｂｋへの入力ビットが、領域ｗｋ以外の入力ビットの少なくとも２つの領域からの少なくとも１のビットを含むことを特徴とするｓボックス。
【請求項３４】
請求項３３の多入力多出力ｓボックスにおいて、各一次ボックスｓｂｉについて、領域ｗ１乃至ｗｄの少なくとも２つのサイズが異なることを特徴とするｓボックス。
【請求項３５】
請求項１乃至２７のいずれか１項の多入力多出力ｓボックスにおいて、入力ビットｓ１、ｓ２乃至ｓｃのセットの入力ビットのｓｌ１、ｓｌ２乃至ｓｌｃの選択はそれぞれ：
隣接番号の（contiguously numbered）入力ビットＩ１、Ｉ２乃至Ｉａでは、ビットＩａがビットＩａ−１と同様にビットＩ１と隣接（contiguous）するよう扱われ、これにより入力ビットＩ１、Ｉ２乃至Ｉａがビットの巡回収集（circular collection）とみなされ；
前記隣接番号の入力ビットＩ１、Ｉ２乃至Ｉａのセットは、入力ビットｗ１乃至ｗｄの隣接領域（windows）のセットを含むとみなされ、ここでｄは２乃至（ａ／３）の範囲にあり：
隣接番号の（contiguously numbered）出力ビットＯ１、Ｏ２乃至Ｏｂのセットでは、前記ビットＯｂがビットＯ（ｂ−１）と同様にビットＯ１と隣接するよう扱われ、これにより出力ビットＯ１、Ｏ２乃至Ｏｂがビットの巡回収集とみなされ；
セットｓｂ１乃至ｓｂｃ内の各一次ｓボックスｓｂｋについて：
一次ｓボックスｓｂｋへの入力ビットが、領域ｗｋ以外の入力ビットの少なくとも２つの領域からの少なくとも１のビットを含むことを特徴とするｓボックス。
隣接番号の（contiguously numbered）出力ビットＯ１、Ｏ２乃至Ｏｂのセットが、出力ビットｗ１乃至ｗｄの隣接領域のセットを含むとみなされ；セットｓｂ１乃至ｓｂｃ内の各一次ｓボックスｓｂｋについて：
出力ビットｗｋの領域が、前記一次ｓボックスｓｂｋの出力ビットを含み、前記一次ｓボックスｓｂｋへの入力ビットが、領域ｗｋ以外の入力ビットの少なくとも２つの領域からの少なくとも１のビットを含むことを特徴とするｓボックス。
【請求項３６】
請求項１乃至３５の多入力多出力ｓボックスを少なくとも２つ含む構造であって、前記多入力多出力ｓボックスのいずれの対もその入力を共有しないことを特徴とする構造。
【請求項３７】
請求項１乃至４１の多入力多出力ｓボックスを少なくとも２つ含む構造であって、少なくとも１対の前記多入力多出力ｓボックスが少なくとも１の入力を共有することを特徴とする構造。
【請求項３８】
請求項３６または３７の構造において、前記多入力多出力ｓボックスの少なくとも２つが接続（pipelined）されていることを特徴とする構造。
【請求項３９】
請求項３６乃至３８のいずれか１項の構造において、少なくとも１の前記多入力多出力ｓボックスへの入力が、別の前記多入力多出力ｓボックスのｂ個の出力より少ないか等しいサブセットを含むことを特徴とする構造。
【請求項４０】
請求項３６乃至３９のいずれか１項の構造において、前記多入力多出力ｓボックスのｂ個の出力より少ないか等しいサブセットが、さらに別の前記多入力多出力ｓボックスの入力に用いられる前に処理（manipulated）されていることを特徴とする構造。
【請求項４１】
請求項３６乃至４０のいずれか１項の構造において、少なくとも２つの前記多入力多出力ｓボックスについて：
一方のｓボックスの入力ビット数が他方のｓボックスの入力ビット数と異なるか；
一方のｓボックスの出力ビット数が他方のｓボックスの出力ビット数と異なるか、のいずれか１以上であることを特徴とする構造。
【請求項４２】
請求項４１の構造において、前記少なくとも２つの多入力多出力ｓボックスの各々の入力ビット数が、１以外の公約数を持たないことを特徴とする構造。
【請求項４３】
請求項４１または４２の構造において、前記少なくとも２つの多入力多出力ｓボックスの各々の出力ビット数が、１以外の公約数を持たないことを特徴とする構造。
【請求項４４】
請求項４１乃至４３のいずれか１項の構造において、前記少なくとも２つの多入力多出力ｓボックスのうちの１つの入力ビット数が、前記少なくとも２つの多入力多出力ｓボックスのうちの別の入力ビット数より少なくとも５０％多いことを特徴とする構造。
【請求項４５】
請求項４１乃至４３のいずれか１項の構造において、前記少なくとも２つの多入力多出力ｓボックスのうちの１つからの出力ビット数が、前記少なくとも２つの多入力多出力ｓボックスのうちの別の出力ビット数より少なくとも５０％多いことを特徴とする構造。
【請求項４６】
請求項３６乃至４５のいずれか１項の構造において、前記少なくとも２つの多入力多出力ｓボックスのうちの１つの前記一次ｓボックスｓｂ１、ｓｂ２乃至ｓｂｃの少なくとも１つが、前記少なくとも２つの多入力多出力ｓボックスのうちの別の一次ｓボックスｓｂ１、ｓｂ２乃至ｓｂｃと異なることを特徴とする構造。
【請求項４７】
請求項１乃至４６のいずれか１項の発明において、少なくとも１つの多入力多出力ｓボックスのｂ個の出力と同じかこれより少ないサブセットが、別のプロセスへの入力に用いられることを特徴とする発明。
【請求項４８】
請求項４７の多入力多出力ｓボックスにおいて、少なくとも１つの多入力多出力ｓボックスのｂ個の出力より少ないか等しいサブセットががさらに、別のプロセスへの入力に用いられる前に処理（manipulated）されることを特徴とするｓボックス。
【請求項４９】
請求項１乃至４０のいずれか１項の多入力多出力ｓボックスにおいて、前記ｃ個の一次ｓボックスｓｂ１、ｓｂ２乃至ｓｂｃへの入力ビットｓ１、ｓ２乃至ｓｃのセットが：
ａ個のビットから導出（drawn）されるｃ個の添字位置（index positions）の順序セット（ordered sets）Ｐ１乃至Ｐｃを確率的（probabilistically）に選択するステップであって、各セットＰ１乃至Ｐｃはそれぞれ要素ｓｌ１、ｓｌ２乃至ｓｌｃを有するステップと；
各添字位置の順序セットＰ１乃至Ｐｃについて、これらのセットのいずれか２つが同じ位置に同じ要素を含む場合に、これら要素の１つをセットＰ１乃至Ｐｃの別のものから確率的に選択された添字位置に交換（swapping）するステップと；
添字位置のｃ個のセットＰ１乃至Ｐｃのそれぞれについて反復的に：
前記セットが添字位置の別のＰ１乃至Ｐｃの各セットと共有する要素の数を決定するステップと；
共通の数の任意数ｔを持つ添字位置のｃ個のセットＰ１乃至Ｐｃのうちの２つの要素ＰｉとＰｋの各々について、Ｐｉの（ｔ＋１）／２の数を：
ｃ個のセットＰ１乃至Ｐｃの残りの（ｃ−２）のセットを、Ｐｉと共有する要素の数の順番で分類（sorting）し；
前記（ｃ−２）のセットから、Ｐｉと共有する要素の数が最も少ない１のセットＰｍを選択し；
前記セットＰｉとＰｋに共通の１の要素を選択し；
前記選択した要素を前記セットＰｍのうちの１つと交換（swapping）することにより、
配置転換するステップと；
を具える実践的プロセス（heuristic process）により選択されることを特徴とするｓボックス。
【請求項５０】
請求項１乃至４９のいずれか１項の発明をシミュレートすることを特徴とするプロセス。
【請求項５１】
請求項５１のプロセスにおいて、ワードベースの一般目的のプロセッサに実装されることを特徴とするプロセス。
【請求項５２】
請求項４９乃至５１のいずれか１項のプロセスにおいて、静的ビット置換処理、キー従属ビット置換処理、データ従属ビット置換処理のいずれか１以上を含むビット置換処理を実行するバイナリマスキング（binary masking）を用いることを特徴とするプロセス。
【請求項５３】
請求項５２のプロセスにおいて、ビット置換処理を実行するバイナリマスキングを用い、これらのビット置換処理が：
前記セットｓ１、ｓ２乃至ｓｃの要素を選択するステップと；
前記ｃ個のブール関数の出力を置換するステップとのいずれか１以上を実現し；
前記バイナリマスキングが；
静的ビット置換処理と；キー従属置換処理と；データ従属置換処理とのいずれか１以上を実行すべく用いられることを特徴とするプロセス。
【請求項５４】
請求項５３のプロセスにおいて、前記ビット置換処理がハードウェアに補助されることを特徴とするプロセス。
【請求項５５】
請求項５４のプロセスにおいて、前記ハードウェアに補助されたビット置換処理が、グループオペレーション（ＧＲＰ）、その逆、オメガフリップネットワーク（ＯＭＦＬＩＰ）、ＰＰＥＲＭ、ＣＲＯＳＳ、ＢＦＬＹ処理からなる群から選択されることを特徴とするプロセス。
【請求項５６】
請求項５０乃至５３のいずれか１項のプロセスにおいて、ハードウェア補助ビットローテーション処理（hardware-assisted bitwise rotation operations）を用いて、前記ビット置換処理を実行することを特徴とするプロセス。
【請求項５７】
請求項５０乃至５３のいずれか１項のプロセスにおいて、ハードウェア補助ビットシフティング処理（hardware-assisted bitwise shifting operations）を用いて、前記ビット置換処理を実行することを特徴とするプロセス。
【請求項５８】
請求項５０乃至５３のいずれか１項のプロセスにおいて、ハードウェア補助バイトスワッピング処理（hardware-assisted byte swapping operations）を用いて、前記ビット置換処理を実行することを特徴とするプロセス。
【請求項５９】
請求項５０乃至５８のいずれか１項のプロセスにおいて、ルックアップテーブルを用いて換字（substitution）およびビット置換処理の少なくとも１を実行することを特徴とするプロセス。
【請求項６０】
請求項５０乃至５９のいずれか１項のプロセスにおいて、少なくとも１のワードベースの基本ブール関数（waord-based primitive Boolean function）を用いて換字処理（substitution operation）を実行することを特徴とするプロセス。
【請求項６１】
ブロック暗号、ストリーム暗号、疑似乱数生成器、またはハッシュ関数のラウンド関数を具える回路であって、この暗号回路が、請求項１乃至４９のいずれか１項の多入力多出力ｓボックスのうちの少なくとも１つを具え、前記回路には、前記１以上の他入力多出力ｓボックスの入出力間でゼロ乃至６以下の範囲の繰り越し操作の破られていない演算繰り越し理論チェーン（unbroken arithmetic carry-logic chain）があることを特徴とする回路。
【請求項６２】
暗号プロセスであって、
ａ個の隣接番号の（contiguously numbered）入力ビットＩ１、Ｉ２乃至Ｉａを受信し、ここでａは少なくとも４であり、
ｂ個の連続番号の出力ビットＯ１、Ｏ２乃至Ｏｂを出力し、
前記方法が：
ｃ個の一次ｓボックス操作（primitive s-box operations）ｓｂ１、ｓｂ２乃至ｓｂｃを含み、その各々が：
多入力単一出力のブール関数ｆ１、ｆ２乃至ｆｃを含み、これらが多入力と単一出力の関係を規定しており、
入力ビットｓ１、ｓ２乃至ｓｃのセットをそれぞれ受信し、これらのセットがそれぞれ暗号化関数（the cryptographic function）へのａ個の入力ビットから選択され、それぞれｓｌ１、ｓｌ２乃至ｓｌｃビットを含み、これにより：
前記ｓｌ１、ｓｌ２乃至ｓｌｃの数が３乃至（ａ−１）の範囲内にあり；
前記ｓｌ１、ｓｌ２乃至ｓｌｃの数の合計がａより大きく、
前記暗号化関数のｂ個の出力ビットが、前記ｃ個のブール関数の出力を含むことを特徴とするプロセス。
【請求項６３】
請求項６２の暗号プロセスにおいて、前記ｓボックスのｂ個の出力ビットが前記ｃ個の一次ｓボックス処理の出力であることを特徴とするプロセス。
【請求項６４】
請求項６２または６３の暗号プロセスにおいて、ａが１６以上であることを特徴とするプロセス。
【請求項６５】
請求項６２乃至６４のいずれか１項の暗号プロセスにおいて、ｂが１６以上であることを特徴とするプロセス。
【請求項６６】
請求項６２乃至６５のいずれか１項の暗号プロセスにおいて、ｃが１２以上ｂ以下であることを特徴とするプロセス。
【請求項６７】
請求項６２乃至６６のいずれか１項の暗号プロセスにおいて、それぞれ１からａのｉとｊについて、ｓｉとｓｊの各セットがｍｉｎ（ｓｌｉ，ｓｌｊ）−１ビット以下を共有することを特徴とするプロセス。
【請求項６８】
請求項６２乃至６７のいずれか１項の暗号プロセスにおいて、前記数ｓｌ１、ｓｌ２乃至ｓｌｃの合計がａの１．５倍より大きいあるいは等しいことを特徴とするプロセス。
【請求項６９】
請求項６２乃至６８のいずれか１項の暗号プロセスにおいて、ａ、ｂ、ｃの少なくとも１つが素数であることを特徴とするプロセス。
【請求項７０】
請求項６２乃至６９のいずれか１項の暗号プロセスにおいて、前記数ａとｂが１より大きな公約数を持たないことを特徴とするプロセス。
【請求項７１】
請求項６２乃至７０のいずれか１項の暗号プロセスにおいて、前記数ｓｌ１、ｓｌ２乃至ｓｌｃの少なくとも２つが同じであることを特徴とするプロセス。
【請求項７２】
請求項７１の暗号プロセスにおいて、前記数ｓｌ１、ｓｌ２乃至ｓｌｃの全部が同じであることを特徴とするプロセス。
【請求項７３】
請求項６２乃至７２のいずれか１項の暗号プロセスにおいて、入力ビットセットｓ１、ｓ２乃至ｓｃがそれぞれ、確率的プロセス（provabilistic）を用いて選択されることを特徴とするプロセス。
【請求項７４】
請求項６２乃至７３のいずれか１項の暗号プロセスにおいて、前記入力ビットセットｓ１、ｓ２乃至ｓｃの少なくとも１つを選択するのに用いられるプロセスがキード（keyed）されていることを特徴とするプロセス。
【請求項７５】
請求項７３または７４の暗号プロセスにおいて、前記入力ビットセットｓ１、ｓ２乃至ｓｃの選択は、少なくとも１の基準（criterion）を満たすよう実践的に改良（heuristically refined）されていることを特徴とするプロセス。
【請求項７６】
請求項６２乃至７５のいずれか１項の暗号プロセスにおいて、前記ブール関数ｆ１、ｆ２乃至ｆｃは確率的プロセス（provabilistic）を用いて生成されることを特徴とするプロセス。
【請求項７７】
請求項６２乃至７６のいずれか１項の暗号プロセスにおいて、前記ブール関数ｆ１、ｆ２乃至ｆｃの少なくとも１つを生成するのに用いられるプロセスがキード（keyed）されていることを特徴とするプロセス。
【請求項７８】
請求項７６または７７の暗号プロセスにおいて、前記少なくとも１のブール関数ｆ１、ｆ２乃至ｆｃの選択は、少なくとも１の基準（criterion）を満たすよう実践的に改良（heuristically refined）されていることを特徴とするプロセス。
【請求項７９】
請求項６２乃至７８のいずれか１項の暗号プロセスにおいて、前記ブール関数ｆ１、ｆ２乃至ｆｃの少なくとも１つは平衡したブール関数（ballanced Boolean function）であることを特徴とするプロセス。
【請求項８０】
請求項７９の暗号プロセスにおいて、前記ブール関数ｆ１、ｆ２乃至ｆｃがそれぞれ平衡したブール関数（ballanced Boolean function）であることを特徴とするプロセス。
【請求項８１】
請求項６２乃至８０のいずれか１項の暗号プロセスにおいて、前記関数ｆ１、ｆ２乃至ｆｃの少なくとも１つが、２対１マルチプレクサ関数（two-to-one multiplexer function）を具えることを特徴とするプロセス。
【請求項８２】
請求項８１の暗号プロセスにおいて、前記関数ｆ１、ｆ２乃至ｆｃがそれぞれ２対１マルチプレクサ関数（two-to-one multiplexer function）を具えることを特徴とするプロセス。
【請求項８３】
請求項６２乃至８２のいずれか１項の暗号プロセスにおいて、前記関数ｆ１、ｆ２乃至ｆｃの少なくとも１つがユニークなブール関数であることを特徴とするプロセス。
【請求項８４】
請求項８３の暗号プロセスにおいて、前記関数ｆ１、ｆ２乃至ｆｃがそれぞれユニークなブール関数であることを特徴とするプロセス。
【請求項８５】
請求項８３または８４の暗号プロセスにおいて、前記関数ｆ１、ｆ２乃至ｆｃ間の差（difference）がアフィン（affine）であることを特徴とするプロセス。
【請求項８６】
請求項６２乃至８５のいずれか１項の暗号プロセスにおいて、実行時に再構成される（reconfigured）ことを特徴とするプロセス。
【請求項８７】
請求項６２乃至８６のいずれか１項の暗号プロセスにおいて、前記入力ビットセットｓ１乃至ｓｃの少なくとも１つが実行時に変更されることを特徴とするプロセス。
【請求項８８】
請求項６２乃至８７のいずれか１項の暗号プロセスにおいて、前記関数ｆ１、ｆ２乃至ｆｃの少なくとも１つが実行時に再構成されることを特徴とするプロセス。
【請求項８９】
請求項６２乃至８８のいずれか１項の暗号プロセスにおいて、（ｃ−ａ）乃至ａのすべてのｉについて：
各一次ｓボックス処理ｓｂｉへのｓｌｉの入力ビットのセットが、入力ビットＩ１乃至Ｉｉから選択され；
入力ビットＩｉと出力ビットの関係が線形であることを特徴とするプロセス。
【請求項９０】
請求項８９の暗号プロセスにおいて、Ｉ１乃至Ｉａのａ個のビットセットのＴ＝（ａ−ｃ）ビットのサブセットが、ビットＩ１乃至ＩＴのＴ×Ｔの全単射（bijective mapping）の入力であることを特徴とするプロセス。
【請求項９１】
請求項６２乃至９０のいずれか１項の暗号プロセスにおいて、Ｗが一定である場合の（Ｗ＋１）乃至ａのずべてのｉについて：
前記一次ｓボックス処理ｓｂｉへのｓｌｉの入力ビットのセットが、入力ビットＩ（ｉ−Ｗ）乃至Ｉｉから選択され；
入力ビットＩｉと前記ｓボックスｓｂｉの出力ビットの関係が線形であることを特徴とするプロセス。
【請求項９２】
請求項９１のいずれか１項の暗号プロセスにおいて、Ｗが２乃至（ａ−１）の範囲にあることを特徴とするプロセス。
【請求項９３】
請求項９１または９２の暗号プロセスにおいて、Ｉ１乃至ＩＷのＷビットが、Ｗ×Ｗの全単射の入力であることを特徴とするプロセス。
【請求項９４】
請求項６２乃至８８のいずれか１項の暗号プロセスにおいて、入力ビットｓ１、ｓ２乃至ｓｃのセットの入力ビットのｓｌ１、ｓｌ２乃至ｓｌｃの選択はそれぞれ：
隣接番号の（contiguously numbered）入力ビットＩ１、Ｉ２乃至Ｉａでは、ビットＩａがビットＩ（ａ−１）と同様にビットＩ１と隣接（contiguous）するよう扱われ、これにより入力ビットＩ１、Ｉ２乃至Ｉａがビットの巡回収集（circular collection）とみなされ；
前記隣接番号の入力ビットＩ１、Ｉ２乃至Ｉａのセットは、ビットｗ１乃至ｗｄの領域（windows）のセットを含むとみなされ、ここでｄは３乃至（ｃ／３）の範囲にあり：
各領域（window）が最初と最後の領域境界を有し、各領域境界が、一次ｓボックスｓｂｉとｓｂｉ＋１間の同じ方向に１ビット位置ずつ増大し；
隣接番号の（contiguously numbered）出力ビットＯ１、Ｏ２乃至Ｏｂのセットでは、前記ビットＯｂがビットＯｂ−１と同様にビットＯ１と隣接するよう扱われ、これにより出力ビットＯ１、Ｏ２乃至Ｏｂがビットの巡回収集とみなされ；
セットｓｂ１乃至ｓｂｃ内の各一次ｓボックスｓｂｋについて：
一次ｓボックスｓｂｋへの入力ビットが、領域ｗｋ以外の入力ビットの少なくとも２つの領域からの少なくとも１のビットを含むことを特徴とするプロセス。
【請求項９５】
請求項９４の暗号プロセスにおいて、各一次ボックスｓｂｉについて、領域ｗ１乃至ｗｄの少なくとも２つのサイズが異なることを特徴とするプロセス。
【請求項９６】
請求項６２乃至８８のいずれか１項の暗号プロセスにおいて、入力ビットｓ１、ｓ２乃至ｓｃのセットの入力ビットのｓｌ１、ｓｌ２乃至ｓｌｃの選択はそれぞれ：
隣接番号の（contiguously numbered）入力ビットＩ１、Ｉ２乃至Ｉａでは、ビットＩａがビットＩａ−１と同様にビットＩ１と隣接（contiguous）するよう扱われ、これにより入力ビットＩ１、Ｉ２乃至Ｉａがビットの巡回収集（circular collection）とみなされ；
前記隣接番号の入力ビットＩ１、Ｉ２乃至Ｉａのセットは、入力ビットｗ１乃至ｗｄの隣接領域（windows）のセットを含むとみなされ、ここでｄは２乃至（ａ／３）の範囲にあり：
隣接番号の（contiguously numbered）出力ビットＯ１、Ｏ２乃至Ｏｂのセットでは、前記ビットＯｂがビットＯ（ｂ−１）と同様にビットＯ１と隣接するよう扱われ、これにより出力ビットＯ１、Ｏ２乃至Ｏｂがビットの巡回収集とみなされ；
セットｓｂ１乃至ｓｂｃ内の各一次ｓボックスｓｂｋについて：
一次ｓボックスｓｂｋへの入力ビットが、領域ｗｋ以外の入力ビットの少なくとも２つの領域からの少なくとも１のビットを含むことを特徴とするｓボックス。
隣接番号の（contiguously numbered）出力ビットＯ１、Ｏ２乃至Ｏｂのセットが、出力ビットｗ１乃至ｗｄの隣接領域のセットを含むとみなされ；セットｓｂ１乃至ｓｂｃ内の各一次ｓボックスｓｂｋについて：
出力ビットｗｋの領域が、前記一次ｓボックスｓｂｋの出力ビットを含み、前記一次ｓボックスｓｂｋへの入力ビットが、領域ｗｋ以外の入力ビットの少なくとも２つの領域からの少なくとも１のビットを含むことを特徴とするプロセス。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、換字ボックス（substitution box）の構成に関し、ある実施例はハードウェアとして有効であり、ある実施例はソフトウェアとして有効である。
【背景技術】
【０００２】
本出願は、２００４年９月２４日出願のオーストラリア暫定特許出願２００４９０５５０７、２００４年１１月１６日出願の２００４９０６５４３、２００４年１２月３０日出願の２００４９０７３６１、２００４年１２月３１日出願の２００４９０７３７４、２００５年４月２９日出願の２００５９０２１３６の優先権を主張するものであり、これらの内容は参照としてここに組み込まれている。
【０００３】
本明細書において、クレームも含み、「具える」または「具えている」の語は明確に規定された特徴、整数、ステップ、構成要素の存在を特定するのに用いるものであり、他の１以上の特徴、整数、ステップ、構成要素の存在または追加を排除するものではなく；またビットｉの「添字位置（index position）」Ｐｉは、隣接入力ビットセットａ内のビットｉの位置を示すのに用いる。
【０００４】
本明細書において、「確率的プロセス」の語は、「乱数」および「疑似乱数」プロセスの双方に用い、これには疑似乱数プロセスが定数またはキー要素で「キード（kyed）」または「シード（seeded）」されている場合や、ランダム性のソースや疑似乱数アルゴリズムが取得可能（available）な場合を含む。様々な公知の疑似乱数生成器やストリーム暗号をこの目的に利用することができる。
【０００５】
本明細書において、公開された文献への参照は、その文献の内容が本明細書の熟練した読者に共有の一般知識の部分をなすと容認するものではない。
【０００６】
我々の創作的な特徴をより容易に認識可能とすべく、我々はこの技術に関連するこれまでに公開されたいくつかの文献の概要を以下に明らかにする。
【０００７】
錯乱（confusion）と拡散（diffusion）の定義は、１９４９年にC. E. Shannonにより彼の文献「Communication THeory of Secrecy Systems」で初めて公に紹介された。
【０００８】
ｓボックス（substitution box：換字ボックス）はデジタル符号化された入力を受け、この入力を異なるデジタル符号化された出力に変換し、すなわち錯乱を生じさせる。ｐボックス（permutation box：置換ボックス）はデジタル符号化された入力を受け、同じビットを出力として返し、これらの値を変更しないがその順番を変え、すなわち拡散を生じさせる。
【０００９】
「雪崩効果」は、最も単純な形では、入力の単一ビット順列（single bit change）にラウンド関数（round function）で少なくとも２ビット順列の出力とする暗号特性である。これはｓボックスに必要な特性として、Horst Feistel により、１９７３年５月のScientific American , Vol. 228, Number 5において公開された彼の暗号特性を記載した「Cryptography and Computer Privacy」にて紹介された。この刊行物は、完全な任意対任意の換字(any-to-any substitution）は１２８×１２８といった大きなｓボックスでは技術の限界により達成できないことを記している。結果として、非常に小さく実用的なサイズ（４×４）の非線形ｓボックスが部分的な錯乱と部分的な拡散を実行すべく選択され、大きなｐボックスがｓボックスの出力に接続されShannonが規定するようにさらなる拡散を実行すべく選択される。
【００１０】
最初のデジタルブロック暗号は広くHorst Feistel により達成された。このブロック暗号は、１９７４年３月１９日に発行された米国特許３，７９８，３５９（Feistel）にあるように、小さな４×４のｓボックスと、６４または１２８ビットに行われる置換処理を組み合わせている。この４×４のｓボックスは、組み合わせ理論（combinatorial logic）を用いるよう設計されている。
【００１１】
ｓボックスとｐボックスは、殆どのフェイステル型またはフェイステルネットワーク暗号および他の暗号原理（cryptographic primitive）の要素として利用されている。これらは１９７６年５月１８日に公開された米国特許３，９５８，０８１（Ehrsam, et al.）に開示された公開データ暗号化標準（ＤＥＳ）にも利用されている。このＤＥＳ暗号は、１９７７年に米国連邦規格となった。ここで注目すべきは、その時点で公に知られていない重要な暗号基準を保護しつつ、組み合わせ理論を用いたハードウェア実装を確たる有効なものにすべく、６×４のｓボックスが慎重に選択されていることである。
【００１２】
ｓボックスの換字処理は、概して演算的ではない。例えば、限定しないが加算、乗算、累乗といった演算処理は、しばしば非演算的ｓボックス（non-arithmetic s-box）の代わりに、またはこれとともに利用される。このような演算処理と非演算的ｓボックスの組合せに基づく換字−置換ネットワーク（substitution-permutation networks）は、ワードベースの処理構造に有効である。この種の構造の一例が、１９８１年３月１０日に公開された米国特許４，２５５，８１１（Adler）に記載されており、２ｎを法とする加算または減算、ｎビット幅ＸＯＲ、静的ｎビット置換（static n-bit permutations）、ｎビットキー従属ローテーション操作（n-bit key-dependent rotation operations）を用いる暗号が開示されている。同種のさらなる構成が、１９９１年１月１日に公開された米国特許４，９８２，４２９（Takaragi, et al.）、１９９２年４月７日に公開された５，１０３，４７９（Takaragi, et al.）に開示されている。ワードベースの非線形演算処理が、例えばRon Rivest による１９９２年４月のRecommendation for Comment 1321に記載されたＭＤ５暗号ハッシュ関数といった暗号ハッシュ関数に用いられている。
【００１３】
ｐボックス（置換ボックス）についての意味深い研究はなく、これは設計者の判断に委ねられ、多くの場合は完全に線形または無作為に選択される。
【００１４】
フェイステルネットワーク暗号はまた、その構造内で殆どの場合に線形で、拡散（diffusion）に寄与する関数の組合せを含む。線形コンバイナ（ＸＯＲ）を拡散率の高い非線形演算処理に置き換える一例に、ソヴィエト国家基準局；情報処理システム；暗号保護；暗号アルゴリズム推奨のＧＯＳＴと呼ばれるものがある。１９８９年ＧＯＳＴ２８１４７−８９。このＧＯＳＴ暗号は、ワードベースのローテーション操作（rotation operation）を用いてｓボックス間でビットの拡散を実現させた暗号の例でもある。
【００１５】
「完成基準」（completeness criterion）は、最初に文献「Structured Design of Substitution-Permutation Encryption Networks」、IEEE Transactions of Computers、Vol.28、No. 10, 747、１９７９年、John B. KamとGeorge I. Davida、により明確に規定された。暗号変換は、各暗号文ビットが平文ビットに従属する場合に「完成」する。この完成基準を満たす暗号が、１９８１年６月２３日公開の米国特許４，２７５，２６５（Davida, et al.）に見られる。この完成基準は、例えばＮインスタンスのＭ入力対単一出力のブール関数がそれぞれＭ入力ビットの完全なセットを入力とするＭ×Ｎのｓボックスを必要とする。
【００１６】
１９８２年の文献「Are Big S-Boxes Best」において、J. Gordon とH. Retkinは、コンテンツがすべての考え得る出力のセットの無作為の置換として選択される場合にｓボックスの暗号特性を探求している。この文献は、最初の役割が、エントリ数が十分に多い場合にはこのように無作為に選択したｓボックスで様々な望ましい暗号特性が発見されることを示すことを含んでいる。例えば、１／２６４の無作為に生成される可逆の６×６ｓボックスは、活用可能な線形性を有する。
【００１７】
１９８２年のF. Ayoubによる文献「Probabilistic completemess of substitution-permutation encryption networks」、IEEE Proceedings, 129(5):195-199には、その時点で最新の研究が、特定の状況下において、計画的なトラップドアからの開放の証明として、ランダム選択により換字関数（substitution function）を設計しうることを示している。この文献はまた、置換もまた例えばユーザキーで無作為に選択しうることを開示しており、得られるネットワークは、非常に高い確立で、完成された特性を有する。
【００１８】
我々のＭ×１のｓボックスへのブール関数のランダム選択を許可する場合に、上記２文献を参照する。
【００１９】
カナダ、オンタリオ、キングストン、クイーンズ大学電気工学部のA. F. Webster とS. E. Tavaresの修士論文「On the Design of S-Boxes」、LNCS no. 219, pp523-534 (1986)において、筆者は「厳格な雪崩基準（strict avalanche criterion：ＳＡＣ）」を明示的に規定している。このＳＡＣは、各暗号文出力ビットが、単一の入力ビットが補足された場合にも正確に１／２の確立で変換されるべきであることを述べている。
【００２０】
この論文は、この実践的なプロセスが、ＳＡＣとさらなる「雪崩変動独立（avalanche variable independence）」特性とを満足する４×４のｓボックスの選択に用いられることを記載している。このプロセスは、ＳＡＣを満たす潜在的に可逆のすべての４×１関数を選択し、一度にこれらを４つ組み合わせて４×４の換字ボックスを生成することで開始する。この論文にはさらなる実践的な技術が記載されており、前のステップで作成された「完全な」ｓボックスの有限数の集合（families）から４×１のブール関数を選択することによりサーチプロセスを最適化する。
【００２１】
この論文は、米国特許４，２７５，２６５（DAVIDA, et al.）記載の暗号がいかにＳＡＣに合致しないかを強調し、他の研究者にそれまで認識されたＤＥＳの潜在的な弱点を確認している。また、ＳＡＣを満足しない構成を、数ラウンドにわたり構築を繰り返すことにより、ＳＡＣを満足する構成に変換しうることを強調している。これは、構築が換字置換ネットワークである場合であって置換の電送（wiring）が無作為である場合に実現するようである。
【００２２】
ｓボックスの完全な非線形の基準は、１９８９年に文献「Nonlinearity Criteria for Cryptographic Functions」、Advances in Cryptology-- EUROCRYPT '89、549-562、筆者Meier とStaffelbachで初めて記載された。この筆者は、完全な非線形基準は拡散に作用し、事実上ＳＡＣの要求よりも厳しい。
【００２３】
１９９２年の文献「On immunity against Biham and Shamir's Differential Cryptanalysis」、Information Processing Letters、vol. 41、１９９２年２月１４日、pp77-80、Carlisle M. Adamsには、差分暗号解読を免除した実用的なサイズのｓボックスの作成方法が記載されている。
【００２４】
１９９８年８月１８日に公開された米国特許５，７９６，８３７（Kim, et al.）は、線形および差分暗号解読を免除した実用的なサイズのＭ×Ｎのｓボックスの作成方法を開示している。２０００年２月２９日に公開された米国特許６，０３１，９１１（Adams, et al.）は、ＳＡＣおよび他の基準を増分プロセス（incremental process）で迅速に満たすＭ×Ｎのｓボックスを生成する発見的な技術を開示している（上述したA. F. Webster とS. E. Tavaresの論文「On the Design of S-Boxes」と同様の技術である）。
【００２５】
公開された案件の前述の分析から、非演算的なｓボックスの研究および非演算的ｓボックスの作成の一般的な方向性は３つの学派に分かれており、すなわち、適度に大きなｓボックスを選択しすべての可能な出力を無作為に置換するもの、強固として知られるｓボックスからキー従属ｓボックス（key-dependent s-boxes）を作成するもの、所望の暗号特性を固定のｓボックスに保証する新規で厳格な発見的基準を見つけ出すものである。いずれの場合にも、これらの非演算的なｓボックスを作成する３つの学派は、ｓボックスが最低限完成した基準を高い確率で保証すべきことに同意している。
【００２６】
以下が非演算的なｓボックスに関する特性である：
−ｓボックス構築用の均衡のとれたブール関数を無作為に選択可能である；
−無作為に均衡のとれたブール関数からＭ×Ｎのｓボックスを構築可能であり、発見的（heuristic）で改良されておりＳＡＣを充足する；
−Ｍ×Ｎのｓボックスを、固定的な初期の置換（fixed initial permutation）により選択可能である；
−暗号換字置換（ＳＰ）ネットワークの単一ラウンドを、このＳＰネットワーク自体はＳＡＣを満足しなくても、各々独立してＳＡＣを満足する１以上のユニークなＭ×Ｎのｓボックスから構築可能である；
−上述の暗号ＳＰネットワークの単一ラウンドがＳＡＣを満たさないが、完全なＳＰネットワークが２またはそれ以上の繰り返しラウンドの後にＳＡＣを満たす；
【００２７】
いずれの場合にも、例えば得られる最高の非線形、得られる最高の代数的階級（algebraic degree）、得られる最速の雪崩といった理想の特性を有する小さく実用的なサイズのｓボックスを選択して、換字−置換ネットワークを技術的に不可能な大きく強固なｓボックスに近似させる。
【００２８】
ソフトウェアまたはワードベースのプロセッサ構造において、基本のブール理論作用（ＡＮＤ、ＭＯＶ−move/copy、ＮＡＮＤ、ＮＯＲ、ＮＯＴ、ＯＲ、ＸＮＯＲ、ＸＯＲ等）は、厳密に構成されたパラレルＮビット幅の入力に対して実行される単一命令多重データ（single-instruction-multiple-data：ＳＩＭＤ）操作の形式である。例えば、ＩＢＭのＰｏｗｅｒＰＣまたはＩｎｔｅｌ×８６構造といった通常目的の３２ビットプロセッサを考えると、ブールのＡＮＤ命令は３２の個別のビット毎にＡＮＤ操作を、３２ビット幅のレジスタブロックに供給される６４ビットの入力に対して行い、３２ビットの出力を出す。
【００２９】
Ｍ×ＮのｓボックスとＭ×１のブール関数を、ルックアップテーブルとして、または適切な基本ＳＩＭＤ操作の選択および構成を通じて、ソフトウェアに実装する。２対１マルチプレクサに有効な３２協働ソフトウェア（32 concurrent software）の暗号実装を用いるＳＩＭＤ操作の一例が、暗号ハッシュ機能ＭＤ５にみられる。
【００３０】
ＳＩＭＤ命令の最も明瞭な特徴は、その完全な平行性にある：各入力レジスタの各ビットは出力の同じ位置のビットにのみ作用し−各入力レジスタの最小桁のビットは出力の最小桁のビットにのみ作用し、各入力レジスタの最上位のビットは出力の最上位のビットにのみ作用する等である。このような作用は、固定または可変のローテーション（fixed or variable rotation）を用いずに繰り返しまたは互いにグループ化する場合に、バイトのスワッピングまたは他の（固定または可変の）置換、換字または演算操作は、各出力ビットがＮビット幅の各入力レジスタの１より多いビットに作用するのを許可しない。このため、暗号化アプリケーションに必須の各入力レジスタの異なるビット間で拡散を生じるには、固定または可変のローテーション、バイトのスワッピングまたは他の（固定または可変の）ビットの置換、ビットの換字、または演算操作が必要である。
【００３１】
以下の技術が、ビットの拡散を導くのに必要なビット毎の置換操作を実行するワードベース構造に使用されている：
−通常ルックアップテーブルとして実装されｓボックスに組み合わせられる、ｐボックス；
−１９８９年公開のＧＯＳＴ基準２８１４７−８９にみられる固定のビットローテーション操作；
−上記米国特許４，２５５，８１１（Adler）に記載のキー従属ビットローテーション操作；
−１９７９年公開の米国特許４，１５７，４５４に記載のデータ従属ローテーション操作；
−１９８９年１２月１９日公開の米国特許４，８８８，７９８（Earnest）に記載された、ビットローテーション操作と組み合わせた、および例えばＯＲ、ＸＯＲ、ＡＤＤ操作と組み合わせた、ビット毎のマスキングＡＮＤ操作；
−「On permutation operations in cipher design」、Ruby B. Lee, Z. J. Shi, Y. L. Yin, Ronald L. Rivest, M. J. B, Robshaw、で提唱されているグループ操作や、例えば文献「Efficient permutation instructions for fast software cryptography」、IEEE Micro, 21(6): 56-69、２００１年１２月、R. B. Lee et al. に記載されたＰＰＥＲＭやＣＲＯＳＳ操作、または「Arbitrary bit permutations in one or two cycles」、Proceedings of the 15th International Conference on Application Specific Systems、Architectures and Processors, 237-247頁、２００３年７月、Z. Shi et al.、にあるような置換命令；
−１９８９年公開のＧＯＳＴ基準２８１４７−８９にみられるワードベースの演算操作（ＡＤＤ、ＳＵＢ、ＭＵＬ、ＤＩＶ）；
−あまり一般的でないバイトスワッピング、ワードスワッピング、ビット順序反転操作；
【００３２】
上記特許に開示されている静的なビット毎の置換と展開操作（expansion operations）は、その提案または目的に拘わらず、ソフトウェアの実装さらなる論理回路を用いることなく、直接ハードウェアに実装されている。動的なビット毎の置換操作はｓボックスと、演算操作と、データ従属およびキー従属ローテーション（任意選択キーとして）とを含み、置換はハードウェア内でブール関数を使用したりルックアップテーブルとして実装される。
【００３３】
Eli Biham により１９９７年に公開された文献A Fast New DES Implementation in Softwareに記載されたビットのスライシングは、基本的なＡＮＤ、ＯＲ、ＸＯＲ、ＮＯＴブール理論関数と移動演算のみを用いて並行に実行される複合暗号インスタンスが得られる。上記にみられるように、ビットのスライシングは３２または６４の異なる暗号インスタンス間での相互関係を生成するものではない。ビットスライシングは、単一のプロセッサレジスタ内のビット置換の代わりに、異なるＮビット幅レジスタを直接参照して迅速な平行化されたソフトウェア実装を実現する。ビットスライシングにより単一の暗号を実行する連続的な実行待ち時間が増大するが、実行量が低減する。
【００３４】
実践的なアルゴリズム（ときに近時アルゴリズムと呼ばれる）は、さもなくば多項式アルゴリズムが与えられない問題（intractable problem）の良好な解答を迅速に導く確率的アルゴリズム（probabilistic algorithms）である。このような解答は最適であったりなかったりするが、良好な解答を見つけたり与えられた回答を導いたりすることが事実上コンピュータで実行不能な、多項式アルゴリズムが与えられない問題に許容しうると考えられる。以下のいずれかの実践的なアルゴリズムを、乱数または疑似乱数的に選択された電送置換（wiring permutations）を改善するために、また品質基準として用いられる暗号基準により判断される本発明の好適な実施例で用いられるブール関数に適用可能である：遺伝的アルゴリズム、グリーディアルゴリズム（Greedy algorithms）、ランダムサーチ、タブーサーチ（Tabu search）、ヒルクライミング、アントコロニー最適化（Ant Colony Optimization）、疑似アニーリング（Simulated Annealing）、またはこれらの混成および並列の変異体（parallel variant）。適切なアルゴリズムが以下に記載されている：
Approximation Algorithms、Vijay V. Vazirani、Springer-Verlag、ハイデルベルグ、２００１年、ISBN:3-540-65367-8
Approximation Algorithms for NP-hard Problems、D. S. Hochbaum、PWS出版社、ボストン、１９９６年、ISBN: 0-534-94968-1
Automated Cryptanalysis of Substitution Ciphers、W. S. Forsyth とR. Safavi-Naini、Cryptologia vol XVII, No. 4にて公開、１９９３年、407-418頁
Automated Cryptanalysis of Transposition Ciphers 、J. P. GiddyとR. Safavi-Naini、The Computer Journal vol XVII, No. 4、１９９４年
Two-Stage Optimisation in the Design of Boolean Functions、John Andrew ClarkとJeremy Jacob、Lecture Notes in Computer Science 1841春号、２０００年、ISBN: 3-540-67742-9、242-254頁
【発明の開示】
【課題を解決するための手段】
【００３５】
これに対し、本発明の一態様は、多入力多出力のｓボックスであって、
ａ個の隣接番号の（contiguously numbered）入力ビットＩ１、Ｉ２乃至Ｉａを受信し、ここでａは少なくとも４であり、
ｂ個の連続番号の出力ビットＯ１、Ｏ２乃至Ｏｂを出力するよう構成され、
このｓボックスが：
ｃ個の一次ｓボックスｓｂ１、ｓｂ２乃至ｓｂｃを含み、それぞれ：
多入力単一出力のブール関数ｆ１、ｆ２乃至ｆｃを含み、これらが多入力と単一出力の関係を規定しており、
入力ビットセットｓ１、ｓ２乃至ｓｃをそれぞれ受信するよう構成され、これらのセットがそれぞれ前記ｓボックスへのａ個の入力ビットから選択され、それぞれｓｌ１、ｓｌ２乃至ｓｌｃビットを含み、これにより：
前記ｓｌ１、ｓｌ２乃至ｓｌｃの数が３乃至（ａ−１）の範囲内にあり；
前記ｓｌ１、ｓｌ２乃至ｓｌｃの数の合計がａより大きく、
前記ｓボックスのｂ個の出力ビットが、前記ｃ個のブール関数の出力を含むことを特徴とする。
【００３６】
別の態様によると、本発明は以下の暗号方法を提供する：
ａ個の隣接番号の（contiguously numbered）入力ビットＩ１、Ｉ２乃至Ｉａを受信し、ここでａは少なくとも４であり、
ｂ個の連続番号の出力ビットＯ１、Ｏ２乃至Ｏｂを出力し、
前記方法が：
ｃ個の一次ｓボックス操作（primitive s-box operations）ｓｂ１、ｓｂ２乃至ｓｂｃを含み、それぞれ：
多入力単一出力のブール関数ｆ１、ｆ２乃至ｆｃを含み、これらが多入力と単一出力の関係を規定しており、
入力ビットセットｓ１、ｓ２乃至ｓｃをそれぞれ受信し、これらのセットがそれぞれ暗号化関数（the cryptographic function）へのａ個の入力ビットから選択され、それぞれｓｌ１、ｓｌ２乃至ｓｌｃビットを含み、これにより：
前記ｓｌ１、ｓｌ２乃至ｓｌｃの数が３乃至（ａ−１）の範囲内にあり；
前記ｓｌ１、ｓｌ２乃至ｓｌｃの数の合計がａより大きく、
前記暗号関数のｂ個の出力ビットが、前記ｃ個のブール関数の出力を含むことを特徴とする。
【発明を実施するための最良の形態】
【００３７】
図１は、本発明の好適な実施例にかかあるキー・データ従属換字置換ネットワーク暗号（key-and-data-dependent substitution-permutation network cipher）の一部を図示するものである。図１は、直接的に回路としてハードウェア的に実現してもよいし、以下に示すようにワードベース構造にシミュレートしてもよい。
【００３８】
図１に示す実施例の入力１００は、５つのビット１０１、１０２、１０３、１０４、１０５からなる。関数（function）１１０が、入力ビットを置換する役割も果たす３つの要素により、入力１００の静的な展開（static expansion）を示している。ファンクション１２０は、３×１のｓボックスのインスタンスを具え、図１にはこれらの３つ（１２１、１２２、１２３）のみを示す。出力１３０は、５つのビット１３１、１３２、１３３、１３４、１３５からなる。３×１のｓボックス１２３は、入力１００から３つの入力のユニークなセット、すなわちビット１０５とサイクリックな次の２ビット１０４と１０３とを取り、単一の出力ビット１３５を生成する。３×１のｓボックス１２２は、入力１００から３つの入力のユニークなセット、すなわちビット１０４とサイクリック名次の２ビット１０３と１０２とを取り、単一の出力ビット１３４を生成する。３×１のｓボックス１２１は、入力８００から３つの入力のユニークなセット、すなわちビット８０１とサイクリックな次の２ビット１０５と１０４とを取り、単一の出力ビット１３１を生成する。各出力ビット１３０は３×１のｓボックスにより生成され、各ｓボックスは入力１００からの３つの入力ビットのセットを受け、ここで３つの入力ビットの５つのセットはそれぞれ、他の３つの入力ビットの５つのセットと２ビットより多くを共有しない。
【００３９】
それぞれ別個に、符号１２０で示されている複数のｓボックス関数は、非線形３入力１出力ブール関数からなる。図１に示す好適な実施例では、符号１２０で示される複数のｓボックス関数はそれぞれ、ユニークな３入力１出力の平衡な（balanced）非線形ブール関数を実行する。
【００４０】
図１に示す本発明の好適な実施例は、従来のＭ×Ｎのｓボックスと比較して電送（wiring）の冗長さが低減されている：符号１２０で示す領域のＬ対１（L-to-1）のブール関数は、領域１２０における他のＬから１のブール関数とＬ以下の入力を共有する。これに対し、従来のＭ×Ｎのｓボックスはすべて、完成基準（completeness criterion）を満足するために、完全な電送の冗長性を有する必要がある：すべての出力ビットの完全なＭ対１ブール関数（M-to-1 Boolean function）は、そのＭ個の入力すべてをｓボックス内の他のＭ対１ブール関数と共有する必要がある。
【００４１】
図示の目的のため、ｓボックス１２３、１２２、１２１は、ビット１１９、１１６、１１３がそれぞれビットセット｛１１８，１１７｝、｛１１５，１１４｝、｛１１２，１１１｝をデータ入力とする各マルチプレクサのセレクタ入力となる２対１マルチプレクサ関数（two-to-one multiplexer functions）となるよう選択される。ｓボックス１２０の選択とデータ入力はともに入力１００から導出され、ｓボックス１２０はデータ従属置換（data-dependent permutation）の形である。
【００４２】
この方法では、図１に示す本発明の実施例は、複数の入力ビットの展開−置換（expansion-permutation）と、マルチプレクサ関数と、出力ビット置換（output bit permutation）とを具える。これにより、入力１００の所定の１対Ｌ（1-to-L）展開と、展開された中間状態１１０の所定のビット置換と、展開された中間状態１１０をＬ対１圧縮（L-to-1 compression）して状態１３０を出力とするキー・データ従属換字（key-and-data-dependent substitution）とが得られる。
【００４３】
出力１３０が入力１００にフィードバックされる場合、このような構成を「並列フィードバックの有数非線形シフトレジスタ」または「並列フィードバック型ＮＬＦＳＲ」と呼ぶことができる。本発明の好適な実施例では、１３０の出力が入力１００としてフィードバックされる。２つのサイクリックビットが右へ流れる出力１３０の各ビットの従属性により、ビット作用はサイクリックに左に流れる。本例では、要求される拡散の完成を得るには最低２ラウンドを要する。
【００４４】
このプロセスを実現する回路において、出力１３０の各ビットのクリティカルパス電送待ち時間はおよそ均一となることが予想される。これに対し本発明では、演算操作に基づいた回路に実装されるｓボックスは常に、繰り越し操作（carry operations）のチェーンの最上位のビットに従属して、強固で非一様なクリティカルパス電送待ち時間を示す。
【００４５】
図２は、本発明の別の好適な実施例にかかるキー・データ従属換字置換ネットワーク暗号プロセスの全単射異形（bijective variant）の一部である。領域２００は、２５ビットの入力を示している。領域２０１は、入力２５２の左の２４ビットを示す。領域２１０は、２５ビットの出力を示す。領域２１１は、領域２４０として示す２５対１ｓボックス（twenty five-to-one s-boxes）に従属する２０ビットの出力を示す（図にはこれらの２０のｓボックスの１つのみを符号２４１で示している）。領域２２１は、５ビットの入力を示す。領域２２３は、５つの入力ビット２２１の全単射（可逆の）５×５換字−置換２２２に従属する５ビットの出力を示す。 
【００４６】
領域２４０の多入力単一出力ブール関数２４１はそれぞれ、例えば領域２０１の符号２３１、２３２、２３３、２３４、２３５といった５ビットの予め定められたセット２３０を入力とし、出力として、ビット２５３を出力として生成する２５０内の線形コンバイナ（ＸＯＲ／ＸＮＯＲ）２５１に第１の入力ビットを生成する。入力ビット２５２は２５１への２つの入力のうちの２つ目である。領域２５０の各線形コンバイナ２５１用に、領域２４０の対応するブール関数がこの第２の入力ビットの左の領域のみから入力をコンバイナに受け取り、この領域が２０１として示されている。
【００４７】
図２に示す本発明の好適な実施例では、領域２４０で図示されたステップに用いられる基本の５対１ｓボックス２４１は、領域２３０に図示するステップで用いられる５つの入力２２１から２３５と、単一の出力と、前記入力ビットと出力ビット感の関係を規定する５対１ブール関数とからなり、各平衡非線形ブール関数２４１は無作為に選択される。
【００４８】
図３は、本発明の好適な実施例にかかるワードベースのキー・データ従属換字−置換ネットワークの一部を示す図である。このデータステート（data state）３１０は１５ビット幅で３ワード（あるいは最も便利な表記により、ブロック、サブブロック、レジスタ）に仕切られている。ワード３１１は、５つのビット３２１、３２２、３２３、３２４、３２５からなり；ワード３１２は、５つのビット３３１、３３２、３３３、３３４、３３５からなり；ワード３１３は５つのビット３４１、３４２、３４３、３４４、３４５からなる。
【００４９】
領域３５０は、このデータステートの３つのファクタによる静的展開置換（static expansion permutation）を示す。領域３６０は、３×１の非線形換字ボックス関数（図にはこれらの１つのみ示す）を示す。
【００５０】
データステート３６５は、１５ビットで、３ワードに仕切られている。ワード３６６は５つのビット３７１、３７２、３７３、３７４、３７５からなり；ワード３６７は５つのビット３８１、３８２、３８３、３８４、３８５からなり；ワード３６８は５つのビット３９１、３９２、３９３、３９４、３９５からなる。
【００５１】
図示する３×１の換字置換関数３６１は、受信される３つの入力のユニークなセットを取得し、これはワード３１３のビット３４４から派生するビット３５２と、ワード３１２のビット３３２から派生するビット３５３と、ワード３１１のビット３２５から派生するビット３５１とからなる。図示するｓボックス３６１は、ワード３６７に単一ビットの出力３８５を生成する。
【００５２】
ステート３６５の１５ビットすべてにおいて、３６０の各３×１ｓボックスは、上記テンプレートに従い、４入力のユニークなセットを出力する。
【００５３】
図３に示す本発明の好適な実施例にかかるワードベースのキー・データ従属換字−置換ネットワーク暗号は、暗号ソフトウェアのパフォーマンスを改善する直接的なメカニズムを提供する。
【００５４】
図４は、本発明の好適な実施例にかかる図１に示す暗号を実装するソフトウェアの一例を示す図である。図４に示すプロセスは、ワード長が５ビットのプロセッサで実行される。ワード４００は、５つのビット４０１、４０２、４０３、４０４、４０５からなり；ワード４１０は、５つのビット４１１、４１２、４１３、４１４、４１５からなり；ワード４３０は５つのビット４３１、４３２、４３３、４３４、４３５からなり、ワード４７０は５つのビット４７１、４７２、４７３、４７４、４７５からなる。ワード４００は、ワード４１０および４３０への複製（duplication）を通して、３つのワードに展開される。
【００５５】
ワード４１０は、サイクリックなローテーション４１９を用いて、１ビットから最上位のビットに向かって静的（static）に置換される。これにより、ビット４１１、４１２、４１３、４１４、４１５は、それぞれ出力４２２、４２３、４２４、４２５、４２１として置換される。出力ビット４２１から４２５は、４５０の単一のワード入力として用いられる。
【００５６】
ワード４３０は、サイクリックなローテーション４３９を用いて、２ビットから最上位のビットに向かって静的（static）に置換される。これにより、ビット４３１、４３２、４３３、４３４、４３５は、それぞれ出力４４３、４４４、４４５、４４１、４４２として置換される。出力ビット４４１から４４５は、４５０の単一のワード入力として用いられる。
【００５７】
領域４５０は、３つの入力ワードをとる関数を規定し、図１に図示するマルチプレクサ作用を実現するワードベースの基本のブール関数でなるワードベースの命令４６０のシーケンスを実行する。仮にワード４００をＡ、ワード４２０をＢ、ワード４４０をＣ、ワード４７０をＤとすると、５つのビット幅２対１マルチプレクサを表すことができ、Ａｈａ選択入力でなり、ＢとＣは以下のデータ入力でなる：
Ｄ＝（Ａ  ＡＮＤ  Ｂ）ＯＲ（（ＮＯＴ  Ａ）ＡＮＤ  Ｃ）
【００５８】
領域４８１は、どのようにビット４７１が入力４０１、４２１、４４１にのみ従属するのかを視覚的に示している。領域４８２から４８５は、それぞれビット４７２から４７５の従属性を示している。
【００５９】
５ビット変数（five-bit variables）の語で完全な５ビット幅のプロセスの実装を説明すると、以下のようになる：
Ｄ＝（Ａ  ＡＮＤ（Ａ  ＲＯＴ１））ＯＲ（（ＮＯＴ  Ａ）ＡＮＤ（Ａ  ＲＯＴ２））
【００６０】
一般目的の５ビットレジスタＲＡが入力であるアセンブラ擬似コード（assembler pseudo code）では、ＲＢとＲＣは一次レジスタでありＲＤが出力であり、これと同じアルゴリズムが以下の６操作で自明的（trivially）に実現される：
RB=RA rotate left 1
RC=RA and RB
RA=not RA
RB=RB rotate left 1
RD=RA and RB
RD=RD or RC
【００６１】
上記プロセスは、普遍性を失わずに、どのように置換操作がカスケード（cascade）されるかと、移動／複製操作が最適化されるかを示している。例えばバイトスワッピング（byte-swapping）、ルックアップテーブル、バイナリマスキング操作（binary masking operations）といった他の操作をがソフトウェアプロセッサで実現可能であり、これにより技術者が、プロセッサ命令の短いシーケンスで表現される幅広い電送置換（wiring permutations）を実現することができ、したがってハードウェア性能を落とすことなく要求されたソフトウェア性能を得ることができる。
【００６２】
図１、２、３に示す本発明の好適な実施例では、すべての入力ビット１００、２０１、３１０をそれぞれ展開された入力ビット１１０、２４０、３５０への割り当てること（assignments）を含む内部電送置換（internal wiring permutations）は、１２０、２４０、３６０内の複数の基本のＬ対１ｓボックスからそれぞれ１３０、２１０、３６５内のすべての出力ビットへの出力ビットのすべての割り当てとともに、無作為に選択される。
【００６３】
本発明の別の好適な実施例では：
−内部電送置換（internal wiring permutation）がキー従属疑似ランダムプロセスで選択される；
−内部電送置換が数式により選択される；
−内部電送置換が、入力と出力ビット間の単一ラウンドまたは複数ラウンドの多項式の関係における冗長性を低減するよう帰納的に細分され（heuristically refined）；
−内部電送置換が、ハードウェア回路最適化の最大電送待ち時間により制限される；
−１２１、１２２、１２３、２４１、３６１への入力が、それぞれ出力１３１、１３４、１３５、２５、３８５からの間隔に制限される；
−領域１２０、２４０、３６０の各基本のＬ対１ｓボックスが、それぞれ領域１３０、２１０、３６５の各出力ビットに関し、領域１００、２０１、３１０、の入力ビットの同じ関連位置から選択される；
−領域１２０、２４０、３６０内の基本のＬ対１ｓボックスのいくつかが、１または複数のキービットを入力として受信するよう構成されている；
−異なる電送置換が暗号処理の各ラウンドで選択される；
−出力１３０、２１０、３６５の幅が、それぞれ入力１００、２００、３１０と異なる；
−内部電送置換が、３２ビットまたは１２８ビットの一般目的のプロセッサ命令の短いシーケンスとして実装しうる置換に限定される；
−内部電送置換が、２００４年１０月１３日に提出された継続中のオーストラリア暫定特許出願２００４９０５８９７、「Process of and Apparatus for Encoding a digital signal」にみられるバイトスワッピングとローテーションシーケンシングの組合せに適合する；
−領域１２０、２４０、３６０のすべての基本のＬ対１ｓボックスに単一のブール関数が用いられる；
−領域１２０、２４０、３６０の基本のＬ対１ｓボックスに複数のブール関数が用いられる；
−領域１２０、２４０、３６０の基本のＬ対１ｓボックスに用いられるすべてのブール関数が異なる；
−領域１２０、２４０、３６０の基本のＬ対１ｓボックスに用いられるブール関数のいくつかが、キー従属疑似ランダムプロセスを用いて選択される；
−領域１２０、２４０、３６０の基本のＬ対１ｓボックスに用いられるブール関数の選択が、入力と出力ビット間の単一ラウンドまたは複数ラウンドの多項式の関係における冗長性を低減するよう帰納的に細分される（heuristically refined）；
−元の入力変数（またはプロセッサレジスタ）のみが後続の処理で用いられる；
−少なくとも１または複数の中間変数（またはプロセッサレジスタ）が後続の処理で用いられる；
−中間変数（またはプロセッサレジスタ）のみが後続の処理で用いられる；
−ｓボックスを設ける方法が、以下の継続中の特許出願にみられる双方向ブロック連鎖方式にも適合する：
２００４年１１月５日出願のオーストラリア暫定出願２００４９０６３６４と２００５年１月１０日出願の２００５９０００８７、ともに名称がA method of Endoding a Signal；
２００５年５月１０日出願の国際特許出願ＰＣＴ／ＩＢ２００５／００１４９９、名称Method of Encoding and Decoding Data；
２００５年５月１０日出願の国際特許出願ＰＣＴ／ＩＢ２００５／００１４８７、名称Process of and Apparatus for Encoding a Signal；
２００５年５月１０日出願の国際特許出願ＰＣＴ／ＩＢ２００５／００１４７５、名称A Method of and Apparatus for Encoding a Signal in a Hashing Primitive；
各文献の内容は本願に参照として組み込まれる。
【００６４】
本発明の好適な実施例で用いられる電送置換および/またはブール関数は、「ファミリー」キーと呼ばれるキー要素に従属し、このような暗号のハードウェア（ＲＦＩＤ、ＡＳＩＣ等）の実装は、固定の基本ブール理論を伴う固定的な電送として実装された場合にまだ有効である。
【００６５】
重要なことは、２５２の左のビットのみへの基本のＬ対１ｓボックス２０１への入力ビットの選択の唯一の制限は、入力ビット２５２と出力ビット２５３間の線形関係と組み合わさり、図２のように操作され、ブール関数または内部電送置換の選択に拘わらず、全単射（可逆の）操作を確実にする。
【図面の簡単な説明】
【００６６】
本発明をより理解し易くすべく、その好適な実施例が図面を参照しながら説明され、ここで図１、２、３、４は本発明の好適な実施例にかかる方法を図示するものである。
【図１】
2008514975.tif 000003
【図２】
2008514975.tif 000004
【図３】
2008514975.tif 000005
【図４】
2008514975.tif 000006
【国際調査報告】
2008514975.tif 000007
2008514975.tif 000008