Abstract:
A data processing device for share-encoding secret information using a (k,n) threshold scheme, where k and n are integers greater than or equal to 2, and k is less than or equal to n. The data processing device includes a holding unit operable to acquire and hold secret information, a reception unit operable to receive from each of n number of users at a time of a user registration, a user ID unique to the user and a password determined by the user, a user information generation unit operable to generate for each user from the user ID and the password received from the user, user information uniquely determined for the user, a registration unit operable to generate registration information for each user, and to register the user by storing the generated registration information in relation to a corresponding user ID, the registration information corresponding to a difference between (i) shared information generated for each user by share-encoding the held secret information using the (k,n) threshold scheme and (ii) user information generated for the user, and a deletion unit operable to delete the held secret information after the n number of users has been registered by the registration unit.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    1. Field of the Invention  
           [0002]    The present invention relates to authentication technology that uses a (k,n) threshold scheme, which is a type of secret sharing scheme.  
           [0003]    2. Related Art  
           [0004]    In recent years, there has been a demand for authentication technology that both realizes high security and is easy to handle.  
           [0005]    Authentication technology that uses a secret sharing scheme relieves concern about secret information being lost or destroyed. Known secret sharing schemes include, for example, a (k,n) threshold scheme.  
           [0006]    A (k,n) threshold scheme is a method for sharing secret information generated by share-encoding n number of pieces of shared information from secret information, so as to only allow the original secret information to be decoded when k or more pieces of shared information have been collected, k being less than n.  
           [0007]    By having n number of people separately manage the n pieces of shared information generated by a (k,n) threshold scheme, secret information can still be decoded, even if (n−k) people lose/destroy shared information, and secret information cannot be decoded, even if shared information managed by up to (k−1) people is leaked. The (k,n) threshold scheme thus realizes high security and is easy to handle.  
           [0008]    A detailed description of secret sharing schemes, the (k,n) threshold scheme, and other related matters can be found in  Introduction to Encryption Theory  (Eiji OKAMOTO, Kyoritsu Shuppan Co., Ltd., 1993, pp.121-128), and in Japanese publication of unexamined patent application no.2001-94556 (“Authentication Method using Secret Sharing Scheme”) and no.2001-111659 (“File Encryption System and Storage Medium storing File Encryption Program and Data”).  
           [0009]    Japanese publication of unexamined patent application no.2001-94556 discloses a way of repeatedly using shared information in an authentication method that employs a secret sharing scheme, by verifying whether a set having a predetermined number of pieces of shared information is capable of recovering secret information, and authenticating the set when the verification result is affirmative.  
           [0010]    Japanese publication of unexamined patent application no.2001-111659 discloses a way of maintaining the security of individual keys in a file encryption system, and protecting the security of encrypted files (i.e. so long as corrupt insiders do not conspire to collect a number of individual keys greater than or equal to a predetermined number), by retrieving individual keys by user inputs of recognition information, and retrieving group keys using a combination key obtained by collecting the predetermined number of the individual keys of users.  
           [0011]    The “share-encryption” in the (k,n) threshold scheme faithfully executes a predetermined complex operation, and as a result the shared information is formed as an enumeration of information that has no readily discernable meaning.  
           [0012]    Because of this, it is difficult for a manager to commit shared information to memory as a passphrase, and so shared information is normally stored on a storage medium of some description.  
           [0013]    For example, when a secret key, for use when an application program is run in a certain device, is shared according to a (k,n) threshold scheme, and shared information is distributed among a plurality of managers, there is a danger, if the managers store the shared information on storage media connected to the device, of pieces of shared information being leaked as a result of an attack on the device from a third party, and of secret information being recovered if the number of leaked pieces of shared information is greater than or equal to a predetermined number. Of course, this is not desirable in terms of security.  
         SUMMARY OF THE INVENTION  
         [0014]    In view of the above issues, an object of the present invention is to provide a data processing device, method and program which eliminate the danger of secret information shared according to a threshold scheme being recovered due to the leaking of information stored on a storage medium connected a device attacked by a third party.  
           [0015]    A data processing device provided to achieve the above object is for share-encoding secret information using a (k,n) threshold scheme, where k and n are integers greater than or equal to 2, and k is less than or equal to n. The data processing device includes a holding unit operable to acquire and hold secret information; a reception unit operable to receive from each of n number of users at a time of a user registration, a user ID unique to the user and a password determined by the user; a user information generation unit operable to generate for each user from the user ID and the password received from the user, user information uniquely determined for the user; a registration unit operable to generate registration information for each user, and to register the user by storing the generated registration information in relation to a corresponding user ID, the registration information corresponding to a difference between (i) shared information generated for each user by share-encoding the held secret information using the (k,n) threshold scheme and (ii) user information generated for the user; and a deletion unit operable to delete the held secret information after the n number of users has been registered by the registration unit.  
           [0016]    A data processing method provided to achieve the above object is for share-encoding secret information using a (k,n) threshold scheme, where k and n are integers greater than or equal to 2, and k is less than or equal to n. The data processing method includes a holding step of acquiring and holding secret information; a reception step of receiving from each of n number of users at a time of a user registration, a user ID unique to the user and a password determined by the user; a user information generation step of generating for each user from the user ID and the password received from the user, user information uniquely determined for the user; a registration step of generating registration information for each user, and registering the user by storing the generated registration information in relation to a corresponding user ID, the registration information corresponding to a difference between (i) shared information generated for each user by share-encoding the held secret information using the (k,n) threshold scheme and (ii) user information generated for the user; and a deletion step of deleting the held secret information after the n number of users has been registered in the registration step.  
           [0017]    A data processing computer program provided to achieve the above object is for having a computer execute a plurality of steps for share-encoding secret information using a (k,n) threshold scheme, where k and n are integers greater than or equal to 2, and k is less than or equal to n. The steps include a holding step of acquiring and holding secret information; a reception step of receiving from each of n number of users at a time of a user registration, a user ID unique to the user and a password determined by the user; a user information generation step of generating for each user from the user ID and the password received from the user, user information uniquely determined for the user; a registration step of generating registration information for each user, and registering the user by storing the generated registration information in relation to a corresponding user ID, the registration information corresponding to a difference between (i) shared information generated for each user by share-encoding the held secret information using the (k,n) threshold scheme and (ii) user information generated for the user; and a deletion step of deleting the held secret information after the n number of users has been registered in the registration step.  
           [0018]    According to these structures, users can easily commit a password to memory as a passphrase, since each user sets their own easily rememberable password.  
           [0019]    Consequently, high security can be achieved if users each remember their easy-to-remember password, since secret information shared by a threshold scheme cannot be recovered, even if information stored on a storage medium is leaked.  
           [0020]    Here, the data processing device may further include a check information generation unit operable to generate check information for each user, by performing a predetermined one-way function on the password received from the user, and the registration unit may further stores the generated check information in relation to the corresponding user ID at a time of the user registration.  
           [0021]    According to this structure, check information is generated and stored at a time of user registration, thus allowing the validity of a password to be checked when data is to be accessed.  
           [0022]    Furthermore, the check information is generated by performing a one-way function on a password, thus eliminating the risk of the original password being recovered, even if information stored on a storage medium is leaked.  
           [0023]    Here, the user information generation unit may generate the user information by inserting, between the user ID and the password received from each user, a fixed value that includes a value that cannot be received by the reception unit, and combining the user ID and the password.  
           [0024]    According to this structure, the boundary between a user ID and a password is specified by inserting, between the user ID and the password, a value that cannot received by the reception unit. As a result, the user information can, when user IDs are unique, be uniquely determined from a user ID and a password, without the risk of mere combinations of passwords and user IDs happening to be the same value.  
           [0025]    Here, the user information generation unit may insert, as the value that cannot be received, a fixed value that includes one of a backspace (0×08) and a carriage return (0×0d).  
           [0026]    According to this structure, the fixed value includes one of a backspace (0×08) and a carriage return (0×0d), thus allowing the boundary between a user ID and a password to be easily judged.  
           [0027]    Here, the user information generation unit may generate the user information by (i) converting one of the user ID and the password received from each user to a value that cannot be received by the receiving unit, by performing a predetermined conversion, and (ii) combining the converted user ID or password with the user ID or password that was not converted.  
           [0028]    According to this structure, the boundary between a user ID and a password is specified by converting one of a user ID and a password to a value that cannot be received by the reception unit. As a result, the user information can, when user IDs are unique, be uniquely determined from a user ID and a password, without the risk of mere combinations of passwords and user IDs happening to be the same value.  
           [0029]    Here, the user information generation unit may convert one of the user ID and the password to a value that includes one of a backspace (0×08) and a carriage return (0×0d).  
           [0030]    According to this structure, one of a user ID and a password is converted to a value that includes one of a backspace (0×08) and a carriage return (0×0d), thus allowing the boundary between a user ID and a password to be easily judged.  
           [0031]    A data processing device alternatively provided to achieve the above object is for recovering secret information, based on information share-encoded using a (k,n) threshold scheme, where k and n are integers greater than or equal to 2, and k is less than or equal to n. The data processing device includes a reception unit operable to receive from each of n number of users at a time of a secret information recovery, a user ID unique to the user and a password determined by the user; a user information generation unit operable to generate for each user from the user ID and the password received from the user, user information uniquely determined for the user; a storage unit having registration information stored therein for each of the n number of users in relation to a corresponding user ID, the registration information corresponding to a difference between (i) shared information generated for each user by share-encoding the secret information using the (k,n) threshold scheme and (ii) user information generated for the user; an extraction unit operable to extract, from the storage unit, registration information corresponded to the user ID received from each user; and a recovery unit operable, after registration information for k number of users has been extracted by the extraction unit, to recover the secret information using (i) the registration information for the k number of users and (ii) user information generated for the k number of users.  
           [0032]    A data processing method alternatively provided to achieve the above object is used in a data processing device for recovering secret information, based on information share-encoded using a (k,n) threshold scheme, where k and n are integers greater than or equal to 2, and k is less than or equal to n. The data processing device has a storage unit that has registration information stored therein for each of n number of users in relation to a corresponding user ID, the registration information corresponding to a difference between (i) shared information generated for each user by share-encoding the secret information using the (k,n) threshold scheme and (ii) user information generated for the user. The data processing method includes a reception step of receiving from each of the n number of users at a time of a secret information recovery, a user ID unique to the user and a password determined by the user; a user information generation step of generating for each user from the user ID and the password received from the user, user information uniquely determined for the user; an extraction step of extracting, from the storage unit, registration information corresponded to the user ID received from each user; and a recovery step of, after registration information for k number of users has been extracted in the extraction step, recovering the secret information using (i) the registration information for the k number of users and (ii) user information generated for the k number of users.  
           [0033]    A data processing computer program alternatively provided to achieve the above object is for having a data processing device execute a plurality of steps for recovering secret information, based on information share-encoded using a (k,n) threshold scheme, where k and n are integers greater than or equal to 2, and k is less than or equal to n. The data processing device has a storage unit that has registration information stored therein for each of n number of users in relation to a corresponding user ID, the registration information corresponding to a difference between (i) shared information generated for each user by share-encoding the secret information using the (k,n) threshold scheme and (ii) user information generated for the user. The steps include a reception step of receiving from each of the n number of users at a time of a secret information recovery, a user ID unique to the user and a password determined by the user; a user information generation step of generating for each user from the user ID and the password received from the user, user information uniquely determined for the user; an extraction step of extracting, from the storage unit, registration information corresponded to the user ID received from each user; and a recovery step of, after registration information for k number of users has been extracted in the extraction step, recovering the secret information using (i) the registration information for the k number of users and (ii) user information generated for the k number of users.  
           [0034]    According to these structures, it is possible to easily recover secret information, as a result of users each setting and memorizing their own easily rememberable password, and a predetermined number (i.e. k) of users inputting their user ID and password.  
           [0035]    Here, the data processing device may further include a data processing unit operable to conduct data processing using the recovered secret information, and a deletion unit operable to delete the secret information after the data processing has been conducted by the data processing unit.  
           [0036]    According to this structure, high security can be achieved because secret information is removed after data processing has been conducted.  
           [0037]    Here, the storage unit may further have stored therein in relation to a corresponding user ID, check information that has been generated by performing a predetermined one-way function on a password, the extraction unit may further extract, from the storage unit, check information corresponded to the user ID received from each user, the data processing device may further include a check information generation unit operable to generate check information by performing the predetermined one-way function on the password received from each user; and an authentication unit operable to authenticate the password as being valid, if the extracted check information matches the generated check information, and the recovery unit, at a time of the secret information recovery, may not use user information corresponding to a password that is not authenticated as being valid.  
           [0038]    According to this structure, it is possible to check the validity of a password, based on stored check information, when secret information is to be recovered.  
           [0039]    Furthermore, the check information is generated by performing a one-way function on a password, thus eliminating the risk of the original password being recovered, even if information stored on a storage medium is leaked.  
           [0040]    Here, the user information generation unit may generate the user information by inserting, between the user ID and the password received from each user, a fixed value that includes a value that cannot be received by the reception unit, and combining the user ID and the password.  
           [0041]    According to this structure, the boundary between a user ID and a password is specified by inserting, between the user ID and the password, a value that cannot received by the reception unit. As a result, the user information can, when the user IDs are unique, be uniquely determined from a user ID and a password, without the risk of mere combinations of passwords and user IDs happening to be the same value.  
           [0042]    Here, the user information generation unit may insert, as the value that cannot be received, a fixed value that includes one of a backspace (0×08) and a carriage return (0×0d).  
           [0043]    According to this structure, the fixed value includes one or a backspace (0×08) and a carriage return (0×0d), thus allowing the boundary between a user ID and a password to be easily judged.  
           [0044]    Here, the user information generation unit may generate the user information by (i) converting one of the user ID and the password received from each user to a value that cannot be received by the receiving unit, by performing a predetermined conversion, and (ii) combining the converted user ID or password with the user ID or password that was not converted.  
           [0045]    According to this structure, the boundary between a user ID and a password is specified by converting one of a user ID and a password to a value that cannot be received by the reception unit. As a result, the user information can, when the user IDs are unique, be uniquely determined from a user ID and a password, without the risk of mere combinations of passwords and user IDs happening to be same value.  
           [0046]    Here, the user information generation unit may convert one of the user ID and the password to a value that includes one of a backspace (0×08) and a carriage return (0×0d).  
           [0047]    According to this structure, one of a user ID and a password is converted to a value that includes one of a backspace (0×08) and a carriage return (0×0d), thus allowing the boundary between a user ID and a password to be easily judged. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0048]    These and other objects, advantages and features of the invention will become apparent from the following description thereof taken in conjunction with the accompanying drawings that illustrate specific embodiments of the present invention.  
         [0049]    In the drawings:  
         [0050]    [0050]FIG. 1 shows a structure of a data processing system according to an embodiment 1 of the present invention;  
         [0051]    FIGS.  2 A- 2 E show exemplary user secret information generated by a user secret information generation unit  103 ;  
         [0052]    [0052]FIG. 3 shows exemplary password files for each user stored in a storage unit  107 ;  
         [0053]    [0053]FIG. 4 shows a sequence of operations performed by the data processing system of embodiment 1 at a time of user registration;  
         [0054]    [0054]FIG. 5 shows a sequence of operations performed by the data processing system of embodiment 1 at a time of data access;  
         [0055]    [0055]FIG. 6 shows a structure of a user registration device according to a variation of the present invention;  
         [0056]    [0056]FIG. 7 shows a structure of a data access device according to a variation of the present invention;  
         [0057]    [0057]FIG. 8 shows a structure of a data processing system according to an embodiment 2 of the present invention;  
         [0058]    [0058]FIG. 9 shows a sequence of operations performed by the data processing system of embodiment 2 at a time of user registration;  
         [0059]    [0059]FIG. 10 shows a sequence of operations performed by the data processing system of embodiment 2 at a time of data transmission; and  
         [0060]    [0060]FIG. 11 shows a sequence of operations performed by the data processing system of embodiment 2 at a time of data reception. 
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0061]    Embodiment 1  
         [0062]    Structure  
         [0063]    [0063]FIG. 1 shows a structure of a data processing system according to an embodiment 1 of the present invention.  
         [0064]    As shown in FIG. 1, the data processing system of embodiment 1 is structured from a data processing device  100  and a database unit  200 .  
         [0065]    Data processing device  100  is structured from a secret key generation unit  101 , an input reception unit  102 , a user secret information generation unit  103 , a check information generation unit  104 , a user registration information generation unit  105 , a registration unit  106 , a storage unit  107 , an authentication unit  108 , a user registration information extraction unit  109 , a secret key recovery unit  110 , a data processing unit  111 , a first deletion unit  112 , and a second deletion unit  113 .  
         [0066]    Secret key generation unit  101  generates, prior to user registration being initiated, a secret key required for accessing database unit  200 , and holds the generated secret key. Here, secret key generation unit  101  generates a random number as a secret key. Also, while the description relates to a secret key being generated in data processing device  100 , a secret key to be used in data processing device  100  may be provided in advance from another device.  
         [0067]    Input reception unit  102 , at a time of user registration and data access, receives a user ID (i.e. “user identifier”) and a password from each of a plurality of users.  
         [0068]    User secret information generation unit  103 , at a time of user registration and data access, generates unique user secret information by performing a predetermined conversion on the user ID and the password received from each user by input reception unit  102 .  
         [0069]    [0069]FIGS. 2A to  2 E show exemplary user secret information generated by user secret information generation unit  103 .  
         [0070]    In the user secret information shown in FIG. 2A, a fixed value is concatenated onto a user ID.  
         [0071]    Since user IDs are not normally handled as information requiring secrecy, there is a strong likelihood, in this case, of user IDs being easily divulged. User secret information such as shown in FIG. 2A is thus easily found out if attacked by a third party, and as a result a secret key can also be easily found out.  
         [0072]    In the user secret information shown in FIG. 2B, a fixed value is concatenated onto a password.  
         [0073]    Since passwords are freely set by users, two or more users will sometimes happen to set the same password. In this case, user secret information such as shown in FIG. 2B will result in matching equations according to a threshold scheme, and thus even when authentication of k number of people is conducted, k pieces of shared information will not be acquired, and it will be impossible to recover the original secret information.  
         [0074]    In the user secret information shown in FIG. 2C, a password and a user ID are simply combined.  
         [0075]    Since combinations of passwords and user IDs will sometimes happen to be matched, user secret information such as in FIG. 2C incurs the same undesirable effects as that shown in FIG. 2B. As a specific example, simply combining a password “ABC” and a user ID “DE” results in the same piece of user secret information “ABCDE” as when a password “AB” and a user ID “CDE” are combined, even though the user IDs are unique. Determining a length of at least one of the user IDs and the passwords in advance allows this problem to be avoided.  
         [0076]    In the user secret information shown in FIG. 2D, a 1-byte fixed value that cannot normally be inputted by an operator is inserted between a password and a user ID. Here, the fixed value is, for example, a control character such as a backspace (0×08), a carriage return (0×0d), or the like. If a system is configured so that numeric characters cannot be inputted at a time of password/user ID input, the fixed value may be an arbitrary numeric character.  
         [0077]    Here, when the user IDs are unique, the uniqueness of user IDs can be guaranteed, since there is no chance of any two pieces of user secret information such as shown in FIG. 2D happening to have the same value. As a result, equations according to a threshold scheme will not be matched, and the undesirable effects incurred by the user secret information in FIGS. 2B and 2C will not arise.  
         [0078]    In the user secret information shown in FIG. 2E, a password is combined with a user ID that has been converted on the basis of a specific conversion rule. Here, the conversion rule preferably is a conversion to a value that cannot normally be inputted by an operator. As a specific example, the conversion may be a one-to-one correspondence conversion based on a conversion table, or a hash of similar conversion that makes collisions unlikely.  
         [0079]    In FIG. 2E a password is combined with a user ID that has been converted on the basis of a specific conversion rule, although it is possible to combine a user ID with a password converted on the basis of a specific conversion rule, or to convert and combine both the user ID and the password.  
         [0080]    Furthermore, although in FIGS. 2A to  2 E a converted user ID (or user ID) is combined to a password (or converted password) it is possible to combine a converted password (or password) to a user ID (or converted user ID).  
         [0081]    Check information generation unit  104 , at a time of user registration and data access, conducts a hash operation on user secret information generated by user secret information generation unit  103 , and generates check information required for checking a validity of user IDs and passwords. Since the hash operation is prior art, a detailed description is omitted here. Also, although check information is described here as being generated from user secret information, it may be generated from user IDs. Moreover, although the check information is not limited to hash values, it is required to be generated based on at least user IDs.  
         [0082]    User registration information generation unit  105 , at a time of user registration, generates, based on user secret information generated by user secret information generation unit  103 , user registration information for each user by sharing, in accordance with a (k,n) threshold scheme, a secret key generated by secret key generation unit  101 , so as to allow the secret key to be recovered from k pieces of user secret information. Combining the user registration information generated here for each user with the user secret information for the user results in information that is similar to conventional shared information for each user generated by share-encoding a secret key using a (k,n) threshold scheme. The user registration information thus corresponds to a difference between the shared information and user secret information. Here, k and n are integers greater than or equal to 2, and k is less than or equal to n.  
         [0083]    Registration unit  106  registers each user by storing, in storage unit  107 , a password file for each user, formed from sets of a user ID, a piece of user registration information generated for each user by user registration information generation unit  105 , and a piece of check information generated by check information generation unit  104 , such that the check information and the user registration information are related to a corresponding user ID.  
         [0084]    Storage unit  107 , at a time of user registration, has a password file stored therein by registration unit  106 .  
         [0085]    [0085]FIG. 3 shows exemplary password files for each user stored in storage unit  107 .  
         [0086]    As shown in FIG. 3, information relating to a single user is described in a single line in a password file, the information being, from left to right, a user ID, base64-converted user ID check information (28 bytes), and a base64-converted secret value (32 bytes), and each piece of information being separated by a colon “:”. Although the password files shown in FIG. 3 are described as being subjected to a base64 conversion, other conversions are acceptable, and nor is it required to conduct a conversion. Moreover, the bit numbers are not limited to the given example.  
         [0087]    Authentication unit  108 , at a time of data access, extracts check information stored in storage unit  107 , using as a retrieval key a user ID received by reception unit  102 , and checks a validity of the user ID and the password by comparing the extracted check information with check information generated by check information generation unit  104 .  
         [0088]    User registration information extraction unit  109 , at a time of data access, extracts user registration information stored in storage unit  107 , using as a retrieval key a user ID received by reception unit  102 , if authentication unit  108  authenticates that the user is valid.  
         [0089]    Secret key recovery unit  110 , at a time of data access, recovers a secret key, using user secret information generated for each user by user secret information generation unit  103  and user registration information extracted for each user by user registration information extraction unit  109 , when judged that the number of users authenticated as valid by authentication unit  108  has reached a threshold value determined in advance.  
         [0090]    Data processing unit  111 , at a time of user registration, instructs database unit  200  to make a setting such that access is only possible using a secret key generated by secret key generation unit  101 , after it has been judged that the number of users registered by registration unit  106  has reached a predetermined total number of users. Also, data processing unit  111 , at a time of data access, accesses database unit  200  using a secret key recovered by secret key recovery unit  110 .  
         [0091]    First deletion unit  112 , at a time of user registration, deletes a secret key generated and held by secret key generation unit  101 , after an instruction has been issued to database unit  200  by data processing unit  111 .  
         [0092]    Second deletion unit  113 , at a time of data access, deletes a secret key recovered by secret key recovery unit  110 , after database unit  200  has been accessed by data processing unit  111 .  
         [0093]    Database unit  200 , at a time of user registration, receives and follows the instruction issued by data processing unit  111 , and, at a time of data access, accepts an access by data processing unit  111 .  
         [0094]    Although database unit  200  is described here as being disposed externally to data processing device  100 , a structure in which database unit  200  is internalized in data processing device  100  is acceptable.  
         [0095]    User Registration Operations  
         [0096]    [0096]FIG. 4 shows a sequence of operations performed by the data processing system of embodiment 1 at a time of user registration.  
         [0097]    The operation procedures at a time of user registration will now be described.  
         [0098]    (1) Secret key generation unit  101  generates secret keys A, B (step S 1 ).  
         [0099]    (2) Input reception unit  102  receives a user ID and a password from a user (step S 2 ).  
         [0100]    (3) User secret information generation unit  103  generates unique user secret information, by performing a predetermined conversion on the user ID and the password received in step S 2  (step S 3 ).  
         [0101]    (4) Check information generation unit  104  conducts a hash operation on the user secret information generated in step S 3 , and generates check information (step S 4 ).  
         [0102]    (5) User registration information generation unit  105  generates, based on the user secret information generated in step S 3 , user registration information for each user by sharing, in accordance with a (k,n) threshold scheme, the secret keys generated in step S 1 , so as to allow the secret keys to be recovered from k pieces of user secret information (step S 5 ).  
         [0103]    (6) Registration unit  106  registers each user by storing, in storage unit  107 , a password file for each user, formed from sets of a user ID, a piece of user registration information generated in step S 5 , and a piece of check information generated in step S 4 , so that the check information and the user registration information are related to a corresponding user ID (step S 6 ).  
         [0104]    (7) Registration unit  106  judges whether the number of users has reached n number. If n has not been reached, return to step S 2  to receive another user ID and password (step S 7 ).  
         [0105]    (8) When the number of users reaches n, data processing unit  111  instructs database unit  200  to make a setting such that access is not possible without using the secret keys generated in step S 1  (step S 8 ).  
         [0106]    (9) First deletion unit  112  deletes the secret keys generated in step S 1  (step S 9 ).  
         [0107]    Data Access Operation  
         [0108]    [0108]FIG. 5 shows a sequence of operations performed by the data processing system of embodiment 1 at a time of data access.  
         [0109]    The operation procedures at a time of data access will now be described.  
         [0110]    (1) Input reception unit  102  receives a user ID and a password from a user (step S 11 ).  
         [0111]    (2) User secret information generation unit  103  generates unique user secret information, by performing a predetermined conversion on the user ID and the password received in step S 11  (step S 12 ).  
         [0112]    (3) Check information generation unit  104  conducts a hash operation on the user secret information generated in step S 12 , and generates check information (step S 13 ).  
         [0113]    (4) Authentication unit  108  extracts check information stored in storage unit  107 , using the user ID received in step S 11  as a retrieval key (step S 14 ).  
         [0114]    (5) Authentication unit  108  checks a validity of the user ID and the password by comparing the check information extracted in step S 14  with the check information generated in step S 13 . If a value of the two pieces of check information agree, authentication unit  108  assumes the user ID and the password to be valid and proceeds to processing to extract user registration information, and if a value of the two pieces of check information does not agree, authentication unit  108  assumes the user ID and the password to be invalid and returns to step S 11  to receive another user ID and password (step S 15 ).  
         [0115]    (6) If the user ID and the password are authenticated as being valid, user registration information extraction unit  109  extracts the user registration information stored in storage unit  107 , using the user ID received in step S 11  as a retrieval key (step S 16 ).  
         [0116]    (7) Secret key recovery unit  110  judges whether the number of users has reached k number. If k has not been reached, return to steps S 11  to receive another user ID and password (step S 17 ).  
         [0117]    (8) When the number of users reaches k, secret key recovery unit  110  recovers the secret keys, using k pieces of user secret information generated in step S 12  and k pieces of user registration information extracted in step S 16  (step S 18 ).  
         [0118]    (9) Data processing unit  111  accesses database unit  200  using the secret keys recovered in step S 18  (step S 19 ).  
         [0119]    (10) Second deletion unit  113  deletes the secret keys recovered in step S 18  (step S 20 ).  
       EXAMPLE 1  
       [0120]    In example 1, k and n according to a (k,n) threshold scheme are “2” and “3”, respectively.  
         [0121]    The following describes example 1 at a time of user registration, with reference to FIG. 4.  
         [0122]    (1) In step S 1 , secret key generation unit  101  generates secret keys “A=3”, “B=−1”.  
         [0123]    (2) In step S 2 , input reception unit  102  receives from a user L a user ID “IL=1” and a password “PL=1”.  
         [0124]    (3) In step S 3 , user secret information generation unit  103  generates user secret information “UL(y,x)=(1,1)” from user ID “IL=1” and password “PL=1”.  
         [0125]    (4) In step S 4 , check information generation unit  104  conducts a hash operation on user secret information “UL(y,x)=(1,1)”, and generates check information “CL”.  
         [0126]    (5) In step S 5 , user registration information generation unit  105  derives user registration information “α=−1” of user L from “1=3×1+(−1)+α”, by assigning user secret information “UL(y,x)=(1,1)” and secret keys “A=3”, “B=−1” to 
           y=Ax+B+α   (equation 1) 
         [0127]    Here, equation 1 is provided in advance.  
         [0128]    (6) Instep S 6 , registration unit  106  stores, in storage unit  107 , a password file “(IL, α, CL)=(1, −1, CL)” so that user registration information “α=−1” and check information “CL” are related to user ID “IL=1”.  
         [0129]    (7) In step S 7 , the number of users has not reached “n=3”, so return to step S 2 .  
         [0130]    (8) In step S 2 , input reception unit  102  receives from a user M a user ID “IM=2” and a password “PM=2”.  
         [0131]    (9) In step S 3 , user secret information generation unit  103  generates user secret information “UM(y′,x′)=(2,2)” from user ID “IM=2” and password “PM=2”.  
         [0132]    (10) In step S 4 , check information generation unit  104  conducts a hash operation on user secret information “UM(y′,x′)=(2,2)”, and generates check information “CM”.  
         [0133]    (11) In step S 5 , user registration information generation unit  105  derives user registration information “β=−3” of user M from “1=3×2+(−1)+β”, by assigning user secret information “UM(y′,x′)=(2,2)” and secret keys “A=3”, “B=−1” to 
           y′=Ax′+B+β   (equation 2) 
         [0134]    Here, equation 2 is provided in advance.  
         [0135]    (12) In step S 6 , registration unit  106  stores, in storage unit  107 , a password file “(IM, β, CM)=(2, −3, CM)” so that user registration information “β=−3” and check information “CM” are related to user ID “IM=2”.  
         [0136]    (13) In step S 7 , the number of users has not reached “n=3”, so return to step S 2 .  
         [0137]    (14) In step S 2 , input reception unit  102  receives from a user N a user ID “IN=3” and a password “PN=3”.  
         [0138]    (15) In step S 3 , user secret information generation unit  103  generates user secret information “UN(y″,x″)=(3,3)” from user ID “IN=3” and password “PN=3”.  
         [0139]    (16) In step S 4 , check information generation unit  104  conducts a hash operation on user secret information “UN(y″,x″)=(3,3)”, and generates check information “CN”.  
         [0140]    (17) In step S 5 , user registration information generation unit  105  derives user registration information “γ=−5” from “1=3×3+(−1)+γ”, by assigning user secret information “UN(y″,x″)=(3,3)” and secret keys “A=3”, “B=−1” to 
           y″=Ax″+B+γ   (equation 3) 
         [0141]    Here, equation 3 is provided in advance.  
         [0142]    (18) In step S 6 , registration unit  106  stores, in storage unit  107 , a password file “(IN, γ, CN)=(3, −5, CN)” so that user registration information “γ=−3” and check information “CN” are related to user ID “IN=3”.  
         [0143]    (19) In step S 7 , the number of users has reached “n=3”, so proceed to step S 8 .  
         [0144]    (20) In step S 8 , data processing unit  111  instructs database unit  200  to make a setting such that access is not possible without using secret keys “A=3”, “B=−1”.  
         [0145]    (21) In step S 9 , first deletion unit  112  deletes the secret keys.  
         [0146]    The following describes example 1 at a time of data access, with reference to FIG. 5.  
         [0147]    (1) In step S 11 , input reception unit  102  receives from a user L a user ID “IL=1” and a password “PL=1”.  
         [0148]    (2) In step S 12 , user secret information generation unit  103  generates user secret information “UL(y,x)=(1,1)” from user ID “IL=1” and password “PL=1”.  
         [0149]    (3) In step S 13 , check information generation unit  104  conducts a hash operation on user secret information “UL(y,x)=(1,1)”, and generates check information “CL”.  
         [0150]    (4) In step S 14 , authentication unit  108  extracts check information “CL” using user ID “IL=1” as a retrieval key.  
         [0151]    (5) In step S 15 , authentication unit  108  checks a validity of user ID “IL=1” and password “PL=1” by comparing check information “CL” extracted in (4) with check information “CL” generated in (3), and authenticates the user ID and the password as being valid.  
         [0152]    (6) In step S 16 , user registration information extraction unit  109  extracts user registration information “α=−1” stored in storage unit  107 , using user ID “IL=1” received in (1) as a retrieval key.  
         [0153]    (7) In step S 17 , the number of users has not reached “k=2”, so return to step S 11 .  
         [0154]    (8) In step S 11 , input reception unit  102  receives from a user N a user ID “IN=3” and a password “PN=3”.  
         [0155]    (9) In step S 12 , user secret information generation unit  103  generates user secret information “UN(y″,x″)=(3,3)” from user ID “IN=3” and password “PN=3”.  
         [0156]    (10) In step S 13 , check information generation unit  104  conducts a hash operation on user secret information “UN(y″,x″)=(3,3)”, and generates check information “CN”.  
         [0157]    (11) In step S 14 , authentication unit  108  extracts check information “CN” using user ID “IN=3” as a retrieval key.  
         [0158]    (12) In step S 15 , authentication unit  108  checks a validity of user ID “IN=3” and password “PN=3” by comparing check information “CN” extracted in (11) with check information “CN” generated in (10), and authenticates the user ID and the password as being valid.  
         [0159]    (13) In step S 16 , user registration information extraction unit  109  extracts user registration information “γ=−5” stored in storage unit  107 , using user ID “IN=3” received in (8) as a retrieval key.  
         [0160]    (14) In step S 17 , the number of users has reached “k=2”, so proceed to step S 18 .  
         [0161]    (15) In step S 18 , user secret key recovery unit  110  obtains 
         1 =A ×1 +B +(−1)  (equation 4) 
         [0162]    by assigning user secret information “UL(y,x)=(1,1)” generated in (2) and user registration information “α=−1” extracted in (6) to equation 1, obtains 
         3 =A ×3 +B +(−5)  (equation 5) 
         [0163]    by assigning user secret information “UN(y″,x″)=(3,3)” generated in (9) and user registration information “γ=−5” extracted in (13) to equation 2, and recovers secret keys “A=3”, “B=−1” by solving the simultaneous equations 4 and 5.  
         [0164]    (16) In step S 19 , data processing unit  111  accesses database unit  200  using secret keys “A=3”, “B=−1”.  
         [0165]    (17) In step S 20 , second deletion unit  113  deletes the secret keys.  
       EXAMPLE 2  
       [0166]    In example 2, k and n according to a (k,n) threshold scheme are “2” and “3”, respectively.  
         [0167]    The following describes example 2 at a time of user registration, with reference to FIG. 4.  
         [0168]    (1)˜(4) are equivalent to (1)˜(4) at a time of user registration in example 1.  
         [0169]    (5) In step S 5 , user registration information generation unit  105  derives user registration information “z=2” of user L from “z=1−α=3×1+(−1)”, by assigning user secret information “UL(y,x)=(1,1)” and secret keys “A=3”, “B=−1” to 
           z=y−α=Ax+B   (equation 6) 
         [0170]    Here, equation 6 is provided in advance.  
         [0171]    (6) In step S 6 , registration unit  106  stores, in storage unit  107 , a password file “(IL, z, CL)=(1, 2, CL)” so that user registration information “z=2” and check information “CL” are related to user ID “IL=1”.  
         [0172]    (7)˜(10) are equivalent to (7)˜(10) at a time of user registration in example 1.  
         [0173]    (11) In step S 5 , user registration information generation unit  105  derives user registration information “z′=5” of user M from “z′=1−β=3×2+(−1)”, by assigning user secret information “UM(y′,x′)=(2,2)” and secret keys “A=3”, “B=−1” to 
           z′=y′−β=Ax′+B   (equation 7) 
         [0174]    Here, equation 7 is provided in advance.  
         [0175]    (12) In step S 6 , registration unit  106  stores, in storage unit  107 , a password file “(IM, z′, CM)=(2, 5, CM)” so that user registration information “z′=5” and check information “CM” are related to user ID “IM=2”.  
         [0176]    (13)˜(16) are equivalent to (13)˜(16) at a time of user registration in example 1.  
         [0177]    (17) In step S 5 , user registration information generation unit  105  derives user registration information “z″=8” for user N from “z″=1−γ=3×3+(−1)”, by assigning user secret information “UN(y″,x″)=(3,3)” and secret keys “A=3”, “B=−1” to 
           z″=y″−γ=Ax″+B   (equation 8) 
         [0178]    Here, equation 8 is provided in advance.  
         [0179]    (18) In step S 6 , registration unit  106  stores, in storage unit  107 , a password file “(IN, z″, CN)=(3, 8, CN)” so that user registration information “z″=8” and check information “CN” are related to user ID “IN=3”.  
         [0180]    (19)˜(21) are equivalent to (19)˜(21) at a time of user registration in example 1.  
         [0181]    The following describes example 2 at a time of data access, with reference to FIG. 5.  
         [0182]    (1)˜(5) are equivalent to (1)˜(5) at a time of data access in example 1.  
         [0183]    (6) In step S 16 , user registration information extraction unit  109  extracts user registration information “z=2” stored in storage unit  107 , using user ID “IL=1” received in (1) as a retrieval key.  
         [0184]    (7)˜(12) are equivalent to (7)˜(12) at a time of data access in example 1.  
         [0185]    (13) In step S 16 , user registration information extraction unit  109  extracts user registration information “z″=8” stored in storage unit  107 , using user ID “IN=3” received in (7) as a retrieval key.  
         [0186]    (14) is equivalent to (14) at a time of data access in example 1.  
         [0187]    (15) In step S 18 , user secret key recovery unit  110  obtains 
         2 =A ×1 +B   (equation 9) 
         [0188]    by assigning user secret information “UL(y,x)=(1,1)” generated in (2) and user registration information “z=2” extracted in (6) to equation 6, obtains 
         8 =A ×3 +B   (equation 10) 
         [0189]    by assigning user secret information “UN(y″,x″)=(3,3)” generated in (9) and user registration information “z″=8” extracted in (13) to equation 7, and recovers secret keys “A=3”, “B=−1” by solving the simultaneous equations 9 and 10.  
         [0190]    (16)˜(17) are equivalent to (16)˜(17) at a time of data access in example 1.  
         [0191]    Variation  
         [0192]    In the data processing system in embodiment 1 of the present invention, user registration and data access are both conducted by the same device. In comparison, a variation of the present invention is structured such that a user registration device for conducting user registration and a data access device for conducting data access are independent.  
         [0193]    [0193]FIG. 6 shows a structure of a user registration device according to the variation of the present invention.  
         [0194]    User registration device  300  is structured from a secret key generation unit  301 , an input reception unit  302 , a user secret information generation unit  303 , a check information generation unit  304 , a user registration information generation unit  305 , a registration unit  306 , a storage unit  307 , a data processing unit  308 , and a first deletion unit  309 .  
         [0195]    [0195]FIG. 7 shows a structure of a data access device according to the variation of the present invention.  
         [0196]    Data access device  400  is structured from an input reception unit  401 , a user secret information generation unit  402 , a check information generation unit  403 , a storage unit  404 , an authentication unit  405 , a user registration information extraction unit  406 , a secret key recovery unit  407 , a data processing unit  408 , and a second deletion unit  409 .  
         [0197]    Secret key generation unit  301 , the same as unit  101  of embodiment 1, generates, prior to user registration being initiated, a secret key required for accessing a database unit  500 , and holds the generated secret key.  
         [0198]    Input reception unit  302  receives a user ID and a password from each of a plurality of users.  
         [0199]    User secret information generation unit  303  generates unique user secret information by performing a predetermined conversion on the user ID and the password received from each user by input reception unit  302 .  
         [0200]    Check information generation unit  304  conducts a hash operation on user secret information generated by user secret information generation unit  303 , and generates check information required for checking a validity of user IDs and passwords.  
         [0201]    User registration information generation unit  305 , the same as unit  105  of embodiment 1, generates, based on user secret information generated by user secret information generation unit  303 , user registration information for each user by sharing, in accordance with a (k,n) threshold scheme, a secret key generated by secret key generation unit  301 , so as to allow the secret key to be recovered from k pieces of user secret information. Combining the user registration information generated here for each user with the user secret information for the user results in information that is similar to conventional shared information for each user generated by share-encoding a secret key using a (k,n) threshold scheme. The user registration information thus corresponds to a difference between the shared information and user secret information. Here, k and n are integers greater than or equal to 2, and k is less than or equal to n.  
         [0202]    Registration unit  306 , the same as unit  106  of embodiment 1, registers each user by storing, in storage unit  307 , a password file for each user, formed from sets of a user ID, a piece of user registration information generated for each user by user registration information generation unit  305 , and a piece of check information generated by check information generation unit  304 , so that the check information and the user registration information are related to a corresponding user ID.  
         [0203]    Storage unit  307  has a password file stored therein by registration unit  306 .  
         [0204]    Data processing unit  308  instructs database unit  500  to make a setting such that access is only possible using a secret key generated by secret key generation unit  301 , after it has been judged that the number of users registered by registration unit  306  has reached a predetermined total number of users.  
         [0205]    First deletion unit  309 , the same as first deletion unit  112  of embodiment 1, deletes a secret key generated and held by secret key generation unit  301 , after an instruction has been issued to database unit  500  by data processing unit  308 .  
         [0206]    Input reception unit  401  receives a user ID and a password from each of a plurality of users.  
         [0207]    User secret information generation unit  402  generates unique user secret information by performing a predetermined conversion on the user ID and the password received from each user by input reception unit  401 .  
         [0208]    Check information generation unit  403  conducts a hash operation on user secret information generated by user secret information generation unit  402 , and generates check information required for checking a validity of user IDs and passwords.  
         [0209]    Storage unit  404  has stored therein password files that have been copied from storage unit  307  via a storage medium, a communications channel, or the like.  
         [0210]    Authentication unit  405 , the same as unit  108  of embodiment 1, extracts check information stored in storage unit  404 , using as a retrieval key a user ID received by reception unit  401 , and checks a validity of the user ID and the password by comparing the extracted check information with check information generated by check information generation unit  403 .  
         [0211]    User registration information extraction unit  406 , the same as unit  109  of embodiment 1, extracts user registration information stored in storage unit  404 , using as a retrieval key a user ID received by reception unit  401 , if authentication unit  405  authenticates that the user is valid.  
         [0212]    Secret key recovery unit  407 , the same as unit  110  of embodiment 1, recovers a secret key, using user secret information generated for each user by user secret information generation unit  402  and user registration information extracted for each user by user registration information extraction unit  406 , when judged that the number of users authenticated as valid by authentication unit  405  has reached a threshold value determined in advance.  
         [0213]    Data processing unit  408  accesses database unit  500  using a secret key recovered by secret key recovery unit  407 .  
         [0214]    Second deletion unit  409 , the same as unit  113  of embodiment 1, deletes a secret key recovered by secret key recovery unit  407 , after database unit  500  has been accessed by data processing unit  408 .  
         [0215]    Database unit  500 , at a time of user registration, receives and follows an instruction issued by data processing unit  308 , and, at a time of data access, accepts an access by data processing unit  408 .  
         [0216]    Although database unit  500  is described here as being disposed externally to user registration device  300  and data access device  400 , a structure in which database unit  500  is internalized in one of user registration device  300  and data access device  400  is acceptable.  
         [0217]    Also, in this variation, the operations at a time of user registration and data access, as well as the specific examples and the like are the same as embodiment 1, and thus a description is omitted here.  
         [0218]    Embodiment 2  
         [0219]    Structure  
         [0220]    The data processing system according to embodiment 1 of the present invention shares secret keys required for accessing a database. In comparison, a data processing system according to an embodiment 2 of the present invention shares secret keys required for encrypted communications.  
         [0221]    [0221]FIG. 8 shows a structure of a data processing system according to embodiment 2 of the present invention.  
         [0222]    As shown in FIG. 8, the data processing system of embodiment 2 is structured from a data processing device  600 , a data processing device  700 , a data processing device  800 , and a network bus  900 .  
         [0223]    Data processing device  600  is structured from a secret key generation unit  601 , an input reception unit  602 , a user secret information generation unit  603 , a check information generation unit  604 , a user registration information generation unit  605 , a registration unit  606 , a storage unit  607 , an authentication unit  608 , a user registration information extraction unit  609 , a secret key recovery unit  610 , a shared unit  611 , an encryption processing unit  612 , a data communication unit  613 , a first deletion unit  614 , and a second deletion unit  615 .  
         [0224]    A structure of data processing devices  700  and  800  is the same as that of data processing device  600 .  
         [0225]    Secret key generation unit  601  generates, prior to user registration being initiated, a secret key required in encrypted communications, and holds the generated secret key. Here, secret key generation unit  601  generates a random number as a secret key. Also, while the description relates to a secret key being generated in data processing device  600 , a secret key to be used in data processing device  600  may be provided in advance from another device.  
         [0226]    Input reception unit  602 , at a time of user registration, data transmission and data reception, receives a user ID and a password from each of a plurality of users.  
         [0227]    User secret information generation unit  603 , at a time of user registration, data transmission and data reception, generates unique user secret information by performing a predetermined conversion on the user ID and the password received from each user by input reception unit  602 .  
         [0228]    Here, the examples of user secret information are the same as in embodiment 1.  
         [0229]    Check information generation unit  604 , at a time of user registration, data transmission and data reception, conducts a hash operation on user secret information generated by user secret information generation unit  603 , and generates check information required for checking a validity of user IDs and passwords.  
         [0230]    User registration information generation unit  605 , at a time of user registration, generates, based on user secret information generated by user secret information generation unit  603 , user registration information for each user by sharing, in accordance with a (k,n) threshold scheme, a secret key generated by secret key generation unit  601 , so as to allow the secret key to be recovered from k pieces of user secret information. Combining the user registration information generated here for each user with the user secret information for the user results in information that is similar to conventional shared information for each user generated by share-encoding a secret key using a (k,n) threshold scheme. The user registration information thus corresponds to a difference between the shared information and user secret information. Here, k and n are integers greater than or equal to 2, and k is less than or equal to n.  
         [0231]    Registration unit  606  registers each user by storing, in storage unit  607 , a password file for each user, formed from sets of a user ID, a piece of user registration information generated for each user by user registration information generation unit  605 , and a piece of check information generated by check information generation unit  604 , so that the check information and the user registration information are related to a corresponding user ID.  
         [0232]    Storage unit  607 , at a time of user registration, has a password file stored therein by registration unit  606 .  
         [0233]    Authentication unit  608 , at a time of data transmission and data reception, extracts check information stored in storage unit  607 , using as a retrieval key a user ID received by reception unit  602 , and checks a validity of the user ID and the password by comparing the extracted check information with check information generated by check information generation unit  604 .  
         [0234]    User registration information extraction unit  609 , at a time of data transmission and data reception, extracts user registration information stored in storage unit  607 , using as a retrieval key a user ID received by reception unit  602 , if authentication unit  608  authenticates that the user is valid.  
         [0235]    Secret key recovery unit  610 , at a time of data transmission and data reception, recovers a secret key, using user secret information generated for each user by user secret information generation unit  603  and user registration information extracted for each user by user registration information extraction unit  609 , when judged that the number of users authenticated as valid by authentication unit  608  has reached a threshold value determined in advance.  
         [0236]    Share unit  611 , at a time of user registration, shares password files by passing password files stored in storage unit  607  to data processing unit  700  and data processing unit  800  via a storage medium, a communication channel or the like, after it has been judged that the number of users registered by registration unit  606  has reached a predetermined total number of users.  
         [0237]    Encryption processing unit  612 , at a time of data transmission, encrypts data for transmission, using a secret key recovered by secret key recovery unit  610 , and at a time of data reception, decrypts received data using a secret key recovered by secret key recovery unit  610 .  
         [0238]    Data communication unit  613 , at a time of data transmission, transmits data encrypted by encryption processing unit  612  to data processing device  700  or data processing device  800  via network bus  900 , and at a time of data reception, receives encrypted data from data processing device  700  or data processing device  800  via network bus  900 .  
         [0239]    First deletion unit  614 , at a time of user registration, deletes a secret key generated and held by secret key generation unit  601 , after it has been judged that the number of users registered by registration unit  606  has reached the predetermined total number of users.  
         [0240]    Second deletion unit  615 , at a time of data transmission and data reception, deletes a secret key recovered by secret key recovery unit  610 , after the encryption/decryption and transmission/reception has been conducted by encryption processing unit  612  and data communication unit  613 , respectively.  
         [0241]    Network bus  900  is a communication channel connecting the various data processing devices.  
         [0242]    User Registration Operations  
         [0243]    [0243]FIG. 9 shows a sequence of operations performed by the data processing system of embodiment 2 at a time of user registration.  
         [0244]    The operation procedures at a time of user registration will now be described.  
         [0245]    (1) Secret key generation unit  601  generates secret keys A, B (step S 21 ).  
         [0246]    (2) Input reception unit  602  receives a user ID and a password from a user (step S 22 ).  
         [0247]    (3) User secret information generation unit  603  generates unique user secret information, by performing a predetermined conversion on the user ID and the password received in step S 22  (step S 23 ).  
         [0248]    (4) Check information generation unit  604  conducts a hash operation on the user secret information generated in step S 23 , and generates check information (step S 24 ).  
         [0249]    (5) User registration information generation unit  605  generates, based on the user secret information generated in step S 23 , user registration information for each user by sharing, in accordance with a (k,n) threshold scheme, the secret keys generated in step S 21 , so as to allow the secret keys to be recovered from k pieces of user secret information (step S 25 ).  
         [0250]    (6) Registration unit  606  registers each user by storing, in storage unit  607 , a password file for each user, formed from sets of a user ID, a piece of user registration information generated in step S 25 , and a piece of check information generated in step S 24 , so that the check information and the user registration information are related to a corresponding user ID (step S 26 ).  
         [0251]    (7) Registration unit  606  judges whether the number of users has reached n number. If n has not been reached, return to step S 22  to receive another user ID and password (step S 27 ).  
         [0252]    (8) When the number of users reaches n, share unit  611  shares password files stored in storage unit  607  to data processing units  700  and  800  (step S 28 ).  
         [0253]    (9) First deletion unit  614  deletes the secret keys generated in step S 21  (step S 29 ).  
         [0254]    Data Transmission Operation  
         [0255]    [0255]FIG. 10 shows a sequence of operations performed by the data processing system of embodiment 2 at a time of data transmission.  
         [0256]    The operation procedures at a time of data transmission will now be described.  
         [0257]    (1) Input reception unit  602  receives a user ID and a password from a user (step S 31 ).  
         [0258]    (2) User secret information generation unit  603  generates unique user secret information, by performing a predetermined conversion on the user ID and the password received in step S 31  (step S 32 ).  
         [0259]    (3) Check information generation unit  604  conducts a hash operation on the user secret information generated in step S 32 , and generates check information (step S 33 ).  
         [0260]    (4) Authentication unit  608  extracts check information stored in storage unit  607 , using the user ID received in step S 31  as a retrieval key (step S 34 ).  
         [0261]    (5) Authentication unit  608  checks a validity of the user ID and the password by comparing the check information extracted in step S 34  with the check information generated in step S 33 . If a value of the two pieces of check information agree, authentication unit  608  assumes the user ID and the password to be valid and proceeds to processing to extract user registration information, and if a value of the two pieces of check information does not agree, authentication unit  608  assumes the user ID and the password to be invalid and returns to step S 31  to receive another user ID and password (step S 35 ).  
         [0262]    (6) If the user ID and the password are authenticated as being valid, user registration information extraction unit  609  extracts the user registration information stored in storage unit  607 , using the user ID received in step S 31  as a retrieval key (step S 36 ).  
         [0263]    (7) Secret key recovery unit  610  judges whether the number of users has reached k number. If k has not been reached, return to steps S 31  to receive another user ID and password (step S 37 ).  
         [0264]    (8) When the number of users reaches k, secret key recovery unit  610  recovers the secret keys, using k pieces of user secret information generated in step S 32  and k pieces of user registration information extracted in step S 36  (step S 38 ).  
         [0265]    (9) Encryption processing unit  612  encrypts data for transmission, using the secret keys recovered in step S 38 , and data communication unit  613  transmits data encrypted by encryption processing unit  612  to data processing device  700  or data processing device  800  via network bus  900  (step S 39 ).  
         [0266]    (10) Second deletion unit  615  deletes the secret keys recovered in step S 38  (step S 40 ).  
         [0267]    Data Reception Operation  
         [0268]    [0268]FIG. 11 shows a sequence of operations performed by the data processing system of embodiment 2 at a time of data reception.  
         [0269]    The operation procedures at a time of data reception will now be described.  
         [0270]    (1)˜(8) are the same as (1)˜(8) at a time of data transmission.  
         [0271]    (9) Data communication unit  613  receives encrypted data from data processing device  700  or data processing device  800  via network bus  900 , and encryption processing unit  612  decrypts the received data using the secret keys recovered in step S 38  (step S 41 ).  
         [0272]    (10) is the same as (10) at a time of data transmission.  
         [0273]    In embodiment 2, the specific examples are based on embodiment 1, and thus a description is omitted here.  
         [0274]    As described above, a data processing system according to the embodiments of the present invention creates and stores user registration information by sharing secret keys, based on passwords (freely settable by each user) and user IDs received from n number of users at a time of user registration, and, at a time of data access or encrypted communications, recovers secret keys using user IDs and passwords received from k number of users (k≦n) and stored user registration information.  
         [0275]    According to these structures, since users set their own easy-to-remember password, they can easily remember their password as a passphrase, without there being a need to stores passwords on a storage medium of some description.  
         [0276]    Consequently, secret keys cannot be recovered without passwords, even if, for example, all information apart from the passwords are stored on storage media connected to a particular device, and all of this information is leaked due to an attack on the device from a third party. Thus a high degree of security can be obtained simply by users each remembering their own easy-to-remember password.  
         [0277]    Furthermore, a computer program that has a computer execute operations such as those described in the embodiments of the present invention can be targeted for business transactions by, for example, storing the program on a computer-readable storage medium and circulating the storage medium, or transferring the program directly over a network.  
         [0278]    Here, a computer-readable storage medium may be, for example, a removable storage medium such as a floppy disk, a CD, an MO, a DVD, a memory card or the like, or a fixed storage medium such as a hard disk, a semi-conductor memory or the like, although no particular limitations apply with respect to the storage medium.  
         [0279]    Although the present invention has been fully described by way of examples with reference to the accompanying drawings, it is to be noted that various changes and modifications will be apparent to those skilled in the art. Therefore, unless such changes and modifications depart from the scope of the present invention, they should be construed as being included therein.