Mixnet system
Claim Score by NHIP
Abstract
Each participant apparatus (103) encrypts a plaintext by using a secret key of secret key cryptography, encrypts the encryption key by a public key, and sends the plaintext and public key to a substitution/decryption apparatus (112). With this processing, the limitation on the length of a ciphertext to be processed can be eliminated. In this invention, a verifiable proof text using a public key by each substitution/decryption apparatus is verified by a verification apparatus (109) by using the public key. If one of a plurality of organizations to decrypt and shuffle ciphertexts has not correctly executed the operation, a third party can specify it and prove that the specified organization is unauthorized.
Term
0.4 yearsto projected expiry
Projected expiry 7 February 2027, counted from filing; an application has no term until it is granted.
- Priority
- Filed
- Published
- Today
- Projected expiry
19 claims: 5 independent, 14 dependent
- 1Broadest claimClaim Score 44, average(NHIP)A participant apparatus characterized by comprising:key encryption means for encrypting one of a plurality of secret keys of secret key cryptography by one public key of a plurality of substitution/decryption apparatuses;data encryption means for encrypting given data by one of the plurality of secret keys of the secret key cryptography;hash value encryption means for calculating a hash value of the given data by using a cryptographic hash function and encrypting the hash value by one public key of the plurality of substitution/decryption apparatuses;repeat means for repeating processing of inputting a plaintext as a first input to said data encryption means and inputting, as subsequent inputs to said data encryption means, preceding outputs from said data encryption means, said key encryption means, and said hash value encryption means a number of times equal to the number of substitution/decryption apparatuses;and output means for outputting data obtained by processing of said repeat means.
- 7A substitution/decryption apparatus characterized by comprising:data division means for divding each element of an input data sequence into a secret key of secret key cryptography, which is encrypted by public key cryptography, data encrypted by secret key cryptography, and a hash value encrypted by public key cryptography;secret key decryption means for decrypting the encrypted secret key of the secret key cryptography by a private key of the public key cryptography;data decryption means for decrypting the encrypted data by using the decrypted secret key to generate output data;hash value decryption means for outputting a value obtained by decrypting the encrypted hash value by the private key of the public key cryptography;hash value verification means for comparing the decrypted hash value with a hash value of the generated output data, if the values coincide, outputting hash value acceptance, and if the values do not coincide, outputting hash value unacceptance;output data sequence generation means for generating a data sequence which contains, as sequence elements, only the output data for which acceptance is output from said hash value verification means and which are corresponding in a sense of being generated from the same element data of the input data sequence, and uniformly shuffling the elements at random to form an output data sequence;hash value decryption authenticity proof means for generating a hash value decryption authenticity proof text as a proof text which proves that the hash value of each element of the output data sequence is always a value obtained by decrypting the encrypted hash value contained in a certain element of the input data sequence, and the hash values are in a one-to-one correspondence;hash value unacceptance authenticity proof means for generating a hash value unacceptance authenticity proof text as a proof text which proves, when said hash value verification means outputs unacceptance, that the output of unacceptance is authentic;and output means for creating an authenticity proof text from the hash value decryption authenticity proof text and the hash value unacceptance authenticity proof text and outputting the authenticity proof text and the output data sequence output from said output data sequence generation means.
- 11A verification apparatus characterized by comprising:hash value decryption authenticity verification means for verifying that a decrypted hash value contained in a hash value decryption authenticity proof text coincides with a hash value obtained by decrypting an encrypted hash value of a certain element of an input data sequence, and the hash values are in a one-to-one correspondence, if the hash values coincide and are in the one-to-one correspondence, outputting acceptance, and if the hash values are not in the one-to-one correspondence, outputting unacceptance;hash value coincidence verification means for, when the decrypted hash value coincides with a hash value of each element of an output data sequence, outputting acceptance, and if the hash values do not coincide, outputting unacceptance;hash value unacceptance authenticity verification means for verifying a hash value unacceptance authenticity proof text as a proof text which proves that for an element of the elements of the input data sequence, which corresponds to a hash value for which said hash value coincidence verification means outputs unacceptance, the output of unacceptance is authentic, if the proof text is authentic, outputting acceptance, and if the proof text is unauthentic, outputting unacceptance;and authenticity determination means for outputting acceptance, for the element of the input data sequence, if said hash value decryption authenticity verification means outputs acceptance while said hash value coincidence verification means outputs acceptance, or if said hash value coincidence verification means outputs unacceptance while said hash value unacceptance authenticity verification means outputs acceptance, and if the output data sequence contains only data corresponding to the elements accepted by said hash value coincidence verification means and all the data, and otherwise, outputting unacceptance.
- 15A mix net system characterized by comprising a plurality of participant apparatuses, a consolidating apparatus, a plurality of substitution/decryption apparatuses, and a verification apparatus, each of said participant apparatuses comprising:key encryption means for encrypting one of a plurality of secret keys of secret key cryptography by one public key of said plurality of substitution/decryption apparatuses;data encryption means for encrypting given data by one of the plurality of secret keys of the secret key cryptography;hash value encryption means for calculating a hash value of the given data by using a cryptographic hash function and encrypting the hash value by one public key of said plurality of substitution/decryption apparatuses;repeat means for repeating processing of inputting a plaintext as a first input to said data encryption means and inputting, as subsequent inputs to said data encryption means, preceding outputs from said data encryption means, said key encryption means, and said hash value encryption means a number of times equal to the number of substitution/decryption apparatuses;and output means for outputting data obtained by processing of said repeat means to said consolidating apparatus, said consolidating apparatus receiving a plurality of data from said plurality of participant apparatuses, verifying authenticity of each of the data, and outputting only data which is determined as authentic to one of said substitution/decryption apparatuses, each of said substitution/decryption apparatuses comprising: data division means for diving each element of an input data sequence input for one of said consolidating apparatus and said substitution/decryption apparatuses into a secret key of secret key cryptography, which is encrypted by public key cryptography, data encrypted by secret key cryptography, and a hash value encrypted by public key cryptography;secret key decryption means for decrypting the encrypted secret key of the secret key cryptography by a private key of the public key cryptography;data decryption means for decrypting the encrypted data by using the decrypted secret key to generate output data;hash value decryption means for outputting a value obtained by decrypting the encrypted hash value by the private key of the public key cryptography;hash value verification means for comparing the decrypted hash value with a hash value of the generated output data, if the values coincide, outputting hash value acceptance, and if the values do not coincide, outputting hash value unacceptance;output data sequence generation means for generating a data sequence which contains, as sequence elements, only the output data for which acceptance is output from said hash value verification means and which are corresponding in a sense of being generated from the same element data of the input data sequence, and uniformly shuffling the elements at random to form an output data sequence;hash value decryption authenticity proof means for generating a hash value decryption authenticity proof text as a proof text which proves that the hash value of each element of the output data sequence is always a value obtained by decrypting the encrypted hash value contained in a certain element of the input data sequence, and the hash values are in a one-to-one correspondence;hash value unacceptance authenticity proof means for generating a hash value unacceptance authenticity proof text as a proof text which proves, when said hash value verification means outputs unacceptance, that the output of unacceptance is authentic;and output means for creating an authenticity proof text from the hash value decryption authenticity proof text and the hash value unacceptance authenticity proof text and outputting the authenticity proof text and the output data sequence output from said output data sequence generation means, and said verification apparatus comprising: hash value decryption authenticity verification means for verifying that a decrypted hash value contained in the hash value decryption authenticity proof text coincides with a hash value obtained by decrypting an encrypted hash value of a certain element of the input data sequence of said substitution/decryption apparatus, and the hash values are in a one-to-one correspondence, if the hash values coincide and are in the one-to-one correspondence, outputting acceptance, and if the hash values are not in the one-to-one correspondence, outputting unacceptance;hash value coincidence verification means for, when the decrypted hash value coincides with a hash value of each element of the output data sequence of said substitution/decryption apparatus, outputting acceptance, and if the hash values do not coincide, outputting unacceptance;hash value unacceptance authenticity verification means for verifying a hash value unacceptance authenticity proof text as a proof text which proves that for an element of the elements of the input data sequence, which corresponds to a hash value for which said hash value coincidence verification means outputs unacceptance, the output of unacceptance is authentic, if the proof text is authentic, outputting acceptance, and if the proof text is unauthentic, outputting unacceptance;and authenticity determination means for outputting acceptance, for the element of the input data sequence, if said hash value decryption authenticity verification means outputs acceptance while said hash value coincidence verification means outputs acceptance, or if said hash value coincidence verification means outputs unacceptance while said hash value unacceptance authenticity verification means outputs acceptance, and if the output data sequence contains only data corresponding to the elements accepted by said hash value coincidence verification means and all the data, and otherwise, outputting unacceptance, wherein the system executes initial setting processing of generating and publishing a safety variable, an area variable of the public key cryptography, the cryptographic hash function, and an encryption function of the secret key cryptography, initial setting processing of generating and publishing the public key of each of said plurality of substitution/decryption apparatuses, participation processing of inputting, to each of said participant apparatuses, the safety variable, the area variable of the public key cryptography, the cryptographic hash function, the encryption function of the secret key cryptography, the public key of each of said plurality of substitution/decryption apparatuses, a plurality of secret keys of the secret key cryptography, and a plaintext which is different for each participant, and causing each of said participant apparatuses to output data to be input to said substitution/decryption apparatuses, consolidation processing of inputting all the data to be input to said substitution/decryption apparatuses, which are obtained by the participation processing, to said consolidating apparatus and inputting an output from said consolidating apparatus as the input data sequence, substitution/decryption processing of inputting the input data sequence and the private key of the public key cryptography to one of said substitution/decryption apparatuses and causing said substitution/decryption apparatus to output the output data sequence and a sequence of an authenticity proof text, integrated substitution/decryption processing of repeatedly executing the substitution/decryption processing while exchanging the substitution/decryption apparatus to be used by inputting an input data sequence as an output of the consolidation processing as a first input data sequence, in which an input data sequence in first substitution/decryption processing is an input data sequence output from the consolidation processing, an input data sequence in subsequent substitution/decryption processing is an output data sequence of immediately preceding substitution/decryption processing, an output data sequence output from final substitution/decryption processing is a decryption result, an output data sequence output from each substitution/decryption processing except the final substitution/decryption processing is an in progress decryption result, the authenticity proof texts output from all the substitution/decryption processing operations are defined as a global authenticity proof text, and the decryption result, the in progress decryption results, and the global authenticity proof text are output, verification processing of separating an input and output of each substitution/decryption apparatus from the decryption result, the in progress decryption results, and the global authenticity proof text, inputting the input data sequence, the output data sequence, and the authenticity proof text of each substitution/decryption processing to said verification apparatus, and causing said verification apparatus to output one of acceptance and unacceptance, and mix net determination processing of collecting outputs of the verification processing for all substitution/decryption processing operations, if all results indicate acceptance, outputting acceptance, and otherwise, outputting unacceptance.
Independent claims4
224 paragraphs in 5 sections, as filed
TECHNICAL FIELD
0001The present invention relates to a mix-net technology of causing a plurality of organizations to, in cooperation with each other, shuffle and decrypt a plurality of input ciphertexts and output data whose correspondence with the input ciphertexts is unnoticeable and, more particularly, to a technique of eliminating the limitation on the length of an input ciphertext and, if one of a plurality of organizations has not executed the correct operation, allowing even a third party to specify it and prove that fact.
BACKGROUND ART
0002Mix-net is an operation of substituting and decrypting the elements of an input ciphertext sequence such that the correspondence between the elements of an output decrypted text sequence and those of the input ciphertext sequence becomes unnoticeable.
00031. Prior Art
0004In a conventional mix-net, a method using a proof apparatus and a verification apparatus is used to make it possible to specify an organization which has not executed the correct operation and specify the fact (e.g., Japanese Patent Laid-Open No. 2002-344445 (reference 1)). This method will be described with reference to <figref idref="DRAWINGS">FIG. 8</figref>.
0005The proof apparatus of reference 1 proves that substitution and decryption are correctly done. The verification apparatus of reference 1 verifies that the proof executed by the proof apparatus is correct. With the functions of the two apparatuses, if the proof apparatus does not execute the correct operation (substitution and decryption), proof fails, and the verification apparatus can determine that the proof apparatus has not correctly operated.
0006The proof apparatus and verification apparatus of reference 1 are used in the following way and operated as a mix-net as a whole. First, a private key <b>906</b> is determined in correspondence with each substitution/decryption apparatus <b>912</b>. A public key <b>901</b> is generated from the private key <b>906</b> and distributed to all participant apparatuses <b>903</b>. Each participant apparatus <b>903</b> encrypts a short plaintext <b>902</b> having a predetermined length by using the public key <b>901</b>.
0007Each substitution/decryption apparatus <b>912</b> substitutes and decrypts an input ciphertext sequence <b>913</b> and transfers it to the next substitution/decryption apparatus <b>912</b> (processing <b>907</b>). This operation is repeated to finally obtain a plaintext sequence <b>911</b>. The substitution/decryption apparatus <b>912</b> proves by using the proof apparatus of reference 1 that the substitution and decryption operations executed by itself are correct (processing <b>908</b>). A verification apparatus <b>909</b> verifies, by using the verification apparatus of reference 1, the proof executed by the substitution/decryption apparatus. Even a third party can execute this verification when it can prepare the verification apparatus.
0008In the above method, the length of the plaintext <b>902</b> that the participant apparatus <b>903</b> can encrypt is limited to almost the same as the length of the public key. Hence, a longer plaintext cannot be processed.
00092. Prior Art
0010In another conventional mix-net, a method by Juels and Jakobsson is used to make it possible to process a ciphertext having an arbitrary length (e.g., “An Optimally Robust Hybrid Mix Network, Proc. of the 20th annual ACM Symposium on Principles of Distributed Computation, 2001” (reference 2)). In this method, a ciphertext to be input is created by encrypting a plaintext by arbitrary secret key cryptography. Hence, the length of the plaintext is not particularly limited. Additionally, in this method, if one of a plurality of organizations to decrypt and shuffle ciphertexts has not correctly executed these operations, it can be specified by the organizations which execute encryption and shuffle in cooperation. However, a third party not in cooperation with the plurality of organizations cannot specify the organization which has not correctly execute the ciphertext operation.
0011The above relationship will be described with reference to <figref idref="DRAWINGS">FIG. 9</figref>. The mix-net of reference 2 operates in almost the same way as the mix-net of the prior art (1) except that a long plaintext <b>1002</b> may be input. In addition, the substitution/decryption apparatuses can verify each other whether substitution and decryption have been done correctly (processing <b>1014</b>). However, any third party cannot verify it, unlike the prior art (1).
DISCLOSURE OF INVENTION
0000Problems to be Solved by the Invention
0012In the prior art (1), if one of a plurality of organizations to decrypt and shuffle ciphertexts has not correctly executed these operations, a third party can specify it and prove that the specified organization is unauthorized. On the other hand, this method has a problem that the processible length of a ciphertext is limited.
0013In the prior art (2), the processible length of a ciphertext is not limited. However, there is a problem that if one of a plurality of organizations to decrypt and shuffle ciphertexts has not correctly executed these operations, any third party can specify it by itself.
0014It is an object of the present invention to allow a third party to specify an unauthorized organization when decryption and shuffle of ciphertexts are done by a plurality of organizations.
0015It is another object of the present invention to eliminate the limitation on the length of a ciphertext.
0000Means of Solution to the Problems
0016A participant apparatus according to the present invention is characterized by comprising:
0017key encryption means for encrypting one of a plurality of secret keys of secret key cryptography by one public key of a plurality of substitution/decryption apparatuses;
0018data encryption means for encrypting given data by one of the plurality of secret keys of the secret key cryptography;
0019hash value encryption means for calculating a hash value of the given data by using a cryptographic hash function and encrypting the hash value by one public key of the plurality of substitution/decryption apparatuses;
0020repeat means for repeating processing of inputting a plaintext as a first input to the data encryption means and inputting, as subsequent inputs to the data encryption means, preceding outputs from the data encryption means, the key encryption means, and the hash value encryption means a number of times equal to the number of substitution/decryption apparatuses; and
0021output means for outputting data obtained by processing of the repeat means.
0022A consolidating apparatus according to the present invention is characterized by comprising an arrangement which receives a plurality of data, verifies authenticity of each of the data, and outputs only data which is determined as authentic.
0023A substitution/decryption apparatus according to the present invention is characterized by comprising:
0024data division means for diving each element of an input data sequence into a secret key of secret key cryptography, which is encrypted by public key cryptography, data encrypted by secret key cryptography, and a hash value encrypted by public key cryptography;
0025secret key decryption means for decrypting the encrypted secret key of the secret key cryptography by a private key of the public key cryptography;
0026data decryption means for decrypting the encrypted data by using the decrypted secret key to generate output data;
0027hash value decryption means for outputting a value obtained by decrypting the encrypted hash value by the private key of the public key cryptography;
0028hash value verification means for comparing the decrypted hash value with a hash value of the generated output data, if the values coincide, outputting hash value acceptance, and if the values do not coincide, outputting hash value unacceptance;
0029output data sequence generation means for generating a data sequence which contains, as sequence elements, only the output data for which acceptance is output from the hash value verification means and which are corresponding in a sense of being generated from the same element data of the input data sequence, and uniformly shuffling the elements at random to form an output data sequence;
0030hash value decryption authenticity proof means for generating a hash value decryption authenticity proof text as a proof text which proves that the hash value of each element of the output data sequence is always a value obtained by decrypting the encrypted hash value contained in a certain element of the input data sequence, and the hash values are in a one-to-one correspondence;
0031hash value unacceptance authenticity proof means for generating a hash value unacceptance authenticity proof text as a proof text which proves, when the hash value verification means outputs unacceptance, that the output of unacceptance is authentic; and
0032output means for creating an authenticity proof text from the hash value decryption authenticity proof text and the hash value unacceptance authenticity proof text and outputting the authenticity proof text and the output data sequence output from the output data sequence generation means.
0033A verification apparatus according to the present invention is characterized by comprising:
0034hash value decryption authenticity verification means for verifying that a decrypted hash value contained in a hash value decryption authenticity proof text coincides with a hash value obtained by decrypting an encrypted hash value of a certain element of an input data sequence, and the hash values are in a one-to-one correspondence, if the hash values coincide and are in the one-to-one correspondence, outputting acceptance, and if the hash values are not in the one-to-one correspondence, outputting unacceptance;
0035hash value coincidence verification means for, when the decrypted hash value coincides with a hash value of each element of an output data sequence, outputting acceptance, and if the hash values do not coincide, outputting unacceptance;
0036hash value unacceptance authenticity verification means for verifying a hash value unacceptance authenticity proof text as a proof text which proves that for an element of the elements of the input data sequence, which corresponds to a hash value for which the hash value coincidence verification means outputs unacceptance, the output of unacceptance is authentic, if the proof text is authentic, outputting acceptance, and if the proof text is unauthentic, outputting unacceptance; and
0037authenticity determination means for outputting acceptance, for the element of the input data sequence, if the hash value decryption authenticity verification means outputs acceptance while the hash value coincidence verification means outputs acceptance, or if the hash value coincidence verification means outputs unacceptance while the hash value unacceptance authenticity verification means outputs acceptance, and if the output data sequence contains only data corresponding to the elements accepted by the hash value coincidence verification means and all the data, and otherwise, outputting unacceptance.
0038A mix-net system according to the present invention is characterized by comprising the plurality of participant apparatuses, the consolidating apparatus, the substitution/decryption apparatuses, and the verification apparatus, the system executing
0039initial setting processing of generating and publishing a safety variable, an area variable of the public key cryptography, the cryptographic hash function, and an encryption function of the secret key cryptography,
0040initial setting processing of generating and publishing the public key of each of the plurality of substitution/decryption apparatuses,
0041participation processing of inputting, to each of the participant apparatuses, the safety variable, the area variable of the public key cryptography, the cryptographic hash function, the encryption function of the secret key cryptography, the public key of each of the plurality of substitution/decryption apparatuses, a plurality of secret keys of the secret key cryptography, and a plaintext which is different for each participant, and
0042causing each of the participant apparatuses to output data to be input to the substitution/decryption apparatuses,
0043consolidation processing of inputting all the data to be input to the substitution/decryption apparatuses, which are obtained by the participation processing, to the consolidating apparatus and inputting an output from the consolidating apparatus as the input data sequence,
0044substitution/decryption processing of inputting the input data sequence and the private key of the public key cryptography to one of the substitution/decryption apparatuses and causing the substitution/decryption apparatus to output the output data sequence and a sequence of an authenticity proof text,
0045integrated substitution/decryption processing of repeatedly executing the substitution/decryption processing while exchanging the substitution/decryption apparatus to be used by inputting an input data sequence as an output of the consolidation processing as a first input data sequence, in which an input data sequence in first substitution/decryption processing is an input data sequence output from the consolidation processing, an input data sequence in subsequent substitution/decryption processing is an output data sequence of immediately preceding substitution/decryption processing, an output data sequence output from final substitution/decryption processing is a decryption result, an output data sequence output from each substitution/decryption processing except the final substitution/decryption processing is an in-progress decryption result, the authenticity proof texts output from all the substitution/decryption processing operations are defined as a global authenticity proof text, and the decryption result, the in-progress decryption results, and the global authenticity proof text are output,
0046verification processing of separating an input and output of each substitution/decryption apparatus from the decryption result, the in-progress decryption results, and the global authenticity proof text, inputting the input data sequence, the output data sequence, and the authenticity proof text of each substitution/decryption processing to the verification apparatus, and causing the verification apparatus to output one of acceptance and unacceptance, and
0047mix-net determination processing of collecting outputs of the verification processing for all substitution/decryption processing operations, if all results indicate acceptance, outputting acceptance, and otherwise, outputting unacceptance.
0000Effect of the Invention
0048In the present invention, each participant apparatus encrypts a plaintext by using a secret key of secret key cryptography, encrypts the encryption key by a public key, and sends the plaintext and public key to a substitution/decryption apparatus. With this processing, the limitation on the length of a ciphertext to be processed can be eliminated.
0049In the present invention, a verifiable proof text using a public key by each substitution/decryption apparatus is verified by a verification apparatus using the public key. If one of a plurality of organizations to decrypt and shuffle ciphertexts has not correctly executed the operation, a third party can specify it and prove that the specified organization is unauthorized.
BRIEF DESCRIPTION OF DRAWINGS
0050<figref idref="DRAWINGS">FIG. 1</figref> is a block diagram showing the overall arrangement of a mix-net system according to the present invention;
0051<figref idref="DRAWINGS">FIG. 2</figref> is a block diagram showing an arrangement example of a participant apparatus according to the first embodiment of the present invention;
0052<figref idref="DRAWINGS">FIG. 3</figref> is a block diagram showing an arrangement example of a substitution/decryption apparatus according to the first embodiment of the present invention;
0053<figref idref="DRAWINGS">FIG. 4</figref> is a block diagram showing an arrangement example of a verification apparatus according to the first embodiment of the present invention;
0054<figref idref="DRAWINGS">FIG. 5</figref> is a block diagram showing an arrangement example of a participant apparatus according to the second embodiment of the present invention;
0055<figref idref="DRAWINGS">FIG. 6</figref> is a block diagram showing an arrangement example of a substitution/decryption apparatus according to the second embodiment of the present invention;
0056<figref idref="DRAWINGS">FIG. 7</figref> is a block diagram showing an arrangement example of a verification apparatus according to the second embodiment of the present invention;
0057<figref idref="DRAWINGS">FIG. 8</figref> is a block diagram for explaining the prior art (1); and
0058<figref idref="DRAWINGS">FIG. 9</figref> is a block diagram for explaining the prior art (2).
BEST MODE FOR CARRYING OUT THE INVENTION
0059The embodiments of the present invention will be described next in detail with reference to the accompanying drawings.
1 First Embodiment
00001.1 Outline
0060The outline of the first embodiment will be described with reference to FIGS. <b>1</b> to <b>4</b>.
0061As shown in <figref idref="DRAWINGS">FIG. 1</figref>, a mix-net system according to this embodiment includes a plurality of participant apparatuses <b>103</b>, a consolidating apparatus <b>104</b>, a plurality to substitution/decryption apparatuses <b>112</b>, and a verification apparatus <b>109</b>.
0000[Participant Apparatus]
0062As shown in <figref idref="DRAWINGS">FIG. 2</figref>, the participant apparatus <b>103</b> has a key encryption means <b>205</b>, data encryption means <b>206</b>, hash value encryption means <b>207</b>, knowledge concatenation means <b>208</b>, repeat means <b>213</b>, random number knowledge proof means <b>210</b>, and output means <b>215</b>.
0063The key encryption means <b>205</b> encrypts one of a plurality of secret keys of secret key cryptography by using one public key <b>101</b> of the plurality of substitution/decryption apparatuses <b>112</b>. The key encryption means <b>205</b> also generates a proof text of knowledge of the secret key encrypted at this time. The data encryption means <b>206</b> encrypts given data <b>214</b> by using one of the plurality of secret keys of secret key cryptography. The hash value encryption means <b>207</b> calculates the hash value of the given data by using a cryptographic hash function and encrypts the hash value by using one public key of the plurality of substitution/decryption apparatuses <b>112</b>. The knowledge concatenation means <b>208</b> encrypts the given data <b>214</b> by using the public key <b>101</b> of the plurality of substitution/decryption apparatuses <b>112</b>. The knowledge concatenation means <b>208</b> also generates a proof text of knowledge of a secret random number used for encryption at this time.
0064The repeat means <b>213</b> repeats processing of inputting a plaintext <b>102</b> as the first input to the data encryption means <b>206</b> and inputting, as subsequent inputs to the data encryption means <b>206</b>, preceding outputs from the data encryption means <b>206</b>, key encryption means <b>205</b>, hash value encryption means <b>207</b>, and knowledge concatenation means <b>208</b> a number of times equal to the number of substitution/decryption apparatuses <b>112</b>. The whole random number knowledge proof means <b>210</b> generates and outputs a proof text of knowledge of the sum of secret random numbers used in all the repeated processing operations for data finally obtained by repeating the processing by the knowledge concatenation means <b>208</b>. The output means <b>215</b> outputs, as a ciphertext <b>211</b>, data obtained by the processing of the repeat means <b>213</b>. The output means <b>215</b> also outputs data to prove that an authentic participant apparatus has created the ciphertext <b>211</b>.
0000[Consolidating Apparatus]
0065The consolidating apparatus <b>104</b> receives, from each of the plurality of participant apparatuses <b>103</b>, the ciphertext <b>211</b> and the data to prove that an authentic participant apparatus has created the ciphertext <b>211</b>. The consolidating apparatus <b>104</b> verifies that the input ciphertext <b>211</b> has been generated by an authentic participant apparatus and outputs only ciphertexts determined as authentic to one of the substitution/decryption apparatuses <b>112</b>.
0000[Substitution/Decryption Apparatus]
0066As shown in <figref idref="DRAWINGS">FIG. 3</figref>, the substitution/decryption apparatus <b>112</b> has a data division means <b>322</b>, secret key knowledge verification means <b>307</b>, secret random number knowledge verification means <b>308</b>, secret key decryption means <b>310</b>, data decryption means <b>313</b>, hash value decryption means <b>312</b>, hash value verification means <b>317</b>, concatenated data decryption means <b>314</b>, output data sequence generation means <b>311</b>, hash value decryption authenticity proof means <b>315</b>, concatenated data decryption authenticity proof means <b>316</b>, hash value unacceptance authenticity proof means <b>318</b>, and output means.
0067The data division means <b>322</b> divides each element of an input data sequence <b>105</b> input from the consolidating apparatus <b>104</b> or another substitution/decryption apparatus into a secret key <b>302</b> of secret key cryptography, which is encrypted by public key cryptography, data <b>303</b> encrypted by secret key cryptography, a hash value <b>304</b> encrypted by public key cryptography, concatenated data <b>305</b> encrypted by public key cryptography, a proof text <b>301</b> of knowledge of the encrypted secret key, and a proof text <b>306</b> of knowledge of secret random numbers used to encrypt concatenated data.
0068The secret key knowledge verification means <b>307</b> verifies the authenticity of the proof text <b>301</b> of knowledge of the secret key. If the proof text <b>301</b> is authentic, acceptance is output. Otherwise, unacceptance is output. The secret random number knowledge verification means <b>308</b> verifies the authenticity of the proof text <b>306</b> of knowledge of the secret random number. If the proof text <b>306</b> is authentic, acceptance is output. Otherwise, unacceptance is output. The secret key decryption means <b>310</b> decrypts the encrypted secret key of secret key cryptography by using a private key <b>106</b> of public key cryptography. The data decryption means <b>313</b> decrypts the encrypted data <b>303</b> by using the decrypted secret key to generate output data. The hash value decryption means <b>312</b> outputs a hash value obtained by decrypting the encrypted hash value <b>304</b> by using the private key <b>106</b> of public key cryptography. The hash value verification means <b>317</b> compares the decrypted hash value with the hash value of the generated output data. If the values coincide, hash value acceptance is output. If the values do not coincide, hash value unacceptance is output. The concatenated data decryption means <b>314</b> decrypts the encrypted concatenated data <b>305</b> by using the private key of public key cryptography.
0069The output data sequence generation means <b>311</b> generates a data sequence which contains, as sequence elements, only output data and decrypted concatenated data for which acceptance is output from all of the hash value verification means <b>317</b>, secret key knowledge verification means <b>307</b>, and secret random number knowledge verification means <b>306</b> and which are corresponding in a sense of being generated from the same element data of the input data sequence <b>105</b>. The output data sequence generation means <b>311</b> also uniformly shuffles the elements at random to form an output data sequence <b>107</b>.
0070The hash value decryption authenticity proof means <b>315</b> generates a hash value decryption authenticity proof text which proves that the hash value of each element of the output data sequence <b>107</b> is always a value obtained by decrypting an encrypted hash value contained in a certain element of the input data sequence <b>105</b>, and the hash values are in a one-to-one correspondence. The concatenated data decryption authenticity proof means <b>316</b> generates a concatenated data decryption authenticity proof text which proves that the decrypted concatenated data contained in each element of the output data sequence <b>107</b> is always data obtained by decrypting encrypted concatenated data contained in a certain element of the input data sequence <b>105</b>, and the concatenated data are in a one-to-one correspondence. The hash value unacceptance authenticity proof means <b>318</b> generates a hash value unacceptance authenticity proof text which proves that output of unacceptance from the hash value verification means <b>317</b> is authentic.
0071The output means creates an authenticity proof text <b>108</b> from the hash value decryption authenticity proof text, concatenated data decryption authenticity proof text, and hash value unacceptance authenticity proof text and outputs the authenticity proof text <b>108</b> and the output data sequence <b>107</b> output from the output data sequence generation means <b>311</b>.
0000[Verification Apparatus]
0072As shown in <figref idref="DRAWINGS">FIG. 4</figref>, the verification apparatus <b>109</b> has a secret key knowledge verification means <b>402</b>, secret random number knowledge verification means <b>404</b>, hash value decryption authenticity verification means <b>406</b>, hash value coincidence verification means <b>408</b>, concatenated data decryption authenticity verification means <b>407</b>, hash value unacceptance authenticity verification means <b>409</b>, and authenticity determination means <b>405</b>.
0073The secret key knowledge verification means <b>402</b> verifies the authenticity of the secret key knowledge proof text <b>301</b> belonging to each element of the input data sequence <b>105</b> input from the consolidating apparatus <b>104</b> or substitution/decryption apparatus <b>112</b>. If the proof text <b>301</b> is authentic, acceptance is output. Otherwise, unacceptance is output. The secret random number knowledge verification means <b>404</b> verifies the secret random number knowledge proof text <b>306</b> belonging to each element of the input data sequence <b>105</b>. If the proof text <b>306</b> is authentic, acceptance is output. Otherwise, unacceptance is output. The hash value decryption authenticity verification means <b>406</b> verifies whether the decrypted hash value contained in a hash value decryption authenticity proof text <b>401</b> coincides with a hash value obtained by decrypting the encrypted hash value of a certain element of the input data sequence <b>105</b>, and the hash values are in a one-to-one correspondence. If the hash values coincide and are in a one-to-one correspondence, acceptance is output. Otherwise, unacceptance is output.
0074The hash value coincidence verification means <b>408</b> outputs acceptance when the decrypted hash value coincides with the hash value of each element of the output data sequence <b>107</b> from the substitution/decryption apparatus <b>112</b>. Otherwise, unacceptance is output. The concatenated data decryption authenticity verification means <b>407</b> verifies whether decrypted concatenated data contained in each element of the output data sequence <b>107</b> coincides with data obtained by decrypting the encrypted concatenated data <b>305</b> contained in a certain element of the input data sequence <b>105</b>, and the concatenated data are in a one-to-one correspondence. If the concatenated data coincide and are in a one-to-one correspondence, acceptance is output. Otherwise, unacceptance is output. For, of the elements of the input ciphertext sequence <b>303</b>, an element corresponding to a hash value for which unacceptance is output from the hash value coincidence verification means <b>408</b>, the hash value unacceptance authenticity verification means <b>409</b> verifies a hash value unacceptance authenticity proof text <b>400</b> which proves that the output of unacceptance is authentic. If the proof text is authentic, acceptance is output. Otherwise, unacceptance is output.
0075For, of the elements of the input data sequence <b>105</b>, all elements for which both the secret key knowledge verification means <b>402</b> and the secret random number knowledge verification means <b>404</b> output acceptance, the authenticity determination means <b>405</b> outputs acceptance if all the following conditions are satisfied. Otherwise, unacceptance is output. <ul id="ul0001" list-style="none"><li id="ul0001-0001" num="0076"> (A) Both the hash value decryption authenticity verification means <b>406</b> and the concatenated data decryption authenticity verification means <b>407</b> output acceptance. </li><li id="ul0001-0002" num="0077"> (B) The hash value coincidence verification means <b>408</b> outputs acceptance, or the hash value coincidence verification means <b>408</b> outputs unacceptance while the hash value unacceptance authenticity verification means <b>409</b> outputs acceptance. </li><li id="ul0001-0003" num="0078"> (C) The output data sequence <b>107</b> contains only data corresponding to the elements accepted by the secret key knowledge verification means <b>402</b>, secret random number knowledge verification means <b>404</b>, and hash value coincidence verification means <b>408</b> and all these data. <br /> [Operation of Mix-Net System] </li></ul>
0079First, initial setting processing <b>100</b> is executed in which a safety variable, an area variable of public key cryptography, a cryptographic hash function, and an encryption function of secret key cryptography are generated and published. Next, initial setting processing <b>320</b> of the substitution/decryption apparatus is executed in which the public key of each of the plurality of substitution/decryption apparatuses <b>112</b> is generated and published.
0080Participation processing is executed then in which each of the plurality of participant apparatuses <b>103</b> receives the safety variable, the area variable of public key cryptography, the cryptographic hash function, the encryption function of secret key cryptography, the public key of each of the plurality of substitution/decryption apparatuses <b>112</b>, a plurality of secret keys of secret key cryptography, and a plaintext which is different for each participant apparatus <b>103</b> to generate data to be output to the substitution/decryption apparatuses through the consolidating apparatus <b>104</b>. All the data obtained by participation processing are input to the consolidating apparatus <b>104</b> and consolidated. The result is output to one of the substitution/decryption apparatuses <b>112</b> as the input data sequence <b>105</b>.
0081Next, substitution/decryption processing is executed in which each of the substitution/decryption apparatuses <b>112</b> receives the input data sequence <b>105</b> and the private key <b>106</b> of public key cryptography and generates the output data sequence <b>107</b> and the sequence of the authenticity proof text <b>108</b>. At this time, the input data sequence <b>105</b> input to the first substitution/decryption apparatus <b>112</b> is the input data sequence <b>105</b> output from the consolidating apparatus <b>104</b>. The input data sequence <b>105</b> input to each succeeding substitution/decryption apparatus <b>112</b> is the output data sequence <b>107</b> output from the immediately preceding substitution/decryption apparatus <b>112</b>. The output data sequence <b>107</b> output from the final substitution/decryption apparatus <b>112</b> is the decryption result. The output data sequence <b>107</b> output from each substitution/decryption apparatus <b>112</b> except the final substitution/decryption apparatus <b>112</b> is an in-progress decryption result. The authenticity proof texts <b>108</b> output from all the substitution/decryption apparatuses <b>112</b> are defined as a global authenticity proof text. The decryption result, in-progress decryption results and the global authenticity proof text are output. The above-described processing is called integrated substitution/decryption processing.
0082Verification processing is executed then in which the input and output of each substitution/decryption apparatus <b>112</b> are separated from the decryption result, in-progress decryption results and the global authenticity proof text, the input data sequence <b>105</b>, output data sequence <b>107</b>, and authenticity proof text <b>108</b> in each substitution/decryption apparatus <b>112</b> are input to the verification apparatus <b>109</b>, and the verification apparatus <b>109</b> outputs acceptance or unacceptance. Mix-net determination processing is executed in which the verification processing results for all substitution/decryption processing operations are collected, if all results indicate acceptance, acceptance is output as the entire system, and otherwise, unacceptance is output as the entire system.
0083The participant apparatus <b>103</b> can use, as the first input to the hash value encryption means <b>207</b>, a random number, a date/time, or a value unique to a mix-net session, or data which combines these values, in addition to the plaintext <b>102</b>.
00001.2 Notation
0084The notation to be used will be described below. Let Hash( ) be a cryptographic hash function, q be a prime number, C be an elliptic curve with an order q, G be a point on C, enc[e]( ) be an encryption function of secret key cryptography, and dec[e]( ) be a decryption function. In this case, e indicates a secret key to be used for encryption or decryption. Let L be the number of bits in the range of the hash function, and L be the number of bits of a key of an encryption function of secret key cryptography. The number of bits of q is larger than L by at least 5. L is called a safety variable. Equation X=[x]G represents that X is an x-fold point of G on the elliptic curve. When the addition symbol “+” is used for a point on the elliptic curve, it indicates an operation on the elliptic curve.
0085The mix-net system of the present invention, which can process a ciphertext with an arbitrary length and allows a third party to verify includes a plurality of substitution/decryption apparatuses, the participant apparatuses of a plurality of mix-net participants, the verification apparatus of a verification organization, and the consolidating apparatus of a consolidating organization. Let m be the number of substitution/decryption apparatuses, n be the number of participant apparatuses, S<sup>(j) </sup>be the jth substitution/decryption apparatus, and U<sub>i </sub>be the ith participant apparatus.
0086Let Ψ be one-to-one mapping from an integral value of L bits to a point on the elliptic curve C, Φ be surjective mapping from a point on the elliptic curve to an integral value of L bits, and Φ·Ψ be identity mapping. Both Φ and Ψ can be calculated efficiently. A detailed example of Φ is mapping which sets e=Φ(E) upon being given a point E and employs L bits from the x-coordinate of the point E. In this case, a detailed example of Ψ is given the bit sequence e of L bits, sets e in the L lower bits of the x-coordinate of the point on the elliptic curve, and pads predetermined 0 to the remaining bits. It is checked whether a point having such an x-coordinate is present on C. If no point is present, the padding is changed in accordance with predetermined procedures, and the processing is executed until such an x-coordinate is found on C. If a point on C is found, it is defined as Ψ(e). Since the L lower bits of the x-coordinate of the point (Ψ(e)) always continue to be e, Φ·Ψ(e)=e holds obviously, and Φ·Ψ is an identity mapping.
00001.3 Detailed Example
0087The first embodiment will be described in detail with reference to FIGS. <b>1</b> to <b>4</b>.
0000[Initial Setting]
0088An initial setting organization for initial setting determines and publishes, by using the initial setting processing <b>100</b> implemented by a computer, a bit length A of a plaintext, the safety variable L, the prime number q whose bit length is larger than L by 5, the elliptic curve C having the order q, the point G on C, a cryptographic hash function Hash( ) having the output bit length L, secret key cryptography using a key with the length L, an encryption function enc[e]( ) and decryption function dec[e] of the secret key cryptography, a function Ψ( ) from a bit sequence with L bits to a point on C, and mapping Φ( ) from a point on C to a bit sequence with L bits. The prime number q, the elliptic curve C with the order q, and the point G on C are the area functions of the public key cryptography.
0000[Initial Setting of Substitution/Decryption Apparatus]
0089All the substitution/decryption apparatuses <b>112</b> execute the next initial setting processing. The initial setting means <b>320</b> (<figref idref="DRAWINGS">FIG. 3</figref>) in each of substitution/decryption apparatuses S<sup>(j) </sup>(j=1, . . . ,m) uniformly selects a private key <b>106</b> x<sup>(j)</sup>εZ/qZ at random and saves the private key in the substitution/decryption apparatus S<sup>(j)</sup>. In addition, the initial setting means <b>320</b> generates and publishes a public key <b>101</b> X<sup>(j)</sup>=[x<sup>(j)</sup>]G.
0090The initial setting means <b>320</b> in each substitution/decryption apparatus S<sup>(j) </sup>uniformly selects r<sup>(j)</sup>εZ/qZ at random and calculates <br />γ<sup>(j)</sup>=Hash(G,[r<sup>(j)</sup>]X<sup>(j)</sup>) <br />α<sup>(j)</sup>=r<sup>(j)</sup>−γ<sup>(j)</sup>r<sup>(j) </sup>mod q <br /> and publishes γ<sup>(j) </sup>and α<sup>(j) </sup>as a zero-knowledge proof text <b>321</b> of knowledge of x<sup>(j)</sup>. <br /> [Ciphertext Generation of Participant Apparatus]
0091For i=1, . . . ,n, a participant apparatus <b>103</b> U<sub>i </sub>(<figref idref="DRAWINGS">FIG. 2</figref>) determines a plaintext <b>102</b> M<sub>i </sub>having the bit length Λ. As the first data <b>214</b>, each participant apparatus <b>103</b> U<sub>i </sub>generates data containing c<sub>i</sub><sup>(m+1)</sup>=M<sub>i</sub>, T<sub>i</sub>′<sup>(m+1)</sup>=G, and arbitrary data <b>203</b> (each containing arbitrary L-bit character strings K<sub>i</sub><sup>(m+1)</sup>, K<sub>i</sub>′<sup>(m+1)</sup>, S<sub>i</sub><sup>(m+1)</sup>, S<sub>i</sub>′<sup>(m+1)</sup>, and P<sub>i</sub><sup>(m+1)</sup>) (processing <b>200</b>). In addition, for j=1, . . . ,m, a key generation means <b>204</b> uniformly selects elements r[1]<sub>i</sub><sup>(j)</sup>, r[2]<sub>i</sub><sup>(j)</sup>, r[3]<sub>i</sub><sup>(j)</sup>, r[4]<sub>i</sub><sup>(j)</sup>, and r[5]<sub>i</sub><sup>(j) </sup>of Z/qZ and a point E<sub>i</sub><sup>(j) </sup>on C at random.
0092Then, the key encryption means <b>205</b>, data encryption means <b>206</b>, hash value encryption means <b>207</b>, knowledge concatenation means <b>208</b>, proof text collection means <b>209</b>, proof generation means <b>210</b>, and output means <b>215</b> execute the following processing <b>213</b> repeatedly in the order of j=m, (m−1), . . . , and 1.
0093As the arbitrary character string, a random number, a number unique to a session, or a date/time is sometimes selected.
0094When a random number is used, the participant apparatus can confirm the presence of its plaintext from the final decrypted text set. When a number unique to a session or a date/time is used, it can be recognized that a ciphertext used for another session is not reused.
0095Encryption Processing by Key Encryption Means <b>205</b>
0096To encrypt a secret key e<sub>i</sub><sup>(j)</sup>, the key encryption means <b>205</b> obtains E<sub>i</sub><sup>(j) </sup>which satisfies <br />e<sub>i</sub><sup>(j)</sup>=Φ(E<sub>i</sub><sup>(j)</sup>) <br /> and calculates <br />(K<sub>i</sub><sup>(j)</sup>,K<sub>i</sub>′<sup>(j)</sup>)=([r[1]<sub>i</sub><sup>(j)</sup>]X<sup>(j)</sup>, [r[1]<sub>i</sub><sup>(j)</sup>]G+E<sub>i</sub><sup>(j)</sup>) <br /> The calculation result is input to the output means <b>215</b>.
0097Secret Key Knowledge Proof Text Generation Processing by Key Encryption Means <b>205</b><br />γ=Hash(K<sub>i</sub><sup>(j)</sup>,K<sub>i</sub>′<sup>(j)</sup>,c<sub>i</sub><sup>(j)</sup>,S<sub>i</sub><sup>(j)</sup>,S<sub>i</sub>′<sup>(j)</sup>,T<sub>i</sub><sup>(j)</sup>,T<sub>i</sub>′<sup>(j)</sup>, [r[4]<sub>i</sub><sup>(j)</sup>]X<sup>(j)</sup>) <br /> and <br />α<sub>i</sub><sup>(j)</sup>=r[4]<sub>i</sub><sup>(j)</sup>−γ<sub>i</sub><sup>(j)</sup>r[1]<sub>i</sub><sup>(j) </sup>mod q <br /> are calculated, and the results are input to the proof text collection means <b>209</b>.
0098Data Encryption Processing by Data Encryption Means <b>206</b><br />e<sub>i</sub><sup>(j)</sup>=Φ(E<sub>i</sub><sup>(j)</sup>) <br /> and <br />c<sub>i</sub><sup>(j)</sup>=enc[e<sub>i</sub><sup>(j)</sup>](K<sub>i</sub><sup>(j+1)</sup>,K<sub>i</sub>′<sup>(j+1)</sup>,c<sub>i</sub><sup>(j+1</sup>, S<sub>i</sub><sup>(j+1)</sup>,S<sub>i</sub>′<sup>(j+1)</sup>, T<sub>i</sub><sup>(j+1)</sup>,T<sub>i</sub>′<sup>(j+1)</sup>, P<sub>i</sub><sup>(j+1)</sup>) <br /> are calculated, and c<sub>i</sub><sup>(j) </sup>is input to the output means <b>215</b>.
0099Hash Value Encryption Processing by Hash Value Encryption Means <b>207</b><br />(S<sub>i</sub><sup>(j)</sup>,S<sub>i</sub>′<sup>(j)</sup>)=([r[2]<sub>i</sub><sup>(j)</sup>]X<sup>(j)</sup>, [r[2]<sub>i</sub><sup>(j)</sup>]G+Ψ(Hash (K<sub>i</sub><sup>(j+1)</sup>,K<sub>i</sub>′<sup>(j+1)</sup>,c<sub>i</sub><sup>(j+1)</sup>, S<sub>i</sub><sup>(j+1)</sup>,S<sub>i</sub>′<sup>(j+1)</sup>,T<sub>i</sub><sup>(j+1)</sup>, T<sub>i</sub>′<sup>(j+1)</sup>, P<sub>i</sub><sup>(j+1)</sup>))) <br /> is calculated to input S<sub>i</sub><sup>(j)</sup>,S<sub>i</sub>′<sup>(j) </sup>to the output means <b>215</b>.
0100Knowledge Concatenation Processing by Knowledge Concatenation Means <b>208</b><br />(T<sub>i</sub><sup>(j)</sup>, T<sub>i</sub>′<sup>(j)</sup>)=([r[3]<sub>i</sub><sup>(j)</sup>]X<sup>(j)</sup>, [r[3]<sub>i</sub><sup>(j)</sup>]G+T′<sup>(j+1)</sup>, <br /> is calculated to input T<sub>i</sub><sup>(j)</sup>,T<sub>i</sub>′<sup>(j) </sup>to the output means <b>215</b>.
0101Random Number Knowledge Proof Text Generation Processing by Knowledge Concatenation Means <b>208</b><br />γ′<sub>i</sub><sup>(j)</sup>=Hash(K<sub>i</sub><sup>(j)</sup>,K<sub>i</sub>′<sup>(j)</sup>,c<sub>i</sub><sup>(j)</sup>,S<sub>i</sub><sup>(j)</sup>,S<sub>i</sub>′<sup>(j)</sup>,T<sub>i</sub><sup>(j)</sup>,T<sub>i</sub>′<sup>(j)</sup>, [r[5]<sup>(j)</sup>]X<sup>(j)</sup>) <br /> and <br />α′<sub>i</sub><sup>(j)</sup>=r[5]<sub>i</sub><sup>(j)</sup>−γ′<sub>i</sub><sup>(j)</sup>r[3]<sub>i</sub><sup>(j) </sup>mod q <br /> are calculated, and the results are input to the proof text collection means <b>209</b>.
0102Collection Processing of Secret Key Knowledge Proof Text and Random Number Knowledge Proof Text by Proof Text Collection Means <b>209</b>
0103The secret key knowledge proof texts γ<sub>i</sub><sup>(j) </sup>and α<sub>i</sub><sup>(j) </sup>and the random number knowledge proof texts γ′<sub>i</sub><sup>(j) </sup>and α′<sub>i</sub><sup>(j) </sup>are collected to generate a proof text P<sub>i</sub><sup>(j)</sup>=[γ<sub>i</sub><sup>(j)</sup>,α<sub>i</sub><sup>(j)</sup>,γ′<sub>i</sub><sup>(j)</sup>,α′<sub>i</sub><sup>(j)</sup>]. If j=1 (P<sub>i</sub><sup>(j)</sup>), it is output as part of a proof text <b>212</b>.
0104Processing by Proof Generation Means <b>210</b>
0105The element r[4]<sub>i</sub><sup>(0) </sup>of Z/qZ is uniformly selected at random. The following entire random number knowledge proof is calculated, and P<sub>i</sub><sup>(0) </sup>is output as part of the proof text. <br />γ′<sub>i</sub><sup>(0)</sup>=Hash(K<sub>i</sub><sup>(1)</sup>,K<sub>i</sub>′<sup>(1)</sup>,c<sub>i</sub><sup>(1)</sup>,S<sub>i</sub><sup>(1)</sup>,S<sub>i</sub>′<sup>(1)</sup>,T<sub>i</sub><sup>(1)</sup>,T<sub>i</sub>′<sup>(1)</sup>, [r[4]<sub>i</sub><sup>(0)</sup>]G) <br />α′<sub>i</sub><sup>(0)</sup>=r[4]<sub>i</sub><sup>(0)</sup>−γ′<sub>i</sub><sup>(0)</sup>Σj=1m r[3]<sub>i</sub><sup>(j) </sup>mod q <br />P<sub>i</sub><sup>(0)</sup>=[γ′<sub>i</sub><sup>(0)</sup>, α′<sub>i</sub><sup>(0)</sup>]
0106Processing by Output Means <b>215</b>
0107Data <b>214</b>′ (K<sub>i</sub><sup>(j)</sup>,K<sub>i</sub>′<sup>(j)</sup>,c<sub>i</sub><sup>(j)</sup>,S<sub>i</sub><sup>(j)</sup>,S<sub>i</sub>′<sup>(j)</sup>,T<sub>i</sub><sup>(j)</sup>,T<sub>i</sub>′<sup>(j)</sup>) is generated from the inputs K<sub>i</sub><sup>(j) </sup>and K<sub>i</sub>′<sup>(j) </sup>from the key encryption means <b>205</b>, the input c<sub>i</sub><sup>(j) </sup>from the data encryption means <b>206</b>, the inputs S<sub>i</sub><sup>(j) </sup>and S<sub>i</sub>′<sup>(j) </sup>from the hash value encryption means <b>207</b>, and the inputs T<sub>i</sub><sup>(j) </sup>and T<sub>i</sub>′<sup>(j) </sup>from the knowledge concatenation means <b>208</b>. If j≠1, the data <b>214</b>′ is fed back as the data <b>214</b>. If j=1, (K<sub>i</sub><sup>(1)</sup>,K<sub>i</sub><sup>(1)</sup>,c<sub>i</sub><sup>(1)</sup>,S<sub>i</sub><sup>(1)</sup>,S<sub>i</sub>′<sup>(1)</sup>,T<sub>i</sub><sup>(1)</sup>,T<sub>i</sub>′<sup>(1)</sup>) is output as the ciphertext <b>211</b>.
0108That is, the participant apparatus <b>103</b> U<sub>i </sub>sends the ciphertext <b>211</b> (K<sub>i</sub><sup>(1)</sup>,K<sub>i</sub>′<sup>(1)</sup>,c<sub>i</sub><sup>(1)</sup>,S<sub>i</sub><sup>(1)</sup>,S<sub>i</sub>′<sup>(1)</sup>,T<sub>i</sub><sup>(1)</sup>,T<sub>i</sub>′<sup>(1)</sup>) and the proof text P<sub>i</sub><sup>(1)</sup>,P<sub>i</sub><sup>(0) </sup>to the consolidating apparatus <b>104</b> of the consolidating organization.
0000[Ciphertext Verification by Consolidating Apparatus]
0109For i=1, . . . , n, the consolidating apparatus <b>104</b> verifies the proof text for the entire data and confirms that <br />γ′<sub>i</sub><sup>(0)</sup>=Hash(K<sub>i</sub><sup>(1)</sup>,K<sub>i</sub>′<sup>(1)</sup>,c<sub>i</sub><sup>(1)</sup>,S<sub>i</sub><sup>(1)</sup>,S<sub>i</sub>′<sup>(1)</sup>,T<sub>i</sub><sup>(1)</sup>,T<sub>i</sub>′<sup>(1)</sup>, [α′<sub>i</sub><sup>(0)</sup>]G<sub>i</sub><sup>(j)</sup>+[γ′<sub>i</sub><sup>(0)</sup>]G) <br /> holds.
0110The proof text for the entire data is sent to the verification apparatus <b>109</b> (<figref idref="DRAWINGS">FIG. 1</figref>; processing <b>110</b>). For only i for which it can be confirmed that the proof text holds, <br />K<sub>i</sub><sup>(1)</sup>,K<sub>i</sub>′<sup>(1)</sup>,c<sub>i</sub><sup>(1)</sup>,S<sub>i</sub><sup>(1)</sup>,S<sub>i</sub>′<sup>(1)</sup>,T<sub>i</sub><sup>(1)</sup>,T<sub>i</sub>′<sup>(1)</sup>,P<sub>i</sub><sup>(1)</sup>,P<sub>i</sub><sup>(0) </sup><br /> is sent to the first substitution/decryption apparatus (processing <b>105</b>). In the example shown in <figref idref="DRAWINGS">FIG. 1</figref>, five data are input, and four data are output. The number of ciphertexts decreases from this point. The number after the decrease is also represented by n. The ciphertexts are assigned numbers i=1 to n. In the following description, <br />K<sub>i</sub><sup>(j)</sup>,K<sub>i</sub>′<sup>(j)</sup>,c<sub>i</sub><sup>(j)</sup>,S<sub>i</sub><sup>(j)</sup>,S<sub>i</sub>′<sup>(j)</sup>,T<sub>i</sub><sup>(j)</sup>,T<sub>i</sub>′<sup>(j)</sup>,P<sub>i</sub><sup>(j) </sup><br /> is generally different from the above-described value except when j=1. <br /> [Shuffle and Decryption of Ciphertext by Substitution/Decryption Apparatus]
0111Sequentially for j=1, . . . ,m, the substitution/decryption apparatus <b>112</b> S<sup>(j) </sup>executes the following calculation and verification.
0112The substitution/decryption apparatus <b>112</b> S<sup>(j) </sup>receives the input data sequence <b>105</b> containing the encrypted secret key <b>302</b> (abbreviated as a secret key ciphertext in <figref idref="DRAWINGS">FIG. 3</figref>) of secret key cryptography <br />K<sub>i</sub><sup>(j)</sup>,K<sub>i</sub>′<sup>(j) </sup><br /> the encrypted data <b>303</b> (abbreviated as a data ciphertext in <figref idref="DRAWINGS">FIG. 3</figref>) <br />c<sub>i</sub><sup>(j) </sup><br /> the encrypted hash value <b>304</b> (hash value ciphertext in <figref idref="DRAWINGS">FIG. 3</figref>) <br />S<sub>i</sub><sup>(j)</sup>,S<sub>i</sub>′<sup>(j) </sup><br /> the encrypted concatenated data <b>305</b> (abbreviated as a concatenated data ciphertext in <figref idref="DRAWINGS">FIG. 3</figref>) <br />T<sub>i</sub><sup>(j)</sup>,T<sub>i</sub>′<sup>(j) </sup><br /> and the secret key knowledge proof text <b>301</b> (abbreviated as a key knowledge proof text in <figref idref="DRAWINGS">FIG. 3</figref>) and the secret random number knowledge proof text <b>306</b> (abbreviated as a random number knowledge proof text in <figref idref="DRAWINGS">FIG. 3</figref>) <br />P<sub>i</sub><sup>(j) </sup><br /> The input data sequence <b>105</b> is divided into the elements <b>301</b> to <b>306</b> by the data division means <b>322</b>.
0113The substitution/decryption apparatus <b>112</b> S<sup>(j) </sup>executes the following processing for all i (i=1, . . . ,n).
0114The secret key knowledge verification means <b>307</b> confirms <br />γ<sub>i</sub><sup>(j)</sup>=Hash(K<sub>i</sub><sup>(j)</sup>,K<sub>i</sub>′<sup>(j)</sup>,c<sub>i</sub><sup>(j)</sup>,S<sub>i</sub><sup>(j)</sup>,S<sub>i</sub>′<sup>(j)</sup>,T<sub>i</sub><sup>(j)</sup>,T<sub>i</sub>′<sup>(j)</sup>, [α<sub>i</sub><sup>(j)</sup>]X<sup>(j)</sup>+[γ<sub>i</sub><sup>(j)</sup>]K<sub>i</sub><sup>(j)</sup>)
0115The secret random number knowledge verification means <b>308</b> confirms <br />γ′<sub>i</sub><sup>(j)</sup>=Hash(K<sub>i</sub><sup>(j)</sup>,K<sub>i</sub><sup>(j)</sup>,c<sub>i</sub><sup>(j)</sup>,S<sub>i</sub><sup>(j)</sup>,S<sub>i</sub>′<sup>(j)</sup>,T<sub>i</sub><sup>(j)</sup>,T<sub>i</sub>′<sup>(j)</sup>, [α′<sub>i</sub><sup>(j)</sup>]X<sup>(j)</sup>+[γ′<sub>i</sub><sup>(j)</sup>]T<sub>i</sub><sup>(j)</sup>) <br /> For i for which the equation does not hold, the data is not added to the final output data sequence.
0116The number of ciphertexts decreases here, too. The number after the decrease is also represented by n. The ciphertexts are assigned numbers i=1 to n.
0117The secret key decryption means <b>310</b> inputs <br />E<sub>i</sub><sup>(j)</sup>=K′<sub>i</sub><sup>(j)</sup>−[1/x<sup>(j)</sup>]K<sub>i</sub><sup>(j) </sup><br /> to the data decryption means <b>313</b>.
0118The data decryption means <b>313</b> calculates <br />e<sub>i</sub><sup>(j)</sup>=Φ(E<sub>i</sub><sup>(j)</sup>) <br />(K<sub>i</sub><sup>(j+1)</sup>,K<sub>i</sub>′<sup>(j+1)</sup>,c<sub>i</sub><sup>(j+1)</sup>,S<sub>i</sub><sup>(j+1)</sup>,S<sub>i</sub>′<sup>(j+1)</sup>,T<sub>i</sub>′<sup>(j+1)</sup>,P<sub>i</sub><sup>(j+1)</sup>)=dec[e<sub>i</sub><sup>(j)</sup>](c<sub>i</sub><sup>(j)</sup>)
0119The hash value decryption means <b>312</b> calculates <br />H<sub>i</sub><sup>(j)</sup>=S′<sub>i</sub><sup>(j)</sup>−[1/x<sup>(j)</sup>]S<sub>i</sub><sup>(j) </sup>
0120The concatenated data decryption means <b>314</b> calculates <br />T′<sub>i</sub><sup>(j+1)</sup>=T′<sub>i</sub><sup>(j)</sup>−[1/x<sup>(j)</sup>]T<sub>i</sub><sup>(j) </sup>
0121The obtained data sequence is <br />(K<sub>i</sub><sup>(j+1)</sup>,K<sub>i</sub>′<sup>(j+1)</sup>,c<sub>i</sub><sup>(j+1)</sup>,S<sub>i</sub><sup>(J+1)</sup>,S<sub>i</sub>′<sup>(j+1)</sup>,T<sub>i</sub>′<sup>(j+1)</sup>,P<sub>i</sub><sup>(j+1)</sup>,H<sub>i</sub><sup>(j)</sup>,T′<sub>i</sub><sup>(j+1)</sup>).
0122The substitution means <b>311</b> uniformly selects substitution π[j]( ) from [1, . . . ,n] to [1, . . . ,n] and executes the following substitution processing. <br />K<sub>i</sub><sup>(j+1)</sup>=Kπ[j](i)<sup>(j+1) </sup><br />K′<sub>i</sub><sup>(j+1)</sup>=K′π[j](i)<sup>(j+1) </sup><br />c<sub>i</sub><sup>(j+1)</sup>=cπ[j](i)<sup>(j+1) </sup><br />S<sub>i</sub><sup>(j+1)</sup>=Sπ]j](i)<sup>(j+1) </sup><br />S′<sub>i</sub><sup>(j+1)</sup>=S′π[j](i)<sup>(j+1) </sup><br />T′<sub>i</sub><sup>(j+1)</sup>=T′π[j](i)<sup>(j+1) </sup><br />P<sub>i</sub><sup>(J+1)</sup>=Pπ[j](i)<sup>(j+1) </sup><br />H<sub>i</sub><sup>(j)</sup>=Hπ[j](i)<sup>(j) </sup><br />T′<sub>i</sub><sup>(J+1)</sup>=T′π[j](i)<sup>(j+1) </sup>
0123The hash value decryption authenticity proof means <b>315</b> generates a proof (hash value decryption authenticity proof text) to prove that H<sub>i</sub><sup>(j) </sup>is generated correctly.
0124The concatenated data decryption authenticity proof means <b>316</b> generates a proof (concatenated data decryption authenticity proof text) to prove that T′<sub>i</sub><sup>(j+1) </sup>is generated correctly.
0125The proof can be done by using, e.g., a method of reference “An Implementation of a Universally Verifiable Electronic Voting Scheme based on Shuffling, Financial Cryptography 2002”.
0126For all i (i=1, . . . ,m), the hash value verification means <b>317</b> confirms that <br />Φ(H<sub>i</sub><sup>(j)</sup>=Hash(K<sub>i</sub><sup>(j+1)</sup>,K<sub>i</sub>′<sup>(j+1)</sup>,c<sub>i</sub><sup>(j+1)</sup>,S<sub>i</sub><sup>(j+1)</sup>,S<sub>i</sub>′<sup>(j+1)</sup>, T<sub>i</sub><sup>(J+1)</sup>,T<sub>i</sub>′<sup>(j+1)</sup>,P<sub>i</sub><sup>(J+1) </sup><br /> holds. If i for which the equation does not hold is present, the hash value unacceptance authenticity proof means <b>318</b> clarifies π[j](i),E<sub>i</sub><sup>(j) </sup>for i and generates a zero-knowledge proof (hash value unacceptance authenticity proof text) to prove that E<sub>i</sub><sup>(j) </sup>is correctly generated. The number of ciphertexts decreases here, too (processing <b>319</b>). The number after the decrease is also represented by n. The ciphertexts are assigned numbers i=1 to n.
0127Finally, the output data sequence <b>107</b> (K<sub>i</sub><sup>(j+1)</sup>,K<sub>i</sub>′<sup>(j+1)</sup>,c<sub>i</sub><sup>(j+1)</sup>,S<sub>i</sub><sup>(j+1)</sup>,S<sub>i</sub>′<sup>(j+1)</sup>,T<sub>i</sub><sup>(j+1)</sup>,T′<sub>i</sub><sup>(j+1)</sup>,P<sub>i</sub><sup>(j+1)</sup>,H<sub>i</sub><sup>(j)</sup>) is sent to the next substitution/decryption apparatus S<sup>(j+1)</sup>.
0128The hash value decryption authenticity proof text, concatenated data decryption authenticity proof text, and the hash value unacceptance authenticity proof text are sent to the verification apparatus <b>109</b> as the authenticity proof text <b>108</b>.
0129When the processing is ended for all the substitution/decryption apparatuses S<sup>(j) </sup>(j=1, . . . ,m), a plaintext <b>111</b> [M<sub>i</sub>]<sub>i=1, . . . , n </sub>in which data are shuffled is obtained.
0000[Processing by Verification Apparatus]
0130The verification apparatus <b>109</b> of the verifier receives
0131the authenticity proof text <b>108</b> containing the hash value decryption authenticity proof text <b>401</b> (abbreviated as a hash value proof text in <figref idref="DRAWINGS">FIG. 4</figref>), concatenated data decryption authenticity proof text <b>403</b> (abbreviated as a concatenation proof text in <figref idref="DRAWINGS">FIG. 4</figref>), and hash value unacceptance authenticity proof text <b>400</b> (abbreviated as an unacceptance proof text in <figref idref="DRAWINGS">FIG. 4</figref>),
0132the input data sequence <b>105</b>,
0133the output data sequence <b>107</b>, and
0134the entire random number knowledge proof text <b>110</b>.
0135For all i, a verification means <b>500</b> for verifying the entire random number knowledge proof text <b>110</b> confirms that <br />γ′<sub>i</sub><sup>(0)</sup>=Hash(K<sub>i</sub><sup>(1)</sup>,K<sub>i</sub>′<sup>(1)</sup>,c<sub>i</sub><sup>(1)</sup>,S<sub>i</sub><sup>(1)</sup>,S<sub>i</sub>′<sup>(1)</sup>,T<sub>i</sub><sup>(1)</sup>,T<sub>i</sub>′<sup>(1)</sup>, [α′<sub>i</sub><sup>(0)</sup>]G<sub>i</sub><sup>(1)</sup>+[γ′<sub>i</sub><sup>(0)</sup>]G) <br /> holds.
0136For all j=1, . . . ,m, the following calculation and verification are done sequentially. For all i (i=1, . . . ,n), the verification means <b>402</b> for executing secret key knowledge verification processing confirms <br />γ<sub>i</sub><sup>(j)</sup>=Hash(K<sub>i</sub><sup>(j)</sup>,K<sub>i</sub>′<sup>(j)</sup>,c<sub>i</sub><sup>(j)</sup>,S<sub>i</sub><sup>(j)</sup>,S<sub>i</sub>′<sup>(j)</sup>,T<sub>i</sub><sup>(j)</sup>,T<sub>i</sub>′<sup>(j)</sup>, [α<sub>i</sub><sup>(j)</sup>]X<sup>(j)</sup>+[γ<sub>i</sub><sup>(j)</sup>]K<sub>i</sub><sup>(j)</sup>)
0137The verification means <b>404</b> for executing secret random number knowledge verification processing confirms <br />γ′<sub>i</sub><sup>(j)</sup>=Hash(K<sub>i</sub><sup>(j)</sup>,K<sub>i</sub>′<sup>(j)</sup>,c<sub>i</sub><sup>(j)</sup>,S<sub>i</sub><sup>(j)</sup>,S<sub>i</sub>′<sup>(j)</sup>,T<sub>i</sub><sup>(j)</sup>,T<sub>i</sub>′<sup>(j)</sup>, [α′<sub>i</sub><sup>(j)</sup>]X<sup>(j)</sup>+[γ′<sub>i</sub><sup>(j)</sup>]T<sub>i</sub><sup>(j)</sup>) <br /> For only i for which the equation does not hold, the subsequent processing is not executed.
0138The verification means <b>406</b> for executing hash value decryption authenticity verification processing verifies that [H<sub>i</sub><sup>(j)</sup>]<sub>i=1, . . . n </sub>is correctly generated (a method corresponding to proof and, for example, the method of the above-described reference is used).
0139The verification means <b>407</b> for concatenated data decryption authenticity verification processing verifies that [T′<sub>i</sub><sup>(j+1)</sup>]<sub>i=1, . . . n </sub>is correctly generated (a method corresponding to proof and, for example, the method of the above-described reference is used).
0140For all i (i=1, . . . ,n), the comparison means <b>408</b> for executing hash value coincidence verification processing confirms that
0000Φ(H<sub>i</sub><sup>(j)</sup>)=Hash(K<sub>i</sub><sup>(j+1)</sup>,K<sub>i</sub>′<sup>(j+1)</sup>,c<sub>i</sub><sup>(j+1)</sup>,S<sub>i</sub><sup>(j+1)</sup>,S<sub>i</sub>′<sup>(j+1)</sup>, T<sub>i</sub><sup>(j+1)</sup>,T<sub>i</sub>′<sup>(j+1)</sup>,P<sub>i</sub><sup>(j+1)</sup>)
0141holds. If i for which the equation does not hold is present, the verification means <b>409</b> for executing hash value unacceptance authenticity verification processing verifies that π[j](i),E<sub>i</sub><sup>(j) </sup>for i is clarified, and equation E<sub>i</sub><sup>(j) </sup>is correctly generated and confirms that c π[j](i)<sup>(j) </sup>is correctly decrypted.
0142The verification means <b>405</b> for executing authenticity determination outputs acceptance when, for all data for which both the verification means <b>402</b> for executing secret key knowledge verification processing and the verification means <b>404</b> for executing secret random number knowledge verification processing output acceptance, both the verification means <b>406</b> for executing hash value decryption authenticity verification processing and the verification means <b>407</b> for executing concatenated data decryption authenticity processing means <b>407</b> output acceptance, and the comparison means <b>408</b> for executing hash value coincidence verification processing outputs acceptance, or the comparison means <b>408</b> for executing hash value coincidence verification processing outputs unacceptance while the verification means <b>409</b> for executing hash value unacceptance authenticity verification processing outputs acceptance, and the output data sequence contains only data corresponding to the elements accepted by the secret key knowledge verification processing, secret random number knowledge verification processing, and hash value coincidence verification processing and all the data. Otherwise, unacceptance is output.
2 Second Embodiment
00002.1
0143The outline of the second embodiment will be described with reference to <figref idref="DRAWINGS">FIGS. 1, 5</figref>, <b>6</b>, and <b>7</b>.
0144As shown in <figref idref="DRAWINGS">FIG. 1</figref>, a mix-net system according to this embodiment includes a plurality of participant apparatuses <b>103</b>, a consolidating apparatus <b>104</b>, a plurality to substitution/decryption apparatuses <b>112</b>, and a verification apparatus <b>109</b>. The participant apparatus <b>103</b> has an arrangement shown in <figref idref="DRAWINGS">FIG. 5</figref>, which is the same as the participant apparatus of the first embodiment except that the apparatus of the second embodiment has neither knowledge concatenation means <b>208</b> nor random number knowledge proof means <b>210</b>. The consolidating apparatus <b>104</b> is also the same as that of the first embodiment.
0000[Substitution/Decryption Apparatus]
0145As shown in <figref idref="DRAWINGS">FIG. 6</figref>, the substitution/decryption apparatus <b>112</b> has a data division means <b>723</b>, secret key knowledge verification means <b>707</b>, secret key decryption means <b>710</b>, data decryption means <b>713</b>, hash value decryption means <b>712</b>, hash value verification means <b>717</b>, output data sequence generation means <b>711</b>, redundant data delete confirmation means <b>720</b>, hash value decryption authenticity proof means <b>715</b>, hash value unacceptance authenticity proof means <b>718</b>, and output means.
0146The data division means <b>723</b> divides each element of an input data sequence <b>105</b> input from the consolidating apparatus <b>104</b> or another substitution/decryption apparatus into a secret key <b>702</b> of secret key cryptography, which is encrypted by public key cryptography, data <b>703</b> encrypted by secret key cryptography, a hash value <b>704</b> encrypted by public key cryptography, and a proof text <b>701</b> of knowledge of the encrypted secret key.
0147The output data sequence generation means <b>711</b> generates a data sequence which contains, as sequence elements, only output data for which acceptance is output from all of the hash value verification means <b>717</b> and secret key knowledge verification means <b>707</b> and which are corresponding in a sense of being generated from the same element data of the input data sequence <b>105</b>. The output data sequence generation means <b>711</b> also uniformly shuffles the elements at random to form an output data sequence <b>107</b>. When the elements of the output data sequence <b>107</b> are redundant, and it is confirmed that the redundant data is deleted by subsequent processing, the redundant data delete confirmation means <b>720</b> outputs acceptance. Otherwise, unacceptance is output.
0148When the decrypted concatenated data contained in each element of the output data sequence <b>107</b> is always data obtained by decrypting encrypted concatenated data contained in a certain element of the input data sequence <b>105</b>, and the hash value verification means <b>717</b> outputs unacceptance, the hash value unacceptance authenticity proof means <b>715</b> generates a hash value unacceptance authenticity proof text which proves that output of unacceptance is authentic. The output means creates an authenticity proof text <b>108</b> from the hash value decryption authenticity proof text and hash value unacceptance authenticity proof text and outputs the authenticity proof text <b>108</b> and the output data sequence <b>107</b> output from the output data sequence generation means <b>711</b>. The remaining components are the same as in the substitution/decryption apparatus of the first embodiment.
0000[Verification Apparatus]
0149As shown in <figref idref="DRAWINGS">FIG. 7</figref>, the verification apparatus <b>109</b> has a secret key knowledge verification means <b>802</b>, hash value decryption authenticity verification means <b>806</b>, hash value coincidence verification means <b>808</b>, hash value unacceptance authenticity verification means <b>809</b>, and authenticity determination means <b>805</b>.
0150For, of the elements of the input data sequence <b>105</b>, all elements accepted by the secret key knowledge verification means <b>402</b>, the authenticity determination means <b>805</b> outputs acceptance if all the following conditions are satisfied. Otherwise, unacceptance is output. <ul id="ul0002" list-style="none"><li id="ul0002-0001" num="0151"> (A) The hash value decryption authenticity verification means <b>806</b> outputs acceptance. </li><li id="ul0002-0002" num="0152"> (B) The hash value coincidence verification means <b>808</b> outputs acceptance, or the hash value coincidence verification means <b>808</b> outputs unacceptance while the hash value unacceptance authenticity verification means <b>809</b> outputs acceptance. </li><li id="ul0002-0003" num="0153"> (C) The output data sequence <b>107</b> contains only data corresponding to the elements accepted by the secret key knowledge verification means <b>802</b> and hash value coincidence verification means <b>808</b> and all these data. </li></ul>
0154The remaining components are the same as in the verification apparatus of the first embodiment.
0155The operation of the mix-net system is the same as in the first embodiment, and a description thereof will be omitted.
00002.2 Detailed Example
0156The second embodiment will be described in detail with reference to <figref idref="DRAWINGS">FIGS. 1, 5</figref>, <b>6</b>, and <b>7</b>.
0000[Initial Setting]
0157An initial setting apparatus <b>100</b> determines and publishes a bit length A of a plaintext, a safety variable L, a prime number q whose bit length is larger than L by 5, an elliptic curve C having the order q, a point G on C, a cryptographic hash function Hash( ) having the output bit length L, secret key cryptography using a key with the length L, an encryption function enc[e]( ) and decryption function dec[e] of the secret key cryptography, a function Ψ( ) from a bit sequence with L bits to a point on C, and mapping Φ( ) from a point on C to a bit sequence with L bits.
0000[Initial Setting of Substitution/Decryption Apparatus]
0158All the substitution/decryption apparatuses S<sup>(j) </sup>(j=1, . . . ,m) execute the next initial setting processing. An initial setting means <b>721</b> (<figref idref="DRAWINGS">FIG. 6</figref>) in each of substitution/decryption apparatuses S<sup>(j) </sup>uniformly selects a private key <b>106</b> x<sup>(j)</sup>εZ/qZ at random and saves the private key in the substitution/decryption apparatus S<sup>(j)</sup>. In addition, the initial setting means <b>721</b> generates and publishes a public key <b>101</b> X<sup>(j)</sup>=[x<sup>(j)</sup>]G. The initial setting means <b>721</b> in each substitution/decryption apparatus S<sup>(j) </sup>uniformly selects r<sup>(j)</sup>εZ/qZ at random and calculates <br />γ<sup>(j)</sup>=Hash(G, [r<sup>(j)</sup>]X<sup>(j)</sup>) and <br />α<sup>(j)</sup>=r<sup>(j)</sup>−γ<sup>(j)</sup>r<sup>(j) </sup>mod q <br /> and publishes γ<sup>(j) </sup>and α<sup>(j) </sup>as a zero-knowledge proof text <b>722</b> of knowledge of x<sup>(j)</sup>. <br /> [Ciphertext Generation of Participant Apparatus]
0159For i=1, . . . ,n, a participant apparatus <b>103</b> U<sub>i </sub>(<figref idref="DRAWINGS">FIG. 5</figref>) determines a plaintext <b>102</b> M<sub>i </sub>having the bit length Λ. As first data <b>614</b>, each participant apparatus U<sub>i </sub><b>103</b> generates data containing c<sub>i</sub><sup>(M+1)</sup>=M<sub>i </sub>and arbitrary data <b>603</b> (each containing arbitrary L-bit character strings K<sub>i</sub><sup>(m+1)</sup>, K<sub>i</sub>′<sup>(m+1)</sup>, S<sub>i</sub><sup>(m+1)</sup>, S<sub>i</sub>′<sup>(m+1)</sup>, and P<sub>i</sub><sup>(m+1)</sup>). In addition, for j=1, . . . ,m, a key generation means <b>604</b> uniformly selects elements r[1]<sub>i</sub><sup>(j)</sup>, r[2]<sub>i</sub><sup>(j)</sup>, and r[3]<sub>i</sub><sup>(j) </sup>of Z/qZ and a point E<sub>i</sub><sup>(j) </sup>on C at random.
0160Then, a key encryption means <b>605</b>, data encryption means <b>606</b>, hash value encryption means <b>607</b>, and output means <b>615</b> execute following processing <b>613</b> repeatedly in the order of j=m, (m−1), . . . , and 1.
0161As in the first embodiment, as the arbitrary character string, a random number, a number unique to a session, or a date/time is sometimes selected. When a random number is used, the participant apparatus can confirm the presence of its plaintext from the final decrypted text set. When a number unique to a session or a date/time is used, it can be recognized that a ciphertext used for another session is not reused.
0162Secret Key Encryption Processing by Key Encryption Means <b>605</b>
0163To encrypt a secret key e<sub>i</sub><sup>(j)</sup>, the key encryption means <b>605</b> obtains E<sub>i</sub><sup>(j) </sup>which satisfies <br />e<sub>i</sub><sup>(j)</sup>=Φ(E<sub>i</sub><sup>(j)</sup>) <br /> and calculates <br />(K<sub>i</sub><sup>(j)</sup>,K<sub>i</sub>′<sup>(j)</sup>)=([r[1]<sub>i</sub><sup>(j)</sup>]X<sup>(j)</sup>, [r[1]<sub>i</sub><sup>(j)</sup>]G+E<sub>i</sub><sup>(j)</sup>) <br /> The calculation result K<sub>i</sub><sup>(j)</sup>,K<sub>i</sub>′<sup>(j) </sup>is input to the output means <b>615</b>.
0164Secret Key Knowledge Proof Text Generation Processing by Key Encryption Means <b>605</b><br />γ<sup>(j)</sup>=Hash(K<sub>i</sub><sup>(j)</sup>,K<sub>i</sub>′<sup>(j)</sup>,c<sub>i</sub><sup>(j)</sup>,S<sub>i</sub><sup>(j)</sup>,S<sub>i</sub>′<sup>(j)</sup>,[r[3]<sub>i</sub><sup>(j)</sup>]X<sup>(j)</sup>), <br />α<sub>i</sub><sup>(j)</sup>=r[3]<sub>i</sub><sup>(j)</sup>−γ<sub>i</sub><sup>(j)</sup>r[1]<sub>i</sub><sup>(j) </sup>mod q, and <br />P<sub>i</sub><sup>(j)</sup>=[γ<sub>i</sub><sup>(j)</sup>,α<sub>i</sub><sup>(j)</sup>]<br /> are calculated, and P<sub>i</sub><sup>(1) </sup>and P<sub>i</sub><sup>(0) </sup>are sent to the consolidating apparatus <b>104</b> as a secret key knowledge proof text <b>612</b>.
0165Data Encryption Processing by Data Encryption Means <b>606</b><br />e<sub>i</sub><sup>(j)</sup>=Φ(E<sub>i</sub><sup>(j)</sup>) <br /> and <br />c<sub>i</sub><sup>(j)</sup>=enc[e<sub>i</sub><sup>(j)</sup>](K<sub>i</sub><sup>(j+1)</sup>,K<sub>i</sub>′<sup>(j+1)</sup>,c<sub>i</sub><sup>(j+1)</sup>,S<sub>i</sub><sup>(j+1)</sup>,S<sub>i</sub>′<sup>(j+1)</sup>, P<sub>i</sub><sup>(j+1)</sup>) <br /> are calculated, and c<sub>i</sub><sup>(j) </sup>is input to the output means <b>215</b>.
0166Hash Value Encryption Processing by Hash Value Encryption Means <b>607</b><br />(S<sub>i</sub><sup>(j)</sup>,S<sub>i</sub>′<sup>(j)</sup>)=([r[2]<sub>i</sub><sup>(j)</sup>]X<sup>(j)</sup>,[r[2]<sub>i</sub><sup>(j)</sup>]G+Ψ(Hash (K<sub>i</sub><sup>(j+1)</sup>,K<sub>i</sub>′<sup>(j+1)</sup>,c<sub>i</sub><sup>(j+1)</sup>,S<sub>i</sub><sup>(j+1)</sup>,S<sub>i</sub>′<sup>(j+1)</sup>, P<sub>i</sub><sup>(j+1)</sup>))) <br /> is calculated to input S<sub>i</sub><sup>(j)</sup>,S<sub>i</sub>′<sup>(j) </sup>is input to the output means <b>615</b>.
0167Processing by Output Means <b>615</b>
0168Data <b>614</b>′ (K<sub>i</sub><sup>(j)</sup>,K<sub>i</sub>′<sup>(j)</sup>,c<sub>i</sub><sup>(j)</sup>,S<sub>i</sub><sup>(j)</sup>,S<sub>i</sub>′<sup>(j)</sup>) is generated from the inputs K<sub>i</sub><sup>(j) </sup>and K<sub>i</sub>′<sup>(j) </sup>from the key encryption means <b>205</b>, the input c<sub>i</sub><sup>(j) </sup>from the data encryption means <b>206</b>, and the inputs S<sub>i</sub><sup>(j) </sup>and S<sub>i</sub>′<sup>(j) </sup>from the hash value encryption means <b>207</b>. If j≠1, the data <b>614</b>′ is fed back as the data <b>614</b>. If j=1, (K<sub>i</sub><sup>(1)</sup>,K<sub>i</sub>′<sup>(1)</sup>,c<sub>i</sub><sup>(1)</sup>,S<sub>i</sub><sup>(1)</sup>,S<sub>i</sub>′<sup>(1)</sup>) is output as a ciphertext <b>211</b>.
0169That is, the participant apparatus <b>103</b> U<sub>i </sub>sends the ciphertext <b>611</b> (K<sub>i</sub><sup>(1)</sup>,K<sub>i</sub>′<sup>(1)</sup>,c<sub>i</sub><sup>(1)</sup>,S<sub>i</sub><sup>(1)</sup>,S<sub>i</sub>′<sup>(1)</sup>) and the proof text P<sub>i</sub><sup>(1)</sup>,P<sub>i</sub><sup>(0) </sup>to the consolidating apparatus <b>104</b>.
0000[Ciphertext Verification by Consolidating Apparatus]
0170The consolidating apparatus <b>104</b> consolidates data collected from the participant apparatuses and sends them to the first substitution/decryption apparatus. K<sub>i</sub><sup>(j)</sup>,K<sub>i</sub>′<sup>(j)</sup>,c<sub>i</sub><sup>(j)</sup>,S<sub>i</sub><sup>(j)</sup>,S<sub>i</sub>′<sup>(j)</sup>, P<sub>i</sub><sup>(j) </sup>is generally different from the above-described value except when j=1.
0000[Shuffle and Decryption of Ciphertext by Substitution/Decryption Apparatus]
0171Sequentially for j=1, . . . ,m, the substitution/decryption apparatus <b>112</b> S<sup>(j) </sup>executes the following calculation and verification.
0172The input data sequence <b>105</b> containing the encrypted secret key <b>702</b> (abbreviated as a secret key ciphertext in <figref idref="DRAWINGS">FIG. 6</figref>) of secret key cryptography <br />K<sub>i</sub><sup>(j)</sup>,K<sub>i</sub>′<sup>(j) </sup><br /> the encrypted data <b>703</b> (abbreviated as a data ciphertext in <figref idref="DRAWINGS">FIG. 6</figref>) <br />c<sub>i</sub><sup>(j) </sup><br /> the encrypted hash value <b>704</b> (abbreviated as a hash value ciphertext in <figref idref="DRAWINGS">FIG. 6</figref>) <br />S<sub>i</sub><sup>(j)</sup>,S<sub>i</sub>′<sup>(j) </sup><br /> and the secret key knowledge proof text <b>701</b> (abbreviated as a key knowledge proof text in <figref idref="DRAWINGS">FIG. 6</figref>) <br />P<sub>i</sub><sup>(j) </sup><br /> and <br /> private key <b>106</b><br />x<sup>(j) </sup><br /> is input. The input data sequence <b>105</b> is divided into the elements <b>701</b> to <b>704</b> by the data division means <b>723</b>.
0173The following processing is executed for all i (i=1, . . . ,n).
0174The secret key knowledge verification means <b>707</b> confirms <br />γ<sub>i</sub><sup>(j)</sup>=Hash(K<sub>i</sub><sup>(j)</sup>,K<sub>i</sub>′<sup>(j)</sup>,c<sub>i</sub><sup>(j)</sup>,S<sub>i</sub><sup>(j)</sup>,S<sub>i</sub>′<sup>(j)</sup>, [α<sub>i</sub><sup>(j)</sup>]X<sup>(j)</sup>+[γ<sub>i</sub><sup>(j)</sup>]K<sub>i</sub><sup>(j)</sup>) <br /> For i for which the equation does not hold, the data is not added to the final output data sequence (processing <b>709</b>).
0175The number of ciphertexts decreases here. The number after the decrease is also represented by n. The ciphertexts are assigned numbers i=1 to n.
0176The secret key decryption means <b>710</b> calculates <br />E<sub>i</sub><sup>(j)</sup>=K′<sub>i</sub><sup>(j)</sup>−[1/x<sup>(j)</sup>]K<sub>i</sub><sup>(j)</sup>.
0177The data decryption means <b>313</b> calculates <br />e<sub>i</sub><sup>(j)</sup>=(E<sub>i</sub><sup>(j)</sup>) <br />(K<sub>i</sub><sup>(j+1)</sup>,K<sub>i</sub>′<sup>(j+1)</sup>,c<sub>i</sub><sup>(j+1)</sup>,S<sub>i</sub><sup>(j+1)</sup>,S<sub>i</sub>′<sup>(j+1)</sup>,P<sub>i</sub><sup>(j+1)</sup>)=dec[e<sub>i</sub><sup>(j)</sup>](c<sub>i</sub><sup>(j)</sup>) <br /> The obtained data sequence is <br />(K<sub>i</sub><sup>(J+1)</sup>,K<sub>i</sub>′<sup>(j+1)</sup>,c<sub>i</sub><sup>(j+1)</sup>,S<sub>i</sub><sup>(j+1)</sup>,S<sub>i</sub>′<sup>(j+1)</sup>,P<sub>i</sub><sup>(j+1)</sup>).
0178The substitution means <b>711</b> uniformly selects substitution π[j]( ) from [1, . . . ,n] to [1, . . . ,n] and executes the following substitution processing. <br />K<sub>i</sub><sup>(j+1)</sup>=Kπ[j](i)<sup>(j+1) </sup><br />K′<sub>i</sub><sup>(j+1)</sup>=K′π[j](i)<sup>(j+1) </sup><br />c<sub>i</sub><sup>(j+1)</sup>=cπ[j](i)<sup>(j+1) </sup><br />S<sub>i</sub><sup>(j+1)</sup>=Sπ[j](i)<sup>(j+1) </sup><br />S′<sub>i</sub><sup>(j+1)</sup>=S′π[j](i)<sup>(j+1) </sup><br />P<sub>i</sub><sup>(j+1)</sup>=Pπ[j](i)<sup>(j+1) </sup>
0179The hash value decryption means <b>712</b> and substitution means <b>711</b> execute operation given by <br />H<sub>i</sub><sup>(j)</sup>=S′π[j](i)<sup>(j)</sup>−[1/x<sup>(j)</sup>]Sπ[j](i)<sup>(j) </sup>
0180The hash value decryption authenticity proof means <b>715</b> generates a proof (hash value decryption authenticity proof text) to prove that H<sub>i</sub><sup>(j) </sup>is generated correctly. For this proof, the method of the above-described reference is used.
0181For all i (i=1, . . . ,m), the hash value verification means <b>717</b> confirms that <br />Φ(H<sub>i</sub><sup>(j)</sup>)=Hash(K<sub>i</sub><sup>(j+1)</sup>,K<sub>i</sub>′<sup>(j+1)</sup>,c<sub>i</sub><sup>(j+1)</sup>,S<sub>i</sub><sup>(j+1)</sup>,S<sub>i</sub>′<sup>(j+1)</sup>, P<sub>i</sub><sup>(j+1)</sup>) <br /> holds.
0182If i for which the equation does not hold is present, the hash value unacceptance authenticity proof means <b>718</b> clarifies π[j](i),E<sub>i</sub><sup>(j) </sup>for i and generates a zero-knowledge proof (hash value unacceptance authenticity proof text) to prove that E<sub>i</sub><sup>(j) </sup>is correctly generated.
0183The number of ciphertexts decreases here, too (processing <b>719</b>). The number after the decrease is also represented by n. The ciphertexts are assigned numbers i=1 to n.
0184The redundant data delete confirmation means <b>720</b> confirms that, for i=1, . . . n, the sets of (K<sub>i</sub><sup>(j+1)</sup>K<sub>i</sub>′<sup>(j+1)</sup>,c<sub>i</sub><sup>(j+1)</sup>,S<sub>i</sub><sup>(j+1)</sup>,S<sub>i</sub>′<sup>(j+1)</sup>,P<sub>i</sub><sup>(j+1)</sup>are not redundant. if redundant sets are present, sets except one are erased. The number of ciphertexts decreases here, too. The number after the decrease is also represented by n. The ciphertexts are assigned numbers i=1 to n.
0185Finally, the output data sequence <b>107</b><br />K<sub>i</sub><sup>(j+1)</sup>,K<sub>i</sub>′<sup>(j+1)</sup>,c<sub>i</sub><sup>(j+1)</sup>,S<sub>i</sub><sup>(j+1)</sup>,S<sub>i</sub>′<sup>(j+1)</sup>,P<sub>i</sub><sup>(j+1)</sup>,H<sub>i</sub><sup>(j) </sup><br /> is sent to the next substitution/decryption apparatus S<sup>(j+1)</sup>.
0186The hash value decryption authenticity proof text and the hash value unacceptance authenticity proof text are sent to the verification apparatus <b>109</b> as the authenticity proof text <b>108</b>.
0187When the processing is ended for all the substitution/decryption apparatuses S<sup>(j) </sup>(j=1, . . . ,m), a plaintext <b>111</b> [M<sub>i</sub>]<sub>i=1, . . . n </sub>in which data are shuffled is obtained.
0000[Processing by Verification Apparatus]
0188The verification apparatus <b>109</b> receives the authenticity proof text <b>108</b> containing a hash value decryption authenticity proof text <b>801</b> (abbreviated as a hash value proof text in <figref idref="DRAWINGS">FIG. 7</figref>) and a hash value unacceptance authenticity proof text <b>800</b> (abbreviated as an unacceptance proof text in <figref idref="DRAWINGS">FIG. 7</figref>), the input data sequence <b>105</b>, and the output data sequence <b>107</b>.
0189For all j=1, . . . ,m, the following calculation and verification are done sequentially. For all i (i=1, . . . ,n), the secret key knowledge verification means <b>802</b> confirms
0000γ<sub>i</sub><sup>(j)</sup>=Hash(K<sub>i</sub><sup>(j)</sup>,K<sub>i</sub>′<sup>(j)</sup>,c<sub>i</sub><sup>(j)</sup>,S<sub>i</sub><sup>(j)</sup>,S<sub>i</sub>′<sup>(j)</sup>, [α<sub>i</sub><sup>(j)</sup>]X<sup>(j)</sup>+[γ<sub>i</sub><sup>(j)</sup>]K<sub>i</sub><sup>(j)</sup>)
0000For only i for which the equation does not hold, the subsequent processing is not executed.
0190The hash value decryption authenticity verification means <b>806</b> verifies that [H<sub>i</sub><sup>(j)</sup>]<sub>i=1, . . . n </sub>is correctly generated (a method corresponding to proof and, for example, the method of the above-described reference is used).
0191For all i (i=1, . . . ,n), the comparison means <b>808</b> for executing hash value coincidence verification processing confirms that <br />Φ(H<sub>i</sub><sup>(j)</sup>)=Hash(K<sub>i</sub><sup>(j+1)</sup>,K<sub>i</sub>′<sup>(j+1)</sup>,c<sub>i</sub><sup>(j+1)</sup>,S<sub>i</sub><sup>(j+1)</sup>,S<sub>i</sub>′<sup>(j+1)</sup>, P<sub>i</sub><sup>(j+1)</sup>) <br /> holds.
0192If i for which the equation does not hold is present, the hash value unacceptance authenticity verification means <b>809</b> verifies that π[j](i),E<sub>i</sub><sup>(j) </sup>for i is clarified, and equation E<sub>i</sub><sup>(j) </sup>is correctly generated and confirms that cπ[j](i)<sup>(j) </sup>is correctly decrypted.
0193The verification means <b>805</b> for executing authenticity determination outputs acceptance when, for all data for which both secret key knowledge verification processing and secret random number knowledge verification processing output acceptance, both hash value decryption authenticity verification processing outputs acceptance while hash value coincidence verification processing outputs acceptance, or hash value coincidence verification processing outputs unacceptance while hash value unacceptance authenticity verification processing outputs acceptance, and the output data sequence contains only data corresponding to the elements accepted by the secret key knowledge verification processing, secret random number knowledge verification processing, and hash value coincidence verification processing and all the data except redundant sets in [K<sub>i</sub><sup>(j+1)</sup>,K<sub>i</sub>′<sup>(j+1)</sup>,c<sub>i</sub><sup>(j+1)</sup>,S<sub>i</sub><sup>(j+1)</sup>,S<sub>i</sub>′<sup>(j+1)</sup>, P<sub>i</sub><sup>(j+1)</sup>]. Otherwise, unacceptance is output.
0000[Reason Why Present Invention is Effective]
0194To prove that the decryption and substitution dec[e<sub>i</sub><sup>(j)</sup>](cπ[j](i)<sup>(j)</sup>) of data by the substitution/decryption apparatus is authentic, that the hash value, dec[e<sub>i</sub><sup>(j)</sup>](cπ[j](i)<sup>(j)</sup>), and the decryption result of the ciphertext by the public key generated by the participant apparatus <b>103</b> equal is proved. This proof processing is hash value decryption proof processing. That the proof processing is executed in an open verification enable form is the main reason why the present invention allows open verification.
0195However, the effect of the above-described proof is obtained only when the participant apparatus correctly generates a hash value ciphertext. The substitution/decryption apparatus must prove the authenticity of its operation without the above generation.
0196First, it is confirmed by hash value verification processing whether the participant apparatus has generated a hash value ciphertext by authentic processing. If no authentic processing is executed, it is proved by hash value unacceptance authenticity proof processing that the participant apparatus is unauthorized. With this processing, the authenticity of processing of the substitution/decryption apparatus is proved.
0197However, the processing of the participant apparatus is sometimes unauthorized by illicit processing of another participant apparatus. That is, data of one participant apparatus is copied by another participant apparatus which generates appropriate data on the basis of the ciphertext. In this case, the substitution/decryption apparatus decrypts the ciphertext of the participant apparatus and proves the authenticity of the decryption because the participant apparatus is unauthentic. This proof may be an attack on the ciphertext of the participant apparatus.
0198If a participant apparatus illicitly processes its ciphertext, the attack occurs as a natural result. However, if the data is copied by a third party, this attack must be prevented. As a defensive measure, secret key knowledge proof processing is executed. With this processing, when an illicit ciphertext is created from the ciphertext of another person, processing is rejected first by substitution/decryption processing.
0199When the ciphertext of another person is copied and illicitly processed, processing is rejected by the substitution/decryption apparatus, as described above. However, if the ciphertext is simply copied and used without any particular processing, processing is not rejected by the above-described method. If this is permitted, the copied ciphertext is decrypted a plurality of number of times. When such a phenomenon occurs, the contents of the copied ciphertext can be known by finding a plurality of identical plaintexts from the finally decrypted plaintexts. Processing of preventing such an attack on privacy is the proof processing for concatenated data in the first embodiment or the processing of deleting redundant data in the second embodiment.
0200If concatenated data is not generated by the apparatus, proof cannot be created finally. Hence, simple copy can be prevented. Deleting redundant data corresponds to processing of directly deleting copied data.
0201The participant apparatus sometimes inputs a character string such as a random number, a number unique to a session, or a date/time in addition to a plaintext. These values are decrypted finally. Various things can be confirmed by using the decrypted character strings. For example, when a random number is used, the participant apparatus can confirm the presence of its plaintext from the final decrypted text set. When a number unique to a session or a date/time is input, it can be recognized that a ciphertext used for another session is not reused.
Contents5
6 sheets
Sheet 1 Sheet 2 Sheet 3 Sheet 4 Sheet 5 Sheet 6
Every citation, both ways
| Document | Relation | Office | Cited during |
|---|---|---|---|
| US9281941B2 | Cited by | United States of America | Applicant |
| US9608817B2 | Cited by | United States of America | Applicant |
| US10333696B2 | Cited by | United States of America | Applicant |
| US8861716B2 | Cited by | United States of America | Applicant |
| US9716590B2 | Cited by | United States of America | Applicant |
| US2019273604A1 | Cited by | United States of America | Search report |
| US8515058B1 | Cited by | United States of America | Search report |
| US10484176B2 | Cited by | United States of America | Applicant |
| US9590963B2 | Cited by | United States of America | Search report |
| US10057057B2 | Cited by | United States of America | Applicant |
| US2008123863A1 | Cited by | United States of America | Pre-grant |
| US9602278B2 | Cited by | United States of America | Search report |
| US9083526B2 | Cited by | United States of America | Applicant |
| US8565435B2 | Cited by | United States of America | Applicant |
| US2011110525A1 | Cited by | United States of America | Pre-grant |
| US2010199042A1 | Cited by | United States of America | Pre-grant |
| US10177905B2 | Cited by | United States of America | Applicant |
| US9141819B2 | Cited by | United States of America | Search report |
| US8009828B2 | Cited by | United States of America | Search report |
| US10904005B2 | Cited by | United States of America | Applicant |
| US10218496B2 | Cited by | United States of America | Search report |
| US8532289B2 | Cited by | United States of America | Applicant |
| US8958555B2 | Cited by | United States of America | Applicant |
| WO2010088437A3 | Cited by | World Intellectual Property Organization (WIPO) | International search |
| US11018857B2 | Cited by | United States of America | Search report |
| US8356177B2 | Cited by | United States of America | Search report |
| US8762642B2 | Cited by | United States of America | Applicant |
| US9942044B2 | Cited by | United States of America | Applicant |
| US8630422B2 | Cited by | United States of America | Search report |
| US10560260B2 | Cited by | United States of America | Applicant |
| US2011107097A1 | Cited by | United States of America | Pre-grant |
| US2009080645A1 | Cited by | United States of America | Pre-grant |
| US2016028702A1 | Cited by | United States of America | Pre-grant |
| US9252954B2 | Cited by | United States of America | Applicant |
| US8903083B2 | Cited by | United States of America | Applicant |
| US2017063814A1 | Cited by | United States of America | Pre-grant |
| US9639687B2 | Cited by | United States of America | Search report |
| US9077540B2 | Cited by | United States of America | Search report |
| US2014133651A1 | Cited by | United States of America | Pre-grant |
| US9742566B2 | Cited by | United States of America | Applicant |
| US2010169645A1 | Cited by | United States of America | Pre-grant |
| US9621346B2 | Cited by | United States of America | Applicant |
| WO2010088437A2 | Cited by | World Intellectual Property Organization (WIPO) | International search |
| US6341349B1 | Cites | United States of America | Pre-grant |
7 priority claims, no other members on record
Priority claims7
| Document | Office | Kind | Date |
|---|---|---|---|
| 2004014560 | Japan | – | |
| 2004014560 | Japan | A | |
| 2005000841 | Japan | W | |
| 2004014560 | – | – | – |
| JP20040014560 | – | – | – |
| PCTJP0500841 | – | – | – |
| WO2005JP00841 | – | – | – |
37 transactions on the USPTO file
Allowed after 1 non-final rejection.
- Non-final rejections
- 1
- Final rejections
- 0
- RCEs
- 0
- Appeals
- 0
Over time
Point at a mark for the transactionTransactions
| Event | Code | |
|---|---|---|
| Post Issue Communication - Certificate of CorrectionN423 | N423 | |
| Post Issue Communication - Certificate of CorrectionN423 | N423 | |
| Recordation of Patent Grant MailedPGM/ | PGM/ | |
| Patent Issue Date Used in PTA CalculationAllowedPTAC | PTAC | |
| Issue Notification MailedAllowedWPIR | WPIR | |
| Dispatch to FDCD1935 | D1935 | |
| Application Is Considered Ready for IssuePILS | PILS | |
| Issue Fee Payment VerifiedN084 | N084 | |
| Issue Fee Payment ReceivedIFEE | IFEE | |
| Mail Miscellaneous Communication to ApplicantMM327 | MM327 | |
| Miscellaneous Communication to Applicant - No Action CountM327 | M327 | |
| Mail Examiner's AmendmentMEX.A | MEX.A | |
| Mail Notice of AllowanceAllowedMN/=. | MN/=. | |
| Notice of Allowance Data Verification CompletedAllowedN/=. | N/=. | |
| Examiner's Amendment CommunicationEX.A | EX.A | |
| Examiner Interview Summary Record (PTOL - 413)EXIN | EXIN | |
| Date Forwarded to ExaminerFWDX | FWDX | |
| New or Additional Drawing FiledC614 | C614 | |
| Response after Non-Final ActionA... | A... | |
| Mail Non-Final RejectionNon-final rejectionMCTNF | MCTNF | |
| Non-Final RejectionNon-final rejectionCTNF | CTNF | |
| Date Forwarded to ExaminerFWDX | FWDX | |
| Response to Election / Restriction FiledELC. | ELC. | |
| Mail Restriction RequirementMCTRS | MCTRS | |
| Restriction/Election RequirementCTRS | CTRS | |
| Case Docketed to Examiner in GAUDOCK | DOCK | |
| Case Docketed to Examiner in GAUDOCK | DOCK | |
| IFW TSS Processing by Tech Center CompleteTSSCOMP | TSSCOMP | |
| Case Docketed to Examiner in GAUDOCK | DOCK | |
| Application Dispatched from OIPEOIPE | OIPE | |
| 371 Completion Date371COMP | 371COMP | |
| Cleared by OIPE CSRL194 | L194 | |
| Information Disclosure Statement consideredIDSC | IDSC | |
| Information Disclosure Statement (IDS) FiledM844 | M844 | |
| Information Disclosure Statement (IDS) FiledWIDS | WIDS | |
| Preliminary AmendmentA.PE | A.PE | |
| Initial Exam Team nnIEXX | IEXX |
7 legal events, as the office reported them to INPADOC
Over the term
Point at a mark for the eventEvents
| Event | Code | |
|---|---|---|
| Maintenance fee paymentMAFP | MAFP | |
| Fee paymentFPAY | FPAY | |
| Fee paymentFPAY | FPAY | |
| Certificate of correctionCC | CC | |
| Information on status: patent grantGrantedPATENTED CASESTCF | STCF | |
| AssignmentAS | AS | |
| AssignmentAS | AS |
Numbers
- Publication
- 20060262933
- Publication, DOCDB
- 2006262933
- Publication, EPODOC
- US2006262933
- Application
- 10546645
- Application, DOCDB
- 54664505
- Application, EPODOC
- US20050546645
Titles
- English
- Mixnet system
Classification
- CPC, 9
- H04L9/14
- H04L9/32
- H04L9/0825
- H04L9/3218
- H04L9/3236
- H04L9/3066
- H04L2209/463
- H04L9/08
- H04L9/30
- IPC, 6
- H04L9 28
- H04L9 30
- H04L9 00
- H04K1 00
- H04L9 08
- H04L9 32
- USPC, 6
- 380281000
- 380028000
- 380030000
- 380284000
- 380285000
- 713181000