**New
type public key cryptography , digital signature by higher order
equations and symmetric expressions **

**(Countering
the realization of quantum computer) **

I have
developed a new type of public key cryptosystem that is considered to
be
able to counter the realization of quantum computers by using
symmetric expressions expressed by basic symmetric formulas. Elgama
encryption type public key cryptography (Diffie-Hellman key sharing),
also supports digital signature. Depending on the difficulty of some
kind of discrete logarithm problem, difficulty of solving
multi-order multivariable equations is added. The bit number of
this encryption key and the time taken for encryption / decryption are
somewhat larger than RSA encryption and Elgama encryption, and it is a
practical encryption. The realization of the quantum computer was
thought to be decades later, but there is a possibility that it will be
realized several years later due to rapid technological progress. We
think that this cryptosystem is the most appropriate public key
cryptography when quantum computer is realized.

Also, in case of this cryptosystem, especially in the case of quadratic
expression, it is not prime number, it is not prime number, it can
not decompose prime factor of N = pq constructed on the residue
type modulo large number of synthesis Λ not solve the
discrete logarithm problem The following ciphers can be proved.
However, although it can not compete with quantum computer, it
is "the
world's fastest public key cryptography" . **Chebyshev2.pdf**

**Public
key cryptography based on higher order equations and symmetric
expressions (higher-order symmetric cryptography) **

The n th order equation on modulo K

x^{n}|Π_{1}x^{n
|1}{Π_{2}x^{n|2}|Π_{3}x^{n|3}{c{
(|1)^{n|1}Π_{n|1}x{(|1)^{n}Π_{n}0
c@

. Let Ώ _{1} , Ώ _{2} , Ώ _{3} ,
..., Ώ _{n }denote the
solution of @ in the extension field of
body K according to this equation, then @

(x - Ώ _{1} ) (x - Ώ _{2} ) (x - Ώ
_{3} )
··· (x - Ώ _{n} ) = 0

Π_{1}
, Π_{2} , Π_{3} , ..., Π_{n}
are basic symmetric equations of Ώ_{1} , Ώ_{2} , Ώ_{3}
, ..., Ώ_{n} .

Here, when the coefficient of x ^{n} is 1 and an n th degree
equation having Ώ _{1} ^{p} , Ώ _{2} ^{p}
, Ώ _{3} ^{p} , ..., Ώ _{n} ^{p} as
a solution

(x - Ώ _{1} ^{p} ) (x - Ώ _{2}
^{p}
) (x - Ώ _{2} ^{p} ) · · · (x - Ώ _{n} ^{p}
) = 0

Let f _{p} (x) be the expansion expression on the left side of

Since the coefficients of the polynomial f _{p} (x) are basic
symmetric equations of Ώ _{1} ^{p} , Ώ _{2} ^{p}
, Ώ _{3} ^{p} , ..., Ώ _{n} ^{p} ,
symmetric equations of Ώ _{1} , Ώ _{2} , Ώ _{3}
, ..., Ώ _{n} Therefore, it can be represented by Π _{1}
, Π _{2} , Π _{3} , ..., Π _{n - 1} , Π _{n}
.

Therefore, let p and q be natural numbers different from f _{1}
(x)

f _{p} (x) and f _{q} (x)

Are required.

Considering f _{pq} (x), the coefficient is a basic symmetric
expression of Ώ _{1} ^{pq} , Ώ _{2} ^{pq}
, Ώ _{3} ^{pq} , ..., Ώ _{n} ^{pq}
, so Ώ _{1} ^{p} , Ώ _{2} ^{p} , Ώ _{3}
^{p} , ..., Ώ _{n} ^{p} , so the coefficients
of f _{pq} (x) can be expressed as coefficients of f _{p}
(x).

Similarly, the coefficient of f _{pq} (x) can be expressed by
the coefficient of f _{q} (x). That is

You can find from f _{p}
(x) and q to f _{pq} (x) , from f _{q} (x) and p
.to f _{pq} (x)

As a result, the sender and receiver can share the
polynomial f _{pq} (x), and the Elgamal encryption type
public key cryptography (Diffie-Hellman key sharing) can be configured.

At the time of implementation, n is a prime number of 3 or more, and
the constant term (-1) ^{n} Π _{n} is -1. At this
time, the constant term of f _{p} (x) is always -1.

Also, take the values of Π _{1} , Π _{2} , Π _{3}
, ... Π _{n} so that @ does not have a solution on body K.
Even in this case, if we consider the extension field, @ always has
solutions Ώ _{1} , Ώ _{2} , Ώ _{3} , ..., Ώ _{n}
.

The problem in implementing the above cryptography is to obtain f _{p}
(x) from f _{1} (x) at high speed, but there was actually a
high speed algorithm and it could be implemented.

Let Ώ be one of the solutions of @

Ώ^{n}|Π_{1}Ώ^{n|1}{Π_{2}Ώ^{n
|2}|Π_{3}Ώ^{n|3}{c{(|1)^{n|1}Π_{n|1}Ώ
{(|1)^{n}Π_{n}0

If you deform by multiplying both sides by Ώ ^{k - n}

(- 1) ^{n - 1} Π _{n - 1} Ώ - (- 1) ^{n} Π _{n}
Ώ ^{k - n} (1) where Ώ ^{k}
= Π _{1}
Ώ ^{k - 1} - Π _{2} Ώ ^{k -2} + Π _{3}
Ώ ^{k - 3} - A

Is satisfied. If A is repeatedly used, Ώ ^{p} is represented
by Ώ ^{0} , Ώ ^{1} , Ώ ^{2} , ..., Ώ ^{n-1}
for any natural number p.

That is, for any natural number p, Ώ ^{p} is

Ώ ^{p} = t _{1} Ώ ^{n -1} + t _{2}
Ώ ^{n - 2} + t _{3} Ώ ^{n - 3} + ... + t _{n
- 1} Ώ + t _{n} ... B

, And the coefficients t _{1} , t _{2} , t _{3}
,..., T _{n-1} , t _{n} on the right side can be
obtained.

Since it is too late to find practically anything if Ώ ^{p} is
sequentially found for Ώ ^{n + 1} , Ώ ^{n + 2} , Ώ ^{n
+ 3} , ..., Ώ p for a huge natural number p, binary Method is
used.

If Ώ ^{k} is represented by Ώ ^{0}
, Ώ ^{1}
, Ώ ^{2} , ..., Ώ ^{n -1} , Ώ ^{k + 1} = Ώ ^{k}
· Ώ and Ώ ^{2 k} = (Ώ ^{k} ) ^{2} are also Ώ
^{0} , Ώ ^{1} , Ώ ^{2} , ..., Ώ ^{n - 1}
, so Ώ ^{k} can be represented by Ώ ^{0} , Ώ ^{1}
, Ώ ^{2} , ..., Ώ ^{n - 1} for arbitrary k by the
binary method.

Therefore, t _{1} , t _{2} , t _{3} , ..., t
_{n - 1} , t _{n} of B can be found at high speed.

next,

S _{p} = Ώ _{1} ^{p} + Ώ _{2} ^{p}
+ ... + Ώ _{n} ^{p}

. S _{p} is a symmetric expression for Ώ _{1} , Ώ _{2}
, ..., Ώ _{n} . I want to find S _{p} .

In Ώ of B, Ώ _{1} , Ώ
_{2} , Ώ _{3}
, ..., Ώ _{n} Substitute and add

S _{p} = t _{1} S _{n -1} + t _{2}
S _{n -2} + t _{3} S _{n -3} + ... + t _{n
-1} S _{1} + t _{n} S _{0}

, The values of S _{0} , S _{1} , S _{2} ,
S _{3} , ..., S _{n-1} and t _{1} , t _{2}
, t _{3} , ..., t _{n -1} , t _{n on} the
right side of this equation By substituting the value, the value of S _{p}
can be obtained.

Furthermore, if B is raised to the second power, the third power, ...

Ώ ^{p} , Ώ 2 ^{p} , Ώ ^{3 p} , ..., Ώ ^{np}

Can also be represented by a linear combination of Ώ ^{0} , Ώ ^{1}
, Ώ ^{2} , ..., Ώ ^{n-1} and its coefficients can
also be obtained, so S _{p} , S 2 _{p} , S _{3 p}
, ..., S _{np} Is required. From the above

Π _{1} , Π _{2} , Π _{3} , ...,
Π _{n - 1} , Π _{n} and S _{0} ,
S _{1} , S _{2} , S _{3} , ..., S _{n
- 1} , The values of
S_{ p} , S_{ 2p} , S_{ 3p} , ..., S_{ np}
can be obtained at high speed.....C

In addition, the following Newton's
formula for mutually transforming the basic symmetric expression Π _{k}
(1 ≤ k ≤ n) and the symmetric equation S _{k} = Ώ
_{1} ^{k} + Ώ
_{2} ^{k} +
... + Ώ _{n} ^{k} (1
k
n) Algorithm) is used.

Algorithm for finding a power sum from a basic symmetric expression

S _{1} = Π _{1}

S _{2} = Π _{1} S _{1} - _{2} Π _{2}

S _{3} = Π _{1} S _{2} - Π _{2} S _{1}
+ _{3} Π _{3}

..................

S _{n} = Π _{1} S _{n -1 -} Π _{2}
S _{n - 2} + ... + (- 1) ^{n} Π _{n - 1} S _{1}
+ (- 1) ^{n + 1} nΠ _{n}

Furthermore, when k n

S _{k} = Π _{1} S _{k -1} Π _{2} S _{k
- 2} + ... + (-1) ^{n} Π _{n - 1} S _{k - n
+ 1} + (- 1) ^{n + 1} Π _{n} S _{k - n}
© Sequence {S _{k} } Can be considered to be
defined by this recurrence formula with S
_{1} , S _{2} , S _{3} , ..., S _{n}

An algorithm for finding a basic symmetric expression from a power sum

Π _{1} = S _{1}

Π _{2} = - (S _{2} - Π _{1} S _{1}
) · 2 ^{-1}

Π _{3} = (S _{3} - Π _{1} S _{2} +
Π _{2} S _{1} ) · 3 ^{-1}

..................

Π _{n} = (- 1) ^{n + 1} {S _{n} - Π _{1}
S _{n - 1} + Π _{2} S _{n - 2} - ... + (- 1)
^{n - 1} Π _{n - 1} S _{1} }

By using this algorithm, the other is
obtained from one of Π_{k} (k = 1, 2, 3, ..., n) and S_{k}
(k
= 1, 2, 3, ..., n).

Therefore, the coefficient of x ^{nk} in the
expansion
expression on the left side of (x - Ώ _{1} ^{p} ) (x
- Ώ _{2} ^{p} ) (x - Ώ _{2} ^{p} )
··· (x - Ώ _{n} ^{p} ) = 0 is Π (p, k), then

Π_{1}CΠ_{2}CΠ_{3}CcC Π_{n} ¨@S_{1}CS_{2}CS_{3}CcCS_{n} @¨@S_{p}CS_{2p}CS_{3p}CcCS_{np}@¨@Π(pC1)CΠ(pC2)CΠ(pC3)CcCΠ(pCn)_{}_{}_{}**
**Can be obtained.

Therefore, Π (p, 1) , Π (p, 2) , Π (p, 3) Letting Π (p) be the set of Π (p, n) numbers

Let p and q be huge natural numbers,

Π (pq) is obtained from both Π (p) and Π (q)

As a result, Elgamal cryptography can be constructed as follows. (It will become extremely fast if the magnitude of p and q below is kept at about the same 128 bit as common key encryption.)

(1) Let s = Π (1) and t = Π (p) be the recipient's public key. p is the secret key.

(2) The sender selects a secret random number q for the document M, calculates Α = Π (q) from s and Π (pq) from t.

The document M is encrypted with common key encryption with Π (pq) as a key.

Send the encrypted document and Α = Π (q) to the recipient.

(3) The recipient calculates Π (pq) from Α = Π (q) and secret key p, and decrypts the document with Π (pq) as a key.

Here, t

The usual Elgamal ciphers are t

Difficulty degree for finding t

Equatiok.pdf also describes the proof of the Frame method, which is an algorithm for finding the inherent polynomial of a matrix using Newton's official proof and Newton's formula. Please see equatiok.pdf for details.

**Digital
signature in higher order symmetric cryptography **

For an a _{2} , a _{3} , ..., a _{n}
and b _{1} , b _{2} , b _{3} , ..., b _{n}
, an identity of the n ^{2} degree polynomial of x (n is a
prime number at the time of implementation, n is an odd number of 3 or
more)

(x|a_{1}b_{1})E
(x| a_{1}b_{2})E (x|a_{1}b_{3})EcE(x|a_{1}b_{n})E
(x|a_{2}b_{1})E (x|a_{2}b_{2})E(x|a_{2}b_{3})EcE
(x|a_{2}b_{n})EcE (x|a_{n}b_{n})

x^{n^2}|ia_{1}{a_{2}{a_{3}{c
{a_{n})ib_{1}{b_{2}{b_{3}{c{b_{n})x^{n^2
|1}{(a_{1}^{2}b_{1}b_{2}{a_{1}^{2}b_{1}b_{3}{a_{1}^{2}b_{1}b_{4}{c
{a_{n}^{2}b_{n|1}b_{n})x^{n^2|2}{c
|(a_{1}a_{2}a_{3}ca_{n}b_{1}b_{2}b_{3}cb_{n})^{n}c@

think of.

coefficient is a
basic symmetric expression of a_{1}b_{1}Ca_{1}b_{2}Ca_{1}b_{3}CcC
a_{1}b_{n}Ca_{2}b_{1}Ca_{2}b_{2}Ca_{2}b_{3}CcC
a_{2}b_{n}CcCa_{n}b_{n}

T_{k}(a_{1}b_{1})^{k}{(a_{1}b_{2})^{k}{(a_{1}b_{3})^{k}{c
{(a_{1}b_{n})^{k}{(a_{2}b_{1})^{k}{(a_{2}b_{2})^{k}{(a_{2}b_{3})^{k}{c
{(a_{2}b_{n})^{k}{c {(a_{n}b_{n})^{k}

. Deformed

T _{k} = (a _{1} ^{k} + a
_{2} ^{k}
+ a _{3} ^{k} + ... + an ^{k} ) (b _{1}
^{k} + b _{2} ^{k} + b _{3} ^{k}
+ ... + b _{n} ^{k} )

Here, using the Newton's algorithm, all the coefficients of the
polynomial @ are represented by T _{k} (k = 1, 2, 3, ..., n ^{2}
), T _{k} is represented by a _{1} , a _{2}
, a _{3} , is represented by the basic symmetric expression of
a _{n} and b _{1} , b _{2} , b _{3}
, ..., b _{n} . The computational complexity for obtaining the
coefficients of polynomial @ from a _{1} , a _{2} , a
_{3} , ..., a _{n} and b _{1} , b _{2}
, b _{3} , ..., b _{n from} the basic symmetry
formula is O (n ^{4} ).

If the coefficient of x ^{k} in @ is (-1) ^{k} A _{n
^ 2 - k} , the right side of @ is

x^{n^2}|A_{1}x^{n^2
|1}{A_{2}x^{n^2|2}{c|A_{n^2}cA

. However, A _{k} are all represented by T _{k} .

The left side of @

(x - a _{1} b _{1} ) · (x - a _{2}
b _{2}
) · (x - a _{3} b _{3} ) · · · (x - a_{n} b _{n}
)

As a factor. Expand this to

x ^{n }= B _{1} x ^{n - 1}
+ B _{2}
x ^{n - 2} + ... - B _{n} ... B

. At this time, A is divisible by B.

In particular, if a _{k} = Ώ _{k}
^{p} , b _{k} = Ώ _{k}
^{q} then a _{k} b _{k}
= Ώ _{k} ^{p + q} (k = 1, 2,
3,.....,n)^{
}So, A can also be divisible by B.

This method is shown.

Digital signature 1 (It is fast for signature 2, signature length is
short, added on March 23, 2015)

(1) Let g = Π (1) and t = Π (p) be the
sender 's public key. p is the secret key.

(2) The sender obtains the hash value e = h (M) of the document M for
the document M and further obtains Ι = Π (p + e).

Ι is the signature of M. (For safety, pad document M)

At this time, the formula (2) made from Π (p) and Π (e)
is Ι = Π (p + e).

The sender sends the document M and its signature Ι .

(3) The receiver calculates the hash value e = h (M ).

Furthermore, Π (e) is obtained from g and e, Then,
Create A from Π (e) and t .

At this time, if we change equation (2) to Ι If the remainder
obtained by dividing it by equation (3) becomes 0, it is considered
that the signature of document M has been confirmed.

Digital signature 2 ( Elgamal
signature or modified digital signature of Schnorr signature )
(Algorithm was revised on June 25, 2011)

(1) Let g = Π (1) and t = Π (p) be the
sender 's public key. p is the secret key.

(2) The sender selects a secret random number q for the document M and
performs the following calculation.

Α = Π (q)

e = h (M, Α) (Hash value of document combining document M and Α)

Β = q-pe

At this time, since pe + Β = q, The formula (2) made from Π
(pe) and Π (Β) is divisible by B by Α = Π (q).

The sender sends the document M and its signature ( Α , Β) to
the recipient.

(3) The receiver obtains the hash value e = h (M, Α ).

Furthermore, Π (Β) is obtained from Π (pe), g
and Β from t and e, Create A from Π (pe) and Π
(Β).

At this time, if the remainder obtained by dividing equation (2) by
equation (3) by Α becomes 0, it is considered that the
signature of document M was confirmed.

Note n is a prime number of 3 or more, and the constant term (-1) ^{n}
Π _{n} is -1.

Equation x ^{n} - Π _{1} x ^{n -1} + Π
_{2}
x ^{n - 2} - Π _{3} x ^{n - 3} + ... + (- 1)
^{n - 1} Π _{n - 1} x - 1 = 0

Dividing both sides by x^{n} and placing 1/x = t

t ^{n} _{- 1} t ^{n -1} +
Π _{n - 2}
t ^{n - 2} - Π _{n - 3} t ^{n - 3} + ... +
(- 1) ^{n - 1} Π _{1} t - 1 = 0

The order of the original equations and coefficients is reversed.

Therefore, in Newton's algorithm, Π _{0} , Π _{1} , Π
_{2} , ..., Π _{n -1} , Π _{n} are replaced
with Π _{n} , Π _{n} _{-1} , Π _{n
-2},....., Π _{1} , Π _{0} and
S _{1} , S _{2}
, S _{3} , ... are replaced by S _{-1} , S _{-2}
, S _{-3} , ... holds. For calculation of Π _{n -1} ,
Π _{n -2} , ... Π _{(n + 1) / 2} , the calculation
amount is about 1/2 in the
digital signature and it can be parallelized.
Therefore, It can be halved further.

Features
of higher-order symmetric cryptography

- This
cipher is a set of the number of prime fields K = Π = (Π
_{1}, Π_{2}, Π_{3}, ..., Π_{n - 1}) and a set of natural numbers p to number (Π_{1, p}, Π_{2, p}, Π_{3 , p}, ..., Π_{n - 1, p}). At this time f ( Π , p), q) = f ( Π , pq) holds but f ( Π , p + q) can not be found from f ( Π , p) and f ( Π , p) Hmm. Therefore, Elgamal cipher (Diffie - Hellman key sharing) can be configured, but efficient cryptanalysis for ordinary Elgamal cipher is ineffective. Furthermore, it is considered to be resistant to quantum computers. - Since
postprocessing is added after calculation of exponents similar to
Elgamal cryptosystem, encryption becomes slightly slower if it is the
same bit length as compared with normal Elgamal cryptosystem.
- The
computational complexity is O (n
^{3}) in a simple method in the case of nth order equation. Therefore, the total calculation amount is O (bit number^{3}). - In the
case of the nth order equation, the number of bits of the key is about
n - 1 times the number of bits of the body to be implemented.
- In
order to solve this cipher efficiently, it seems to be necessary to
solve a multi-order multivariable equation, so it is considered to be
multi-order
multivariable public key cryptosystem . However, for safety, it is
better to set n to 100 or more.
- The
signature length of the digital signature 1 is the same as the public
key length, and the signature length of the digital signature 2 is
longer than the public key length. Also, there are O (n
^{3}) and O (n^{4}) parts in the calculation, but the coefficients of O (n^{4}) are small, so if n is around 100 it will be fast enough. - We have
not applied for patents, so the algorithm is free to use.

Higher
order symmetric cryptography and its digital signature were implemented
in the case of 13 bit ~ 103 order equation.

- Explanation
of creation of public key cryptography by higher order equations equation.pdf
- Implementation
example of encryption in the case of 13 bit ~ 103 degree equation
Equation.c multi.c
© multi.c must be changed to multi.h and be included
- Digital
signature 2 implementation example signature.c
Please change multi.c
© multi.c to multi.h and include it
- A
program "decimal BASIC" that finds prime numbers necessary for this cryption
equationprime.bas

Below
is the cubic expression up to which we came up with the above cipher.
It remains for the sake of reference only.

- Explanation
of encryption · digital signature when extending Chebyshev polynomial Chebyshev.pdf
- Example
of implementation of encryption when extending Chebyshev polynomial Chebyshev
127.c
- Implementation
example of encryption in the case of cubic equation with equation of
higher order equation125.c

I think that this cipher can only be solved in exponential time. This
is the "world's strongest public-key cryptosystem" which is
thought to survive when the quantum computer realizes, RSA cipher,
Elgamal cipher, elliptic curve cryptograpy is destroyed.

There is also vulnerability in "CAB method cipher" which claimed that
"cryptanalysis was proved mathematically proved" also in "Sarah's
cipher" famous for his book "The world's strongest cipher challenged by
16-year-old Sarah". did. Sarah.pdf
CAB.pdf

There is a possibility of this vulnerability also in this cipher. Those
who have found mistakes or defects in theory or implementation, those
who think that it is not the world's strongest public key cryptosystem,
those who think that such ciphers can be easily solved should be
informed by e-mail.

(E-mail address is an image for anti-spam measures.)