Method for sharing secret information and performing certification in a communication system that has a plurality of information processing apparatuses

A signature generation method for a communication system, wherein a plurality of apparatuses are connected by secret communication channels across which said apparatuses exchange information with other apparatuses while keeping said information secret from any remaining apparatuses, and by broadcast communication channels, across which each of said apparatuses commonly exchanges information with all other apparatuses, said signature generation method comprising the steps of:

• randomly selecting first secret information by employing each of said apparatuses that belongs to a group of signers, and secretly sharing said first secret information with said apparatuses in said group;
• performing a predetermined first function on said first secret information byemploying said apparatuses, and broadcasting obtained output values to all of said apparatuses in said group;
• sharing said first secret information from each of said apparatuses among said apparatuses in said group, and adding said first secret information;
• sharing said output values among said apparatuses in said group for multiplication, and performing a predetermined second function on a result that is obtained by multiplication and a message;
• sharing second secret information among said apparatuses in said group and computing said second secret information by employing a result that is obtained by performing said second function, a result that is obtained by sharing and addition, and an element that becomes public;
• and
• decrypting, through a cooperative effort involving all said apparatuses in said group, said second secret information that is shared, and outputting said decrypted second secret information as a signature together with said result that is obtained by sharing and multiplication.

An authentication method for a communication system, wherein a plurality of apparatuses are connected and wherein apparatuses among those that belong to a specific group commonly provide authentication, said authentication method comprising the steps of:

• transmitting an authentication request message, which includes identifiers for a testifier and for an authenticator, from an apparatus of said testifier, who transmits a request for authentication from an apparatus of said authenticator, to each of said apparatuses of said specific group;
• generating an authentication element, which is encrypted with a secret key that is related to said authenticator, that is based on said authentication request message by employing a cooperative effort involving all of said apparatuses that belong to said specific group, and generating an authentication message by encrypting said authentication element with a secret key that is related to said testifier;
• transmitting said authentication message from each of said apparatuses of said specific group to said apparatus of said testifier;
• decrypting said authentication message at said apparatus of said testifier upon receipt of said authentication message, and transmitting said decrypted authentication element to said apparatus of said authenticator;
• and
• decrypting said authentication element at said apparatus of said authenticator and transmitting authentication to said testifier.

A communication system that has a plurality of information processing apparatuses, secret communication channels, across which each of said apparatuses can exchange information secretly with the other apparatus while keeping said information secret from any remaining apparatuses, and broadcast communication channels, across which each of said apparatuses commonly transmits information to all other apparatuses, with a first information processing apparatus of said plurality of information processing apparatuses comprising:

• first generation means, for generating a predetermined partial array from secret information, extraction means, for extracting, from said partial arrangement, first information segments for any remaining information processing apparatuses, and for transmitting said first information segments to said remaining information processing apparatuses,
• function processing means, for performing a predetermined function on said first information segments and broadcasting output values so obtained across said broadcast communication channels to said remaining information processing apparatuses, and second generation means, for generating a second information segment, which is in consonance with random numbers that are broadcast by said remaining information processing apparatuses, and for broadcasting said second information segment across said broadcasting communication channels;
• and with each of said remaining information processing apparatuses comprising:
• random number generation means, for generating a random number and for broadcasting said random number across said broadcast communication channels,
• third generation means, for generating, in consonance with said first information segment and said random number, a third information segment that is to be generated as said second information segment by said first information processing apparatus, and
• verification means, for comparing said third information segment with said second information segment that is broadcast and for verifying the sharing of a secret that is performed by said first information processing apparatus.

A communication system that has a plurality of information processing apparatuses, secret communication channels, across which each of said apparatuses can exchange information secretly with other apparatuses while keeping said information secret from any remaining apparatuses, and broadcast communication channels, across which each of said apparatuses commonly transmits information to all the other apparatuses, with each of said apparatuses, among said plurality of apparatuses, that.belongs to a group of signers comprising:

• sharing means, for selecting first secret information at random and for secretly sharing said first secret information among said apparatuses of said group;
• broadcast means, for performing a predetermined first function on said first secret information and for broadcasting an obtained value to all remaining apparatuses of said group;
• addition means, for sharing said first secret information held by each of said apparatus among said apparatuses of said group and for adding said first secret information;
• processing means, for sharing said output value held by each of said apparatuses among said apparatuses of said group and multiplying said output value, and for performing a predetermined second function on a result, which is obtained by multiplication, and a message;
• computation means, for employing said multiplication result, a result that is obtained by sharing and addition, and an element that is made public to share second information among said apparatuses of said group and to compute said second information;
• and
• decryption means, for decrypting said second secret information by a joint effort of all of said apparatuses of said group among which said second secret information is shared, and for outputting decrypted second secret information as a signature together with said result obtained by sharing and multiplication.