Verifiable anonymous channel6937728Abstract Two El Gamal ciphertexts, which are input to a two-input two-output unit switching gates SW forming a permutation network, are randomized with a random number and randomly permuted, and a zero-knowledge proof, which proves the correspondence between the inputs and outputs of the switching gates SW, is output to a verifier without revealing the random number and the random permutation. A decryption unit decrypts ciphertexts from a unit switching gate SW in he last column through the use of a secret key, and proves in zero-knowledge the validity of the decryption without revealing the secret key. A verification unit verifies the proof of each unit switching gate and the proof of the decryption unit. Claims 1. A verifiable anonymous channel in which N encrypted input messages, where N is an integer equal to or greater than 2, are permuted and randomized to obtain N output messages and it is proved to an arbitrary verifier that said output messages and said input messages have a one-to-one correspondence with each other, comprises: Description BACKGROUND OF THE INVENTION
Step 4: Drive the random generator 13 in FIG. 4 to generate random numbers w1, w2, eb′, z1b′, z2b′∈Zq and provide them to the permutation proving part 14 together with b, t1, t2. Assume that b′=2 when b=1 and b′=1 when b=2. And p, q, g, y are read out of the memory 11 and fed to the permutation proving part 14. Step 5: The permutation proving part 14 operates as follows (see FIG. 5). The permutation proving part 14 has branched thereto the two inputs I1, I2 and two outputs O1, O2 of he switching part 12.
Let R1, R2, R3, R4 represent the outputs that are provided at the terminals of the permutation network 10. At this time, setting R1=(M′1, G′1), the following relations hold.
The decryption unit 20 comprises, as depicted in FIG. 7, a decryption part 21, a decryption proving part 22, a memory 23 and a control part 24 for controlling their operation. The decryption part 21 is made up of a modular exponentiator 21A and a modular divider 21B as depicted in FIG. 8. The decryption proving part 22 comprises, as shown in FIG. 9, a random generator 22A, a modular exponentiator 22B, a hash calculator 22C and a modular multiplier/subtractor 22D. The decryption unit 20 performs the following steps to process the outputs R1 to R4 one after another. Step 1: The control part 24 sequentially receives the inputs Ri and provides them to the decryption part 21. Further, the control part 24 reads out x, p from the memory 23 and inputs them to the decryption part 21. Step 2: In decryption part 21, G′i and x, p are input to the modular exponentiator 21A to compute Ki:=G′ix mod p. Step 3: M′i, p and the output from the modular exponentiator 21A are input to the modular divider 21B to compute mi:=M′i/Ki mod p which is output as the result of decryption. Following this, the decryption unit 20 generates in the decryption proving part 22 the ProofD that proves the correctness of the decryption as described below. Step 1: The decryption proving part 22 generates a random number w∈Zq by the random generator 22A as depicted in FIG. 9 and provides it to the modular exponentiator 22B. Step 2: The modular exponentiator 22B first computes To:=gw mod p, then computes Ti:=G′iw mod p, and provides them to the hash calculator 22C. In this example, N=4. Step 3: The hash calculator 22C computes c:=Hash(y, To, K1, T1, . . . , KN, TN) and provides c to the modular multiplier/subtractor 22D. Step 4: The modular multiplier/subtractor 22D computes z:=w-cx(mod q) and outputs it together with c, z, K1, . . . , KN. At this time, set ProofD:=(c, z, K1, . . . , KN). The verification terminal 200 first drives the permutation verification part 30 to make sure that the permutation was executed correctly. The permutation verification part 30 comprises, as depicted in FIG. 10, a modular exponentiation multiplier 31, a hash calculator 32, a comparator 33 and an adder 34. The permutation verification part 30 follows the following procedure to verify Proofi by the i-th switching gate SWi. Step 1: Drive the modular exponentiation multiplier 31 to compute S11:=(N1e Step 2: Input S11, S12, S21, S22 and I1, I2, O1, O2 to the hash calculator 32, and input its output to the comparator 33. Step 3: Input e1, e2 to the adder 34 to compute e1+e2, and input the result of addition to the comparator 33. Step 4: Input q to the comparator 33 to make a check to see if e1+e2=c(mod q) holds. If it holds, output OK, and if not, output NG. In this way, the correctness of permutation is verified in zero-knowledge without revealing the random number b on the basis of which the permutation was performed. The above-described verification is made for the input/output of every switching gate, and a switching gate that outputs NG is regarded as being faulty. When the proofs from all the switching gates successfully pass the verifications, R1, . . . , R4, m1, . . . , m4 and ProofD are provided to the decryption verification part 40 to verify that the decryption was performed correctly. FIG. 11 depicts in block form the decryption verification part 40, which is made up of a modular divider 41, a comparator 42, a modular exponentiation multiplier 43, a hash calculator 44 and a comparator 45. The decryption verification part 40 verifies the decryption as described below. Step 1: Input M′i and Ki to the modular divider 41 to compute M′i/Ki and input the result of division, together with mi, to the comparator 42 for comparison. If they are not equal to each other, the comparator 42 outputs NG, making the result of verification NG. When the result of comparison is OK for all i=1, . . . , N, proceed to the nest step. Step 2: Drive the modular exponentiation multiplier 43 to compute gzcy and G′1zK1c, . . . , G′NzKNc, and provide the results of computation to the hash calculator 44. Step 3: Drive the hash calculator 44 to compute e:=Hash(y, gzyc, K1, G′1zK1c, . . . , KN, G′1zK1c). Step 4: Input c and e output from the hash calculator 44 to the comparator 45, which outputs OK or NG, depending on whether they are equal or not. When the decryption was conducted correctly, Gzyc=gw-cxyc=gw=Tc and G′izKic=G′iw-cxKic=G′i=Ti hold, and hence the output from the hash calculator 44 is equal to c. In this embodiment, when the random elements used in each switching gate, that is, b, t1, t2, w1, w2, are all kept secret, the correspondence Ei→mj is concealed for any values of i and j. As described above, since this embodiment has a construction in which each switching gate proves the correctness of its random permutation, the amount of data to be processed is significantly smaller than in the case of proving the validity of random permutation by the afore-mentioned R. Cramer et al. scheme, especially when the number N of inputs to the anonymous channel is large. Second Embodiment This embodiment is adapted to conceal the correspondence between inputs and outputs as a whole even if random elements used in some of the switching gates leak out. FIG. 12 depicts in block form the principal part of this embodiment, in which the permutation network 10 is comprised of V "permutation servers" PS1, . . . , PSV each of which performs tasks of several switching gates in a sequential order. The following description will be given of the case where four permutation servers form the permutation network 10 and four messages are input. The permutation servers PS1 to PS4 and the verification terminal 200 are supposed to be connected to a bulletin board 400. The bulletin board 400 accepts writes E1, . . . , EN from authenticated users, and has a function that information once written thereon cannot be erased. Assume that the information written on the bulletin board 400 is accessible by anyone. In this embodiment, too, as is the case with the first embodiment, each switching gate SW (FIG. 13) of each permutation server PS in the permutation network 10 does not perform decryption but perform randomization (transformation) and random permutation of input ciphertexts, and the decryption server ultimately perform decryption. FIG. 13 depicts in block form the permutation server PS. The switching gate SW in the permutation server PS is identical with the switching gate SW in FIG. 4 except that the control part 15 and the memory 11 are placed outside the switching gate SW. FIG. 14 shows in block form the decryption server 20S. The decryption server 20S comprises a permutation verification part 30S, a decryption part 21S and a decryption proving part 22S, which are identical with the permutation verification part 30, the decryption part 21 and the decryption proving part 22 shown in FIGS. 10, 8 and 9, respectively. The decryption server 20S further comprises a memory 23S and a control part 24S. This embodiment uses the four permutation servers PS1, . . . , PS4 to form two four-input perfect permutation networks. The flow of data in this case is depicted in FIG. 15. Though not shown, all data transfers between the permutation servers are made via the bulletin board 400 as depicted in FIG. 12. That is, each permutation server SP, writes its permuted output in the bulletin board 400, and the permutation server SPj+1 in the next stage reads out the data from the bulletin board 400 and performs permutation. The permutation server SP1 performs the tasks of the switching gates SW1 and SW2 in the first embodiment and sends the results of processing via the bulletin board 400 to the permutation server SP2. Similarly, the permutation server SP2 performs the tasks of the switching gates SW3, SW4 and SW5, the permutation server SP3 the tasks of the switching gates SW6 and SW7, and the permutation server SP4 the tasks of the switching gates SW8, SW9 and SW10. As depicted in FIG. 13, only one switching gate SW is disposed in each permutation server SP in practice, and the flow of data shown in FIG. 15 is implemented by applying appropriate inputs under the control of the control part 15. In practice, however, more than one switching gates may also be placed in one permutation server PS. As depicted in FIGS. 12 and 15, the cascade-connected permutation servers PS1 to PS4 constitute at least two cascade-connected perfect permutation networks. For the output from each permutation server PS, the proof of permutation is verified, as in the first embodiment, by the decryption server 20S that has the permutation verification part 30S connected to the bulletin board 400, and if any fault is detected in the input/output relation, the permutation server PS is regarded as being faulty. In such an instance, a different permutation server may be substituted for the faulty permutation server to perform its processing; alternatively, if only one permutation server is defective, its processing may be omitted. Having verified that all the permutations are correct, the decryption server 20S decrypts the outputs from the permutation network 10 (the outputs from the final-stage permutation server PSV) in the decryption part 21S, and at the same time, generates the decryption proof ProofD in the decryption proving part 22S and writes it in the bulletin board 400. The verification terminal 200 verifies the permutation proofs Proof1 to Proof4 written by the respective permutation servers into the bulletin board 400, and further verifies the results of decryption (messages m1, . . . , mN) and the decryption proof ProofD written by the decryption server 20S, following the same procedure as in the first embodiment. With the above construction, even in the case where the random elements are leaked from a certain permutation server due to an attack thereto and consequently the permutation therein is revealed to a third party, the input-output relationship of permutation by the overall system is kept secret as long as the random elements in the remaining permutation servers are concealed. For example, even if the input-output relationship of permutation by the permutation server PS1 is revealed, it is feasible to implement any input-output relationships of permutation since the permutation servers PS3 and PS4 constitute a perfect permutation network. Similarly, even if the input-output relationship of permutation chosen by any one of the permutation servers leaks, the other two permutation servers form a perfect permutation network, making it possible to conceal the random elements. Third Embodiment FIG. 16 illustrates in block form a third embodiment of the present invention, in which the decryption server 20S in the second embodiment is divided into two or more decryption servers 20S1, . . . , 20SL so that they perform in their entirety the same function as does a single decryption server. According to this embodiment, if at least t+1 decryption servers normally operate for t where t The system configuration of this embodiment is identical with that of the second embodiment except the decryption servers. Assume that the decryption servers Di each has stored therein a value xi obtained by secret sharing a decryption key x with a polynomial of degree t. That is, there is a degree-t (where t The permutation servers PS1, . . . , PSV are identical in construction and operation with those shown in FIG. 12 embodiment. Each decryption server 20St verifies the input-output relationships of all the permutation servers PS1, . . . , PSV in the same manner as in the second embodiment. Upon completion of verification of correct permutation results R1 to RN provided from the last-stage permutation server PSV, each decryption server performs decryption. The j-th decryption server 20Sj processes the permuted outputs R1 to RN as described below. Step 1: The control part receives inputs Ri one after another and provides them to the decryption part 21S (see FIG. 14). Furthermore, the control part inputs xi and p to the decryption part 21S from the memory 23S. Step 2: In the decryption part 21S (see FIG. 17), G′i and xj, p are input to the modular exponentiator 21SA to compute Kj,i:=G′ixj. After this, the decryption proving part 22S (see FIG. 14) is driven to generate a proof ProofDj that proves the correctness of decryption. The actual decryption proving operation is the same as in the case where x and y in the corresponding operation of the first embodiment are replaced with xj and yj, respectively. Let the output from the proving part 22S be represented by ProofDj:(cj, zj, Kj,1, . . . , Kj,n). The verification terminal 200 has the same configuration as that depicted in FIG. 2. In this case, however, the decryption verification part 40 is configured as shown in FIG. 18. The operations of the decryption verification part 40 are the same as those in Steps 2 to 4 of the decryption verification part in the first embodiment. When the outputs from t+1 or more decryption servers successfully pass the verifications, the verification terminal outputs OK. In this embodiment the output from the decryption server 20Sj is Kij and the following procedure is used to actually obtain each decryption result mi. The first step is to set A⊂{1, . . . , L} such that |A|≧t+1. In this case, however, the output from the decryption server 20Sj needs to have passed the verification for j where j∈A. Suppose that λj,A is an interpolation coefficient defined by ##EQU1## Then, the message mi is given by ##EQU2## for the following reasons. That is, since x=Σλj,Ax mod q (where Σ is for j∈A) holds, it follows that ##EQU3## Hence, the decryption operation in this embodiment is equivalent to the decryption operation in the first embodiment. The above steps of operation may be performed by each decryption server. In such an instance, the decryption verification needs only to be done following the same procedure as used in the first embodiment. Furth Embodiment In the second and third embodiments described above the permutation server PS in each stage randomizes input ciphertexts and randomly permutes them and sends such processed ciphertexts to the permutation server of the next stage, and the ciphertexts output from the permutation server in the last stage are decrypted by the decryption server into the original plaintexts. It is possible to verify that the thus obtained plaintexts are those cast correctly, though the owner of each plaintext is not identified. In the second and third embodiments, it may be considered to arrange such that each time a corrupt server is detected, a fault recovery processing is performed. Therefore, the recovery process would be performed at most t times. As the number of times for fault recovery increases, the throughput of the anonymous channel decreases. In the fourth embodiment described below, even if the reliability of the anonymous channel decreases to some extent, it is possible to efficiently perform fault recovery to provide the required throughput while maintaining the function of the verifiable anonymous channel. The first, second and third embodiments have been described to be adapted so that each switching gate SW or each permutation server does not perform decryption but that the decryption unit or decryption server collectively decrypts the ciphertexts. In this embodiment each permutation server is adapted to perform partial decryption. Each permutation server transforms the input ciphertext I in respective permutation stages and performs collective partial decryption in the last permutation stage, making the overall processing time shorter than in the case of performing partial decryption in every permutation stage. In this embodiment, let f represent the partial decryption process by each permutation server and fx(I) an output plaintext corresponding to an arbitrary input ciphertext I to the permutation server that has secret key X. The partial decryption process f by each permutation server is limited to the following. Commutable For arbitrary secret keys A and B, the relation fA(fB(I))=fB(fA(I)) holds. Collectively Processible For arbitrary known secret keys A and B there exists a function g(A, B) such that fA(fB(I))=fg(A, B)(I), making it possible to compute fg(A, B)(I) faster than fA(fB(I)). In the even that the output from a certain permutation server is regarded as faulty on such premises as mentioned above, only reliable information of a permutation server which is nearest to the unreliable permutation server upstream thereof and whose output has been declared to be correct is used to execute the random permutation/randomization/partial decryption process, which is followed by the nest step without making any compensation for the incorrect process. The secret key of each permutation server is verifiably secret-shared by all the other permutation servers in advance. Upon detection of an unreliable permutation server, the remaining permutation servers downstream thereof execute the random permutation/randomization/partial decryption process through utilization of the information of the reliable permutation server upstream of the dishonest permutation server, and upon completion of process by all the reliable permutation servers, the reliable servers collect all the shared secret keys of the unreliable permutation server and cooperate to restore them. The partial decryption process of that part of information that the unreliable permutation server ought to have execute (the recovery operation) is collectively performed using all the restored secret keys of the unreliable permutation server. With this collective processing scheme, it is feasible to perform the fault recovery by only one recovery operation even if outputs from two or more permutation servers are not reliable. This embodiment will be described below to use an El Gamal partial decryption system as an example of the commutable and collectively processible partial decryption process. As long as the above-mentioned properties are satisfied, a generalized El Gamal cryptosystem is also applicable (for example, an elliptic curve El Gamal cryptosystem). A description will be given of a system configuration with which it is possible to conceal the correspondence between inputs and outputs as a whole even if some permutation servers leak the random elements. In this embodiment the anonymous channel is formed by V permutation servers, each of which sequentially executes some proof-accompanying random permutation/randomization/partial decryption processes. FIG. 19 depicts an example of the system configuration of this embodiment, in which the permutation servers PS1 to PSV are connected to the bulletin board 400 as is the case with the embodiments of FIGS. 12 and 16. In this embodiment, since each permutation server is equipped with a verification function for processes of the other permutation servers and a partial decryption function for input ciphertexts, the verification servers and the decryption servers are not provided unlike the embodiments of FIGS. 12 and 16. Each permutation server has a decision part P60 for deciding whether the processes of the other permutation server are correct, and a verification part P70 for proving the random permutation/partial decryption process, in addition to a permutation part P50 corresponding to the permutation part formed by the plural switching gates SW in each permutation server in the second and third embodiment. The permutation servers PS1 to PS5 have their permutation parts P501 to P505 cascade-connected via the bulletin board 400 as shown in FIG. 19. The permutation parts P501 to P505 each have switching gates SW for the permutation/randomization/partial decryption process. No verification terminal 200 is provided independently, but it is placed in each permutation server. The flow of data between the permutation servers via the bulletin board 400 in the system of FIG. 19 is depicted in FIG. 20, in which there are shown only the permutation parts P501 to P505 in the permutation servers PS1 to PS5. In this example, the two cascade-connected permutation parts P501 and P502 form an eight-input perfect permutation network, the two cascade-connected permutation parts P503 and P504 also form an eight-input perfect permutation network, and the permutation part P505 singly forms an eight-input perfect permutation network. Accordingly, the five permutation parts constitute in their entirety three cascade-connected perfect permutation networks. In the formation of each eight-input perfect permutation network, it is not necessary that all two-input-two-output unit switching gates SW arranged in a 4 by 5 matrix form; even if input-output relationships are fixed in the switching gates indicated by broken lines, it is feasible to implement all sets of inputs by a combination of switching operations of the remaining switching gates. With a view to reducing the workload in the permutation server, no permutation of inputs is performed in such switching gates in which the input-output relationship can be fixed. Such fixed switching gates are indicated by SWF. However, in the case of decrypting ciphertexts through the permutation networks forming the anonymous channel of the present invention, if the number of times the partial decryption process is executed for input data differs according to its chosen route, the correct decryption cannot be achieved. In the present invention, the fixed switching gate SWF does not perform permutation of input data but executes other processes (such as randomization, partial decryption and proof generation) for the input data. In the following description, the switching gate SW that executes all processes such as permutation, randomization, partial decryption and proof generation will hereinafter be referred to as a PR partial decryptor with proof function, and the switching gate SWF that does not execute the permutation process will be referred to as a fixed partial decryptor with proof function. And permutation/randomization will be denoted simply by PR. In the FIG. 19 embodiment, the inputs to each permutation network are eight messages and five permutation servers PS1 to P55 are used; even if two permutation servers are faulty in their process, it is possible to achieve a correct permutation/randomization/partial decryption. The PR partial decryptor with proof function SW, which forms part of each of the permutation servers PS1 to PS5 has such a configuration as depicted in FIG. 21 or 28. The fixed partial decryptor with proof function SWF is configured as shown in FIG. 27. These partial decryptors will be described later on. The permutation servers PS1 to PS5 are each provided with the verifier P70. The verifier P70 comprises a PR proof verifier P70A, a partial decryption proof verifier P70B and a PR partial decryption proof verifier P70C. The bulletin board 400 accepts writes of ciphertexts from authorized users and has a function that information once posted thereon cannot be erased. The information written on the bulletin board 400 is made accessible from anyone. The illustrated system uses the five permutation servers PS1 to PS5 to form the anonymous channel 100 composed of three eight-input, cascade-connected perfect permutation networks 10A to 10C. Even if random elements of two of the three perfect permutation networks 10A to 10C leak out, it is possible to completely conceal the correspondence between the inputs and outputs by the remaining three perfect permutation networks. The permutation servers PS1 to PS5 process input data in a predetermined order, and each permutation server reads from the bulletin board 400 the input-output data and proof information of the permutation server of the immediately preceding stage. At this time, the permutation server verifies by the verifier P70 of its own the reliability of the preceding-stage permutation server through utilization of the input-output data and proof information thereof. If an incorrect input-output relationship is detected, that is, when the output is not reliable, the permutation server of the preceding stage is regarded as defective. In this instance, the other preceding permutation servers are checked in a retrograde order until an honest permutation server is found, and the output from the permutation server thus found honest is used to execute the required process. Each permutation server is capable of verifying the outputs of any other permutation servers used, and those permutation servers whose input-output relations are found correct cooperate to compensate for the decryption process that the faulty permutation server ought to have performed. To this end, the secret key of every permutation server is shared by all the permutation servers through a secret sharing scheme. As described previously, each permutation server performs tasks of plural PR partial decryptors with proof function one after another. The PR partial decryptor with proof function SW is made up of, for instance, a permuter/randomizer with proof function 120 and a partial decryptor with proof function 140 as shown in FIG. 21. The permuter/randomizer with proof function is composed of, for example, a permuter/randomizer 121 and a permutation/randomization (PR) proof generator 122. The partial decryptor with proof function 140 is formed by, for instance, two partial decryptors with proof function 141 and 142. FIG. 21 illustrates an example of the PR partial decryptor with proof function SW which permutes and randomizes two input El Gamal ciphertexts, partially decrypts the ciphertexts through the use of the partial secret key, and outputs the results of the permutation/randomization/decryption process and a proof that provies its correctness. The PR partial decryptor with proof function SW is used in the verifiable anonymous channel with collective fault recovery function depicted in FIG. 20. The PR partial decryptor with proof function SW performs operations as described below; in this case, simultaneously executable steps may be performed in parallel. And commutable steps may be exchanged in order of execution. Further, a plurality of operations by plural devices of the same function may be sequentially conducted by one device while changing parameters one after another as required. Step 1: The permuter/randomizer with proof function 120 uses various pieces of information in random information to permute and randomize inputs (M0, G0), (M1, G1) and outputs the results of the process (M0+, G0+), (M1+, G1+) together with proof information 0 that proves their validity. Step 2: The PR partial decryptor with proof function SW outputs (M0+, G0+), (M1+, G1+) as part of the proof information. Step 3: The fixed partial decryptor with proof function 140 outputs (M′0, G′0), (M′1, G′1) resulting from partial decryption of the inputs (M0+, G0+), (M1+, G1+) through the use of various pieces of information in the random information and proof information 1 which proves the validity of the outputs. Incidentally, the permutation, randomization and partial decryption processes in the PR partial decryptor with proof function SW can be executed in an arbitrary order. In such a case, however, the contents of proof information differ with the order of execution of the processes. The permuter/randomizer 121 comprises, for instance, a permuter 121A and two randomizers 121B and 121B as depicted in FIG. 22. The randomizers 121B and 121C are identical in construction and they each have two multipliers 121B1 and 121B2 as depicted in FIG. 23. The functional configurations of these parts will be described below one after another. Randomizer 121B (121C) FIG. 23 depicts an example of the configuration of the randomizer 121B (121C) which is used to randomize the input El Gamal ciphertexts so as to conceal the correspondence between the input and outputs in the permuter/randomizer 121 shown in FIG. 22. Letting (M, G) represent the input El Gamal ciphertexts, the following equation holds for a plaintext m, a public key (Y, g), a secret key X and a random number w. Y=gx, G=gw, M=mYw The randomization of the input ciphertexts (M, G) is to compute M′ and G′ by the multipliers 121B1 and 121B2 as shown below and output (M′, G′). M′←M×Y-r, G′←G×g-r where g-r and Y-r are parameters computed prior to the input of M and G through the use of a random number r kept secret from third parties other than a person in charge of the randomization process. Sine the output (M′, G′) satisfies M′=mYw-r, G′=gw-r, it is an El Gamal ciphertext related to the plaintext m, the public key (Y, g), the secret key X and the random number w-r. The randomizer 121B performs the above operations. When the operations are simultaneously executable, they may be performed in parallel. The order of operations may be changed, if possible. Furthermore, the same operations performed by different devices may be performed by one device while changing parameters as required. Permuter/Randomizer 121 FIG. 22 illustrates an example of the configuration of the permuter/randomizer 121 which permutes and randomizes the two input El Gamal ciphertexts (M0, G0) and (M1, G1). Let D(M, G, r) describe an El Gamal ciphertext obtained by randomizing the El Gamal ciphertext (M, G) with the random number r. The permuter/randomizer 121 generates the following output messages (M′0, G′0) and (M′1, G′1) following a permutation parameter B∈{0,1} held secret from third parties other than a person in charge of the PR process. When B=0: (M′0, G′0)←D(M0, G0, r0) (M′1, G′1)←D(M1, G1, r1) When B=1: (M′0, G′0)←D(M1, G1, r0) (M′1, G′1)←D(M0, G0, r1) The permuter/randomizer 121 is made up of a permuter 121A and randomizers 121B and 121C. The randomizers 121B and 121C each comprise the two multipliers 121B1 and 121B2 as depicted in FIG. 23. The permuter/randomizer 121 performs the following operations. When the operations are simultaneously executable, they may be performed in parallel. The order of operations may be changed, if possible. Furthermore, plural operations by plural devices of the same function may be performed by one device while changing parameters as required. Step 1: If B=0, the permuter 121A yields (L0, L1)←(M0, G0) (L2, L3)←(M1, G1) and if B=1, (L0, L1)←(M1, G1) (L2, L3)←(M0, G0) Step 2: The randomizer 121B randomizes the inputs (L0, L1) with randomization parameters (Y-r0, gr0) and outputs (M′0, G′0). Step 3: The randomizer 121C randomizes the inputs (L2, L3) with randomization parameters (Y-r1, g-r1) and outputs (M′1, G′1). That is, the outputs are randomized so as to conceal the correspondence B=i⊕j between Gi and Gj, where i,j∈{0, 1}. Accordingly, it is necessary that the values Y-r0, g-r0 and Y-r1 as well as the values r0 and r1 be kept secret. While in FIG. 22 the permutation precedes the randomization, the latter may precedes the former. Permutation/Randomization (PR) Proof Generator 122 The PR proof generator 122 in FIG. 21 proves the correctness of operation of the permuter/randomizer 121 without revealing the secret information (B∈{0, 1} and the value of the parameters for randomization). To execute this proof, it is necessary to prove that, provided b=i⊕j, logY(Mi/M′j)=logg(Gi/G′j) for all i,j∈{0, 1} such that b=0, or for all i,j∈{0, 1} such that b=1. To perform this, the PR proof generator 122 computes and outputs the proof information Tij, Wij, zij, eb described below. An input B is a permutation parameter input to the permuter 121A in the permuter/randomizer 121. An input rj (j∈{0, 1}) is a randomization parameter input to the randomizers 121B and 121C in the permuter/randomizer 121. Inputs e, Rij (i, j∈{0, 1}) are random numbers for proof. Inputs YRij, gRij (i, j∈{0, 1}) are parameters for proof computed prior to the application of the inputs Mi, Gi, M′j, G′j (i, j∈{0, 1}). These pieces of information (B, rj, e, Rij, Yrij, gRij) will hereinafter be referred to as random information RDM. The outputs eb, Tij, Wij, zij (b, i, j∈{0, 1}) are information that proves the correspondence between (Mi, Gi) and (M′j, G′j), where b=i⊕j, or proves such correspondence as if it actually exists. The PR proof generator 122 performs operations as described below. That is, for i,j∈{0, 1}, when i⊕j=B, Tij←YRij, Wij←gRij when i⊕j=B′ (where B′ represents an inversion of B), Tij←(Mi/M′j)eYRij, Wij←(Gi/G′j)egRij when B=0, e0←-e+h(T00, T01, T11, W00, W01, W10, W11) e1←e and when B=1, e0←-e+h(T00, T01, T11, W00, W01, W10, W11) e1←e For arbitrary i, j∈{0, 1}, when i⊕j=B, zij←Rij←eBrj and when i⊕j=B′, zij←Rij By the above operation the prover (the PR proof generator 121) outputs proof information VRF={eb, Tij, Wij, zij}. In the above, when the operations are simultaneously executable, they may be performed in parallel. The order of operations may be changed, if possible. Furthermore, the same operations performed by different devices may be performed by one device while changing parameters as required. PR Proof Verifier P70A The PR proof verifier P70A in the verifier P70 placed in each permutation server shown in FIG. 19 verifies the output from the PR proof generator 122, that is, the proof information VRF={eb, Tij, Wij, zij} so as to verify the correctness of the operation of the permuter/randomizer 121. The inputs eb, Tij, Wij, zij (b, i, j∈{0, 1}) are outputs from the PR proof generator 122 and are information that proves the correspondence between (Mi, Gi) and (M′j, G′j), where b=i⊕j, or proves such correspondence as if it actually exists. The verifier P70A is supplied with M0, G0, M1, G1, M′0, G′0, M′1, G′1 as well as Tij, Wij, zij, eb and determine whether the following equation holds e0+e1=h(T00, T01, T10, T11, W00, W01, W10, W11). If not, the verifier P70A outputs False and finishes its operation. The function h is a one-way function. After this, provided b=i⊕j for all i, j∈{0, 1}, the verifier P70A makes a check to determine if the following equations hold Tij=(Mi/M′j)ebYzij and Wij=(Gi/G′j)ebgzij. If any of them does not hold, then the verifier P70A outputs False and finishes its operation. If the both equations hold, it outputs True. Even if an dishonest prover tries to compute and output Tij←(Mi/M′j)ebYzij, Wij←(Gi/G′j)ebgzij Using eb, zij prepared by some means, it is difficult to precompute either one of e0 and e1 due to unpredictability of the function h(x0, x1, . . . )-this constitutes proof of Lemma 1. The output from the verifier P70A is an estimation as to whether the permuter/randomizer 121 correctly operated, and it is a truth value. The PR proof verifier P70A performs the operations as described above. In the above, when the operations are simultaneously executable, they may be performed in parallel. The order of operations may be changed, if possible. Furthermore, plural operations by plural devices of the same function may be performed by one device while changing parameters as required. Permuter/Randomizer with Proof Function 120 The permuter/randomizer with proof function 120 outputs, without revealing secret information, (M′0, G′0), (M′1, G′1) resulting from permutation and randomization of two input El Gamal ciphertexts (M0, G0), (M1, G1) and proof proving the correctness of the process (zero-knowledge proof. The permuter/randomizer with proof function 120 comprises the permuter 121 and the PR proof generator 122. The permuter/randomizer with proof function 120 performs operations as described below. In this instance, when the operations are simultaneously executable, they may be performed in parallel. The order of operations may be changed, if possible. Furthermore, plural operations by plural devices of the same function may be performed by one device while changing parameters as required. Step 1: The permuter/randomizer 121 permutes and randomizes the inputs (M0, G0), (M1, G1) with the input B and randomization parameters g-r0, Y-ro, g-r1, Y-r1 and outputs (M′0, G′0), (M′1, G′1). Step 2: The PR proof generator 122 generates and outputs the proof information VRF={eb, Tij, Wij, zij} through utilization of the inputs (M0, G0), (M1, G1) and the outputs (M′0, G′0), (M′1, G′1) and the random information RDM={B, rj, e, Rij, YRij, grij}. Partial Decryptor with Proof Function 141 Turning to FIGS. 24, 25 and 26, the partial decryptors 141 and 142 shown in FIG. 21 will be described below. The partial decryptor with proof function 141 is composed of a partial decryptor 141A and a partial decryption proof generator 141B, which are shown in more detail in FIGS. 25 and 26. The partial decryptor with proof function 142 is identical in construction with the partial decryptor 141, and hence no description will be repeated. FIG. 25 illustrates an example of the configuration of the partial decryptor 141A that partially decrypts the El Gamal ciphertexts, using partial information of a secret key. Letting the input El Gamal ciphertexts be represented by (M, G), the following holds M=mYw, G=gw for the plaintext m and the public keys (Y, g) and the random number w. Suppose that the partial decryptor knows the values of partial information x on the secret keys Y=yxy′ and y=gx. The partialdecryptor computes M′←M×G-x for the inputs (M, G) and outputs (M′, G′). Since the outputs satisfy M′=my′w, G=gw, they constitute El Gamal ciphertexts concerning the plaintext m and the public keys (y′, g) and the random number w. The partial decryptor 141A is composed of a modular exponentiation multiplier 141A1 and a multiplier 141A2. This device performs operations as described below. In this instance, when the operations are simultaneously executable, they may be performed in parallel. The order of operations may be changed, if possible. Furthermore, the same operations performed by different devices may be performed by one device while changing parameters as required, Step 1: The modular exponentiation multiplier 141A1 compute L0←G-x with the inputs -x and G, and outputs L0. Step 2: The multiplier 141A2 computes M′←M×L0 with the inputs M and L0, and outputs M′. Step 3: The partial decryptor 141A outputs the input G intact. Partial Decryption Proof Generator 141B FIG. 26 illustrates an example of the configuration of the partial decryption proof generator 141B that proves, without revealing secret information, the correctness of the operation of the partial decryptor 141A. To generate this proof, the partial decryption proof generator 141B proves in zero-knowledge that: without revealing the value of the secret key x such that y=gx. The proof proves by a Chaum-Pederson protocol that two discrete logarithms logg y and logG (M/M′) are equal. The input R is a random number kept secret from other persons except the prover, and gR is a value computed before the application of the input G. The partial decryption proof generator 141B comprises a modular exponentiation multiplier 141B1, a hash calculator 141B2, a register 141B3, a multiplier 141B4 and a subtractor 141B5. The hash calculator 141B2 is to calculate the one-way hash function h, and let it be assumed that specifications of the hash functions are made public. The hash calculator 141B2 performs operations as described below. In this instance, when the operations are simultaneously executable, they may be performed in parallel. The order of operations may be changed, if possible. Furthermore, the same operations performed by different devices may be performed by one device while changing parameters as required. Step 1: The modular exponentiation multiplier 141B1 uses the inputs R and G to compute T←GR and outputs T. Step 2: The hash calculator 141B2 calculates e←h(T, V) with the input T and V=gR stored in the register 141B3, and outputs e. Step 3: The multiplier 141B4 uses the inputs e and x to compute L0←e×x, and outputs Lo. Step 4: The subtractor 141B5 uses the input R and L0 to copute s←R-L0, and outputs s. Step 5: The partial decryption proof generator 141B outputs T, V, e, s as the proof information VRF to the partial decryption proof verifier P70B in FIG. 19. Partial Decryption Proof Verifier P70B The partial decryption proof verifier P70B, which verifies the output from the partial decryption proof generator 141B (142B), is to verifies the correctness of the operation of the partial decryptor 141A (142A). This device decides whether "the partial decryptor 141A knows the value x and M/M′=Gx holds (Lemma 2)" and outputs the result of decision. The partial decryption proof verifier P70B follows the Chaum-Pdersen protocol to verify the output from the partial decryptor 141B depicted in FIG. 26. Let h be a one-way hash function whose specifications have been made public. g and y are already published as referred to previously. This device performs operations as described below. In this instance, when the operations are simultaneously executable, they may be performed in parallel. The order of operations may be changed, if possible. Furthermore, the same operations performed by different devices may be performed by one device while changing parameters as required. Step 1: If the following does not hold for the inputs m, M′, G, e, s, e=h(T, V), the partial decryption proof verifier P70B (FIG. 19) outputs False and finishes its operation. Step 2: If the following does not hold for the inputs m, M′, G, e, s, T=(M/M′)eGs, the partial decryption proof verifier P70B outputs False and finishes its operation. This can be understood from the fact that when substituting the relations M′=MG-x, s=R-ex, the equality holds if they are correct. Step 3: If V=yegs does not hold for the inputs V, e, s, the partial decryption proof verifier P70B outputs False and finishes its operation. This is understood from the relations V=gR, y=gx and s=R-ex. Step 4: If all the verifications hold, the partial decryption proof verifier P70B outputs True and finishes its operation. The above is the function configuration of each PR partial decryptor with roof function SW which serves as a switching gate in each perfect permutation network depicted in FIG. 20 and the associated verifier P70B. Next, a description will be given of the fixed partial decryptor with proof function SWF in the perfect permutation network shown in FIG. 20. Fixed Partial Decryptor with Proof Function SWF FIG. 27 illustrates an example of the configuration of the fixed partial decryptor with proof function SWF which performs partial decryption of two input El Gamal ciphertexts by using a partial secret key, and outputs the results of decryption together with proofs of their validity. The fixed partial decryptor SWF is used to perform the fixed permutation and partial decryption in the permutation network of FIG. 20 as described previously. The fixed partial decryptor SWF comprises partial decryptors with proof function 141F and 142F as depicted in FIG. 27, which are identical construction with the partial decryptor with proof function shown in FIG. 24. The fixed partial decryptor with proof function SWF performs operations as described below. In this instance, when the operations are simultaneously executable, they may be performed in parallel. The order of operations may be changed, if possible. Furthermore, plural operations by plural devices of the same function may be performed by one device while changing parameters as required. Step 1: The partial decryptor 141F performs partial decryption of (M0, G0) with the inputs -x and (M0, G0) and the random information 0, and outputs the result (M′0, G′0) of the partial decryption and proof information 0 proving its validity. Step 2: The partial decryptor 142F performs partial decryption of (M1, G1) with the inputs -x and (M0, G0) and the random information 1, and outputs the result (M′1, G′1) of the partial decryption and proof information 1 proving its validity. PR Partial Decryptor with Proof Function SW FIG. 28 illustrates a modified form of the PR partial decryptor with proof function SW shown in FIG. 21. As described previously, the partial decryptor with proof function SW performs the permutation/randomization/partial decryption of the two input El Gamal ciphertexts (M0, G0) and (M1, G1), and outputs (M′0, G′0) and (M′1, G′1) together with their validity proofs without revealing the secret information. In the example of FIG. 21 the proof for the permutation/randomization process and the proof for the partial decryption are generated separately, whereas in the example of FIG. 28 the results of the permutation/randomization and the partial decryption process are proved at the same time. The PR partial decryptor with proof function SW is composed of a PR partial decryptor 124 and a PR partial decryption proof generator 125. The PR partial decryptor 124 is formed by a permuter/randomizer 124A and two partial decryptors 124B and 124C. The PR partial decryptor SW performs operations as described below. In this instance, when the operations are simultaneously executable, they may be performed in parallel. The order of operations may be changed, if possible. Furthermore, plural operations by plural devices of the same function may be performed by one device while changing parameters as required. Step 1: The PR partial decryptor 124 performs the permutation/randomization/partial decryption of he inputs (M0, G0) and (M1, G1) with the inputs B, the randomization parameters and partial information of he secret key, and outputs (M′0, G′0) and (M′1, G′1). Step 2: The PR partial decryption proof generator 125 outputs proof information through utilization of the inputs (M0, G0), (M1, G1) and (M′0, G′0), (M′1, G′1) and random information. In the PR partial decryptor with proof function SW, too, the permutation, randomization and partial decryption processes can be executed in an arbitrary order. The permuter/randomizer 124A in FIG. 28 is identical in construction with the permuter/randomizer 121 depicted in FIG. 22, and the partial decryptors 124B and 124C also have the same configuration as that of the partial decryptor 141A (141B) depicted in FIG. 25. The PR partial decryptor 124 performs operations as described below. In this instance, when the operations are simultaneously executable, they may be performed in parallel. The order of operations may be changed, if possible. Furthermore, plural operations by plural devices of the same function may be performed by one device while changing parameters as required. Step 1: The permuter/randomizer 124A outputs two pairs of information representing the results of the permutation/randomization process of the inputs (M0, G0) and (M1, G1) through the use of permutation/randomization parameters B, g-r0, Y-r0, g-r1 and Y-r1. Step 2: The partial decryptor 124B partially decrypts the one of the two pair of information on the permutation/randomization process through the use of the partial information -x of the secret key, and outputs (M′0, G′0). Step 3: The partial decryptor 124C partially decrypts the other pair of information on the permutation/randomization process through the use of the partial information -x of the secret key, and outputs (M′1, G′1). PR Partial Decryption Proof Generator 125 The PR partial decryption proof generator 125 proves the correct operation of the PR partial decryptor 124A without revealing secret information. The input B is a permutation parameter input to the permuter (see FIG. 22) in the permuter/randomizer 124A; the input rj (j∈{0, 1}) is a random number for randomization input to the randomizer (see FIG. 22) in the permuter/randomizer 124A; the input x is partial information of a decryption key; the inputs e, K0, K1 and Rij (i, j∈{0, 1}) are random numbers for proof information generation use; and the inputs gK0, gK1+ex, y′Rij, and gRij (i, j∈{0, 1}) are parameters for proof information generation use computed prior to the application of the inputs Mi, Gi, M′j and G′j (i, j∈{0, 1}). The outputs Vb, eb, sb, Tij, Wij and zij (b, i, j∈{0, 1}) are information are information that proves the correspondence between (Mi, Gi) and (M′j, G′j), where b=i⊕j, or proves such correspondence as if it actually exists. To directly prove the correctness of the operation of the PR partial decryptor 124, it is necessary to prove that, provided b=i⊕j, To perform this, proof information Vb, eb, sb (b∈{0, 1}) and Tij, Wij, Zij (i, j∈{0, 1}) are generated as described below. The PR partial decryption proof generator 125 computes: for all i, j∈{0, 1}, when i⊕j=B, Tij←y′RijGiK0, Wij←gRij; and when i⊕j=B′ (where B′ represents an inversion of B), Tij←(Mi/M′j)ey′RijGjK1, Wij←(Gi/G′j)egRij. Furthermore, the PR partial decryption proof generator 124: performs substitutions VB←gK0, and VB′←gRij, and computes e0←-e+h(T00, T01, T10, T11, W00, W01, W10, W11) when B=0; performs a substitution e1←e, and computes e1←-e+h(T00, T01, T10, T11, W00, W01, W10, W11) when B=1; performs a substitution e0←e, and computes zij←Rij-ebrj when i⊕j=B; if i⊕j=B′, performs substitution zij←Ri and computes s0←K0-e0x when B=0; and performs a substitution s1←K1 and, when B=1, computes s1←K0-e1x, thereby s0←K1. The PR partial decryption proof generator 125 performs operations as described above. In this instance, when the operations are simultaneously executable, they may be performed in parallel. The order of operations may be changed, if possible. Furthermore, plural operations by plural devices of the same function may be performed by one device while changing parameters as required. PR Partial Decryption Proof Verifier P70C The PR partial decryption proof verifier P70C in FIG. 19 is to verifies the correct operation of the PR partial decryptor 124 by checking the output from the PR partial decryptor proof generator 125 in FIG. 28. The inputs to the PR partial decryption proof verifier P70C are eb, Tij, Wij and zij (b, i, j∈{0, 1}), which are the outputs from the PR partial decryption proof generator 125 in FIG. 28 and are information that proves the correspondence between (Mi, Gi) and (M′j, G′j), where b=i⊕j, or proves such a correspondence as if it actually exists. The verifier P70C first makes a check, by computation, to see if e0+e1=h(T00, T01, T10, T11, W00, W01, W10, W11) holds, and if not, it outputs False and finishes its operation. If the above holds, the verifier P70C makes a check, by computation, to see if Vb=gsbysb holds for all b∈{0, 1}, and if not, it outputs False and finishes its operation. If the above holds, the verifier P70C makes a check, by computation, to determine if Tij=(Mi/M′j)eby′zijGisb, Wij=(Gi/G′j)ebgzij holds for all i, j∈{0, 1} with b=i⊕j, and if not, outputs False and finishes its operation. If the above holds, the verifier P70C outputs True. In this way, it is decided whether Lemma 3 is true or false. The verifier P70C performs operations as described above. In this instance, when the operations are simultaneously executable, they may be performed in parallel. The order of operations may be changed, if possible. Furthermore, plural operations by plural devices of the same function may be performed by one device while changing parameters as required. Perfect Permutation Network 10 FIGS. 29A and 29B illustrates examples of configurations of four- and eight-input perfect permutation networks 10A and 10B, respectively. What is meant by the "perfect permutation network" is a network which is formed by plural PR partial decryptors with proof function SW and fixed partial decryptors with proof function SWF are arranged in a matrix form and connected in cascade and which is able to implement every permutation of inputs by a combination of values of secret permutation parameters Bi of the PR partial decryptors with proof function SW. The inputs are N El Gamal ciphertexts and the outputs are N El Gamal ciphertexts or N plaintexts. And information that proves the validity of permutation is proof information of each PR partial decryptor with proof function and each fixed partial decryptor with proof function and input/output information except secret keys, permutation/randomization parameters and random information. In FIG. 29A PR partial decryptors with proof function SW and fixed partial decryptors with proof function SWF, each of which receives two input El Gamal ciphertexts and outputs two El Gamal ciphertexts, are arranged in a two-by-three matrix form. The one output from the partial decryptor on each row is supplied to the partial decryptor on the same row in the next column, whereas the other output is input to the partial decryptor in the next column on a different row. Indicated by the solid line blocks in FIG. 29A are the PR partial decryptors SW, each of which permutes and randomizes the two El Gamal ciphertexts and partially decrypts them through the use of partial information of secret keys, thereafter outputting the results of permutation/randomization process together with proof information proving their validity. Indicated by the broken-line block is the fixed partial decryptor SWF, which partially decrypts the two input El Gamal ciphertexts through the use of partial information of secret keys, and outputs the results of decryption together with proof information proving their validity. In this instance, the number of possible permutations of four inputs is 4!=4×3×2=24. When the number of permutation parameters Bi is 5, the four inputs can be permuted in 25=32 ways; thus, the network can be set for any of all possible permutations of four inputs. That is, in the case of four inputs, a perfect permutation network can be formed using five PR partial decryptors with proof function, i.e. five processors in which the permutation parameters Bi can be set, respectively. On the other hand, the fixed partial decryptor with proof function is appreciably simpler in configuration than the PR partial decryptor with proof function, that is, is computation complexity is small; hence, it is used as the processor on the first row in the third column. It may also be substituted with the PR partial decryptor with proof function. In FIG. 29B PR partial decryptors SW and fixed partial decryptors are arranged in a four-by-five matrix form. In the middle three columns the one output from the partial decryptor on each row is supplied to the partial decryptor on the same row in the next column, whereas the other output is input to the partial decryptor in the next column on a different row. The illustrated configuration is a combination of two four-input four-output perfect permutation networks of FIG. 29A as indicated by the broken lines in FIG. 29B. If the value of the secret permutation parameter Bi in the i-th column is unknown, it is impossible to estimate what permutation was performed. That is, when the combination of the values Bi is unknown, it is impossible to find out the person who input M′0, . . . , M′3. To ensure correct decryption, each partial decryptors in the same column (the i-th column) have the same decryption key xi in both of FIGS. 29A and 29B. Perfect Permutation Network 10C FIG. 30 illustrates an example of the configuration of a 2N-input perfect permutation network 10C. The principle of this network is described in A. Waksman, "A permutation network," Journal of the ACM, 15(1): 159-163, 1968. Since the permutation network 10C comprises N-input perfect permutation networks 10C1 and 10C2 and two-input perfect permutation networks (PR partial decryptors with proof function) SW, it is feasible to form a four-, eight-, . . . , 2n-input perfect permutation networks by two-input perfect permutation networks. The illustrated example comprises two N-input perfect permutation networks, N two-input two-output PR partial decryptors with proof function provided at the input stage, and (N-1) two-input two-output PR partial decryptors with proof function SW and one fixed partial decryptor with proof function SWF provided at the output stage. The configuration of FIG. 29B uses a four-input perfect permutation network that is the N-input perfect permutation network of FIG. 30. Accordingly, a 2n-input perfect permutation network which possesses the partial decryption function can be constituted using only PR partial decryptors with proof function and fixed partial decryptors with proof function. The parts necessary for the N(=2n)-input perfect permutation network are N log2N-N+1 PR partial decryptors with proof function and (N-1) fixed partial decryptors with proof function, and the total number of stages (the number of columns) is 2N log2 N-1. Verifiable Anonymous Channel with Collective Fault Recovery Function 100 FIG. 20 depicts an example of an 8-input, 2-secret leakage tolerance, 2-fault tolerance, verifiable anonymous channel with collective fault recovery function. The verifiable anonymous channel with collective fault recovery function 100 is formed by a cascade-connection of permutation servers PS1 to PS5. The t-secret leakage tolerance means that the correspondence between inputs and outputs is completely concealed even if secret permutation information Bi of a maximum of t permutation servers among a total of V(>2t) permutation servers leaks out due to an attack or the like. The verifiable anonymous channel with collective fault recovery function 100 includes three perfect permutation networks 10A, 10B and 10C, and does not have any permutation servers spanning the perfect permutation networks. Hence, even if the secret permutation information Bi leaks out from two permutation servers, there exists at least one perfect permutation network which does not include the two permutation servers and secret information of this perfect permutation network is entirely concealed; therefore, this perfect permutation network conceals the correspondence between its inputs and outputs, and consequently, conceals the correspondence between inputs and outputs of the anonymous channel 100 as well. Accordingly, the verifiable anonymous channel 100 with collective fault recovery function has 2-secret leakage tolerance since the anonymous channel shown in FIG. 20 is made up of the five permutation servers PS1 to PS5. Generally, in the case where the verifiable anonymous channel 100 with collective fault recovery function has a network formed by a series connection of t+1 perfect permutation networks and the network is divided into V and the divided parts are formed by permutation servers, if the network is divided such that any permutation server does not span two perfect permutation networks, the verifiable anonymous channel with collective fault recovery function has t-secret leakage tolerance. The t-fault tolerance mans a verifiable anonymous channel with collective fault recovery function which is allowed by fault recovery to ultimately provide correct outputs even if a maximum of t permutation servers among a total of V (>2t) permutation servers are not correct in operation. Every permutation server has its secret key shared by the other permutation servers through a verifiable secret sharing scheme so that the key can be restored if t+1 or more permutation servers agree to do so. For example, let a 0-degree coefficient be a secret key xi to be concealed and assume that a value xij=fi(j) of a t-degree polynomial fi(z) related to z, for which other coefficients are determined by secret random numbers, is distributed or assigned to a j-th permutation server. If t+1 or more values xij and the corresponding permutation servers j gather for one i, the secret key can be restored as xi=fi(0) by using the following Lagrange interpolation formula concerning a set J of t+1 or more arbitrary and different j among them. ##EQU4 | ||||||