Nippon Telegraph and Telephone Corporation

Nippon Telegraph and Telephone Public Corporation

Kazuo Ohta

Tatsuaki Okamoto

Kazumaro Aoki

Youichi Takashima

Masayuki Kanda

Eiichiro Fujisaki

Kazmaro Aoki

Masayuki Abe

Shiho Moriai

Hiroki Ueda

Tsutomu Matsumoto

Atsushi Fujioka

In the evaluation of the randomness of an S-box, measures of resistance to higher order cryptanalysis, interpolation cryptanalysis, partitioning cryptanalysis and differential-linear cryptanalysis and necessary conditions for those measures to have resistance to each cryptanalysis are set, then for functions as candidates for the S-box, it is evaluated whether one or all of the conditions are satisfied, and those of the candidate functions for which one or all of the conditions are satisfied are selected as required. It is also possible to further evaluate the resistance of such selected functions to at least one of differential cryptanalysis and linear cryptanalysis and select those of the candidate functions which are resistant to at least one of the cryptanalyses as required.

Method and apparatus for evaluating the strength of an encryption

A plurality of round processing parts ( ) are provided each of which contains a nonlinear function part ( ), and each nonlinear function part ( ) comprises: a first key-dependent linear transformation part ( ) which performs a linear transformation based on a subkey; a splitting part ( ) which splits the output from the first key-dependent linear transformation part into n pieces of subdata; a first nonlinear transformation part ( ) which nonlinearly transforms those pieces of subdata, respectively; a second key-dependent linear transformation part ( ) which linearly transforms those nonlinearly transformed outputs based on a subkey and outputs n pieces of transformed subdata; a second nonlinear transformation part ( ) which nonlinearly transforms those transformed subdata; and a combining part ( ) which combines the nonlinearly transformed outputs. An n&times;n matrix, which represents the linear transformation in the second key-dependent linear transformation part ( ), is formed by n vectors whose Hamming weights are equal to or larger than T&minus;1 for a security threshold T, thereby increasing the invulnerability against differential cryptanalysis and linear cryptanalysis.

Data converter and recording medium on which program for executing data conversion is recorded

A scheme for arithmetic operations in finite field and group operations over elliptic curves capable of realizing a very fast implementation. According to this scheme, by using a normal basis &lsqb;&agr; &agr;&plus;1&rsqb;, the multiplicative inverse calculation and the multiplication in the finite field GF(2,) can be realized as combinations of multiplications, additions and a multiplicative inverse calculation in the subfield GF(2,). Also, by using a standard basis &lsqb;1 &agr;&rsqb;, the multiplication, the square calculation, and the multiplicative inverse calculation in the finite field GF(2,) can be realized as combinations of multiplications, additions and a multiplicative inverse calculation in the subfield GF(2,). These arithmetic operations can be utilized for calculating rational expressions expressing group operations over elliptic curves that are used in information security techniques such as elliptic curve cryptosystems.

Scheme for arithmetic operations in finite field and group operations over elliptic curves realizing improved computational speed

Upon receiving a message &lcub;ID&prime;,, X&prime;,, m&prime;,, Y,&rcub; from a signer (i&minus;1), a signer,generates a random number r,, then calculates X,&equals;g,mod p using pieces of public information p, q and g, then sets X&prime;,&equals;(X&prime;,, X,), m&prime;,&equals;(m&prime;,, m,), then calculates e,&equals;f,(X&prime;,, m&prime;,), d,&equals;h,(X&prime;,, m&prime;,) with public one-way functions f,and h,, calculates y,&equals;(y,&plus;d,r,&plus;e,s,) mod q using a secret random number s,, sets ID&prime;,&equals;(ID&prime;,, ID,), and sends information &lcub;ID&prime;,,X&prime;,,m&prime;,,y&prime;,&rcub; to the next signer (i&plus;1). A verifier calculates e,and d,with the one-way functions f,and h,using X&prime;,and m&prime;,contained in received information &lcub;ID&prime;,, X&prime;,, m&prime;,, y,&rcub;, and makes a check to see if g,&equiv;X,I,. . . X,I,(mod p), thereby verifying signatures of the signers en bloc.

Method and apparatus for en-bloc verification of plural digital signatures and recording medium with the method recorded thereon

A scheme for arithmetic operations in finite field and group operations over elliptic curves capable of realizing a very fast implementation. According to this scheme, by using a normal basis [.alpha. .alpha.+1], the multiplicative inverse calculation and the multiplication in the finite field GF(2.sup.2n) can be realized as combinations of multiplications, additions and a multiplicative inverse calculation in the subfield GF(2.sup.n). Also, by using a standard basis [1.alpha.], the multiplication, the square calculation, and the multiplicative inverse calculation in the finite field GF(2.sup.2n) can be realized as combinations of multiplications, additions and a multiplicative inverse calculation in the subfield GF(2.sup.n). These arithmetic operations can be utilized for calculating rational expressions expressing group operations over elliptic curves that are used in information security techniques such as elliptic curve cryptosystems.

Scheme for arithmetic operations in finite field and group operations

In an electronic cash implementing method using a trustee, a user registers his identification information ID.sub.U and anonymous public key N with the trustee and receives a license (B,I). The user processes the license (B,I) by a public key corresponding to the amount to be issued and sends the processed information to a bank to have it attach a blind signature to the information so that the user obtain electronic cash C from the blind signature. The user transmits to a shop the information B,I,C,N and a digital signature that assures the divisional use of the electronic cash. The shop verifies the validity of the information B and C and accepts it as cash and sends a history H of communication with the user to the bank and receives a payment therefrom. The bank places all received communication histories under its supervision and makes a check to see if the amount x spent by the electronic cash C is in excess of its face value X, and if so, informs the trustee of the information N contained in the communication history. The trustee uses the information ID.sub.U thus received to specify the corresponding user identification information ID.sub.U.

Electronic cash implementing method using a trustee

In a method for implementing traceable electronic cash, a user US sends a bank BK a product N of prime numbers P and Q, a prime number L and his real name ID.sub.U, and the bank BK generates a pseudonym I corresponding to the real name ID.sub.U and keeps the correspondence between the real name ID.sub.U and the pseudonym I secret. The bank BK uses a signature function .OMEGA.=D.sub.eB (N,L,I) to attach a signature to information composed of the above-mentioned N, L and I and sends the user US the signed information .OMEGA. as information containing a license B. The user US generates authentication information X from the N and a random number R and sends the bank BK information Z obtained by performing blind signature preprocessing on information (X,B) with a function F.sub.eC and has the information Z signed by the bank BK with a signature function D.sub.eC (Z) to obtain electronic cash C. When the user US abuses the electronic cash C, the bank BK follows a court order to reveal the correspondence between the real name ID.sub.U and pseudo name of the user US and trace the electronic cash spent.

Method and apparatus for implementing traceable electronic cash

In an electronic cash system, K sets of blind signature information are derived from secret information containing identification information of a user, K/2 sets of them are opened and a bank attaches a blind signature to the remaining K/2 sets of information. The user obtains a signed license from the blind signature. The user generates blind signature information from the license and a desired amount of money and gets a blind signature of the bank to the blind signature information and obtains electronic cash signed by the bank from the blind signature. The user presents to a shop a residue power root of a node in a money hierarchial structure and the electronic cash, corresponding to the amount of money to be used, and the shop verifies their validity and, if they are valid, offers inquiry information to the user. The user offers, as response information, a residue power root of the node corresponding to the amount of money to be used to the shop. The shop verifies the validity of the response information and, if it is valid, acknowledges the payment with electronic cash of the amount of money to be used.

Electronic cash system

In an electronic cash implementing method, a user makes a bank apply a blind signature to user information Vi produced, by a one-way function, from secret information Si containing identification information, thereby obtaining signed user information. Further, the user makes the bank apply a blind signature to information containing authentication information Xi produced, by a one-way function, from random information Ri, thereby obtaining signed authentication information. The user uses an information group containing the signed user information, the signed authentication information, the user information and the authentication information, as electronic cash for payment to a shop. The shop verifies the validity of the signed user information and the signed authentication information, and produces and sends to the user an inquiry. In response to the inquiry the user produces a response Yi by using secret information and random information and sends it to the shop. Having verified the validity of the response the shop accepts the electronic cash.

Method and apparatus for implementing electronic cash

In the case where a prover A proves the validity of a pretender B to a verifier C, B receives an initial response x' created by A, randomizes it with a random component and sends it as x', and randomizes an inquiry .beta. from C with the random component and sends it as .beta.' to A. A proves, for the received randomized inquiry .beta.', the validity of B by a secret key s randomized with a random number r and then sends it as a proved response z to B. B removes the random component from the proved response z and sends it as A's proof to C for verification. B keeps secret the procedures for randomizing the initial response x' and the inquiry, thereby maintaining secret the correlation between A-B interactions (x', .beta.', z) nand B-C interactions (x', .beta., z'). In the case of proving the validity of a message m of a signature client B to the verifier C by attaching a signature of A to the message m, B receives an initial response x' created by A and randomizes it with a random component to create a randomized response x', creates a randomized inquiry .beta.' containing a random component by use of the randomized response x' and the message m, and sends the randomized inqiury .beta.' to A. A proves, for the randomized inqiury .beta.', its validity by a secret key s randomized with a random number r and then sends it as a proved response z to B. B removes the random component from the proved response z to create a derandomized response z', which is sent to C for verification.

Growing community of inventors

Zushi, Japan

Kazuo Ohta