Common secret key generation device, encryption device, decryption device, common secret key generation method, encryption method, decryption method, and program

A decryption device, comprising:

• a processor;
• and
• memory storing instructions executable by the processor, wherein execution of the instructions by the processor causes the decryption device to:
• set public data including a prime number p, a natural number d, a d×d matrix Q (mod p) with determinant equal to 1, and a d×d matrix S (mod p) for which an inverse matrix exists;
• generate a secret key including natural numbers nA (mod p), kA (mod p);
• employ the secret key to calculate a d×d matrix MA (mod p) according to MA =S−kAQnASkA, and transmit the matrix MA to a communication partner;
• acquire a d×d matrix MB (mod p), calculated by employing natural numbers nB (mod p), kB (mod p) included in a secret key of the communication partner according to MB=S−kBQnBSkB;
• and
• compute a d×d matrix MAB (mod p) as a common secret key employing the matrix MB according to MAB =S−kAMBnASkA;
• generate two non-commutative matrices A1, A2, based on the common secret key MABand two prime numbers p1, p2, that are set in common with an encryption device;
• iteratively derive:
• a vector vi1 by operating the non-commutative matrix A1 on a d dimensional initial vector v0 set in common with the encryption device or on a d dimensional vector vi−11 that was derived in a preceding iteration, and a vector vi2 by operating the non-commutative matrix A2 on the initial vector v0 or on a d dimensional vector vi−12 that was derived in a preceding iteration, wherein at least one out of a sum calculation or a product calculation for operations of the non-commutative matrices A1, A2 is substituted into a predetermined calculation method combining a plurality of operator types, and performs operations of the non-commutative matrices A1, A2;
• and
• a bit sequence W1i by performing a non-linear transformation to transform the vector vi1 into a transformed bit sequence and by joining the transformed bit sequence to the bit sequence W1i−1 that was derived in the preceding iteration, and a bit sequence W2i by performing a non-linear transformation to transform the vector vi2 into a bit sequence and by joining the transformed bit sequence to the bit sequence W2i−1 that was derived in the preceding iteration;
• where the iterative derivation is repeated until a respective number of bits of the derived bit sequence W1i and the derived bit sequence W2i have reached a number of bits of a bit sequence expressing decryption target data;
• in response to reaching the number of bits, derive a pseudo-random number bit sequence by calculating an exclusive logical sum between the bit sequence W1i and the bit sequence W2i;
• and
• decrypt the decryption target data by calculating an exclusive logical sum between the pseudo-random number bit sequence and the bit sequence expressing the decryption target data.

A non-transitory computer readable medium storing a program causing a computer to execute a process for common secret key generation, the process comprising:

• setting public data including a prime number p, a natural number d, a d×d matrix Q (mod p) with determinant equal to 1, and a d×d matrix S (mod p) for which an inverse matrix exists;
• generating a secret key including natural numbers nA (mod p), kA (mod p);
• employing the secret key to calculate a d×d matrix MA (mod p) according to MA=S−kAQnASkA, and transmitting the matrix MA to a communication partner;
• acquiring a d×d matrix MB (mod p), calculated by employing natural numbers nB (mod p), kB (mod p) included in a secret key of the communication partner according to MB =S−kBQnBSkB;
• and
• computing a d×d matrix MAB (mod p) as a common secret key by employing the matrix MB acquired by the matrix acquisition section according to MAB=S−kAMBnASkA
• generate two non-commutative matrices A1, A2, based on the common secret key MAB and two rime numbers p1, p2 that are set in common with an encryption device;
• iteratively deriving:
• a vector vi1 by operating the non-commutative matrix A1 on a d dimensional initial vector v0 set in common with the decryption device or on a d dimensional vector vi−11 that was derived in a preceding iteration, and a vector vi2 by operating the non-commutative matrix A2 on the initial vector v0 or on a d dimensional vector vi−12 that was derived in the preceding iteration, wherein at least one out of a sum calculation or a product calculation for operations of the non-commutative matrices A1, A2 is substituted into a predetermined calculation method combining a plurality of operator types, and performs operations of the non-commutative matrices A1, A2;
• and
• a bit sequence W1i by performing a non-linear transformation to transform the vector vi1 into a transformed bit sequence and by joining the transformed bit sequence to the bit sequence W1i−1 that was derived in the preceding iteration, and a bit sequence W2i by performing a non-linear transformation to transform the vector vi2 into a bit sequence and by joining the transformed bit sequence to the bit sequence W2i−1 that was derived in the preceding iteration;
• where the iterative derivation is repeated until a respective number of bits of the derived bit sequence W1i and the derived bit sequence W2i have reached a number of bits of a bit sequence expressing encryption target data;
• in response to reaching the number of bits, deriving a pseudo-random number bit sequence by calculating an exclusive logical sum between the bit sequence W1i and the bit sequence W2i;
• and
• encrypting the encryption target data by calculating an exclusive logical sum between the pseudo-random number bit sequence and the bit sequence expressing the encryption target data.

An encryption method, comprising:

• setting public data including a prime number p, a natural number d, a d×d matrix Q (mod p) with determinant equal to 1, and a d×d matrix S (mod p) for which an inverse matrix exists;
• generating a secret key including natural numbers nA (mod p), kA (mod p);
• employing the secret key to calculate a d×d matrix MA (mod p) according to MA=S−kAQnASkA and transmits the matrix MA to a communication partner;
• acquiring a d×d matrix MB (mod p), calculated by employing natural numbers nB (mod p), kB (mod p) included in a secret key of the communication partner according to MB=S−kBQnBSkB;
• and
• computing a d×d matrix MAB (mod p) as a common secret key by employing the matrix MB acquired by the matrix acquisition section according to MAB=S−kAMBnASkA;
• generating two non-commutative matrices A1, A2, based on the common secret key MABand two prime numbers p1, p2, that are set in common with a decryption device;
• iteratively deriving:
• a vector vi1 by operating the non-commutative matrix A1 on a d dimensional initial vector v0 set in common with the decryption device or on a d dimensional vector vi −1 that was derived in a preceding iteration, and a vector vi2 by operating the non-commutative matrix A2 on the initial vector v0 or on a d dimensional vector vi−12 that was derived in a preceding iteration, wherein at least one out of a sum calculation or a product calculation for operations of the non-commutative matrices A1, A2 is substituted into a predetermined calculation method combining a plurality of operator types, and performs operations of the non-commutative matrices A1, A2;
• and
• a bit sequence W1i by performing a non-linear transformation to transform the vector vi1into a transformed bit sequence and joining the transformed bit sequence to the bit sequence W1i−1 that was derived in the preceding iteration, and a bit sequence W2i by performing a non-linear transformation to transform the vector vi2 into a bit sequence and joining the transformed bit sequence to the bit sequence W2i−1 that was derived in the preceding iteration;
• where the iterative derivation is repeated until a respective number of bits of the derived bit sequence W1i and the bit derived sequence W2i have reached a number of bits of a bit sequence expressing encryption target data;
• in response to reaching the number of bits, deriving a pseudo-random number bit sequence by calculating an exclusive logical sum between the bit sequence W1i and the bit sequence W2i;
• and
• encrypting the encryption target data by calculating an exclusive logical sum between the pseudo-random number bit sequence and the bit sequence expressing the encryption target data.

A decryption method, comprising:

• setting public data including a prime number p, a natural number d, a d×d matrix Q (mod p) with determinant equal to 1, and a d×d matrix S (mod p) for which an inverse matrix exists;
• generating a secret key including natural numbers nA (mod p), kA (mod p):
• employing the secret key to calculate a d×d matrix MA (mod p) according to MA =S−kAQnASkA and transmits the matrix MA to a communication partner:
• acquiring a d×d matrix MB (mod p), calculated by employing natural numbers nB(mod p), kB (mod p) included in a secret key of the communication partner according to MB =S−kBQnBSkB;
• and
• computing a d×d matrix MAB (mod p) as a common secret key by employing the matrix MB acquired by the matrix acquisition section according to MAB=S−kAMBnASkA;
• generating two non-commutative matrices A1, A2, based on the common secret key MABand two prime numbers p1, p2, that are set in common with an encryption device;
• iteratively deriving:
• a vector vi1 by operating the non-commutative matrix A1 on a d dimensional initial vector v0 set in common with the encryption device or on a d dimensional vector vi−1 that was derived in a preceding iteration, and a vector vi2 by operating the non-commutative matrix A2 on the initial vector v0 or on a d dimensional vector vi −12 that was derived in a preceding iteration, wherein at least one out of a sum calculation or a product calculation for operations of the non-commutative matrices A1, A2 is substituted into a predetermined calculation method combining a plurality of operator types, and performs operations of the non-commutative matrices A1, A2;
• and
• a bit sequence W1i by performing a non-linear transformation to transform the vector vi1into a transformed bit sequence and joining the transformed bit sequence to the bit sequence W1i−1 that was derived in the preceding iteration, and a bit sequence W2i by performing a non-linear transformation to transform the vector vi2 into a bit sequence and joining the transformed bit sequence to the bit sequence W2i−1 that was derived in the preceding iteration;
• where the iterative derivation is repeated until a respective number of bits of the derived bit sequence W1i and the derived bit sequence W2i have reached a number of bits of a bit sequence expressing decryption target data;
• in response to reaching the number of bits, deriving a pseudo-random number bit sequence by calculating an exclusive logical sum between the bit sequence W1 and the bit sequence W2i;
• and
• decrypting the decryption target data by calculating an exclusive logical sum between the pseudo-random number bit sequence and the bit sequence expressing the decryption target data.

A non-transitory computer readable medium storing a program causing a computer to execute a process for common secret key generation, the process comprising:

• setting public data including a prime number p, a natural number d, a d×d matrix Q (mod p) with determinant equal to 1, and a d×d matrix S (mod p) for which an inverse matrix exists;
• generating a secret key including natural numbers nA (mod p), kA (mod p);
• employing the secret key to calculate a d×d matrix MA (mod p) according to MA =S−kAQnASkA, and transmitting the matrix MA to a communication partner;
• acquiring a d×d matrix MB (mod p), calculated by employing natural numbers nB (mod p), kB (mod p) included in a secret key of the communication partner according to MB=S−kBQnBSkB;
• and
• computing a d×d matrix MAB (mod p) as a common secret key by employing the matrix MB acquired by the matrix acquisition section according to MAB =S−kAMBnASkA;
• generate two non-commutative matrices A1, A2, based on the common secret key MAB and two prime numbers p1, p2, that are set in common with an encryption device;
• iteratively deriving:
• a vector vi1 by operating the non-commutative matrix A1 on a d dimensional initial vector v0 set in common with the encryption device or on a d dimensional vector vi−11 that was derived in a preceding iteration, and a vector vi2 by operating the non-commutative matrix A2 on the initial vector v0 or on a d dimensional vector vi−12 that was derived in a preceding iteration, wherein at least one out of a sum calculation or a product calculation for operations of the non-commutative matrices A1, A2 is substituted into a predetermined calculation method combining a plurality of operator types, and performs operations of the non-commutative matrices A1, A2;
• and
• a bit sequence W1i by performing a non-linear transformation to transform the vector vi1 into a transformed bit sequence and by joining the transformed bit sequence to the bit sequence W1i−1 that was derived in the preceding iteration, and a bit sequence W2i by performing a non-linear transformation to transform the vector vi2 into a bit sequence and by joining the transformed bit sequence to the bit sequence W2i−1 that was derived in the preceding iteration;
• where the iterative derivation is repeated until a respective number of bits of the derived bit sequence W1i and the derived bit sequence W2i have reached a number of bits of a bit sequence expressing decryption target data;
• in response to reaching the number of bits, deriving a pseudo-random number bit sequence by calculating an exclusive logical sum between the bit sequence W1i and the bit sequence W2i;
• and
• decrypting the decryption target data by calculating an exclusive logical sum between the pseudo-random number bit sequence and the bit sequence expressing the decryption target data.