CN1092434C - Method for sharing secret information, generating digital signature, and performing certification in communication system that has plurality of information processing apparatus and communication...... - Google Patents

Abstract

The present invention is directed to perform verifiable secret sharing by a practical amount of calculation and a practical amount of communication. In addition, by using this process, a shared digital signature is generated, or a shared authentication server is provided.

Description

Share security information, produce data signature and carry out method and the communication system of confirming

The present invention relates to a kind of method, and the security information that can transmit in of the information processing equipment that combines by the communication path in the communication system (being called " user " later on) whereby can be shared by the user, and relates to the communication system of using this method.Near and, the invention relates to is to be shared or produced digital signature by some one groups of constituting in a large number of users, and relates to the communication system of using this method.In addition, the present invention relates to make a large amount of users to share the method for an affirmation function, this function can be confirmed the recipient of information, and information transmits from correct conveyer (also not changed by the miscellaneous equipment on the circuit); And relate to a communication system of using this quadrat method.

The coding techniques that common generation increases redundant data is one of known improvement information communication system technology of dependability.

Particularly can make the mistake that has produced in communication process is not that to be detected be exactly the communication system that the self-correcting code that is carried out correction often is used to realize effectively high reliability.

Near and; A.Shamir proved, to increase redundant coding techniques be effectively (to see that " how sharing secret " ACM communicates by letter, roll up 22 as improving reliability and providing an instrument of protection to security information simultaneously in communication system by sharing security information; 1979,11).

In the communication system of forming by a large number of users; share security information (promptly; by the security information that all users kept and shared) protection maintaining secrecy of the physics that provides by single specific user not merely is provided; but it may increase reliability (can realize the tolerance that lost efficacy), and for example available following two definition are described.

One is reliability, it guarantee that security information is protected and even it can not revealed when being shared yet, it is called as secret inefficacy tolerance.

Another is a reliability, and it guarantees to export will be correct, although unauthorized behavior is carried out on the information of sharing; This is called as the inefficacy tolerance of patent rights.Safety that it should be noted that physics means, and is not revealed to any other user by the information that the specific user keeps, and the calculating that the specific user carries out is not subjected to any other user's control.

More specifically, share and keep specific security information X to mean by all users, each individual consumer i produce the message segment of common corresponding security information X and distribute the message segment that produces to other some users to satisfy following requirement (a) and (b).

(a) message segment that obtains from t+1 user is required to be used for decoding security information X.After, t+1, the number of users that need be used for decoding security information is called as threshold values.

(b) when the number of the part information that obtains from the user is lower than threshold values (t or still less), can not obtain to be relevant to the data of security information.

Common basic secret shared system proposes (" how sharing secret ", ACM communication, volume 22,1979,11) by A.Shamir and this system finishes by following.

In order to share information secretly with the source user of determining that has in a large number of users, its constant term be described to security information-polynomial of degree n f (x) selects randomly.And the polynomial f (i) of a corresponding n different value (i=1 ..., value n) is distributed to the user.The value of distributing to each user's polynomial f (i) is above-mentioned message segment.The interpolation polynomial that use has a t+1 message segment with regard to can decode security information (use t or still less message segment with regard to any information that obtains to be relevant to security information, be very little).

The shared in the above described manner system that maintains secrecy is called as the threshold values scheme and can realizes above-mentioned secret inefficacy tolerance with being assumed to be.It should be noted that when when existing incorrect message segment in the middle of the Sharing Information section of the security information X that in the middle of t+1 or more user, collects, only use above-mentioned definition can not decode initial security information.That is, can find that the correct inefficacy tolerance that obtains shared security information no longer can guarantee.

In order in the shared system of foregoing description, fully to increase reliability, must consider in order to maintain secrecy and to get both inefficacy tolerances for correct acquisition.

The conduct that the function that proposes is duplicated the user that any mistake takes place is maintained secrecy and is shared positive the maintaining secrecy of testing of method and share method by requiring (a) in the threshold values scheme and (b) adding following requirement (c) and (d) defined.

(c) although mix when non-correct message segment and correct message segment, as long as exist t+1 correct message segment here, that also is enough for decoding initial security information.

(d) relate to secret message segment when all users have received, they can verify that message segment is correct message segment for decoding specific security information X.

M.Ben-Or, S.Goldwasser, with A.Wigderson common error correction coding techniques has been described, this technology can be satisfactorily (when threshold values t is satisfied with t＜n/3) as long as these users' number is less than whole users' one of three, but secret shared system that should probatio inspectionem pecuoarem just can be duplicated the user of any mistake for the communication with secure communication channel provides the secret shared system that can verify.(seeing the complete theory that non-password inefficacy tolerance distributes and calculates, ACM STOC 1988).

Near and, for as long as but a half that has less than whole users the user can produce the secret shared system of probatio inspectionem pecuoarem that reproducible has the user of any mistake, just need additional requirement, suppose, all users have them can verify that all usefulness received the broadcast communication channel of same information per family, and two following methods disclose.

(1) use the method for in zero knowledge demonstration system, using that is called as " downcut and choose " (to see that " password and information-intensive society " is by Tsujii and Kasahara, Shokodo, write 1990) and use the secret substantially shared system that proposes by A.Shamir go to share initial secret S and go further to share the message segment S-i that cooperates (i=1 ... n)

More specifically, can be regarded as the matrix of part, to such an extent as to it is that what so to produce is the secret part of corresponding pieces of confidential information S-i by all message segments of the secret shared system dispensing that can verify.By using " downcut and choose " technology, can carry out as requested the checking of (a) satisfactorily, make the wrong probability that will take place in decision output, pointed out whether to carry out correct the sharing of decoding security information.When error probability when using to the minimizing of the parameter of security set, it can be ignored, the method (seeing the most multilateral accord book of maintaining secrecy and sharing and having honesty that can verify, ACMSTOC, 1989) that is proposed by J.Rabin and M.Ben-Or is a specific example.

(2) use be not conversational the single channel function method and have specific algebraic property.Safety for so secret shared system that constitutes, must the supposition of password be claimed, make that the opposite composition that obtains a single channel function is very difficult, this single channel function satisfies algebraic property (actual algorithm of calculating opposite constituent does not exist), by P.Feldman proposed a particular instance (see " the non-practical solution of maintaining secrecy and sharing that can verify mutually; " IEEE FDCS, 1987).

Near and by T.Rabin, M.Ben Or (see " maintaining secrecy of can verifying shared and had a honest most multilateral accord book, ACM.STOC; 1989), D Beaver (see " guarantee multilateral accord and allow that minority lost efficacy zero know the authenticating method system ", cryptography magazine; 1991,4,75-122 page or leaf; " use the randomized effective multilateral accord book of circuit ", cryptography-password guide ＇ 91,1992) and M.Franklin and S.Habtr (see " in conjunction with coding and information-effectively guarantee calculating ", cryptography-password guide ＇ 93,1994) described, use the above-mentioned shared method of verifying of maintaining secrecy to can be provided in to carry out in the given finite aggregate and share the circuit that calculates.

For above-mentioned dialogue method (1), yet many known security parameters of working as represent that with K (use value 100 usually) requiring to share a required traffic secret for n partly is n^3K^2 time (a^b refers to ab) here, and this method is not effective.

And to the cryptographic methods of non-dialogue, n is maintained secrecy partly must be to the calculating of special single channel function n time.Particularly when using secret shared procedure to share calculating as the part process fully to carry out, the number of times of the secret shared procedure that must carry out just must increase (that is being n2 time to sharing use) more.Whole calculation times is with unpractical huge.

As mentioned above, in common technology, dialogue method (1) needs a large amount of communication, and compiling method (2) needs the calculating of huge number of times.

In the common communication system of the overwhelming majority, transmit information with the data block unit that is called bag.Even when bag was sent to the designated destination, all equipment (user) that constitute communication system can receive those bags.Near and, owing to be connected in together by the identical logical a large amount of equipment of communication news, this is the transfer source of very difficult appointment bag just.Therefore such communication system is tended to the process that oneself makes an initiative sally publicly, for example pass through " eavesdropping ", thus, by means of crafty plot, obtained to be transferred to the bag on various objectives ground wrongly, the inappropriate destination that is assumed to be miscellaneous equipment of specific equipment here.

Let us is discussed the problem how above-mentioned communication system maintains secrecy, and this above-mentioned communication system guarantees that the information that transmits only offers the user of selected transmission destination as appointment and do not have unauthorized obtaining (information is maintained secrecy) here.(page or leaf 224-225 IEEE) is one of known useful technology to coding techniques for Ikeno and Koyama work, " present encoding theory ".

As everyone knows, cryptographic technique not only for the function of carrying out maintenance information secret and also for checking be received the function of information and be referred to as " electronic signature " be used to verify that the function of having transmitted the third party of information from specified equipment reception all is effective.The cryptographic communication that has digital signature by use can pre-anti-eavesdrop and devious conduct.

The checking that is to use the KSA coded system and the digital signature method of special well-known, this RSA coded system be one of publicty effect cryptographic system (for example, see " method that obtains digital signature and publicty effect cryptographic system " R.Rivest, A.Shamir and L.Adleman work, ACM communication 1978,2,21, the page or leaf 120-125 or see USP 4,405,828).

Being different from the rsa cryptosystem system uses the method for the another kind of known digital signature of conduct of a publicty effect cryptographic system to be proposed (to see " how to verify yourself: the actual solution of identification and signature problem " by A.Fiat and A.Shamir, cryptography-password guide ＇ 87, the lecture note of computer science, 263, Spriner-Verlag, 1988, page or leaf 186-194 or see USP 4,748,668).According to this method, carry out following process and provide effective recognition and digital signature for given information.

(1) calculate an equipment of given message digit signature or as the equipment at the reliable center of communication system randomly from { 1,, N-1} chooses the security information that an element (N is the long-pending of two prime number p and q) and the element of choosing are considered as calculating this equipment of signing here.

(2) chosen the calculation of equipments a of secret element ¹Mod N (notices that 1 satisfies gcd (1, λ (N))=1, λ (N)=1cm (P-1 here, q-1), (a b) represents greatest common divisor to gcd, and 1cm (a b) represents least common multiple) and use the public information of the digital signature that the result produces by this equipment as checking.

(3) going to produce in the digital signature procedure of a given information m by the equipment execution, R=r^1 modN, it is by using with at random method { 1 for R, the secret element r that N-1} selects obtains, and R/m, and this value is continuous given public information m and obtaining, they all are considered as input, calculate e=h (R/m) by using function h given in advance.After this use above-mentioned value to calculate S=r*a^e (mod N) as input.S as a result that obtains and R are used as the digital signature that knot is decided information.

(4) calculate S^1 modN and R* (a^1) ^ (h (R/m)) mod N for the digital signature (S.R) of verifying given information m, when coming to the same thing, just confirmed digital signature.

(see " Efficient Identification and Signatures ForSmart Card " Advances In Cryptology-Crypto 189 according to effective identification that proposes by C.P.Schnorr and the method that obtains the digital signature of a given information, LectureNotes In Computer Science, 435, Springer-Verlag, 1990, page or leaf 139-252, or see USP 4,995,082) carry out following process.

(1) calculate given message digit signature equipment or as the equipment at the reliable center of communication system randomly from 1 ..., choose an element (P is a prime number) among the P} here, the element of choosing is considered as the security information of this equipment of compute signature.

(2) chosen this calculation of equipments g of secret element ^-aModq (q is such prime number here, and p is that the number of the numeral of the approximate number of q-1 and the element g that belongs to finite aggregate GF (q) is p) and use result calculated are as the public information of checking by the digital signature of this equipment generation.

What (3) carried out by equipment be in the process of given information m generation digital signature, R=g ^TModq, it is to use from { 1, the secret element r that p} selects at random obtains, and R/m, and it is the value that obtains by given public information m continuously, they all are considered as input, the function h predetermined with use calculates e=h (R/m), after this uses above-mentioned value to calculate S=r+a*e (mod p), the digital signature that the S as a result of acquisition and R are used as given information as input.

(4) digital signature (S, R) in order to verify given information m, (g^S ((g^ (a) ^ (h (R/m)))) (mod q)/m (R/m)) (noticing that x^y represents Xy) has just verified digital signature when this result is equal with e to calculate h.

(see " A Pullic-Key Cryptosystem And ASignature Scheme Based On Discrete Logarithms " according to the effective recognition that proposes by T.ElGamal with for the method for given information acquisition digital signature, IEEETransactions On Information Theory, IT-31,4,1985, page or leaf 469-472, American National Standard X 9,30-199x, digitalSignature Algorithm, February, 1992), carry out following process.

(1) be an equipment of given information calculations digital signature, or as the equipment at the reliable center of communication system randomly from 1 ..., choose an element (P is a prime number) among the P} here, the element of choosing is considered as the security information of this equipment of compute signature.

(2) ((a) (q is a prime number to modq to g^ here to choose the calculation of equipments of security information, p is the approximate number of q-1, and the digital number that belongs to the g element of finite aggregate GF (q) is p) and use the result as the public information of checking by the digital signature that these equipment produced.

(3) produce in the process of digital signature for given information m by going of carrying out of equipment, use R=gTmod q, it is to use from { 1, the secret element r of p} picked at random obtains, and e=h (m), and it is the value that obtains from predefined function h, and given public information m is considered as input, calculates S=(e+R*a) * r ^-1Modp.S as a result that obtains and R are as the digital signature of given information.

(4) (S R), calculates that (g^ (a)) ^ (g^r) ^S and g^m (mod q) when these values equate, have verified digital signature for the digital signature of verifying given information m.

In other words, for the above-mentioned information communication system of maintaining secrecy and realizing checking of keeping, Y.Desmedt and Y.Frankel put forward as increasing reliability and keeping the instrument of information secret and conduct to share security information and the method that is shared as given information calculations digital signature simultaneously, and it is in a large amount of computers that link together with communication line that this knot is decided information.(the computer here is called one group of signer later on, each computer that belongs to this group is called the user, the numerical statement of computer is shown n in the group) (see " ThresholdCryptosystem ", Advances in Cryptology-Crypto ＇ 89,435, Springer-Verlay, 1990, page or leaf .307-315; " Shared Generationof Authenticators And Signatures ", Advances In Cryptology-Crypto ＇ 91,576, Springer-Verlag, 1992, page or leaf 457-469)

The essential part of sharing digital signature method is to share by above-mentioned to satisfy the interior security information of communication system that aforesaid requirement (a) and a large number of users (b) are formed,

The shared digital signature method that is proposed by Y.Oesmedt and Y.Frankel has used the secrecy system of the RSA that shares method according to maintaining secrecy and has satisfied following requirement (I) and (II).

(I) the t+1 user collaboration is for being that to go to produce digital signature be enough to one group of signer for given information

(II) when user's number is less than a threshold values (be t or still less), can not produce the digital signature of given information.

Only with requiring (I) and (II) time, yet, when shared digital signature production process, if when in the t+1 of cooperation or more users, wrongful user being arranged, generation that can not the combine digital signature.

On the other hand, many known, the method that produces digital signature for each user of each existing any kind mistake can be based on being provided by the defined secret shared system of verifying of aforementioned requirement (a) to (d).In other words, can realize satisfying the shared digital signature system of following requirement.

(I),, still can produce the digital signature of given information as long as the proper user's of t+1 cooperation is arranged although there is wrongful user to appear between the proper user.

(II) (, t or still less) can not produce the digital signature of given information when user's number is less than threshold values.

Be well known that, can design sharing and the generation system of various aforesaid digital signature methods by using the above-mentioned shared and counting circuit of sharing method of maintaining secrecy of verifying.

Be well known that, to satisfying above-mentioned requirements (I) and (II) the desired traffic of shared digital signature and amount of calculation are actual.Yet as previously mentioned, when the user who participates in sign shared and production process carries out wrongful things, just can not produce signature.

On the other hand, as mentioned above, use can be verified maintain secrecy to share method and shares and the shared digital signature system of counting circuit meets the demands (I) and (II), be well known that, according to maintaining secrecy of can verifying the type of living share the desired traffic of method (1) be unpractiaca and according to non-conversational verify maintain secrecy that to share the desired amount of calculation of method (2) also be unpractiaca.

As mentioned above, by using common technology, for can verify the shared digital signature system of sharing method (1) of maintaining secrecy according to conversational for, the desired traffic is huge; By using common technology, maintaining secrecy of can verifying according to non-conversational shared the shared digital signature system of method (2) and desired amount of calculation is huge.

As reducing owing to eavesdropping and pretending to cause another dangerous measure, here there is one to be called as the known discrimination method of Kerberos network and (to see UNIX Security, byS.Gartinkel and G.Spafford/ are edited, are translated by Hide Yamaguchi, ASC II, page or leaf 349-357 and page or leaf 535-542,1993), it has used a publicty effect cryptographic system that needs low computational effort.

To explain special authentication protocol, they are based on by Needham and Schroeder and (see R.N.Needham and M.D.Schroeder: " Using Encryptionfor Authentication In Large Network of computers " CACM 21,12, page or leaf 993-999, Dec.1978) authentication protocol and (see A.D.Birrell " SecureCommunications Using RemotePro Cedureudurt Calls " by the SecureRPC (Remote Procedure Call) of Birrell, ACMTransaction Computersystems, Vol.3 No.1, page or leaf 114, February .1985) agreement be basic.

Generally speaking, in Kerberos, exist the authentication server of administrative security information (this is equivalent to be equal to privacy key) for the communication system all devices.Authentication server jointly uses the privacy key pKi that has each autonomous device i, and this is shown in Figure 31 A.After this, the person that needs to differentiate is the statement people, and the person that provides the statement people to differentiate is the authentication people.

Shown in Figure 31 B, when statement people A when authentication people B requires to differentiate, A transmits has that { data 161 of R} form are given authentication server for A, B.It should be noted that A and B are public identification information item, they have specified statement people A and authentication people B, for example equipment or address name, and R is the number of picked at random.

According to the data 161 that receive, the authentication server backspace has { differentiates element R, B, the data 162 to A of CK}^pkA form.It should be noted that { the data that the M}^K representative uses key K to obtain by coded message M.Differentiate element be to use time mark T by T, A, the data 163 that CK}^pkB constitutes, and the CK representative produce by authentication server and after this be the employed publicty effect of publicty effect secure communication between A and the B.

For the secret publicty effect of stating the publicty effect secure communication between people and the authentication people is called the talk key later on.Authentication server is later on for talking key as transmitting server.At last, statement people A sends previous the description and differentiates that element 163 is to authentication people B.Authentication people B removes to authenticate A with the synthetic discriminating element 163 that receives of its secret major key PKB, uses public talk key CK to carry out secure communication then.

By using Kerberos authentication protocol book, the danger that may eavesdropping and camouflage be caused reduces.Must carry out the calculating of remainder of the integer power series of 512 or bigger figure place corresponding to the time slot scrambling of publicty effect, make that calculation times is huge.

Near and, because in the Kerberos agreement in the publicty effect method, authentication server is being managed and is being constituted that communication system comprises because physical cause is the security information of all devices of safe and reliable discriminating service, this also be desired (similarly, for the publicty effect time slot scrambling, the centralized-control center of managing all publicty effects is requirement).Therefore, in order to ensure maintaining secrecy, strictly controlling authentication server by it being placed on lock indoor.In without permission mustn't anyone goes into.Near and, owing to error takes place or because undelegated handling makes authentication server no longer reliable, the inefficacy tolerance is so reduced, and makes that the confidentiality of whole system is in the flue entirely.

The purpose of this invention is to provide the method for maintain secrecy sharing that can verify, when using this method, during from value that live system (1) and secrecy system (2) are obtained, the amount of calculation that is obtained and the traffic have constituted the number of times of actual margin when more above-mentioned.

The present invention so is placed to the appropriate location, make it be located at the centre of conversational system (1) and non-conversational system (2), with use maintaining secrecy of can verifying and share method, by using this method, the required amount of calculation and the traffic have all constituted actual amplitude number of times, and the digital signature system of sharing has been proposed (when the number of carrying out unauthorized user is equal to or greater than threshold values, system does not produce digital signature, but can discern such user) this digital signature system is the suitable position that is placed between requirement (I) (system does not produce signature when the user who carries out unauthorized behavior exists) and the requirement (I ＇) (when the user's of the unauthorized behavior of execution number was equal to or less than specific threshold values, system can produce a signature).

Another object of the present invention is the problems referred to above that overcome the authentication server reliability, makes to have proposed to use large number quipments to remove the shared authentication server of shared and administrative security information.

Requiring of shared authentication server is as follows:

(1) for statement people and authentication people, shares the authentication protocol book and carry out identical Discrimination Functions as the authentication protocol book that provides by common centralization administrative institute.

(2), share the authentication protocol book and guarantee that same-interface (data format) is as the authentication protocol book that is provided by common centralization administrative institute for statement people and authentication people.

(3) for statement people and authentication people, by the authentication protocol book of carrying out and realizing by the calculating of the needed same amount of authentication protocol book of carrying out and providing by the administrative institute of common centralization sharing.

(4) above-mentioned requirement is satisfied, unless when the equipment of sharing authentication server more than the formation of half no longer reliable.

According to one side, realize the security information processing method that the present invention relates to a communication system of these targets, wherein, connect a large amount of information processing equipments by secure communication channel, each equipment in the middle of all these and in the equipment another are by the broadcast communication channel exchange message and simultaneously to any remaining equipment maintenance information privacy, all these equipment devices exchange information that normally other is included with all, the security information processing method comprises the steps:

As large number quipments and first equipment of handling security information is that a large amount of second group of instrument produce an array of maintaining secrecy from security information;

Using first equipment is that second group of equipment takes out first message segment and transmits this first information section to second group of equipment by secure communication channel from secret array;

The output valve of using first equipment on the basis of secret array part, to carry out predetermined function and obtain by broadcast communication channel broadcasting;

Use second group of equipment to produce random number; With broadcast this random number by broadcast communication channel;

Using this first equipment is that second group of equipment produces second message segment from secret array and in conjunction with the random number that is broadcasted out, by second message segment of broadcast communication channel broadcasting;

Use second group of equipment to produce the 3rd message segment, this message segment is second message segment that this second group of equipment produces as using first instrument, these message segments and received first information section and consistent by many random numbers of second group of equipment generation; With

Use second group of equipment comparison the 3rd message segment and what be broadcasted is second message segment of second group of equipment, the checking security information is shared by first equipment.

According on the other hand, realize the signature production method that the present invention relates to communication system of these targets, wherein, the large number quipments that links together by secure communication channel, all these equipment and miscellaneous equipment keep the information secret by the broadcast communication channel exchange message and to remaining instrument, in all equipment each jointly with all miscellaneous equipment exchange messages, the signature production method may further comprise the steps:

Each of equipment that use belongs to a signature group is chosen equipment in first security information and the group randomly, and it enjoys first security information in confidence;

The output valve of using all equipment to carry out first predetermined function and broadcasting acquisition on the basis of first security information arrives all devices in the group;

In group in all equipment each is shared first security information and is added first security information;

In group, share output valve with multiplication in the instrument, on the basis of result who obtains by multiplication and an information, carry out the second predetermined function;

In group, share second security information in the equipment and use, promptly by shared and add result of acquisition and one and become disclosed unit and usually calculate second security information carrying out second result that function obtained;

By all devices in organizing make joint efforts to second security information of sharing decipher and export second security information of decoding and in conjunction with the result who shares the multiplication acquisition as signature.

According to additional one side, that finishes these targets the present invention relates to the communication system discrimination method, and wherein, a large amount of equipment link together, and those equipment that belong to particular group provide discriminating altogether, and discrimination method comprises following step:

Transmission comprises that the identifier of stating the people and authentication people's the discriminating solicited message of identifier is from the statement people's that transmits the request of discriminating equipment and each equipment from authentication people's equipment to particular group;

Generation is with the discriminating element of privacy key coding, and this privacy key relates to the authentication people and belongs to the discriminating solicited message of all devices concerted effort in the particular group based on use, uses to relate to that the privacy key of state people and discriminating element are encoded and the authentication information that produces;

The equipment of transmission from the authentication information of each equipment of particular group to the statement people;

Receiving this authentication information of decoding in the equipment of stating the people on the basis of authentication information, transmitting the equipment of the discriminating element of this decoding to the authentication people; With

In authentication people's equipment, decipher this discriminating element and transmission and differentiate the statement people.

According to another aspect, realize a communication system that the present invention relates to have bulk information treatment facility and secure communication channel of these targets, each equipment in the middle of all these can information converting be also secret to remaining equipment simultaneously in confidence with another equipment, with each equipment transmission information jointly in the middle of broadcast communication channel is connected all these to all other equipment, the first information treatment facility of bulk information treatment facility comprises:

First generation device is used for producing predetermined part array from security information;

Withdrawing device is used for from taking out in the middle of part is arranged to the first information section of any remaining messaging device and transmit first information section to remaining messaging device,

The function processing unit is used for first information section is carried out predetermined functional operation and broadcasting output valve, crosses broadcast communication channel to remaining messaging device; With

Second generation device is used to produce with corresponding to second message segment of random number that produces with remaining messaging device broadcasting with by broadcast communication channel and broadcasts second message segment; Each of remaining messaging device comprises:

Random number generating apparatus is used to produce a random number and broadcasts random number by broadcast communication channel;

The 3rd generation device is used for consistently producing the 3rd message segment with first message segment and this random number, and the 3rd message segment produced as second message segment by first information treatment facility; With

Demo plant is used for the 3rd message segment of comparison and second message segment that is broadcasted and checking by the performed secret of sharing of first information treatment facility.

According on the other hand, realize a communication system that the present invention relates to have bulk information treatment facility and secure communication channel of these targets, in the middle of all these each equipment can and other equipment exchange of secret information and simultaneously remaining equipment is kept information privacy; With each equipment transmission information jointly in the middle of broadcast communication channel is connected all these to all other equipment, each equipment that belongs to same group of mirror famous person in large number quipments comprises:

Sharing means is used for choosing randomly shared in confidence first security information in the middle of first security information and the equipment in group;

Broadcaster is used for that first security information is carried out the first predetermined functional operation and arrives all equipment that are left in the group with the value that broadcasting is obtained;

Adder is used for first security information that each equipment is kept in the shared group and adds first security information;

Processing unit is used for the output valve that each equipment keeps in the shared group and takes advantage of output valve and result and the second predetermined functional operation of information and executing to obtaining with multiplication;

Calculation element is used to use multiplication result, by sharing and adding the result of acquisition and equipment is shared second information disclosure in group an element and calculating second information; With

Code translator is used under the effort second security information and the combination deciphered are deciphered and exported to second security information by uniting of all devices in the shared second security information group and is signed with result that multiplication obtains conduct together by shared.

In conjunction with the preferred embodiment of following invention, will be significantly for the those skilled in the art from other purpose of above-mentioned discussion and advantage, in specification with reference to as constituting a part and the accompanying drawing that provide the invention example of invention.Yet such example is not whole various embodiment of invention.Therefore determine the claim of invention scope with reference to following description.

Fig. 1 is the block diagram of the communication system architecture of one embodiment of the invention;

Fig. 2 is the block diagram of the messaging device structure of each user's use;

Fig. 3 is the block diagram that concerns between secret and the part matrix;

Fig. 4 is the block diagram of the processing of single channel hash function operation;

Fig. 5 is the block diagram of secret shared processing process;

Being stranded 6 is block diagrams of secret decoding treatment process;

Fig. 7 explains the block diagram of sharing with computing;

Fig. 8 A to 8C obtains the block diagram that hashed value is handled from input information;

Fig. 9 is the block diagram that produces the communication system architecture of digital signature when sharing;

Figure 10 A and 10B explain that privacy key and publicty effect produce the figure of the process of handling;

Figure 11 is a figure of explaining the input and output relation of sharing secret linear combination processing;

Figure 12 explains to share the figure that signature produces processing procedure;

Figure 13 A and 13B explain that privacy key and publicty effect produce the figure of processing procedure;

Figure 14 explains to maintain secrecy to share the figure of multiplication process;

Figure 15 explains to share the figure that secret linear combination is handled;

Figure 16 explains to share the figure that signature produces processing procedure;

Figure 17 is a figure of explaining the shared multiplication process process of maintaining secrecy that can verify;

Figure 18 is a figure of explaining the shared multiplication process process of maintaining secrecy that can verify;

Figure 19 is a figure of explaining maintain secrecy shared and multiplication process process;

Figure 20 explains the figure of sharing the signature production process;

Figure 21 is a block diagram of carrying out the communication system architecture of sharing for differentiating;

Figure 22 explains to share the figure that secret linear combination is handled;

Figure 23 A and 23B share the figure that pseudo random number produces processing procedure;

Figure 24 A and 24B are the figures of privacy key and encoding process process;

Figure 25 A and 25B are the figures of sharing authentication protocol book process;

Figure 26 is the figure that the off line pseudo random number produces processing procedure;

Figure 27 connects the figure that the machine privacy key transmits processing procedure;

Figure 28 A and 28B are the figures of sharing authentication protocol book process;

Figure 29 A and 29B are the figures of sharing authentication protocol book process;

Figure 30 A and 30B are the figures of sharing authentication protocol book process; And

Figure 31 A and 31B are the figures of sharing authentication protocol book process usually;

The preferred embodiment of the invention is described in conjunction with the accompanying drawings

(embodiment 1)

Principle of the present invention is at first described

Fig. 3 is the block diagram that concerns between secret S and the P part matrix S.

The part matrix S that is used for secret S in this embodiment is matrix S=(S (i, j)) (i, j=1 of secret section nxn, n) how it obtains, and this will narrate afterwards, adds to be required for the employed part matrix of secret shared system that common conversational can be verified.

At first, vector S-the r of each row (i)=(S (i, 1) ... S (i, n)) (i=1 ... n) be the secret part vector (vector of element j is the secret part of user j in specific secret shared method) of secret S-r (i) and vector of each row, ((S (1 for S-C (j)=S, j), S (n, j)) (j=1 ... n) be the secret part vector of secret S-C (j).

The vector of difference corresponding secret S-r (i) and S-C (j) (S-r (1) ... S-r (n)) and (S-C (1) ... S-r (n)) is the secret part vector of secret element.Like this row vector i of component part matrix (i=1 ..., n) be sent to the pieces of confidential information of user i as each user i with secret S-r (i).Therefore, in secret decode procedure.Whether do not carry out unauthorized action as long as receive the user of message segment, might be correct with the information that each individual consumer was broadcasted with very high probabilistic verification just.

Increasing this embodiment is in order to verify, even when peculiar initial security information and and dispensing the user of pieces of confidential information carried out unauthorized action, the message segment whether checking is broadcasted in secret decode procedure is correct, as corresponding each user i (i=1, a value of the discriminating element of secret S-r (i) n) before pieces of confidential information is by dispensing by the single channel hash function produced (see " ModernCryptologicalTheory; " by Ikeno and Royama, page or leaf .224-225, IEEE, 1986).

To explain the single channel hash function

The single channel hash function is a kind of function, uses it can carry out amount of data compressionization, and using this function is easy by the calculating that input value obtains output valve, but it is difficult asking the calculating of input value from output valve conversely.In this embodiment, yet and compare at the employed single channel function of the secret shared system of verifying of common non-conversational, special algebraic property is not essential, can use like this provides the single channel of supercomputing hash function.

Particular example as the single channel hash function, R.Merkel proposed use block coding art for example DES (a single channel hash function of digital coding standard (is seen " One-Way Hash Functions and DES " Advances in Cryptology-Crypto 189, Lecture Notes In Computer Science, Vol.345, Springer-Verlag, 1990)

Fig. 8 A to 8C is the figure of single channel hash function ad hoc structure

Provide block coding in Fig. 8 A, this coding is carried out DES and coding circuit 81 is to provide one 64 output from 64 inputs or from 56 keys, (DES represents with E to Fig. 8 A to 8C).

Then, it is that 119 and output length are the processing of 112 function F that Fig. 8 B has provided input length, and DES is used as section processes.Label 82 indications one function function circuit.This processing is defined as follows.

At first input is divided into two parts K and X (length of noting the K part is 55, and the length of remaining part X is 64).Then, X partly is used as the input of DES, and uses built-up section K and ' 0 ' or the value ' 0 ' that obtains, and K is used as 55 keys.Carry out the EXOR operation with output that obtains and X, and the result who obtains is regarded as 64 of the function F output left side.Make in the same way, same part, X is used as input, makes remaining Partial K of combination and ' 1 ' value ' 1 ' that obtains, and K is used as a key, carries out the EXOR operation with output that obtains such as X.From 64 of result 48 (the right 48) are as the function F remainder.Are 112 outputs of function F by two results that output provided that obtain like this of combination then.

Along with this, Fig. 8 C provided a given information be input and single channel to loose to functional value be the processing of exporting, label 83 is represented the hash function operating unit, this process is pressed following execution.

Preceding 119 inputs that are used as above-mentioned function F of given information obtain first output of 112 like this.Then, this output is used as 112 input once more, after this Sheng Xia 7 information repeatedly are input to function F, at last, when all information is transfused to the hashed value when having very few position to go last 7 of input information (if, add ' 0 ' as required) that 112 outputs that obtained are used as information here

R.Merkel states in aforementioned paper, the single channel hash function that obtains with above-mentioned calculating (promptly, when obtaining different input informations be that to obtain identical hashed value be the unusual factor of difficulty with being presented when a hashed value) be provided as the array coding safety (when inputing to regularly, the output that obtains from key is change at random, with export to regularly, the input that obtains from key is a change at random) for example above-mentioned employed DES.

Near and, in same piece of writing paper, the single channel hash function more difficult than above-mentioned hash function proposed also.In addition, R Rivest proposed not use the array coding an effective single channel hash function (see " The MD4 Massage Digest Algorithm; " Adances In Cryptology-Crgpto ＇ 90, Lecture Notes InComputer Science, Vol.537, Sprviger-Verlag, 1991.NistFederal Information Processing Standard For Secure Hash, American National Standard X 9.30-199X).

" downcutting and choose processing " will be described in the present embodiment.

In order to verify that the pieces of confidential information whether all users have received is can verify to share similar cutting-out of maintaining secrecy and the message segment of choosing in secret shared processing, as performed in the common secret shared system of conversational, dispensing the part matrix and the hashed value of secret element S, with at dispensing meanwhile the K that is selected at random maintain secrecy 11,1K, part matrix and hashed value.All relate to the K/2 that determines at random by all users (1i (1) ..., the security information of 1i (k/s) is broadcasted.When it be maintain secrecy for lefting in k/2 (1j (1) ..., 1j (k/2)) time, all relate to 1j (1)+s ..., the security information of 1j (k/2)+S has been broadcasted.When the part of in all broadcast messages, having made mistakes outnumber t the time, it just determines that secret shared processing has been incorrect.

Can provide by this way and satisfy following requirement (c ') and (d ') rather than can verify usually to maintain secrecy and share method and require (c) and maintaining secrecy and share method (d), use this method, can realize finishing safely shared Calculation Method and communication system.

(c ') is when incorrect message segment and correct message segment are mixed, even initial security information is not decoded when having t+1 correct message segment, but can discern the user who carries out unauthorized action.

(d ') when independent user had received the message segment of maintaining secrecy, the content of message segment was not correct for the decoding of security information X, when decoding is handled, can discern a user who carries out unauthorized behavior.

These require to make that detecting the promptly wrong detection of user of making mistakes becomes possibility, even by usual way, when having the user who makes a mistake here, can not decipher maintaining secrecy, and promptly can not execution error proofread and correct.(c) and (d) asked in use, even when being the user who makes mistakes here, can carry out sharing operation, near and, use switch to require (c1), it is possible detecting the user who makes mistakes, after providing warning, handle to continue carry out, can obtain correctly to export and can realize suitable inefficacy tolerance.

In this embodiment, what proposed to verify maintain secrecy to share method, and this method can be discerned a user who carries out unauthorized action, and when such user exists, even maintaining secrecy of sharing also is like this can not be decoded the time.That is, this just may provide the method for maintain secrecy sharing that can verify, and this method is in above-mentioned conversational method (1) and the suitable position between the coding method (2), it to the requirement of the amount of calculation and the traffic all in the number of times scope of actual margin.

Fig. 1 is the block diagram of an information processing system according to an embodiment of the invention, and it has comprised the Sharing Information treatment facility.

Fig. 1 is the information processing instrument 11 that is used by system user.In following explanation, each equipment that uses this system and user are considered to be identical and equipment 11 is called as the user.Broadcast communication channel 12 is used for the information of opening and is used as with each user to all user 11 and secure communication channel 13 and carries out secure communication.

Fig. 2 is the block diagram of information processing instrument 11 structures, and in Fig. 2, communication unit 21 is used to communicate by letter with another equipment 11 by broadcast communication channel 12 or secure communication channel 13.One algorithm operating processing unit 22 is carried out various algorithm operatings, for example single channel hash function and according in the processing decision of the program of memory cell 24 with controlling each cell mesh.One random number generation unit 23 for example is a pseudorandom number generator, and be used for producing pseudo random number, memory cell 24 is used to the program that storage algorithm operational processes unit 22 is carried out, the algorithm operating result's who produces in processing procedure information for example is from information and the various parameter that miscellaneous equipment received.

In a given finite aggregate F, carry out sharing the method for maintaining secrecy and ad hoc to be described below of to verify.

At first, the part matrix X of secret S will ad hoc be explained.

In given finite aggregate to part matrix S=(S (i, j)) (i, the j=1 of secret element S,, n) in, each row vector S-r (i)=(S (i, 1), S (i, n)) (i=1 ... n) corresponding n different value i1, in, be the value fi (i1) of the polynomial f i of tth power ... fi (in), wherein sr (i) is as constant term.Every column vector S-C (j)=(S (l, j) ..., S (n, j)) (j=1 ..., element correspondence n) n different value j1 ... jn is the value gj (j1) that the multinomial gj of tth power is arranged ..., gj (jn), wherein S-C (j) is as constant term.Near and, when two vectors (S-r (1) ... S-r (n)) and (S-C (1) ... S-C (n)) be respectively the polynomial f of tth power and the value f of g (i1 ..., in) and g (j1 ..., jh), wherein have secret element S as constant term.

Now explain the processing procedure of this embodiment, it can divide and divides two processing procedures into: secret shared procedure, the dispensing all users that maintains secrecy in finite aggregate, and making maintains secrecy keeps in the middle of the user and shares; Secret decode procedure is by the secret user (if unauthorized behavior taken place) that decipher or discern execution unauthorized behavior of all users to sharing.

(1) secret shared procedure

Secret shared procedure is the process that the user d that holds secret element S has distributed its secret part.Fig. 5 is the figure of processing procedure, in Fig. 5, is carried out to Rj the processing of i by user i in scope j.

After this, h represents effective single channel hash function (having comprised the supercomputing method).The hash function (seeing aforementioned " ModernCryptological Theory ") that use is formed by high speed array coding is as an example, for given K ＇, security parameter K satisfies K=nk, in this case, according to downcutting and choose processing, the checking of secret shared processing is 2^ (K ＇ (t+1)) (seeing the aforementioned " Verifiable Secret Sharing and Multiparty Protocols With HonestMajority ", T.Rabin and M.Ben-Or) with the probability that lost efficacy.

Secret element S and secret element 11 that (scope 1) user d uses random number generation unit 23 to be respectively in given finite aggregate picked at random ..., 1k generating unit sub matrix S, L1 ... Lk.As shown in Figure 4, use hash function operational processes unit 83 to obtain hush values S-r (1) ..., S-r (n), 11r (1) ... 11-r (n) ... 11-r (n) ..., 1K-r (1) ..., the single channel Hash functional value S* of 1Kr (n).

User d transmits the matrix column vector S-C (i) of each generation by secure communication channel 13, L1-C (i),, LK-C (i) and secret S-r (i), 11-r (i), 1K-r (i) (information Bi.i) is to each user i (i-1,, n, it is own to comprise him). arrive value S* (information B1 loosing by broadcast communication channel 12 then, d) be broadcast to all users and (handle R1, d).

(scope 2) each user i (i-1 ..., n) use random number generation unit 23 to broadcast (processing R2, i) K ＇ position (the information B2.i) of picked at random.Each of the K ＇ position of picked at random is called as Bi-1 ..., Bi-K ＇ and be called as B1 to all n users' position ... Bk.

(scope 3) is if at every Bj (j=1 of second scope broadcasting, K) be 1, the part matrix Lj that user d broadcasting is produced in first scope by user d, if Bj is 0, user d broadcasting be each element of the part matrix S that produces and the Lj of finite aggregate (handle R3, d) addition and result's (being written as S+Lj) of obtaining. the information representation by user d broadcasting is the B3.d in Fig. 5.

(scope 4) is for each value j (j=1 of the information B1.i that has received in confidence in scope 1, K), each user i (i=1, n) whether verify that column vector Lj-C (i) and Lj-r (i) (when a position Bj who is broadcasted is 1) or Lj-C (i)+S-C (i) and Lj-r (i)+S-r (i) (when Bj is 0) are column vector and the hush values that equals part matrix in scope 3 in scope 2, when they were not equal to the particular value j that relates to, the decision information (information B4.i) of user d was broadcasted (handling R4.i).

When (scope 5) is broadcasted when the decision information in scope 4, user d broadcasting it in scope 1 the secret information B1.j that transmits to the user j of each unit of having broadcasted decision information (processing R5.d).

(reprocessing) when the information of broadcasting in the 5th scope is incorrect, or when at the number of the decision information of the 4th scope broadcasting during greater than threshold values t, each user i (i=1 ..., n) decision, user d has carried out non-action (handling Pi) of awarding machine.

The full detail that each user i has received to the scope 5 in scope 1 is shown S-i.

(2) secret decoding is handled

The decoding of maintaining secrecy handle be by all users from being kept by each user and processing by the secret element S of acquisition the information S-i of above-mentioned secret shared procedure, Fig. 6 is the process of this processing.

(scope 1) each user i (i=1 ..., n) broadcasting hush values S-C (i) and be included in S-r (i) (processing R1, i) in the message segment S-i.

(scope 2) each user i (i=1 ..., n) from the value of broadcasting in scope 1, choose t+1 value S-C (i, 1) ..., S-C (i, t+1) and S-r (i, 1) ..., S-r (i, t+1).Then, obtain S (C) and S (r) as a result by interpolation polynomial.User i checking whether two end values equates and the broadcasted values that keeps is correct value for the multinomial of corresponding S (C)=r.When all values are correct, can determine that secret element S equals S (C)=S (r), decode procedure finishes.When not corresponding same polynomial value was broadcasted, (information B2 i) was broadcasted and (handles R2, i) to be included in the column vector S-C (i) of message segment S-i

(scope 3) each user i (i=1 ..., n) from the column vector S-C (j) that in second scope, is broadcasted (j=1 ..., n) the middle partly matrix S ＇ that produces.Then, user i is from respect to all altogether collection t1 ..., t _m(m= _nC _T+1/ (t+1)! (n-t-1)! ) in choose the column vector collection, T1 ..., Tm, all this collection t1 ..., tm comprises by 1 ..., the t+1 that n forms a different value.End value S ＇-r (1) ..., S ＇ (r) and S ＇-C (1) ..., the corresponding row and column that S ＇-C (n) obtains by interpolation polynomial.Near and, use interpolation polynomial can obtain S ＇ (r) and S ＇ (c) as a result by above-mentioned value.User i checking whether two in these end values whether equate and all elements of these column vectors for respective value S ＇-C (1) ..., S ＇-C (n) and S ＇-r (1) ..., the multinomial of S ＇-r (n) all is correct values.

At collection T1 ..., comprising in the middle of the Tm that the t+1 column vector has been verified like this, the number of times maximum of the collection of corresponding different correct part matrixs is that t+1 and part matrix are called as S-1 ..., S-T (T＜t+1) here.When only having a correct part matrix (T=1) here, can determine, be to equal initial maintaining secrecy for the secret S of this matrix, but not the user that corresponding column vector represents to carry out unauthorized action.When existing two or more correct part matrixs, each user i (i=1 ..., all message segments of (the handling R3, i) of n) broadcasting that it kept (information B3, i).

(reprocessing) each user i (i=1 ..., n) use the information S-j in the 3rd scope, broadcasted (j=1 ..., n) remove to calculate identical single channel hash function, these computational methods are used in above-mentioned secret shared processing.Like this, user i checking whether all broadcast messages be that correct and correspondence the value S* that is broadcasted when the shared processing of first scope.This just can determine that the secret S ＇ of corresponding correct part matrix (may exist and at most only have) equals secret element S here.On the other hand,, can determine if do not find correct part matrix, secret sharing users d executed unauthorized action (handle Pi).

As mentioned above,, require the traffic of n^2k power, and the above-mentioned traffic that requires for common conversational method (1) is the n^3k^2 power according to this embodiment.Near and, only require once to calculate the single channel hash function in this embodiment, and require to calculate the n power of a specific single channel function for common non-conversational method (2).Like this and the desired traffic of the usual method that can provide and amount of calculation compared, it all is actual using the traffic and the amount of calculation of the inventive method.

(embodiment 2)

Handling the section processes that is used as the shared method of common safety as the secret shared processing of verifying in embodiment 1 and the decoding of maintaining secrecy (sees, for example, " SecureMultiparty Protocols and Zero-Knowledge ProofSystemsTolerating A Faulty Minority ", D.Beaver, Journalof Cryptology, 1991, or " A Note On Multiparty Protocols ToCompute Multiplicative Inverses; M.Cerecedo; T.Matsumoto; and H.Imai, SCIS ¹94, Biwako, Japan, January 1994), making to provide more effective sharing operation treatment system.

In share operating system, share with multiplication process and share and add to handle being used as basic processing, part adds the section processes that processing is used as the part multiplication process.Use to share and multiplication process and share and add and handle the two and can carry out general algorithm operation at the finite aggregate that provides.To explain as sharing of handling of the essential part of all processing and add processing, can use the situation of the performed operation of processing among the embodiment 1 referring to Fig. 7.

When two secret element X in given finite aggregate and Y are shared (at this moment, each user is keeping distinguishing secret part X-i and the Y-i of corresponding secret element X and Y), not executive communication, secret part (X+Y)-i of corresponding X+Y in the finite aggregate that provides is calculated by following.

At first the hush values X-r (i) of the part matrix of the element of column vector X-(Ci) and Y-C (i) and each user maintenance and the element of Y-r (i) carry out addition.This definition from part matrix can find out significantly that the result that (element of row and column is polynomial value) adds is that X-C (i)+Y-C (i) and x-r (i)+y-r (i) are column vector and the hush values that is relevant to the part matrix of X+Y.

Be stored as checking message segment and single channel Hash functional value X* and Y* of using in secret decode procedure.When the result who adds of X+Y carried out decode procedure at that time, these values were used and have verified so the part matrix X+Y of corresponding secret x+y according to need.

Use above-mentioned sharing to provide the general algorithm operating system of sharing as section processes with additive process.

The present invention is not limited to the dimension of described part matrix in the above-described embodiments, and can be the part matrix of multidimensional number.Near and; the function that uses can be the function outside the single channel hash function; as long as it is just passable that this function guarantees to obtain the single channel characteristic; as for downcutting and selecting technology; it be not limited in embodiment 1 the special process of setting forth, as long as it can include the checking characteristic and not have any method of maintaining secrecy of revealing.

As mentioned above, according to this embodiment, use as the user and carry out a unauthorized action and the method and system of the processing security information that can be identified, this method and system just can be realized by the communication of effective dose and the calculating of effective dose.

In addition, because the traffic and amount of calculation are less than handling for for example handling the safe sharing operation that need repeatedly carry out secret shared processing under normal conditions, can reduce the communication in communication system, because calculating has reduced communications cost and can carry out under high speed owing to calculating this processing in a small amount in a small amount.

To use above-mentioned maintaining secrecy to share method by the shared method that produces of digital signature that a large number of users that belongs to same signature group is carried out.

In this embodiment, use the above-mentioned shared method of verifying of maintaining secrecy.The user who belongs to a signature group shares the secret conduct of being shared by interior their all secret elements selected at random of group and use and is signing for deciphering to produce to give birth in the shared process of exporting, and this signature obtains by carrying out shared algorithm operating.

In this embodiment, therefore, can provide a digital signature system of sharing, use this system, carrying out the non-user who only awards can be identified, and the amount of calculation and the traffic are all in the amplitude number of times of reality.

Fig. 9 is the figure of this embodiment.

At Fig. 9 internal information processing instrument 11 is that user in the system uses, broadcast communication channel 12, and those parts of secure communication channel 13 and Fig. 1 are identical.Here user A, B, C have formed one group of signer, and the structure of arrays of information processing instrument 11 is as shown in Figure 2.

Use such arrangement, use the method for the digital signature of sharing to set forth (embodiment 3) especially

To describe in this embodiment, use is by the special structure of the method for the shared digital signature of the above-mentioned digital signature of C.P.Schnorr proposition.

At first, 1 ..., the secret element among the P-1} verifies that by use is above-mentioned the shared method of maintaining secrecy is shared.This secret element 11 ..., 1K be at random from 1 ..., select among the P-1}.In this manner, processing can be done, and a specific user's of there signer group secret element is shared and kept by all interior users of this group.

For sharing digital signature system, go the process of the public information (same publicty effect such as public information and it are used to verify the signature of generation) of security information of generation group (it is equal to a privacy key and organizes interior all users as the signer and share) and corresponding security information to explain for using the shared method of maintaining secrecy.Key production process (seeing Figure 10 A and 10B).

(scope 1 to 5) each user i at random from 1 ..., P-1} chooses secret element a (i) and all users in the signer organizes share by carrying out above-mentioned secret shared procedure.Near and, each user i calculates g^ (r (i)) mod q (q is the prime number of selecting as stated above) here, then by broadcast communication channel broadcasting it.

(scope 6) carries out the reprocessing of secret shared procedure.The correctly shared secret element r (i) of use (i=1 ...,, use the shared output that obtains with reference to shared the adding of Fig. 7 elaboration to be defined as security information a n) as input.Near and, value A (i)=g^ (a (i)) modq, this value is broadcasted with respect to the correct pre-treatment of sharing secret element a (i) in scope 1 to scope 5, and this value is multiplied each other, and obtain as a result A=g^a modq is used as the public information (public label) of checking by the signature of group generation.

To carry out the shared multiplication of sharing a secret element x and common element a in order resembling sharing the addition, to relate to the element of the part matrix of x*a by the result who uses each element by user's retaining part matrix of elements to multiply each other to obtain.

Therefore, can carry out the shared calculating of two linear combination a*x+b*y that share secret element x and y and common element a and the dialogue between the user in need not organizing.Linear combination is handled as shown in figure 11.What note is, has provided each user's of the title that will be performed processing and this processing input and output in Figure 11.User i (i=1 ..., input n) is with respect to the message segment x-i and y-i and common element a and the b that share secret element x and y.Output is with respect to the linear combination message segment z-i of x as a result.

Use the privacy key that obtains by above-mentioned processing, the digital signature of given information m has been produced and has been shared simultaneously as follows by this group

Signature produces handles (seeing Figure 12)

(scope 1 is to scope 5) each user i randomly from 1 ..., P-1} chooses secret element r (i) and makes and be chosen for signer all users in organizing and share by carrying out above-mentioned secret shared procedure.Near and, each user i calculate g^ (r (i)) modq (q is a prime number of choosing as stated above here) and by broadcast communication channel broadcasting it.

(scope 6) carries out the reprocessing of secret shared processing.Use correct shared secret element r (i)=(i=1, n) as importing by carrying out the r as a result that shared addition obtains to share, near and calculate R=g^modq, R is the result of value R (i)=g^ (r (i)) modq product and was relevant to correctly shared secret element r (i) at 1 to 5 o'clock and is broadcasted in scope.

(scope 7) each user uses by the value R/m that makes up given information m and obtain at 6 acquisition values of scope R and calculates output e=h (R/m) with above-mentioned predetermined function h and handle indoor shared and calculating S=r+h (R/m) the * a of usefulness all the signer organizes in by carrying out shared linear combination.

(scope 8 to 10) uses the secret decoding processing of sharing method of maintaining secrecy that the secret S that shares is deciphered.The signature definition of given information be (R, S).Use the signature verification process of publicty effect and combine digital endorsement method that the signature that produces is verified, when signature is incorrect, can determine the user of unauthorized action that has been executed here, the secret decode procedure of sharing method of maintaining secrecy is performed discerns such user.

(embodiment 4)

The special construction of digital signature method is shared in realization that describe to use the previously described numeral mirror name method that is proposed by A.Fiant and A.Schamir, at first be can verify maintain secrecy the execution element 1 ..., the special arrangement in the N-1}.

The part matrix of given secret S will be explained (see figure 3) especially.From 1 ..., the part matrix S=(S (i that the specific secret S of N-1} is relevant, j)) (i, j=1 ... n) be such formula, there each row vector (S-r (i)=(S (i, 1) ... S (i, n)) i=1 ..., element n) is defined as follows: S (i, j)=S-r (i) * q-r (i, 1) ^ (j) * q-r (i, 2) ^ (j^2) * ... * q-r (i, t) (j^t) mod N (j=1 ..., n)

Element q-r (i, 1) ... q-r (i, 1) be from 1 ... select among the N-1}, make and satisfy following requirements, each column vector (S-C (j)=(and S (1, j),, S (n, j)), j=1 ..., n) be defined as follows: S (j, i)=S-C (j) * q-C (j, 1) ^ (K) * q-C (j, 2) ^ (i^2) * ... * q-C (j, t) ^ (i^t) mod N (i=1 ..., n)

Element q-C (j, 1) ..., q-C (j, t) be from 1 ..., select among the N-1}, make and to satisfy following requirement, near and have above-mentioned value two vectors (S-r (1) ... S-r (n)) and (S-C (i) ..., S-C (n)) satisfy from { 1,, the q-r that takes out among the N-1} (1) ... q-r (t), q-C (1) ..., the following requirement of q-C (t):

S-r(j)＝S*q-r(1)^(j)*q-r(2)^(j^2)*…

* q-r (t) ^ (j^t) mod N (j=1 ..., n) and

S-C(i)＝S*q-C(1)^(i)*q-C(2)^(i^2)*…

* q-C (t) ^ (i^t) mod N (i=1 ..., n), S representative here is initial maintains secrecy

Secret shared procedure is distributed to secret part, make secret element S to have to be belonged to all users of same signer group to share and keep that the user's of the secret or identification unauthorized behavior of execution (if having such action to take place) that decoding is shared like this secret decode procedure is to be carried out in the processing (1) of first embodiment and the method for (2) execution.Handle in (2) in the decoding of maintaining secrecy, do not use polynomial interpolation and carry out following calculating, so as from be included in each row vector (S-r (i)=(i, 1) ... S (i, n)) i=1 ..., t+1 element (S (i n), j0) ..., acquisition value S-r (i) among the S (i, jt)):

S-r (i) ^ (n! )=Prod-K (S (i, jk) ^ (prod-1 (1*n! / (1-K))) mod N here ProdK (k=j0 is worked as in f (K) representative ..., the product value of f during jt (k), and the t=j0 among Prod-1 (g (1)) the typical value g (1) ... jt (the product value of g (1) 1 ≠ R) time.

Similarly, for from each column vector (S-((i)=(S (and 1, j) ..., S (n, j)) j=1 ..., the element of t+1 n) (S (i0, j) ..., (it, j) middle acquisition value S-C (j) will carry out following calculating to S.

S-C(j)^(n！)＝Prod-k(S(ik，j)^(Prod-1(1*n！/(1-k)))mod?N

For from segment vector (S-r (1) ^ (n! ) ..., Sr (n) ^ (n! ) or (S-C (1) ^ (n! ) ..., S-C (n) ^ (n! ) t+1 element (S-r (i0) ^ (n! ) ..., S-r (it) ^ (n! ) or (S-C (j0) ^ (n! ) ... S-C (jt) ^ (n! ) in obtain secret S, carry out following calculating (when S-r (i) ^ (n! )) time:

S^(n！*n！)＝Prod-k(S-r(k)^(n！*Prod-1(1*n！/(1-k)))mod?N

S=(S^ (n! * n! )) ^u* (S^1) ^mod N notes, yet that is by A, Fiant and A, the digital signature method employed 1 that Shamir proposes is so to choose, make u and V satisfy u*n! * n! *+and V*1=1, the value S^1 modN that shares secret S produces in the processing at the following signature that will be described and is calculated.

Can handle by this way, the secret element that the specific user of there in the signer organizes keeps can be shared by all users in the group and keep, use this security information (this is to be equal to the privacy key of sharing for all users in organizing) of maintain secrecy sharing method and producing and be the shared digital signature system of security information (this equates publicty effect) key generation processing, will explain this process below for verifying that signature that this group produces uses for signer in organizing.

(scope 1 to 5) each user i randomly from 1 ..., N-1} choose secret element a (i) and by carry out above-mentioned secret shared procedure make make be chosen for the signer organize in all users share.Near and, each user i calculate a (i) ^1mod N (the 1st, the element that said method is chosen) and by the road broadcasting of broadcast communication news it.

(scope 6) carries out the reprocessing of secret shared processing.Use the correct secret element a (i) that shares (i=1 ... n) be defined as security information a as the shared output of importing and obtain by following shared multiplication.Near and, value A (i)=a (i) the ^1 mod N that is broadcasted with respect to the preliminary treatment of the scope 1 to 5 of correctly sharing secret element a (i) time is multiplied each other.The mod of the A=a^1 as a result N that obtains is used as the public information of checking by the signature of group generation.

To in scope 6, explain the multiplication process of using of sharing with reference to Figure 14.

When 1 ..., two secret element X in the n} and Y are that secret shared processing is when sharing (each user i is keeping secret part X-i and the y-i of corresponding secret element X and Y), communication is not carried out, be included in 1 ..., the secret part of the product X*Y of N-1} is calculated by following.

Can find out significantly that from the definition of part matrix the hush values X-r (i) of the part matrix that is kept by column vector X-C (i) and Y-C (i) and each user and Y-r (i) are multiplied each other and X-C as a result (i) the * C (i) and X-r (i) the * Y-r (i) that obtain are column vector and the hush values of part matrix X*Y.Two single channel Hash functional value X*Y* that are stored in authorization information section in the secret decode procedure and use in the decode procedure of result of product X*Y, use them to remove checking and the corresponding to part matrix X*Y of secret X*Y as required.

An index product of sharing secret element X and common element a is shared similarly, the index of the element of the part matrix that each user has and common element a multiplies each other and the result that obtains is the element of x^a part matrix, like this two secret element X that share at said process and Y and common element ab is combined as X^a*Y^b and can is shared and calculates and need not the mutual dialogue between the user in the adding group, among Figure 11, this process provides in Figure 15 as it.

The privacy key that obtains by above-mentioned processing is organized uses that to produce the digital signature of sharing as follows for given information m.

(scope 1 to 5) each user i randomly from 1 ..., choose a secret element r (i) among the N-1}, by carry out above-mentioned secret shared procedure make be chosen for the signer organize in all users share.Near and, each user i calculate r (i) ^1 mod N (1 is the element that said method is chosen here) and by the road broadcasting of broadcast communication news it.

(scope 6) carries out the reprocessing of secret shared processing, the correctly shared secret element r (i) of use (i=1 ..., n) as input, the r as a result that uses above-mentioned shared multiplication to obtain to share.Near and calculate R=r^1mod N, it is the value of the multiplication of value R (i)=r (i) ^1 mod N of being broadcasted with respect to correct shared secret element r (i) in scope 1 to 5.

(scope 7) each user uses the value R/m that obtains by the value R that makes up given information m and obtain in scope 6 to calculate output e=h (R/m) for input with above-mentioned predetermined function h, use share linear combined treatment make S=r*a^ (h (R/m) organized by the signer in all users share and calculated.

The secret decoding that (scope 8 to 10) use to maintain secrecy shares method is handled and is deciphered sharing secret S, the signature of given information be defined as (R, S).Use publicty effect a and use the processing of the signature verification of digital signature method that the signature that produces is verified.When signature is incorrect, can determine that this is to have carried out the non-only user of action that awards, the process of the secret decoding of the shared method of maintaining secrecy is performed discerns such user.

(embodiment 5)

The special construction of the shared digital signature method that uses the digital signature method that is proposed by T.EIGamal (American National Standard, Digital Signature Algorithm) will be described in this embodiment.

That be used as shared secret element that the specific user of signer in organizing choose in the method that embodiment 1 describes and be the specific process that all users held in organizing.Set forth now that using maintains secrecy and share method and go to the process of public information (public information that is equivalent to publicty effect is used to verify the signature of generation) of security information of generation group (this is equivalent to the privacy key that all users shared by signer's group) and security information and the system of shared digital signature.Key production process (seeing Figure 10 A and 10B)

(scope 1 is to scope 5) each user i randomly from 1 ..., P-1} chooses secret element a (i) and such choosing, and all users are shared by the signer organizes by carrying out above-mentioned secret shared procedure.Near and, each user i calculate g^ (a (i)) mod q (q is the prime number of choosing as stated above here) and by the road broadcasting of broadcast communication news it.

(scope 6) carries out the reprocessing of secret shared processing.The correctly shared secret element a (i) of use (i=1 ..., n) as input, the shared output that is obtained by following shared addition is defined as security information a.Scope 1 to 5 with respect to the correct processing of sharing secret element a (i) time value A (i)=g^ (a (i)) mod q of being broadcasted multiplied each other, the q of A=g^mod as a result of acquisition is used as the public information (publicty effect) of the signature that checking produces by group.

When { 1, two secret element X in the P-1} and Y be secret shared procedure when sharing (when each user i holds the secret part X-i of relative secret element X and Y and Y-i) do not carry out communication, be included in (1,, P-1) secret part (the X+Y)-i with X+Y in calculates according to embodiment 1 described method.

When in secret shared processing, share 1 ..., when two the secret element X of P-1} and Y, do not carry out communication, be included in 1 ..., P-1) secret part (X*Y)-i of Nei long-pending X*Y calculates as follows.

When a specific user d 1 ..., P-1) in execution can verify shared secret S the time, it calculates shared long-pending S*X by secret S and the previous X that shares safely.This process is called as maintaining secrecy of can verifying and shares and multiplication process.Maintaining secrecy of can verifying shared and multiplication process (seeing Figure 17 and 18)

After this h is represented as the effective single channel hash function among the embodiment 1, satisfies k=nk ＇ for specific constant security parameter k ＇.

(scope 1) user d use random number generation unit 23 go to produce secret element S and from 1 ..., the secret element of selecting at random among the P-1} 11 ..., the part matrix of 1k.Computational security value S-r (1) ... S-r (n), 11-r (1) ..., 11r (n) ..., 1k-r (1), the single channel Hash functional value S* (see figure 4) of 1k-r (n).

User d transmits column vector S-(i), L1-C (i) ..., the secret S-r (i) of the part matrix of LK-C (i) and each generation, 11-r (i) ..., 1K-r (i) by secure communication news road to each user i (i=1 ..., n, comprise it oneself).Be broadcast to all users (in Figure 17, be expressed as and handle R1, d) with hashed value S* (B1 of Figure 17, d) by broadcast communication news road.

(scope 2) each user i (i=1, n) use the secret S-r (i) that in scope 1, receives, 11-r (i) ..., 1K-r (i) and the previous X-r (i) of X that shares are as input, calculate t-r (i)=S-r (i) * X-r (i), m1-r (i)=11-r (i) * X-r (i) ..., mk-r (i) * X-r (i) mod N.Random number 23 is used the generating unit sub matrix, and (it is called as T (i), M1 (i) ... MK (i), and the part matrix X-r (i) of the previous secret X that shares is called as X (i)) as the result who obtains, computational security value t (i)-r (i) then, t (i)-r (n), m1 (i)-r (1) ... m1-r (n),, mk (i)-r (i) ..., the Hash functional value (see figure 4) of mk (i)-r (n).Each user i transmits column vector T-C (j), M1-C (j), the secret t (i) of the part matrix of MK-C (j) and each generation-r (j), m1 (i)-r (j) ... mk (i)-r (j) arrives each user j (j=1 by the broadcasting news road of maintaining secrecy,, n comprises itself) and hashed value S* be broadcast to all users (in Figure 17, be expressed as and handle R2, i) by broadcast communication news road.The information representation that user i has broadcasted is Bs, i among Figure 17.

(scope 3) each user i (i=1 ..., the n) position (the process R3 among Figure 17, i) of using random number generating apparatus to go to broadcast picked at random.Each of the K ＇ position of picked at random is called as Bi-1 ..., each of a Bi-k and entire n user's figure place is called as B1 ..., Bk, user i second is expressed as B3, i through the information of broadcasting in Figure 17.

(scope 4) if in scope 3 broadcasting each Bj (j=1 ..., be 1 k), user d broadcasts the part matrix that is produced by user d in first scope so.If Bj is 0, users broadcasting is by part matrix S that adds generation and the result's (being written as S+Lj) (processing R4, the d of Figure 17) who obtains at the Lj of finite aggregate.Information by user d broadcasting is expressed as B4, d in Figure 17.

(scope 5) is for the information B1 that has maintained secrecy and received in scope 1, each value j (j=1 of i, k), each user i (i=1,, n) whether verify column vector Lj-C (i) and Lj-r (i) (when the Bj in the broadcasting of second scope is 1), or Lj-C (i)+S-C (i) and Lj-r (i)+S-r (i) (when Bj is 0) equal column vector and the hush values of the part matrix of broadcasting in the 4th scope.When they were not equal to relevant particular value j, decision information was by user d broadcasting (handling R5, i in Figure 17).Information by user i broadcasting is expressed as B5, i in Figure 17 and 18.

(scope 6) is if at each Bj (j=1 of the 3rd scope broadcasting, k) be 1, the part matrix Mj (i) that each user i broadcasting is produced by user i in second scope, if Bj is 0, user d broadcast results (T that writes (i)+Mj (i)), this result is (the handling R6, i at Figure 18) that obtains by the Mj (i) (mod P) that adds the part matrix T (i) that produced and finite aggregate, near and, user d broadcasting uses the information by family d broadcasting to be expressed as B6, i at Figure 18 at the column vector of the definite user i of the 5th scope.

(scope 7) for each j (j=1 ..., k), the information that user i checking is broadcasted in the 5th and the 6th scope, when correct matrix function greater than threshold values t and the position of the 3rd scope broadcasting Bj (j=1 ..., k) being at 1 o'clock, following part matrix is broadcasted:

(1j-r (i) ^ (1) * Mj (i)-X (i) is when Bj is 0, and following part matrix is broadcasted.

(S-r (i)-1j-r (r)) ^ (1) * (T (i)+Mj (i))-X (i) (at processing R7, the i of Figure 18), by the linear combination (for each element) of aforementioned operating part matrix, the information that user i has broadcasted is expressed as B7, i at Figure 13.

(scope 8) for each j, 0 (j, 0=1 ..., k), each user i (i=1 ..., n) use the information of broadcasting in the 4th scope.When B0 was 1,1j-r (0) was decoded, below the calculated column vector, the result who obtains when the calculated column vector be equate with correspondence value of wearing 0 time, it is verified:

(1j-r (0)) ^ (1) * Mj (0)-r (i)-X (0)-r (i) when B0 be 0, (S-r (0)+1j-r (0)) is decoded can to verify that with the column vector that calculates below vector result of calculation is identical and the correspondence value of wearing 0:(S-r (0)+1j-r (0) ^ (1) * (T (0)-r (i)+Mj (0)-r (i))-X (0)-r (i).When the result can not be verified as corresponding specified value 0, user 0 decision information was broadcasted (processing R8, the i of Figure 18).The information that user i has broadcasted is expressed as R8.i in Figure 18.

(scope 9) when decision information when scope 8 is broadcast to user 0, he broadcasts its column vector (the processing R9.0 of Figure 18), the information that user i has broadcasted is expressed as R9.i in Figure 18.

(scope 10) each user i verifies all broadcast messages and broadcasts the user's 0 who has carried out unauthorized row decision information (at the processing R10.i of Figure 18) that the information that user i has broadcasted is expressed as B10, i in Figure 18.

The linear combination of sharing of shared portion matrix S (i) the * X (i) that (reprocessing) is correct is all users performed (processing list of each user i is shown in the processing Pi among Figure 18), so correct part matrix S*X is shared and calculates, in the time can not producing matrix owing to unauthorized action, the user of mistake is identified with the result and is broadcasted.

By said process, specific user i randomly from 1 ..., shared and while computational security S that the secret element S quilt of choosing among the P-1} can be verified and the product S*X that before can verify shared secret X.Secondly will describe by carrying out above-mentioned processing to obtain two computational processes of sharing secret X and Y, this process such as Figure 19.

(scope 1 to 10) each user i randomly from 1 ..., choose secret element r (i) among the P-1} and the element selected carried out the above-mentioned shared procedure of verifying and calculated r (i) * Y simultaneously.

(scope 11) by use previous share add be implemented as all user j1 (1=1 ..., m) with for they can share secret calculating r=r (the i)+r (j1) that is executed correctly with verifying ..., r (jm) and r*y=r (j1) * y+r (j2) * y+ ... + r (jm) * y.

(scope 12) is to maintaining secrecy and shared the adding of U=X-r execution.

(scope 13-15) all users decipher secret U,

(scope 16) carries out the calculating of sharing to secret linear combination Z=r*y-U*y=X*y.

By said process, the long-pending X*y of two shared secret element X and Y can be added into the privacy key that the user of this group shares and calculates, uses above-mentioned processing to obtain, and the digital signature of given information m is shared as follows by group and produced.Signature produces handles (seeing Figure 20)

(scope 1 to 5) each user i is randomly from { 1, select secret element r (i) among the P-1}, use above-mentioned secret shared processing to make this all user that are chosen for signer's group share, near and, each user i calculate g^ (r (i)) mod q (q is the prime number of choosing with said method here) and by the road broadcasting of broadcast communication news it.

(scope 6) carries out the reprocessing of secret shared processing, the correctly shared secret element r (i) of use (i=1 ...,, obtain shared r as a result by carrying out shared addition n) as input.Closely calculate R=g^r mod q, this R is the product of value R (i)=g^ (r (i)) modq, and it is that correct relatively shared secret element r (i) is broadcasted in scope 1 to 5.

(scope 7) each user uses given information m to remove to calculate the output e=h (m) of above-mentioned predefined function h as input.Then, use and share linear combined treatment, all users in b=(e+R*a) is organized by the signer share and are calculated.

(scope 8 to 17) S=b*r^ (1) here shared by all users of signer's group of using above-mentioned shared product and calculated.(element reciprocal of (r (i) ^-1) mod q is handled, and does not use g^ (r (i)) mod q (referring to scope 1-5) in the random number generation is handled for fear of sharing r^ (1) g^.

(scope 18 to 20) uses the secret decoding of sharing method of maintaining secrecy to handle shared secret decoding.The signature definition of given information m be (R, S).Use publicty effect and combine digital endorsement method and signature-verification process to verify the signature that has produced.When signature when being incorrect, can determine that this is the user who carries out unauthorized action, it is exactly to discern such user that the secret decoding that carrying out maintains secrecy shares method is handled.

The present invention is not limited to the dimension of the part matrix described in the foregoing description 3 to 5, and can be multidimensional part matrix number.Near and function that use is not a single channel function of guaranteeing to obtain the single channel characteristic.As for downcutting and selecting technology, this is not limited to the special process explained among the embodiment 1, and can be checking characteristic and any method of not betraying the pot to the roses.

As mentioned above, according to the present invention, it can provide shared digital signature method, the correct signature number of the group of forming when a large amount of computers (signer) that are connected to communication system is during greater than threshold values t, produce a signature by group, when the signer carries out a unauthorized action, can discern this signer, invention and common shared digital signature method are compared, even when unauthorized action takes place, correctly sign and also can produce, the method for this embodiment only needs the communication and the calculating of effective dose.

Near and and can not discern the common shared digital signature method that the user who makes mistakes can not produce signature and be compared, use this method can discern the user who makes mistakes, thereby method safety of the present invention is many.

More specifically, be the index multiplication owing to need to calculate maximum, require to be assumed to be identical with the required amount of calculation of the common digital signature method of the latter in fact for each signer's of adding signature group amount of calculation.The required traffic of each signer is 1*n^2*k power (on behalf of security parameter and 1 representative, n representative of consumer number here, k use the length of integer), thereby the traffic reality more required than the former common digital signature method is many.

Suppose, when the decoding of maintaining secrecy is handled, comprise t+1 different lines vector m=n! / ((t+1)! (n-t-1)! ) collection number consistent (seeing the secret shared processing in scope 3 embodiment 1), be not actually difficulty if n is not the user that little (n＜20) identification is very made a mistake.Therefore, when number of users hour, it is effective sharing method according to maintaining secrecy of this embodiment.Even when user's number when being little, maintaining secrecy of can verifying usually shared method and but required the communication and the amount of calculation that do not gear to actual circumstances.

Use the signature production method of this embodiment can reduce required communication and amount of calculation as mentioned above.In addition, because a spot of communication makes communication and communication cost at communication system to reduce, because a spot of calculating can be carried out processing at a high speed.

(embodiment 6)

Use big measuring appratus to carry out the embodiment of the discriminating of sharing in the communication system with being described in.

Figure 21 is the figure according to the communication system of one embodiment of the present of invention, and the present invention has shared and carries out the authentication information process instrumentation.

In Figure 21, extensively retouch communication news road 12 and secure communication news road 13 and have identical functions as those of Fig. 1.Instrument 14 is instrument AS (1) ..., AS (k) (being called " member " later on), they are to share authentication server.For the purpose of effectively, in this case member's number be defined compare less, 20 or still less.

The number that constitutes whole instruments of communication system can be much larger than member's number, and they are coupled to all members by secure communication news road 13.By the communication between normal (insecure) communication news road 16 execution instruments.When an instrument transmits the service request that another instrument has (, file transmits, remote call-in or the like), the instrument of asking like this is called as " client " (client), receive ask like this and provide the instrument of such service to be called as " server " at Figure 21, instrument 15 is instrument C/S (1) ... C/S (n), they are as a client and a server.It should be noted that a member can be a client or a server.

In this embodiment, client and server are used as the mutual discriminating and the discriminating of Content of communciation.Near and, client and server are shared the privacy key of carrying out secure communication.In addition, because security information is shared with control and computing information by the member, authentication server in this embodiment is more reliable than common authentication server.When client requires identification oneself to require server service, the client of require differentiating is called as the statement people, and the server that provides discriminating is called as the authentication people, comprises that each independent instrument of member's communication system is arranged in the structure of arrays shown in Figure 2.

The essential part of sharing the authentication protocol book is above-mentioned VSS (maintaining secrecy of can verifying shared) agreement.(sharing secret linear combination handles)

When two secret element X of given finite aggregate and Y are shared by two the above-mentioned secret shared processing that can verify (at this moment, each user i keeps secret part X-i and the Y-i of corresponding secret element X of difference and Y), communication is not carried out, and correspondence is calculated by following with secret part X+Y (X+Y)-i given finite aggregate.

At first the element of column vector X-C (i) and Y-C (i) and hush values X-r (element of (i) and part matrix Y-r (i) addition that keeps by each user, can find out obviously that from the definition (the row and column element is polynomial value) of part matrix the X-C as a result (i) of addition+Y-C (i) is the hush values of the segment vector of column vector and relative X+Y with X-r (i)+Y-r (i).

Being stored in the decoding of maintaining secrecy and being used for authorization information section employed single channel Hash functional value X* and Y* in handling.Use these values when the X+Y as a result that adds is carried out as required when decoding is handled, like this, just verified the part matrix X+Y of corresponding secret X+Y.

Near and, in order to carry out the multiplication of sharing of a secret element X who shares and common element a, multiply by the result that an element of the part matrix that the user keeps obtains is the element of the part matrix of relative X*a, like this, by above-mentioned process, can carry out the calculating of two linearity group a*X+b*y that share secret element X and Y common element a and b and the dialogue between the user in need not to organize.

In above-mentioned method, can be but maintain secrecy by being shared between the member who uses verification method.

Secondly will be set forth in the close generation agreement of shared pseudo-organizational security of member's shared generation pseudo random number.(pseudo random number of sharing is maintained secrecy and is produced agreement)

As the member AS (1) that shares authentication server ..., the secret part r (i) of the random secret r that AS (K) output is shared (i=1 ..., k) to the member AS (i) that controls r.Agreement press Figure 23 A and 23B shown in content realize.

Each member AS (i) produces the secret ri of pseudorandom (handling 81) that is represented as an element in a finite aggregate.

Make AS (i) share the secret ri of pseudorandom by carrying out the above-mentioned secret shared procedure of verifying secretly.Because each member carries out this process, each member AS (j) (j=1 ... k) keeping each member's secret part r1 (j),, rm (j), it should be noted that m (≤k) be proved to be and the member's that sharing of maintaining secrecy correctly carried out number (handling 82).

Each member AS (j) add the part of maintaining secrecy produce at one r (j)=r1 (j)+... rm (j), this value is with respect to the secret part of the secret r of pseudorandom of AS (j) (handling 83).

The secret r of pseudorandom is any unknowable per capita number, unless most of member has planned a secret, it is to have produced in above-mentioned mode that the pseudorandom of sharing is maintained secrecy, and produced can and authenticate talk key between the people as the statement people for random secret.

Now explain the agreement of carrying out the privacy key coding of sharing among the member, processing changes with situation, and the privacy key coded data is the private data of sharing in this case, and data are common datas in this case.(the privacy key coding/decoding of sharing of the private data of sharing)

Figure 24 A is the figure that explains this agreement,

One is formed N array m1 ..., mN, and be that length is arranged is that the information of N is defined as m.Notice that the VSS agreement is at finite aggregate GF (2 ^L) on carried out, secret part m1 (i) ..., mN (i) is assumed to be in member AS (i) and shares secretly.Near and, the same privacy key pk with equal length with information m is divided into each N with L length array pk1 ... Pkn. these arrays are shared in above-mentioned member secretly, make member AS (i) have each independent secret part pk (i) ..., pkN (i).

In order by use privacy key pk information m to be carried out the privacy key encoding process, each member is as follows to carrying out addition in each array of given finite aggregate:

cl(i)＝m1(i)+pk1(i)，…，cN(i)＝mN(i)+pkN(i)。

Since the VSS agreement form be half-phase etc., C1 (i) ..., cN (i) corresponding the statement C by dividing coding be the secret portion C 1 that N the array of L obtains for each length ..., CN.Therefore, use aforesaid secret decoding to handle code statement e is deciphered, the statement C of this coding becomes public.

Instrument with communication system of privacy key pk can translate initial information m from public code statement C.Notice that privacy key pk only uses once and never and reuses.(the privacy key coding/decoding of sharing of common data)

For public information m, when using above-mentioned coding protocol, by from making privacy key pk for known to the third party, because the agreement in Figure 24 B is used by common data for deducting information m the public code statement C.

As providing well in precedent, information m has a N array m1 that length is L ... mN forms, and the content of information m is the known common data of member, and privacy key pk is two double-lengths of information m and the 2N array pKN-1 that is divided into length L, pKN-2 ..., pKN-! And pKN-2, each keeps secret part pk1-1 (i) to pK individually in order to share with member AS (i) between the member secretly, pk1-2 (i) ..., pkN-1 (i), pkN-2 (i).

For by using privacy key pk to be that information m realizes privacy key pk encoding process, each member AS (i) is the following algorithm operating of each array execution on given finite aggregate, in following expression, represent multiplication with+represent addition:

C1(i)＝m1·pk1-1(i)+pk1-2(i)…，

CN(i)＝mN·pkN-1(i)+pkN-2(i)。

Owing to the information of VSS agreement for having the secret portion C 1 that the N array of length L obtains for each by the statement C that divides coding ..., CN corresponding linear combination C1 (i) ... CN (i) is semiidentical.Therefore, code statement C is used the aforementioned secret decoding processing of execution and decodes, and becomes public.

From the above mentioned and since the agreement book use a key pkj-1 of two types and pkj-2 (j=1 ..., N) no matter information m becomes common data this all has no chance to reveal privacy key pk.Though it is easier to use short L to encode, it is 2-L for mistake volume statement C ＇ with the probability that error message m ＇ is provided that the people who makes mistakes revises statement C, and the L value can not be selected very for a short time for reasons of safety, and like this, suitable L value is to be about 32.

As for decoding, use the instrument of the communication system of privacy key to carry out pkj-for each length L at public decomposition privacy key pk and coding words sentence C, the algorithm operating of pkj-2 and Cj (Cj-pkj-2)/pkj-1 is to obtain mj, and by this process, initial information m can be decoded.Privacy key pk only can use once and in this case and never re-use.(authentication protocol)

Use above-mentioned agreement by sharing authentication server, and it is as follows not use the authentication server of common centralization can realize having the discriminating of publicty effect

The authentication protocol communication receives authentication information and provides authentication data by the artificial authentication of communication statement people from the authentication server of sharing by communication statement people, and this is called as " connecting machine handles ".

Prerequisite as the machine processing of the company of execution, at shared authentication server with as the privacy key shared procedure between statement people or the authentication people with by the talk key production process of sharing authentication server is necessary, can carry out processed off-line each time, privacy key or talk key need when connecting the machine processing, and machine is handled the needed time and communication time has been extended but connect.

When processed off-line is when connecting machine and handle, companys of execution machine is handled effectively, " processed off-line " and connect the machine processing and will be described respectively referring to Figure 25 A and 25B.(processed off-line)

Must be information sharing Sharing Information between the member of authentication server in advance with respect to this privacy key of all appts, as what in sharing privacy key coding/decoding agreement, set forth, yet, after information coding or decoding, must the configuration privacy key between statement people and shared authentication server.Like this, must produce a lot of keys, transmit to handle by following privacy key and can carry out this processing, the secret production process of shared pseudorandom that is used as talk key between statement people and the authentication people also is performed as follows during processed off-line.(privacy key transmits and handles)

Require the instrument j of the communication system of discriminating to carry out secret shared processing prior to sharing, between the member, at random chosen the secret pkj-1 of pseudorandom,, the effectively big number M of pkj-M, member AS (i) receives the secret part pkj-1 (i) that pseudorandom is maintained secrecy like this, pkj-M (i) maintains secrecy if instrument j shares improperly, and only instrument j does not receive the discriminating service of using its privacy key.Therefore, for verifying that whether Sharing Information is that correct reprocessing is not must will carry out just in this case, verify that by its all member j is not that the broadcast communication of wrong statement is interrogated the road and be there is no need to be provided between instrument j and the member and (see Figure 27).

In this process, the privacy key pkj-i that j remains valid big (i=1 ..., M) be a table, and each member h (h=1 ..., k) keep secret part pkj-i (h) (i=1 ..., M) be a table.As mentioned above, because privacy key only uses once, j and each member h keep pointer (index) pkj and pkj (h) respectively, the key that use next time in their dial gauges, when it can be done like this, instrument j produces a new privacy key, when communication system does not use, shares this privacy key and is upgraded constantly.(pseudorandom is maintained secrecy to produce and is handled)

As shown in figure 26, when when privacy key transmits processing, be at the secret r1 of pseudorandom that shares that states the talk key that uses between people and the authentication people ... RQ is produced and is maintained in the table when processed off-line.Maintain secrecy in order to produce shared pseudorandom, produce as maintaining secrecy described in the agreement in the pseudorandom of sharing, the essential secret shared procedure of pseudorandom of carrying out of all members, yet, because all members do not carry out that processing at the same time, when not handling when being performed and communication system when not being used, they can be carried out and handle and share maintain secrecy other member of the pseudorandom that produces then.Then, each member keeps the secret r1 of pseudorandom (j) that shares ..., indicating the pointer of its position when rQ (j) and use is a table.(connecting machine handles)

The machine authentication protocol book communication system client P of company (statement people) that obtains from the authentication server of sharing is sent to the discriminating element of server V (authentication people) and will be carried out by step S1 to S4.

(step 1) client P by normal communication news road send to the member who shares authentication server comprise information (id-P, id-V, the information 101 of the requirement of S} (seeing Figure 28 A), this requires information to be called as AUTH-REQUEST.Notice that id-P represents client P, id-V represents the data of particular server V, the random number that the S representative is chosen arbitrarily.

(step 2) received that the member of AUTH-REQUEST carries out the process (seeing Figure 28 B) of following step S21 to S26.

The time mark of (step 21) indication current time is broadcasted with the public time and is identified.

(step 22) when use sharing the shared privacy key coding protocol book of private data, be used as talk key between statement people and the authentication people (k1 ... the secret rz of the pseudorandom of cka ..., rz+a-1 is by definition pkv-x,, pkv-x+a-1 is that the scrambling coding key is encoded.It should be noted that a representative indication pseudorandom secret number and z and x represent the pointer of the beginning of pseudorandom table and privacy key pk table.At this moment, the result that z and x are updated to z=2+a and the acquisition of x=x+a coding respectively is CT-1 ..., CT-a.

(step 23) uses the shared privacy key coding protocol book of common data, and mark id-P common time of harmony person of good sense identifier is used in the step 22, to the 2b privacy key of privacy key pk table, and pkv-x ..., pkv-x+2b is encoded.Pointer x is updated x=x+2b+1 then.The result that coding obtains is CT-a+1 ..., CT-a+b.This result and step 22 obtain results added to a piece, this value again with in the pointer x addition of carrying out before the step 22 upgrades.Obtain the result and be defined as differentiating element.

(step 24) uses the shared privacy key coding protocol book of sharing private data, the code statement CT-1 that use obtains at step S22 for the authentication people, CT-a+b and the publicty effect ck1 that uses at step S22, cka and by using 2a+b privacy key pkp-y ... pkp-y+2a+b encodes as key letter.Note, the pointer that the secret key table of y representative indication statement people begins, it is updated to Y=Y+2a+b+1, and Bian Ma result is CCT-1 like this ..., CCT-2a+b.

(step S25) uses the shared privacy key coding protocol book of common data, the id-V that has become secret S of public pseudorandom and authentication people identifier at step S1 is used from the 2C privacy key pkp-y of the secret key table that uses at step S24 ..., pkp-y+2c encodes.Pointer y is updated to y=y+2c+1.Bian Ma result is CCT-2a+b+1 like this ..., CCT-2a+b+c.Such result with the step S24 results added, final result is CCT-1 ... CCT-2a+b+c.

(step S26) carries out the decoding processing of maintaining secrecy and translates the CCT-1 that maintains secrecy and share ... CCT-2a+b+c.The result that decoding obtains is as authentication information 102 and be combined in the pointer y that step S24 upgrades and send client P to by normal communication news road, and he promptly is the statement people.

(step 3) statement people P reference pointer y that receives and the privacy key pkp-y that is included in his the own secret key table ..., pkp+2a; B; 2c and use the shared privacy key decoding agreement of common data to go from receiving data CCT-1 ..., translate the secret ck of pseudorandom among the CCT-2a+b+c.Then, S and id-v that statement people P checking translates are correct, and when they were verified, the secret ck of the pseudorandom that translates was stored and transmits the discriminating element 103 that translates to authenticating people's (seeing Figure 29 A) as authentication people's publicty effect.

(step 4) is differentiated interior pointer X of element and the interior privacy key pkv-y of the secret key table that is included in it with reference to being included in ..., pkv-y+a; 2b, authentication people V use the shared privacy key decoding agreement of common data to translate a time mark harmony person of good sense's identifier id-p from the discriminating element of receiving and use the privacy key of the sharing decoding agreement of sharing private data to remove to translate the secret ck of pseudorandom.The authentication people verifies that then the time mark that translates and the identifier id-p that translates are correct, when they are verified, statement people P is provided discriminating and the secret ck of pseudorandom that translates is stored (seeing Figure 29 B) as the publicty effect that combines with the authentication physiognomy.(embodiment 7)

In embodiment 6, when the people who makes mistakes eavesdrops that the statement people sends authentication people's discriminating element to and when having stored the discriminating element, the people who makes mistakes submits to and differentiates that element is to authenticating the people and can requiring to authenticate the service that the people provides the statement people not require, therefore, the statement people is disturbed, and this action is called as to respond attacks.

In this embodiment, therefore, additionally offered the discriminating element that is sent to the authentication people when connecting machine handling in the embodiment 6 of step S3 by the statement people in order to prevent to respond the temporal information of attacking exchange, this process provides at Figure 30 A and 30B.Processing in the present embodiment is identical with content among the embodiment 6, exception be to append in the process of step S3 ＇ and S4 ＇ and connect on the step S3 and S4 that machine handles.To explain the process that only goes on foot S3 ＇ and S4 ＇ below.(step S3 '), the statement people used the new time mark T2 of the talk key ck of acquisition and coding and for obtaining { T2, the statement people's of id-p}^ck identifier id-p after the step of embodiment S3 process is carried out.The statement people transmits authentication people and { T2, the id-p}^ck that differentiate that element combines.

(step 4 ＇) authentication people carries out the process in the step 24 among the embodiment 6 and removes to translate the discriminating element and use the talk key ck that obtains to remove to translate supplementary { T2, id-p}^ck, an authentication people proving time mark T2 harmony person of good sense's identifier id-p, when T2 was old one, he did not receive service request.

As mentioned above, according to this embodiment, this just can provide the common centralization management of a ratio authentication server performance that the authentication server of higher reliability and fail safe is arranged.

When most of instruments of sharing authentication server when being reliable, can provide following content.

Use the authentication protocol of sharing, to stating that the identical identification function of function of the authentication protocol that provides with common centralization management is provided for people and authentication people, has realized high inefficacy tolerance.

Company's machine of authentication protocol is treated to the statement people and the authentication people has guaranteed to be the same interface (data format) of common authentication protocol interface owing to share, common authentication server can be easily by the replacement of the authentication server in the present embodiment.

For statement people and authentication people, company's machine processing of sharing authentication protocol can provide with common discriminating assists desired identical amount of calculation.

Though the present invention has described the preferred form with specific special circumstances, under the situation that does not break away from the spirit and scope of the present invention, can realize many visibly different embodiment, be to be understood that invention is not confined in the certain embodiments, it should be established by appended claim.

Claims (30)

1. A confidential information processing method for confidentially sharing information between a plurality of information processing devices in a communication system in which the plurality of information processing devices are connected via a secure communication channel and a broadcast communication channel together, each of said devices exchanges information with another of said devices over a secure communication channel, and at the same time keeps said information secret from the rest of the devices, over a broadcast communication channel between said devices and all other The equipment commonly exchanges information, and said secret information processing method includes the following steps: generating a secret array for a plurality of second devices from the secret information by using a first device of said plurality of devices for processing said secret information; Using said first device to fetch a first segment of information from said secure array for said second group of devices, and transmit said first segment of information to said secure communication channel through said secure communication channel the second set of equipment; performing a predetermined function on the first piece of information using said first device, and broadcasting the resulting output value over said broadcast communication channel; generating a random number using said second set of devices, and broadcasting said random number over said broadcast communication channel; using said first device to generate a second set of information segments for said second set of devices from said secret array consistent with said broadcasted said random number and communicated over said broadcast communication channel broadcast said second set of information segments; using said second set of devices to generate a third set of information segments that is consistent with said second set of information segments from said first set of information segments received and all generated by said second set of devices corresponding to the random number; and Using said second set of devices, comparing said third set of information segments with said second set of information segments broadcast for said second set of devices, and verifying that said secret information is received by said shared by the first device. 2. The confidential information processing method as claimed in claim 1, wherein, in said verifying step, when said comparison result does not match, said second group of devices broadcasts a message via a broadcast communication channel, and when broadcasted Validation is performed on the basis of said information and . 3. The confidential information processing method as claimed in claim 1, further comprising using all of said second group of devices to translate said confidential information on the basis of said first information segment transmitted to said second group of devices code steps. 4. The confidential information processing method as claimed in claim 3, wherein, in said decoding step, said second group of devices performs calculations and performs calculations based on the results of the calculations independently, respectively, according to said received first piece of information. decoding. 5. The confidential information processing method as claimed in claim 1, wherein, said secret array is to determine the matrix used for said secret information and randomly selected secret elements, and the row vector and column vector of said matrix are defined as the Said the first piece of information. 6. The confidential information processing method according to claim 1, wherein said predetermined function is a one-way function. 7. The secret information processing method as claimed in claim 1, wherein said secret element information is an element in a finite set, and in said generating step, performing calculation on said said elements in the finite set . 8. A method for generating a signature for the communication system capable of executing the method for processing confidential information as claimed in claim 1, said method for generating a signature comprises the following steps: randomly selecting a first secret using each of said devices belonging to the same group of signers, and using said secret processing method to confidentially share the first secret with said devices in said group; performing a predetermined first function on said first secret using said device and broadcasting the obtained output value to all said devices in the group; performing an addition of said first secret from each of said devices by employing all said devices in said group; performing a multiplication of said output values from said devices in said group and performing a predetermined second function on the result obtained by said multiplication and a message; by calculating said second secret information from a result obtained by performing said second function, a result obtained by said addition, and a known element; By the joint action of all said devices in said group, said second secret information shared is deciphered, and said second secret information deciphered is used as a signature with all obtained by the multiplication Said results are output together. 9. The signature generation method according to claim 8, wherein, in said calculating step, a linear combination process of said second secret information is performed. 10. The signature generating method according to claim 8, wherein, in said calculating step, combining processing is performed using a product of exponential multiplication including said second secret information. 11. The signature generating method according to claim 8, wherein, in said calculation step, linear combination processing and multiplication of said second secret information are performed. 12. The signature generating method of claim 8, wherein said second function is a one-way function. 13. The signature generating method according to claim 8, wherein said first secret information is an element in a finite set, and addition to said finite set is performed in said adding step. 14. An authentication method of a communication system in which a plurality of devices are connected together and wherein those devices belonging to the same specific group are capable of performing the confidential information processing method according to 1, and the specific group's The equipment jointly provides identification, and said identification method includes the following steps: transmitting an authentication request message including the claimant and authenticator identifiers from a device of the claimant that transmitted a request for authentication from a device of the authenticator to each of the specified groups said device; generating an authentication element - this element is coded using a secret key and the secret key relates to said authenticator, the authentication element is performed by all devices belonging to said particular group acting together and using said secret information processing method and according to said authentication request message, and an authentication message is generated by encoding said authentication element with a secret key associated with said claimant; transmitting said authentication information from each of said devices of said particular group to said devices of said claimant; Upon receipt of said authentication information, said authentication information is decoded at said device of said claimant, and said decoded authentication element is transmitted to said authenticator's said authentication information equipment; and Said authentication element is decoded at said device of said authenticator and the authentication information is transmitted to said assertor. 15. An authentication method as claimed in claim 14, further comprising the step of cooperatively transmitting, from said particular group of said devices to said devices of said claimant and said authenticator, a public key is used Encoding the communication between the two devices. 16. An authentication method as claimed in claim 14, wherein a public key is used for secure communication between said device of said claim and said device of an authenticator, and the public key included in said authentication information The key is transmitted to said device of said claimant. 17. An authentication method as claimed in claim 14, wherein, in said step of transmitting said authentication element, encoding and other means for communicating between said devices of said claimant and said authenticator The public key itself included in said authentication information is transmitted to said device of the authenticator. 18. An authentication method as claimed in claim 14, further comprising using a provably secret sharing process, and using said specific group of said devices and between devices of said claimant and said authenticator The public key used to encode the communication is cooperatively generated as a shared pseudo-random secret process step. 19. An authentication method as claimed in claim 14, wherein, in said generating step, by dividing the data to be encoded into a large number of arrays and adding different secret keys to said data groups in a predetermined finite set Encoding of the secret key is performed. 20. An authentication method as claimed in claim 14, wherein, in said generating step, by distributing the data to be encoded to a large number of arrays, by using different secret keys with said The data is multiplied, and encryption of the secret key is performed by further adding a different secret key to the result of the multiplication. 21. An authentication method as claimed in claim 14, further comprising the step of sharing and distributing a secret key associated with each device of the communication system to said specific group of said devices performing a secret sharing process. 22. An authentication method as claimed in claim 14, wherein in said generating step, said authentication element and time stamp together using the public key of said equipment of said claimant and said authenticator code, the result of which is transmitted, and in the authentication step, the device of the authenticator decodes and verifies the information received from the device of the claimant by using the public key. time stamp. 23. A communication system in which information is confidentially shared among a plurality of information processing devices, said communication system comprising a secure communication channel and a broadcast communication channel through which each of said devices is confidentially exchanging information with another device while keeping the information confidential to the other devices, and each of said devices commonly transmits information to all other devices through these broadcast communication channels; a first of said plurality of information processing devices An information processing device includes: The first generating means is used to generate a predetermined secret array for the plurality of second devices among the plurality of information processing devices from the secret information; extracting means for extracting a first information segment from said secure array for said second device, and for transmitting said first information segment to said second device via said secure communication channel; function processing means for performing a predetermined function operation on said first piece of information and broadcasting an output value thus obtained through a broadcast communication channel; and second generating means for generating a second information segment-the second information segment being consistent with the random number broadcast by said second device, and for broadcasting said second information segment via said broadcast communication channel; and Each of said remaining information processing devices includes: random number generating means for generating random numbers and broadcasting said random numbers over a broadcast communication channel; third generating means for generating a third information segment from said first information segment and said random number, said third information segment corresponding to said second information segment; and authenticating means for comparing the third piece of information with said second piece of information being broadcast, and for verifying the secret sharing performed by said first information processing device. 24. A communication system as claimed in claim 23, wherein said information processing apparatus comprises information broadcasting means for broadcasting information through said broadcast communication channel when said comparison result does not match, wherein said The verification device performs verification based on all broadcasted information. 25. A communication system as claimed in claim 23, wherein said information processing equipment has decoding means for using all said information processing equipment to said confidential The information is decoded. 26. A communication system as claimed in claim 23, wherein said information processing apparatus has calculation means for performing calculations based on said first piece of information transmitted and wherein said decoding means performs calculations based on said calculations As a result, the said confidential information was translated. 27. A communication system as claimed in claim 23, wherein said partial array is a partial matrix defined by said secret information and randomly selected secret elements, and the row vectors and column vectors of said partial matrix are corresponding The secret portion of the secrecy, the elements of said row vector and said column vector are the secrecy portion of said row vector and said column vector. 28. A communication system as claimed in claim 23, wherein said predetermined function is a one-way function. 29. A communication system as claimed in claim 23, wherein said secret information is an element of a finite set, and wherein said generating means operates on said finite set. 30. The communication system according to claim 24, wherein each of said devices among said plurality of devices belonging to a group of signatories provided with means of said first and second devices further comprises: first sharing means for randomly selecting a first secret using said means of said first and second devices and for confidentially sharing said first secret among said devices of said group information; broadcasting means for performing a predetermined first functional operation on said first confidential information and for broadcasting the obtained information to all other devices in all said groups; adding means for performing the addition of the first secret information held in each of said devices; processing means for performing multiplication of said output value held by each of said devices, and for performing a predetermined second function operation on a result obtained by the multiplication and a message; second sharing means for said devices in said group by computing said second secret information from said multiplication result, a result obtained by said addition, and a known element share the second information between; and Decoding means, for decoding the second secret information through the cooperation of all the devices in the group that share the second secret information, and for using the decoded second secret information as a signature It is output together with the result obtained by this multiplication.

Images