(57)【特許請求の範囲】
【請求項１】
２入力２出力の置換網（以下ゲートと記す）の複数個を組合わせて、入力数ｎ（ｎは整数、かつ２k-1 ＜ｎ＜２k,ｋは２以上の整数）の置換網を構成する方法であり、
入力数ｍの置換網Ｐｍ１とＰｍ２の２個を設け、これらの入力側にｍ個のゲートＧｉ１〜Ｇｉｍを配し、これらゲートＧｉ１〜Ｇｉｍの各一方の出力を置換網Ｐｍ１のｍ個の入力にそれぞれ接続し、各他方の出力を置換網Ｐｍ２のｍ個の入力にそれぞれ接続し、置換網Ｐｍ１，Ｐｍ２の出力側にｍ−１個のゲートＧｏ２〜Ｇｏｍを配し、置換網Ｐｍ１，Ｐｍ２の各１番目の出力を組合せた２ｍ入力２ｍ出力の置換網Ｐ２ｍの１番目と２番目の出力とし、ゲートＧｏ２〜Ｇｏｍの各一方の入力を置換網Ｐｍ１の２〜ｍ番目出力にそれぞれ接続し、各他方の入力を置換網Ｐｍ２の２〜ｍ番目出力にそれぞれ接続して２ｍ入力２ｍ出力の置換網Ｐ２ｍを構成する置換網の構成方法において、
２k −ｎを２進展開し２k −ｎ＝Σi=0k-2ｅi ２i,ｅi∈｛０，１｝、
ｉ＝ｋ−２，ｋ−３，…,０の順に、
ｅi ＝０の場合は、構成されている入力数（…（（２・２−ｅk-2）・２−ｅk-3）…）・２−ｅi-1 の置換網の２個を、複数のゲートとを用いて組合わせ、入力数（（（…（（２・２−ｅk-2）・２−ｅk-3）…）・２−ｅi-1）・２の置換網を構成し、
ｅi＝１の場合は、構成されている入力数（…（（２・２−ｅk-2）・２−ｅk-3）…）・２−ｅi-1の置換網の２個を、複数のゲートを用いて組合わせて構成される入力数（（（…（（２・２−ｅk-2）・２−ｅk-3）…）・２−ｅi-1）・２の置換網の一番最後の入力と出力を使用しないことにより、入力数（（（…（（２・２−ｅk-2）・２−ｅk-3）…）・２−ｅi-1）・２−１の置換網を構成することを
順次行って構成することを特徴とする任意数入力の置換網構成方法。
【請求項２】
２入力２出力の置換網（以下ゲートと記す）の複数個を組合わせた入力数ｎ（ｎは整数、かつ２k-1 ＜ｎ＜２k,ｋは２以上の整数）の置換網をであって、
入力数ｍの置換網Ｐｍ１とＰｍ２の２個を設け、これらの入力側にｍ個のゲートＧｉ１〜Ｇｉｍを配し、これらゲートＧｉ１〜Ｇｉｍの各一方の出力を置換網Ｐｍ１のｍ個の入力にそれぞれ接続し、各他方の出力を置換網Ｐｍ２のｍ個の入力にそれぞれ接続し、置換網Ｐｍ１，Ｐｍ２の出力側にｍ−１個のゲートＧｏ２〜Ｇｏｍを配し、置換網Ｐｍ１，Ｐｍ２の各１番目の出力を組合せた２ｍ入力２ｍ出力の置換網Ｐ２ｍの１番目と２番目の出力とし、ゲートＧｏ２〜Ｇｏｍの各一方の入力を置換網Ｐｍ１の２〜ｍ番目出力にそれぞれ接続し、各他方の入力を置換網Ｐｍ２の２〜ｍ番目出力にそれぞれ接続して２ｍ入力２ｍ出力の置換網Ｐ２ｍを構成する置換網であって、
２k −ｎを２進展開し２k −ｎ＝Σi=0k-2ｅi ２i,ｅi∈｛０，１｝、
ｅi ＝０の部分においてはその対応２個のｍ入力ｍ出力置換網の入力、出力が前記のように接続され、ｅi ＝１の部分においては該当２個のｍ入力ｍ出力置換網の各最後の入力と出力が使用されていないことを特徴とする任意数入力置換網。
【請求項３】
上記ｎ個の入力にそれぞれ暗号文が入力され、上記各ゲートに、その入力された２つの暗号文をランダム化する手段と、入力された２つの暗号文をランダムに置換する手段と、上記ランダム化及び上記ランダム置換が正しく行われたことのゼロ知識証明を作成して公開する手段とが設けられていることを特徴とする請求項２記載の任意数入力置換網。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、情報通信技術や、その応用技術に用いられ、２入力２出力置換網の複数個の組合せにより構成され、ｍ入力ｍ出力に対し、任意の１つの入力を任意の１つの出力に接続することができるように接続替えをすることができる置換網の構成方法、及び、その置換網に関する。
【０００２】
【従来の技術】
２入力２出力置換網とは、図５Ａに示すように２個の入力をそのままの順で出力するストレート網と、図５Ｂに示すように交換した順で出力するクロス網との何れにも設定できるものである。以下一般の置換網と２入力２出力置換網を区別するために、２入力２出力置換網をゲートと呼ぶ。
一般の置換網は、複数のゲートを組合わせて構成され、各ゲートを適切に設定することにより、入力に任意の置換を施し出力できるような交換装置である。置換網を構成するゲートの数をゲート数、入力から出力までに通過するゲートの最大数を段数という。たとえば、図６に示す置換網は、ゲート数５段数３の４入力４出力の置換網である。
【０００３】
５個のゲートＧ１，１,Ｇ１，２,Ｇ２，１，Ｇ２，２,Ｇ２，３を適切に設定することにより、４個の入力に任意の置換を行い出力することができる。
置換網をできるだけ少ないゲート数・段数で実現することが求められるが、Ｗａｋｓｍａｎにより以下の結果が得られている（A.Waksman,A Permutation Network,Journal of the Association for Computing Machinery 15(1),1968.参照）。
Ｗａｋｓｍａｎの構成法によれば入力数２k の置換網を、ゲート数２k(ｋ−１）＋１、段数２ｋ−１で構成することができる。
【０００４】
Ｗａｋｓｍａｎによる構成法は図７に示すようにまず、入力数ｍの置換網Ｐｍ１とＰｍ２の２個を設け、これらの入力側にｍ個のゲートＧｉ１〜Ｇｉｍを配し、これらゲートＧｉ１〜Ｇｉｍの各一方の出力を置換網Ｐｍ１のｍ個の入力にそれぞれ接続し、各他方の出力を置換網Ｐｍ２のｍ個の入力にそれぞれ接続し、置換網Ｐｍ１，Ｐｍ２の出力側にｍ−１個のゲートＧｏ２〜Ｇｏｍを配し、置換網Ｐｍ１，Ｐｍ２の各１番目の出力を組合せた２ｍ入力２ｍ出力の置換網Ｐ２ｍの１番目と２番目の出力とし、ゲートＧｏ２〜Ｇｏｍの各一方の入力を置換網Ｐｍ１の２〜ｍ番目出力にそれぞれ接続し、各他方の入力を置換網Ｐｍ２の２〜ｍ番目出力にそれぞれ接続して２ｍ入力２ｍ出力の置換網Ｐ２ｍを構成する。
【０００５】
２入力２出力の置換網から始めて、この操作を再帰的に繰り返すことにより、入力数２k の置換網Ｐ２k をゲート数２k(ｋ−１)＋１、段数２ｋ−１で構成することができる。
【０００６】
【発明が解決しようとする課題】
しかし、入力数が２k ではない場合は、入力数が２k になるように入力数を増加しなければならず、それだけ不必要に多くのゲート数を用いることになる。
この発明の目的は、入力数が２k でない場合に、入力数が２k になるように増加させることなく、それだけ少ないゲート数で構成することができる置換網構成方法及びその装置を提供することにある。
【０００７】
【課題を解決するための手段】
この発明によれば、入力数ｎが２k-1 ＜ｎ＜２k （ｋは２以上の整数）の場合に、２k−ｎを２進展開し２k−ｎ＝Σi=0k-2ｅi ２i，ｅi∈｛０，１｝，ｉ＝ｋ−２，ｋ−３，…，０の順に、以下を再帰的にくりかえす。
ｅi ＝０の場合は、入力数ｍ＝（…（（２×２−ｅk-2)×２−ｅk-3)…）×２−ｅi-1 の置換網の２個を、従来と同様に図１Ａに示すように、ｍ入力ｍ出力置換網を入力側に、ｍ個のゲート、出力側に（ｍ−１）個のゲートを設け、各ゲートをそれぞれ、２個のｍ入力ｍ出力置換網に、接続して、２ｍ入力２ｍ出力置換網に組合せ、
ｅi＝１の場合は入力数ｍ＝（…（（２×２−ｅk-2)×２−ｅk-3)…）×２−ｅi-1の置換網の２個を、図１Ｂに示すように、ｍ入力ｍ出力置換網を入力側に、ｍ個のゲート、出力側に（ｍ−１）個のゲートを設け、各ゲートをそれぞれ、２個のｍ入力ｍ出力置換網に接続して、組合せるが、その２ｍ個の入力の最後のものＩ2mと２ｍ個の出力の最後のものＯ2mを不使用として（２ｍ−１）入力（２ｍ−１）出力置換網とすることを順次行う。この不使用とされた入力Ｉ2mと出力Ｏ2mは入力Ｉ2mの入力が出力Ｏ2mに出力するように内部的に接続する。
【０００８】
これにより２k-1＜ｎ＜２k入力置換網をゲート数、
２k(ｋ−１）＋１−Σi=0k-2ｅi ２i ｉ
段数２ｋ−１で実現することができる。
【０００９】
【発明の実施の形態】
実施形態１
以下この発明の実施の形態を説明する。例としてｎ＝１１とする。この場合２4−ｎ＝１０１2(Ａ2はＡの２進数表示）となり、ｅk-2=2＝１、ｅk-3=1＝０、ｅk-4=0＝１であり、（（２×２−１）×２−０）×２−１＝１１を用いて以下のように構成する。
（１）ｅ2 ＝１であるから、図２Ａに示すように２入力置換網つまりゲートＰ２，１、Ｐ２，２を２つ組合せて４入力置換網をつくり、その４入力置換網の一番最後の入力Ｉ4と出力Ｏ4を使用しないことにして３入力置換網Ｐ３をつくる。
【００１０】
（２）ｅ1 ＝０であるから、図２Ｂに示すようにその３入力置換網を２つＰ３，１とＰ３，２を組合せて６入力置換網Ｐ６をつくる。
（３）ｅ0 ＝１であるから、図２Ｃに示すように、その６入力置換網を２つＰ６，１とＰ６，２を組合せて１２入力置換網をつくり、その１２入力置換網の一番最後の入力Ｉ12と出力Ｏ12を使用しないことにより１１入力置換網が構成される。
また、発明法で構成した置換網は入力の任意の置換を実現することができる。
【００１１】
まず、図１Ｂについて述べたように一番最後の入力Ｉ2mの入力を一番最後の出力Ｏ2mに出力するようにするが入力Ｉ2mと出力Ｏ2mを使用しないようにすることにより、２ｍ入力の置換網を用いて（２ｍ−１）入力の置換網を構成している。２ｍ入力の置換網が２ｍ個の入力の任意の置換を実現できるので、この（２ｍ−１）入力置換網は（２ｍ−１）個の入力の任意の置換を実現できる。
つぎに、図１Ａに示すように２つのｍ入力の置換網を組合せて、２ｍ入力の置換網を構成しているが、図１Ａの２ｍ−１個のゲートをつぎのように設定することにより２ｍ個の入力の任意の置換を実現できる。まず、出力Ｏ1 ＝１に対応する入力を入力Ｉ1 として、入力Ｉ1 の入るゲートを設定する。つぎに、入力Ｉ1 と同じゲートに入る入力Ｉ2 に対応する出力を出力Ｏ2 とし、出力Ｏ2 が出ているゲートを設定する。つぎに、出力Ｏ2 と同じゲートから出る出力Ｏ3 に対応する入力を入力Ｉ3 とし、入力Ｉ3 の入るゲートを設定する。これを繰り返すことにより、２ｍ−１個のゲートを設定する。
【００１２】
これらのことを再帰的に用いることにより、任意の置換を実現するように各ゲートを設定することができる。よって、この発明方法により構成した置換網は入力の任意の置換を実現することができる。
従来法では、入力数２k-1 ＜ｎ＜２k の置換網を、入力数を２k に切り上げてゲート数２k(ｋ−１）＋１、段数２ｋ−１で構成していたが、この発明方法を用いることにより、ゲート数
２k(ｋ−１）＋１−Σi=0k-2ｅi ２i ｉ
段数２ｋ−１で構成することができる。なお、このようにゲート数が少なくて済むことが直感的に理解できる例としてｎ＝５、２3
−５＝３＝１１2 、（２×２−１）×２−１の構成を図３に示す。３入力置換網Ｐ３，１とＰ３，２を２つ組合せて６入力置換網を構成するため、図中破線で示すように２3 置換網よりもゲートが２個減少する。
【００１３】
最も改善の効果がでるｎ＝２k-1 ＋１の場合、従来法ではゲート数２k(ｋ−１）＋１であるが、この発明方法ではゲート数２k(ｋ−１）＋１−Σi=0k-2２i ｉ＝２k(ｋ−１）＋１−（２k-1 （ｋ−３）＋２）で構成することができ、漸近的には
【００１４】
【数１】
0003741360.tif 000002
【００１５】
となり、２倍効率が改善されている。
たとえば、入力数ｎ＝１０２５＝２10＋１の置換網の場合、従来法では２11（１１−１）＋１＝２０４８１個のゲートを用いていたが、この発明方法では２11（１１−１）＋１−Σi=09２i ｉ＝２０４８１−８１９４＝１２２８７個のゲートだけで構成することができる。
実施形態２
Ｍｉｘ−ｎｅｔは、電子投票などにおいて匿名性を確保するために重要な役割を果たす仕組みであり、近年、置換網を用いて効率的に全体検証可能なＭｉｘ−ｎｅｔを実現する方法が示されている（例えば特願２０００−１４５９９２や、M.Abe,Mix-Networks on Permutation Net-works,Proc.of ASIACRYPT '99 258-273,1999.参照）。ここでＭｉｘ−ｎｅｔとは、ｎ個の入力暗号文をランダム化し置換を施して出力することにより、入力暗号文と出力暗号文との対応関係つまり施した置換を秘匿するものである。また全体検証可能とは、施した置換を秘匿したまま、正しく置換が施されたことを誰にでも証明できるということである。
【００１６】
前記全体検証可能なＭｉｘ−ｎｅｔの構成では、Ｗａｋｓｍａｎの方法によりｎ＝２k 入力の置換網を構成し、その置換網の各ゲートにおいて、
（１）入力された２つの暗号文をランダム化する機能
（２）入力された２つの暗号文をランダムに置換する機能
（３）上記操作が正しく行われたことのゼロ知識照明を公開する機能
を設けたものである。
この発明の他の実施形態では前述したこの発明によるｎ入力置換網を構成する各ゲート（２入力２出力置換網）を図４に示すように構成する。つまり入力Ｉ1 ，Ｉ2 より入力された暗号文はランダム化部１１において秘密情報によりランダム化され、その２つのランダム化された暗号文は置換部１２において、図５に示したようなその順序が入れ替えられないこと（ストレート）、又は順序が入れ替えられること（クロス）がランダムに行われ、２つの入力と２つの出力の対応が隠蔽されて出力Ｏ1 ，Ｏ2 へ出力され、また入力と出力とが置換証明部１３に入力され、入力と出力を対応づける秘密情報及びランダムな置換が存在することを、使用した秘密情報およびランダム置換を明かすことなくゼロ知識証明により、任意の検証者に対して、証明する証明が公開される。なお、これらランダム化部１１、置換部１２、置換証明部１３の詳細は例えば前記文献を参照されたい。
【００１７】
前述したように、この発明による置換網は入力数が２巾でない場合にゲート数を削減でき、それにより、不要な暗号文のランダム化、暗号文のランダム置換、ゼロ知識証明の各操作を省略することができ、Ｍｉｘ−ｎｅｔの効率を従来法よりも最大で２倍改善できる。
【００１８】
【発明の効果】
以上述べたようにこの発明によれば、入力が２巾でない場合にゲート数を少なくすることができ、それだけ置換網の効率を向上させることができる。この置換網の各ゲートに暗号文ランダム化機能、２つの入力暗号のランダム置換機能、これらが正しく行われたことのゼロ知識証明作成機能を付加することにより、Ｍｉｘ−ｎｅｔの効率を改善することができる。
【図面の簡単な説明】
【図１】この発明の方法を説明するための２ｍ入力置換網と（２ｍ−１）入力置換網を示す図。
【図２】この発明方法の実施形態を示す図。
【図３】この発明方法によりゲート数が削減できる状態を示す図。
【図４】ゲートにランダム化部、置換部及び置換証明部を設けた例を示す図。
【図５】２入力２出力置換網（ゲート）の機能を説明するための図。
【図６】４入力４出力置換網を示す図。
【図７】従来の置換網構成方法を説明するための図。
【図１】
0003741360.tif 000003
【図２】
0003741360.tif 000004
【図３】
0003741360.tif 000005
【図４】
0003741360.tif 000006
【図５】
0003741360.tif 000007
【図６】
0003741360.tif 000008
【図７】
0003741360.tif 000009