Patent Publication Number: US-6990200-B1

Title: Encryption method, cryptographic communication method, ciphertext generating device and cryptographic communication system of public-key cryptosystem

Description:
BACKGROUND OF THE INVENTION 
     The present invention relates to a public-key cryptosystem encryption method and ciphertext generating device for transforming a plaintext into a ciphertext by using a public key, a cryptographic communication method and cryptographic communication system using this encryption method, and a memory product/data signal embodied in carrier wave for recording/transmitting operation programs for these methods. 
     In the modern society, called a highly information-oriented society, based on a computer network, important business documents and image information are transmitted and communicated in a form of electronic information. Such electronic information can be easily copied, so that it tends to be difficult to discriminate its copy and original from each other, thus bringing about an important issue of data integrity. In particular, it is indispensable for establishment of a highly information oriented society to implement such a computer network that meets the factors of “sharing of computer resources,” “multi-accessing,” and “globalization,” which however includes various factors contradicting the problem of data integrity among the parties concerned. In an attempt to eliminate those contradictions, encrypting technologies which have been mainly used in the past military and diplomatic fields in the human history are attracting world attention as an effective method for that purpose. 
     A cipher is defined as exchanging information in such a manner that no one other than the parties concerned can understand the meaning of the information. In the field of ciphers, encryption is defined as converting an original text (plaintext) that can be understood by anyone into a text (ciphertext) that cannot be understood by the third party and decryption is defined as restoring a ciphertext into a plaintext, and cryptosystem is defined as the overall processes covering both encryption and decryption. The encrypting and decrypting processes use secret information called an encryption key and a decryption key, respectively. Since the secret decryption key is necessary in decryption, only those knowing this decryption key can decrypt ciphertexts, thus maintaining data security. 
     The encryption scheme is roughly classified into two types: common-key cryptosystem and public-key cryptosystem. In a common-key cryptosystem, an encryption key and a decryption key are identical with each other, and a sender and a recipient perform cryptographic communications by possessing an identical common key. The sender encrypts a plaintext based on a secret common key and transmits the resultant ciphertext to the recipient, and then the recipient decrypts the ciphertext into the original plaintext by using this common key. 
     On the other hand, in a public-key cryptosystem, an encryption key and a decryption key are different from each other, and cryptographic communications are performed by encrypting a plaintext by the sender with the use of a publicized public key of the recipient and decrypting the resultant ciphertext by the recipient with the use of its own secret key. The public key is a key used for encryption and the secret key is a key used for decrypting the ciphertext transformed by the public key, and the ciphertext transformed by the public key can be decrypted only by the secret key. 
     As one scheme of public-key cryptosystem, a product-sum type encryption scheme has been known. In this encryption scheme, the sender as one of entities generates ciphertext C=m 1 c 1 =m 2 c 2 = . . . +m K c K  by using plaintext vector m=(m 1 , m 2 , . . . , m K ) obtained by dividing plaintext into K pieces and base vector c=(c 1 , c 2 , . . . , c K ) as a public key, and the recipient as the other entity decrypts the ciphertext C into the plaintext vector m by using a secret key to obtain the original plaintext. 
     Regarding the product-sum type cryptosystem using an operation on an integer ring, new schemes and attacking methods have been proposed one after another. In particular, development of encryption/decryption techniques capable of performing high-speed decryption has been desired so as to process a large quantity of information in a short time. Then, the present inventors proposed an encryption method and decryption method of the product-sum type cryptosystem, which enable high-speed decryption processing by expressing plaintext by using multi-adic numbers (Japanese Patent Application Laid-Open Nos. 2000-89668 and 2000-89669). 
     The following description will explain the encryption method and decryption method proposed in Japanese Patent Application Laid-Open No. 2000-89668 (hereinafter referred to as the “first conventional example”). The secret and public keys are prepared as follows.
         Secret key: {b i }, {v i }, P, w   Public key: {c i }       

     By multiplying a base-product b 1 b 2  . . . b i  by a random number term v i , a base B i  is given as shown by (1) below.
 
 B   i   =v   i   b   1   b   2    . . . b   i   (1)
 
     Here, v i  is set so that each B i  expressed by equation (1) has an almost equal size. However, the condition gcd(v i , b i=1 )=1 must be satisfied. 
     With the use of a random number w, the public key {c i } is found as shown by (2) below.
 
c i ≡wB i (mod P)  (2)
 
     By performing the product-sum operation of messages {m i } obtained by dividing the plaintext into K pieces and the public keys {c i }, the ciphertext C is obtained as shown by (3) below.
 
 C=m   1   c   1   +m   2   c   2   + . . . +m   K   c   K   (3)
 
     Decryption processing is carried out as follows. 
     For the ciphertext C, an intermediate decrypted text M is found as shown by (4) below.
 
 M≡w   −1   C (mod  P )  (4)
 
     This intermediate decrypted text M is specifically given as equation (5), and it can be decrypted by a sequential decryption algorithm shown below.
 
 M=m   1   b   1   v   1   +m   2   b   1   b   2   v   2   + . . . +m   K   b   1   b   2    . . . b   K   v   K   (5)
 
[Sequential Decryption Algorithm]
 
     Step 1
 
 M   1   =M/b   1  
 
 m   1   =M   1   v   1   −1 (mod  b   2 )
 
     Step i (i=2 to K−1)
 
 M   1 =( M   i−1   −m   i−1   v   i−1 )/ b   1  
 
 m   1   ≡M   i   v   i   −1 (mod  b   i+1 )
 
     Step K
 
 M   K =( M   K−1   −m   K−1   v   K−1 )/ b   K  
 
 m   K   =M   K   /v   K  
 
     Originally, such a public-key encryption scheme bases its security on the difficulty of factoring and the difficulty of solving a discrete logarithm problem, and various attacks against it have been proposed. 
     Moreover, the present inventors proposed a new type of public-key cryptosystem encryption method which bases its security on such a point that a set of public keys can be freely selected among a very large number of combinations of public keys (Japanese Patent Application No. 11-269407/1999, hereinafter referred to as the “second conventional example”). This scheme is a modified scheme of the above-mentioned first conventional example. In this scheme, a plurality of public keys produced from the products of integers and random number terms are prepared in advance for each divided plaintext obtained by dividing a plaintext, an arbitrary public key is selected for each divided plaintext among these prepared public keys, and a ciphertext is generated by using the selected public keys. The following description will explain the encryption method and decryption method proposed in this second conventional example. 
     The intermediate decryped text M during the first transfer by the encryption scheme of the second conventional example based on the scheme of the first conventional example is given by (6) below.
 
 M=m   1   ′b   1   v   1   +m   2   ′b   1   b   2   v   2   + . . . +m   K   ′b   1   b   2    . . . b   K   v   K   (6)
 
     However, m 1 ′ is encoded to establish (7) below module J for j given by adding jog 2  J-bit redundancy to message (divided plaintext) m 1 , and the information indicating which public key among later-described plurality of public keys is to be selected for each divided plaintext is transmitted.
 
 m   i   ′≡j (mod  J )  (7)
 
       FIG. 1  is an illustration showing a public key list indicating a plurality of public keys prepared for each divided plaintext. In  FIG. 1 , K represents a dividing number (class number) of plaintext. As illustrated in  FIG. 1 , the set {b 1 b 2  . . . b i v i   (j) } provided by multiplying the base-product by a random number term is prepared as J pieces of public keys for each divided plaintext (each class). 
     An entity as the recipient transforms these products of the base-product and random number term by a random number w and publicizes them. In other words, the products of the base-product and random number term shown in  FIG. 1  are transformed as shown by (8) below, and the set {c ij } thereof is publicized.
 
 b   1   b   1    . . . b   i   v   i   (j)   w≡c   ij (mod  P )  (8)
 
     A set of public keys which is randomly selected by an entity as the sender is expressed as shown by (9) below. In this case, it is possible for the entity as the sender to select public keys in J K (&gt;&gt; 1) ways. 
     [Eq. 1]
 
( c   1   , j   1   , c   2   , j   2   , . . . , c   K   , j   K )  (9)
 
     According to a set of the selected public keys shown in (9) above, the entity as the sender lets m i ′≡j i  (mod J), and then generates the ciphertext C to the entity as the recipient as shown by (10) below. 
     [Eq. 2]
 
 C=m   1   ′c   1   , j   1   +m   2   ′c   2   , j   2   + . . . +m   K   ′c   K   , j   K   (10)
 
     In order to decrypt the ciphertext C thus generated, the entity as the recipient predetermines the random number term v i   (j)  of  FIG. 1  as shown by (11) below.
 
 v   i   (j)   =w   b, i   +r   i   (j)   b   i+l   (11)
 
where each of w b, i,  r i   (j)  is a random number.
 
     Further, the entity as the recipient has w b, i   −1  that satisfies (12) below as a secret key.
 
 w   b, i   ·w   b, i   −1 ≡1(mod  b   i+l )  (12)
 
     The decryption processing by the entity as the recipient is carried out as follows. An intermediate decrypted text M 0  is given as shown by (13) below. 
     [Eq. 3]
 
 M   0   =m   1   ′b   1   v   1   (j     1     )   +m   2   ′b   1   b   2   v   2   (j     2     )   + . . . +m   K   ′b   1   b   2   , . . . b   K   v   K   (j     K     )   (13)
 
     Therefore, decryption can be performed by the sequential decryption algorithm shown in (14) below. Incidentally, in (14), although b K+1  is a random number satisfying m K ′&lt;b K+i , it is not used as a base. In general, the random number term for j i  in step i is expressed as shown by (15) below. 
               [     Eq   .           ⁢   4     ]     ⁢           ⁢   Sequential   ⁢           ⁢   Decryption   ⁢           ⁢   Algorithm                                   Step   ⁢           ⁢   1                       M   1     =       ⁢       M   0       b   1                     m   1   ′     ≡       ⁢         M   1     ·     w     b   ,   i       -   1         ⁢           ⁢     (     mod   ⁢           ⁢     b   2       )                     m   1   ′     ≡       ⁢       j   i     ⁢           ⁢     (     mod   ⁢           ⁢   J     )                         Step   ⁢           ⁢   i   ⁢           ⁢     (     i   =       2   ⁢           ⁢   to   ⁢           ⁢   K     -   1       )                         M   i     =       ⁢         M     i   -   1       -       m     i   -     i   ′         ⁢     v     i   -   1       (     i     i   -   i       )             b   i                     m   i   ′     ≡       ⁢       M   i     ⁢     w     b   ,   i       -   1       ⁢           ⁢     (     mod   ⁢           ⁢     b     i   +   1         )                     m   i   ′     ≡       ⁢       j   i     ⁢           ⁢     (     mod   ⁢           ⁢   J     )                         Step   ⁢           ⁢   K                       M   K     =       ⁢         M     K   -   1       -       m     K   -     1   ′         ⁢     v     K   -   1       (     j     K   -   1       )             b   K                     m   K   ′     ≡       ⁢       M   i     ⁢     w     b   ,   K       -   1       ⁢           ⁢     (     mod   ⁢           ⁢     b     K   +   1         )                     }           (   14   )               v     (     j   i     )             (   15   )             
 
     In the decryption method proposed in the above-described second conventional example, since public keys are arbitrarily selected, i.e., since the entity as the sender freely selects public keys and generates ciphertext, the selection pattern of the public keys is unknown to attackers, and thus making it difficult to attack. Besides, the present inventors are further researching on a more practical encryption method. 
     BRIEF SUMMARY OF THE INVENTION 
     An object of the present invention is to provide a public-key cryptosystem encryption method, cryptographic communication method, ciphertext generating device and cryptographic communication system which are capable of achieving high-speed processing while ensuring security by free selection of public keys, and a memory product/data signal embodied in carrier wave for recording/transmitting operation programs for these methods. 
     According to a first aspect of the present invention, two public keys including a random number term therein are prepared for each divided plaintext in advance, a plaintext to be encrypted is divided into a plurality of 1-bit divided plaintexts, one public key is selected for each divided plaintext among the two public keys prepared, according to a bit pattern of the plurality of divided plaintexts, and a ciphertext is generated by using the plurality of divided plaintexts and selected public keys. In the encryption method proposed in the above-mentioned second conventional example, this first aspect limits the divided plaintexts to one bit and restrains the number of rows in the public key list to two rows (J=2). It is therefore possible to perform encryption and decryption processing at extremely high speeds. However, with the simple addition of such limitations, since a public key of the first row is selected when m i =0 and a public key of the second row is selected when m i =1, a 0, 1-knapsack cryptosystem with an extremely low level of security will result. Then, with the first aspect, the ciphertext is generated by determining which public key is to be selected for each divided plaintext, according to a bit pattern of a plurality of divided plaintexts. Hence, unlike the 0, 1-knapsack cryptosystem, high security is achieved. 
     According to a second aspect of the present invention, 2 s  public keys including a random number term therein are prepared for each divided plaintext in advance, a plaintext to be encrypted is divided into a plurality of s-bit divided plaintexts, one public key is selected for each divided plaintext among the 2 s  public keys prepared, according to the bit data of each divided plaintext, and a ciphertext is generated by using the selected public keys. For example, when s=1, two public keys including a random number term therein (a public key list with two upper and lower rows) are prepared for each divided plaintext, one of the public keys is selected according to the bit data (“0”, “1”) of each divided plaintext, and all the selected public keys are added to generate the ciphertext. At this time, as an example, when the plaintext is “0”, the public key of the upper row is selected, while when the plaintext is “1”, the public key of the lower row is selected. With the second aspect, the ciphertext is generated simply by adding the public keys including a random number term therein, which are selected according to the bit data, and the encryption and decryption processing becomes extremely fast. The bit data of each divided plaintext used as a criterion to select a public key is unknown to the attackers and the selection pattern of the public keys can never be known, thereby achieving high security. 
     With the present invention, it is possible to achieve high-speed encryption/decryption processing while ensuring security by free selection of public keys, and the present invention can largely contribute to the development and realization of practical use of public-key encryption schemes. 
     The above and further objects and features of the invention will more fully be apparent from the following detailed description with accompanying drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS 
         FIG. 1  is an illustration showing a public key list according to an encryption scheme of the second conventional example, 
         FIG. 2  is a depiction showing a state of cryptographic communications of information between two entities according to a first embodiment, 
         FIG. 3  is an illustration showing a public key list in a database according to the present invention, 
         FIG. 4  is a depiction showing a state of cryptographic communications of information between two entities according to a second embodiment, and 
         FIG. 5  is an illustration showing the structures of embodiments of a memory product. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     The present invention will be described below with reference to the drawings illustrating the embodiments thereof. 
     First Embodiment 
     The following description will explain a first embodiment in which a public key is selected according to a bit pattern of a plurality of divided plaintexts. 
       FIG. 2  is a depiction showing a state in which an encryption scheme according to the first embodiment (first aspect) is used for information communications between entities A and B. The example shown in  FIG. 2  illustrates a case where one of the entities, A, encrypts a plaintext X into a ciphertext C and transmits the ciphertext C to the other entity, B, via a communication path  1 , and the entity B decrypts the ciphertext C into the original plaintext X. 
     The entity A as the sender is provided with a plaintext divider  2  for dividing the plaintext X into a plurality of 1-bit divided plaintexts, a public-key selector  3  for selecting a public key for each divided plaintext from a database  6  storing a public key list as described later, and an encryptor  4  for generating the ciphertext C by using the selected public keys and respective divided plaintexts. Besides, the entity B as the recipient is provided with a decryptor  5  for decrypting the transmitted ciphertext C into the original plaintext X. In this example, the issuer of the public key list is the entity B as the recipient, and the user of this public key list is the entity A as the sender. 
     Next, a specific technique will be explained.  FIG. 3  is an illustration showing the public key list in the database  6  that stores a plurality of public keys for each divided plaintext in advance.  FIG. 3  shows a public key list in accordance with the supposition that a public key for each divided plaintext is constructed by modular transformation by (w 1 , P 1 ). In  FIG. 3 , K represents a dividing number (class number) of the plaintext X, two (upper row, lower row) public keys including a random number term therein are prepared for each of K pieces of divided plaintexts (for each class). 
     In the encryption method proposed in the second conventional example, when m i =0, the component v i   (0)  of the upper row of the public key list of  FIG. 3  is selected, while when m i =1, the component v i   (1)  of the lower row is selected. Thus, when the technique is simply applied to the encryption method of the second conventional example, a 0, 1-knapsack cryptosystem with an extremely low level of security will result. 
     Then, in the first embodiment, it is determined which row of the public keys in the public key list is to be selected for each divided plaintext, according to a bit pattern of a plurality of divided plaintexts. In other words, after dividing the plaintext X into K pieces of 1-bit divided plaintexts, selection information (x 1 , x 2 , . . . , x K ) indicating which row of the public keys is to be selected is determined for each divided plaintext, according to a bit pattern of the K pieces of divided plaintexts (m 1 , m 2 , . . . , m K ). An algorithm for pre-coding the divided plaintexts to the selection information is as follows. 
     [Pre-coding Algorithm] 
     Step 1
         x 1 =0, i.e., the upper row is selected.       

     Step i (i=2 to K−1)
         When m i−1 =0, x i  selects the same row as x i−1 .   When m i−l =1, x i  selects a row different from x i−1 .       

     For example, when the divided plaintexts are (m 1 , m 2 , m 3 , m 4 , m 5 )=(0, 1, 0, 1, 0), if the selection of the upper row is represented by 0 and the selection of the lower row is represented by 1, the precoded selection information of the upper and lower rows is (x 1 , x 2 , x 3 , x 4 , x 5 )=(0, 0, 1, 1, 0). 
     The entity A generates the ciphertext C to the entity B as shown by (16) below, based on a set of public keys selected according to the bit pattern of a plurality of divided plaintexts.
 
 C=m   i   v   i   (t1)   w   1   +m   2 2 v   2   (t2)   w   1   + . . . +m   K 2 K−1   v   K   (tK)   w   1   (16)
         (t1, t2, . . . , tK=0 or 1)       

     For example, when the divided plaintext are (m 1 , m 2 , m 3 , m 4 , m 5 )=(0, 1, 0, 1, 0), since the selection information of the upper and lower rows of the public keys is (x 1 , x 2 , x 3 , x 4 , x 5 )=(0, 0, 1, 1, 0), the ciphertext C is concretely given as shown by (17) below.
 
 C= 2 v   2   (0)   w   1 +2 3   v   4   (1)   w   1   (17)
 
     The ciphertext C thus generated is transmitted from the entity A to the entity B via the communication path  1 . Then, the ciphertext C is decrypted into the original plaintext X by the entity B. 
     The decryption processing by the decryptor  5  of the entity B is carried out as follows. 
     An intermediate decrypted text M 1  found as shown by (18) below.
 
 M   1   ≡C·w   1   −1 (mod  P   1 )  (18)
 
     Let the selection information of the upper and lower rows be x 1 =0. 
     Next, with the use of the component v 1   (0)  of the upper row, m 1  is found as shown by (19) below.
 
 m   1   ≡M   1 ·( v   1   (0) ) −1 (mod 2)  (19)
 
     The next intermediate decrypted text M 2  is found as shown by (20) below.
 
 M   2   =M   1   −m   1   v   i   (0)   (20)
 
     Supposing that x 2 =x 1  xor m 1 , the next selection information x 2  is found. 
     Then, by considering that the upper row is selected when x 2 =0 and the lower row is selected when x 2 =1, m 2  is found as shown by (21) below.
 
 m   2   =M   2 ·( v   2   (x2) ) −1 (mod 2)  (21)
 
     Thereafter, in the same manner as for m 2 , the remaining m 3 , . . . , m K  are decrypted. 
     In the first embodiment as described above, the first base-product v 1   (1) w 1  in the lower row of  FIG. 3  is not used for decryption of the pre-coding. Since the number of rows in the public key list is 2 rows (J=2), in the first embodiment, the length of the input plaintext becomes twice longer, but the weight index=(average weight)/(concatenate plaintext length)=¼. 
     Incidentally, the above-described algorithm for pre-coding divided plaintexts to selection information is merely an example and, needless to say, it is possible to use another example of algorithm for determining the selection information of public keys according to the bit pattern of a plurality of divided plaintexts. 
     The following description will explain examples of the application of the first embodiment that achieve improved security. 
     (Application of Multi-Stage Encryption) 
     This is the application of the encryption method (the concept of multi-stage encryption) proposed in Japanese Patent Application No. 11-173338/1999 by the present inventors to the above-described encryption method, in which application ciphertext is generated by using the result of operating multi-stage modular-transformation by a plurality of random numbers on a public key selected for each divided plaintext. With respect to a base-product shown in  FIG. 3 , a plurality of sets (S sets) of a pair (w, P) of random number w and prime number P are set, multiplication by the random numbers are performed over S stages, and the result is used as a public key. Hence, by applying the multi-stage encryption technique to the basic encryption scheme of the first embodiment, it is possible to establish a scheme that achieves higher security. 
     (Application of Product-Sum-Product Encryption) 
     This is the application of the encryption method (the concept of product-sum-product encryption) proposed in Japanese Patent Application No. 11-205381/1999 by the present inventors to the above-described encryption method, in which application ciphertext is generated by setting a plurality of product-sum terms of the divided plaintexts and public keys selected for each divided plaintext and combining the plurality of the product-sum terms in the forms of product or sum. A part of divided plaintexts obtained by dividing plaintext and public keys selected for each of that part of the divided plaintexts are used to generate plural sets of product-sum terms as shown by (16) above, and multiplication and/or addition of the generated plural sets of the product-sum terms are further performed to generate ciphertext. Thus, by applying the product-sum-product encryption technique to the basic encryption scheme of the first embodiment, it is possible to establish a scheme that achieves higher security. 
     As described in detail above, in the first embodiment, two public keys are prepared for each divided plaintext in advance, a plaintext to be encrypted is divided into a plurality of 1-bit divided plaintexts, one public key is selected among the two public keys prepared for each divided plaintext, according to a bit pattern of the plurality of divided plaintexts, and a ciphertext is generated by using the plurality of divided plaintexts and selected public keys. It is therefore possible to achieve high-speed encryption/decryption processing while ensuring security by free selection of public keys and to foster the development and practical use of the public-key encryption scheme. 
     Second Embodiment 
     The following description will explain a second embodiment in which public keys are selected according to the bit data of a plurality of divided plaintexts. 
       FIG. 4  is a depiction showing a state in which an encryption scheme according to the second embodiment (second aspect) is used for information communications between the entities A and B. Like  FIG. 2 , the example shown in  FIG. 4  illustrates a case where one of the entities, A, encrypts a plaintext X into a ciphertext C and transmits the ciphertext C to the other entity, B, via a communication path  11 , and the entity B decrypts the ciphertext C into the original plaintext X. 
     The entity A as the sender is provided with a plaintext divider  12  for dividing the plaintext X into a plurality of divided plaintexts, a public-key selector  13  for selecting a public key for each divided plaintext from a database  16  storing a public key list, and an encryptor  14  for generating the ciphertext C by using the selected public keys. Besides, the entity B as the recipient is provided with a decryptor  15  for decrypting the transmitted ciphertext C into the original plaintext X. In this example, the issuer of the public key list is the entity B as the recipient, and the user of this public key list is the entity A as the sender. 
     Next, a specific technique will be explained. Note that the following explanation is given by illustrating an example in which s=1, i.e., each divided plaintext is one bit and two public keys are provided for selection with respect to each divided plaintext.  FIG. 3  is an illustration showing the public key list in the database  16  that stores two public keys for each divided plaintext in advance.  FIG. 3  shows a public key list in accordance with the supposition that a public key for each divided plaintext is constructed by modular transformation by (w 1 , P 1 ). In  FIG. 3 , K represents a dividing number (class number) of the plaintext X, two (upper row, lower row) public keys including a random number term therein are prepared for each of K pieces of divided plaintexts (for each class). Besides, the random number v i   (0)  and random number v i   (1)  in  FIG. 3  satisfy (22) and (23) below, respectively.
 
 v   i   (0) ≡0(mod 2)  (22)
 
 v   i   (1) ≡0(mod 2)  (23)
 
     After dividing the plaintext X into K pieces of 1-bit divided plaintexts, the entity A selects a public key according to the bit data of each of the divided plaintexts. In other words, when the divided plaintext is m i =0, a public key of the upper row, i.e., the base-product 2 i−1 v i   (0) , is selected, while when the divided plaintext is m i =1, a public key of the lower row, i.e., the base-product 2 i−1 v i   (1) , is selected. By sequentially adding the selected public keys, the ciphertext C to the entity B is generated as shown by (24) below.
 
 C=v   i   (t1)   w   1 +2 v   2   (t2)   w   1 + . . . +2 K−1   v   K   (tK)   w   1  
 
(t1, t2, . . . , tK=0 or 1)  (24)
 
     For example, when the divided plaintexts are (m 1 , m 2 , m 3 , m 4 , m 5 )=(0, 1, 0, 1, 0), the ciphertext C to the entity B is generated as shown by (25) below.
 
 C=v   1   (0)   w   1 +2 v   2   (1)   w   1 +2 2   v   3   (0)   w   1 +2 3   v   4   (1)   w   1 +2 4   v   5   (0)   w   1   (25)
 
     The ciphertext C thus generated is transmitted from the entity A to the entity B via the communication path  11 . Then, the ciphertext C is decrypted into the original plaintext X by the entity B. 
     The decryption processing by the decryptor  15  of the entity B is carried out as follows. 
     An intermediate decrypted text M 1  is found as shown by (26) below.
 
 M   1   ≡C·w   1   −1 (mod  P   1 )  (26)
 
     Here, it is apparent that the intermediate decrypted text M 1  is expressed as shown by (27) below. Here, however, (28) shown below must be satisfied. 
     [Eq. 5]
 
 M   1   +v   1   (m     1     ) +2 v   2   (m     2     ) +2 2   v   3   (m     3     )  . . . +2 K−1   v   K   (m     K     )   (27)
 
|2 i−1 v i   (m     i     )   |≧K+ 64  (28)
 
     Therefore, decryption can be performed by a decryption algorithm shown in (29) below. It will be appreciated that this decryption algorithm is extremely simplified. 
               [     Eq   .           ⁢   6     ]     ⁢           ⁢   Decryption   ⁢           ⁢   Algorithm                                   Step   ⁢           ⁢   1                   when   ⁢           ⁢     M   1       ≡     0   ⁢           ⁢     (     mod   ⁢           ⁢   2     )         ,       decryption   ⁢           ⁢   of   ⁢           ⁢     m   1       =   0                     when   ⁢           ⁢     M   1       ≡     1   ⁢           ⁢     (     mod   ⁢           ⁢   2     )         ,       decryption   ⁢           ⁢   of   ⁢           ⁢     m   1       =   1                 Step   ⁢           ⁢   i   ⁢           ⁢     (     i   =     2   ⁢           ⁢   to   ⁢           ⁢   K       )                   M   i     =         M     i   -   1       -     v     i   -   1       (     m     i   -   1       )         2                     when   ⁢           ⁢     M   1       ≡     0   ⁢           ⁢     (     mod   ⁢           ⁢   2     )         ,       decryption   ⁢           ⁢   of   ⁢           ⁢     m   1       =   0                     when   ⁢           ⁢     M   1       ≡     1   ⁢           ⁢     (     mod   ⁢           ⁢   2     )         ,       decryption   ⁢           ⁢   of   ⁢           ⁢     m   1       =   1             }           (   29   )             
 
     The following description will explain the characteristics of the encryption scheme of the second embodiment by mainly discussing the comparison between this encryption scheme and a 0, 1-knapsack cryptosystem which is very close to this. There is a notable difference between the encryption scheme of the second embodiment and the conventional knapsack cryptosystem in that the encryption scheme of the second embodiment does not have Σm i c i  form, i.e., is not of product-sum type but is of addition type. 
     In the scheme of the second embodiment, the weight index=½ for the concatenate plaintext. For this sense, it would be considered that the scheme of the second embodiment is strengthened against concatenate attacks. The scheme of the second embodiment has the following significant characteristics in comparison with the conventional 0, 1-knapsack cryptosystem. 
     In the scheme of the second embodiment, as the sum of ciphertext C shown in (30) below based on the public keys (c 1 , c 2 , . . . , c K ) corresponding to the upper row of  FIG. 3  and ciphertext C′ shown in (31) below based on the public keys (c 1 ′, c 2 ′, . . . , c K ′) corresponding to the lower row of  FIG. 3 , ciphertext C s  is given as shown by (32) below. 
     [Eq. 7]
 
 C=Σ{overscore (m     i     )}   c   i   (30)
 
 C=Σm   i   c   i   (31)
 
 C   S   =C+C′   (32)
 
     For example, when the divided plaintexts are (m 1 , m 2 , m 3 , m 4 , m 5 )=(0, 1, 1, 0, 1), the ciphertext C and ciphertext C′ are given as shown by (33) and (34) below, respectively. 
     [Eq. 8]
 
 C={overscore (m     1     )}   c   1   +{overscore (m     4     )}   c   4   (33)
 
 C′=m   2   c′   2   +m   3   c′   3   +m   5   c′   5   (34)
 
     The ciphertext C and ciphertext C′ are generated by multi-stage encryption, and designed to achieve higher security by different random numbers {v i }, {v i ′}, respectively. The ciphertext C s  according to the scheme of the second embodiment is given as the sum of two apparently different ciphertexts of the knapsack cryptosystem. For this sense, is should be considered that a breakthrough was made in the 0, 1-knapsack cryptosystem. Regarding the LLL (Lenstra-Lenstra-Lovasz) attack, it is considered that it is extremely difficult for the attacker to attack since (the input plaintext lengh)/(ciphertext)=2 is satisfied. 
     The following description will explain examples of the application of the second embodiment that achieve improved security. 
     (Application of Multi-Stage Encryption) 
     This is the application of the encryption method (the concept of multi-stage encryption) proposed in Japanese Patent Application No. 11-173338/1999 by the present inventors to the above-described encryption method, in which application ciphertext is generated by using the result of operating multi-stage modular-transformation by a plurality of random numbers on a public key selected for each divided plaintext. With respect to a base-product shown in  FIG. 3 , a plurality of sets (S sets) of a pair (w, P) of random number w and prime number P are set, multiplication by the random numbers are performed over S stages, and the result is used as a public key. Hence, by applying the multi-stage encryption technique to the basic encryption scheme of the second embodiment, it is possible to establish a scheme that achieves higher security. 
     (Application of Product-Sum-Product Encryption) 
     This is the application of the encryption method (the concept of product-sum-product encryption) proposed in Japanese Patent Application No. 11-205381/1999 by the present inventors to the above-described encryption method, in which application ciphertext is generated by setting a plurality of sum terms obtained by adding a plurality of selected public keys and combining a plurality of the sum terms in the form of product and/or sum. Plural sets of sum terms as shown by (24) above are generated with the use of a plurality of public keys selected according to the bit data of each divided plaintext, and multiplication and/or addition of the generated plural sets of the sum terms are further performed to generate ciphertext. Thus, by applying the product-sum-product encryption technique to the basic encryption scheme of the second embodiment, it is possible to establish a scheme that achieves higher security. 
     Incidentally, in the above-described example, while the case where two public keys are provided for selection with respect to each divided plaintext (s=1) has been explained, it is possible to expand the application to the case where b i =2 s (s: natural number no less than 2) by using a random number as shown by (36) below that satisfies (35) below. For example, when s=2, four public keys are prepared for each divided plaintext, a plaintext is divided into 2-bit divided plaintexts, one public key is selected for each divided plaintext among the four public keys according to the bit data of each divided plaintext, and a ciphertext is generated in the form of sum of all of the selected public keys. 
     [Eq. 9]
 
 v   i   (m     i     )   =m (mod2 S )  (35)
 
 v   i   (m     i     )   (36)
 
     As described in detail above, in the second embodiment, 2 s  public keys including a random number term therein are prepared for each divided plaintext in advance, a plaintext to be encrypted is divided into a plurality of s-bit divided plaintexts, one public key is selected for each divided plaintext among the 2 s  public keys prepared for each divided plaintext, according to the bit data of each divided plaintext, and a ciphertext is generated by using the selected public keys. It is therefore possible to achieve high-speed encryption/decryption processing while ensuring security by free selection of public keys and to foster the development and practical use of the public-key encryption scheme. 
     Further, while the above-described examples are illustrated for the cryptographic communication system, needless to say, it is possible to apply the encryption methods of the first and second embodiments of the present invention to the case where a ciphertext is by encrypting a plaintext and the generated ciphertext is simply recorded. 
     Next, examples of a memory product and transmission medium of the present invention will be explained.  FIG. 5  is an illustration showing the structures of embodiments of the memory product of the present invention. The programs exemplified here include a process for selecting a public key for each divided plaintext among a plurality of public keys stored in the database  6  (or  16 ) in advance, according to the data pattern of a plurality of divided plaintexts (or the bit data of each divided plaintext), and a process for generating ciphertext by using the selected public keys and divided plaintexts (or by using the selected public keys), or include a process for decrypting the ciphertext thus generated according to the above-described decryption algorithm, and are recorded in the memory product explained below. Besides, a computer  20  is provided for each entity. 
     In  FIG. 5 , a memory product  21  to be on-line connected to the computer  20  is constructed by, for example, a WWW (World Wide Web) server computer installed at a distant point from the installation position of the computer  20 , and a program  21   a  as mentioned above is stored in the memory product  21 . The program  21   a  read from the memory product  21  through a transmission medium  24  such as a communication line controls the computer  20  to generate the ciphertext C, or decrypt the ciphertext C into the original plaintext X. 
     A memory product  22  provided inside the computer  20  is constructed by, for example, a hard disk drive or ROM installed in the computer  20 , and a program  22   a  as mentioned above is stored in the memory product  22 . The program  22   a  read from the memory product  22  controls the computer  20  to generate the ciphertext C, or decrypt the ciphertext C into the original plaintext X. 
     A memory product  23  which is used by loading it in a disk drive  20   a  provided for the computer  20  is constructed by, for example, a portable magneto-optical disk, CD-ROM or flexible disk, and a program  23   a  as mentioned above is stored in the memory product  23 . The program  23   a  read from the memory product  23  controls the computer  20  to generate the ciphertext C, or decrypt the ciphertext C into the original plaintext X. 
     As this invention may be embodied in several forms without departing from the spirit of essential characteristics thereof, the present embodiment is therefore illustrative and not restrictive, since the scope of the invention is defined by the appended claims rather than by the description preceding them, and all changes that fall within metes and bounds of the claims, or equivalence of such metes and bounds thereof are therefore intended to be embraced by the claims.