QUANTUM-SAFE DIGITAL SIGNATURE METHOD AND SYSTEM
A method of operating a computing apparatus, which includes receiving a signed message including a digital asset xo and a signature {F, H}. A public key associated with a private key that is unknown to the computing apparatus is received, the public key including s p , s q , p ij ′, q ij ′, μ ij and v ij i=0 to n+λ, j=1 to m, with λ, n and m being predetermined integers. Based on the signature, the public key and the digital asset, it is verified whether the following validation equation holds true: ∑ i = 0 n + λ U i j ( H ) x 0 i = ∑ i = 0 n + λ V i j ( F ) x 0 i , j = 1 to m , where U i j ( H ) = Hp ′ i j - s p ⌊ H μ i j / R ⌋ mod p V i j ( F ) = Fq ′ i j - s q ⌊ F v i j / R ⌋ mod p In case the validation equation holds true for all j=1 to m, it is concluded that the signature was derived from the digital asset and the private key, and the signature is considered authentic.
1 . A method of operating a computing apparatus for verifying authenticity of digital cryptographic communications received from a sending device over a data network, the method comprising:
receiving a signed message from the sending device, the signed message including (i) a digital asset represented by an integer x 0 and (ii) a signature, the signature including data elements represented by integers F and H;
obtaining a public key associated with a private key that is unknown to the computing apparatus, the public key including data elements represented by integers s p , s q , p ij ′, q ij ′, μ ij and v ij , i=0 to n+λ, j=1 to m, with λ, n and m being predetermined integers stored in a memory of the computing apparatus;
verifying, based on the signature, the public key and the digital asset, whether a validation equation holds true, wherein the validation equation comprises:
∑
i
=
0
n
+
λ
U
ij
(
H
)
x
0
i
=
∑
i
=
0
n
+
λ
V
ij
(
F
)
x
0
i
,
j
=
1
to
m
,
where
U
ij
(
H
)
=
Hp
′
ij
-
s
p
⌊
H
μ
ij
/
R
⌋
mod
p
V
ij
(
F
)
=
Fq
′
ij
-
s
q
⌊
Fv
ij
/
R
⌋
mod
p
;
wherein p is a predetermined integer stored in the memory of the computing apparatus and wherein R is predetermined power of 2 stored in the memory of the computing apparatus;
in case the validation equation holds true for all values of j=1 to m, concluding that the signature was derived from the digital asset and the private key, whereby the signature is considered authentic;
outputting on a network or storing in the memory of the computing apparatus an indication that the signature is considered authentic.
2 . The method of claim 1 , in case the validation equation does not holds true for at least one value of j=1 to m, concluding that the signature was not derived from the digital asset and the private key, whereby the signature is considered forged.
3 . The method of claim 1 , carried out for each digital asset forming a segment of a hashed original message.
4 . The method of claim 1 , wherein the predetermined integer p is selected to be a prime number.
5 . The method of claim 1 , wherein R is a base for a Barrett reduction algorithm and μ ij and v ij are Barrett parameters.
6 . The method of claim 5 , wherein R=2 K , where K>>log 2 n or K>>l S .
7 . The method of claim 1 , wherein the signed message further includes the public key.
8 . The method of claim 1 , further comprising obtaining the public key over the data network from the sending device.
9 . The method of claim 1 , further comprising obtaining the public key over the data network from a key generation computer.
10 . A non-transitory computer-readable medium storing computer-readable instructions which, when read and executed by at least one processing unit associated with a computing apparatus, cause the processing unit to carry out the method of claim 1 .
11 . A computing apparatus, comprising:
a memory storing computer-readable instructions;
a processor coupled to the memory and configured to read and execute the computer-readable instructions to carry out a method for verifying authenticity of digital cryptographic communications received from a sending device over a data network, the method comprising:
receiving a signed message from the sending device, the signed message including (i) a digital asset represented by an integer x 0 and (ii) a signature, the signature including data elements represented by integers F and H;
obtaining a public key associated with a private key that is unknown to the computing apparatus, the public key including data elements represented by integers s p , s q , p ij ′, q ij ′, μ ij and v ij , i=0 to n+λ, j=1 to m, with λ, n and m being predetermined integers stored in a memory of the computing apparatus;
verifying, based on the signature, the public key and the digital asset, whether a validation equation holds true, wherein the validation equation comprises:
∑
i
=
0
n
+
λ
U
ij
(
H
)
x
0
i
=
∑
i
=
0
n
+
λ
V
ij
(
F
)
x
0
i
,
j
=
1
to
m
,
where
U
ij
(
H
)
=
Hp
′
ij
-
s
p
⌊
H
μ
ij
/
R
⌋
mod
p
V
ij
(
F
)
=
Fq
′
ij
-
s
q
⌊
Fv
ij
/
R
⌋
mod
p
;
wherein p is a predetermined integer stored in the memory of the computing apparatus and wherein R is predetermined power of 2 stored in the memory of the computing apparatus;
in case the validation equation holds true for all values of j=1 to m, concluding that the signature was derived from the digital asset and the private key, whereby the signature is considered authentic;
outputting on a network or storing in the memory of the computing apparatus an indication that the signature is considered authentic.
12 . A method of operating a computing apparatus for transmitting cryptographic communications to a verification device over a data network, the method comprising:
obtaining a digital asset x 0 ;
selecting a variable a belonging to a finite field GF p , wherein p is a predetermined integer stored in a memory of the computing apparatus;
computing a signature that includes the data elements F and H, where:
F
=
R
q
-
1
×
[
α
f
(
x
0
)
mod
p
]
mod
S
q
H
=
R
p
-
1
×
[
α
h
(
x
0
)
mod
p
]
mod
S
p
,
wherein
f(·) is a first polynomial;
h(·) is a second polynomial;
R p and S p are a first co-prime pair; and
R q and S q are a second co-prime pair; and
transmitting a signed message to the second computing apparatus over a communication channel, wherein the signed message includes the digital asset x 0 and the signature.
13 . The method defined in claim 12 , wherein the signature is a lossless combination of data elements F and H.
14 . The method defined in claim 12 , wherein the signature is authenticated by:
obtaining a public key that includes data elements represented by integers s p , s q , p ij ′, q ij ′, μ ij and v ij , i=0 to n+λ, j=1 to m; and
verifying whether a validation equation holds true, wherein the validation equation comprises:
∑
i
=
0
n
+
λ
U
ij
(
H
)
x
0
i
=
∑
i
=
0
n
+
λ
V
ij
(
F
)
x
0
i
,
j
=
1
to
m
,
where
U
ij
(
H
)
=
Hp
′
ij
-
s
p
⌊
H
μ
ij
/
R
⌋
mod
p
V
ij
(
F
)
=
Fq
′
ij
-
s
q
⌊
Fv
ij
/
R
⌋
mod
p
;
wherein λ, n and m are predetermined integers and R is predetermined power of 2;
and wherein the signature is considered authentic in case the validation equation holds true for all values of j=1 to m.
15 . The method defined in claim 12 ,
wherein f(·), h(·), R p , S p , R q and S q are elements of a private key;
wherein the signature is authenticated by obtaining a public key associated with the private key and verifying whether a validation equation involving the digital asset, the signature and the public key holds true.
16 . The method of claim 15 , further comprising sending the public key together with the digital asset and the signature.
17 . The method of claim 15 , carried out for each digital asset forming a segment of a hashed original message.
18 . The method of claim 15 , further comprising withholding the private key from the verification device.
19 . The method of claim 12 , wherein the bit length of x, does not exceed the bit length of p and p is prime.
20 . The method of claim 12 , wherein the variable a is arbitrarily selected in the finite field GF p .
21 . The method of claim 12 , wherein the first polynomial function f(·) and the second polynomial function h(·) each have an order of 3 or less.
22 . A non-transitory computer-readable medium storing computer-readable instructions which, when read and executed by at least one processing unit associated with a computing apparatus, cause the processing unit to carry out the method of claim 12 .
23 . A computing apparatus, comprising:
a memory storing computer-readable instructions;
a processor coupled to the memory and configured to read and execute the computer-readable instructions to carry out a method for transmitting cryptographic communications to a verification device over a data network, the method comprising:
obtaining a digital asset xo;
selecting a variable α belonging to a finite field GF p , wherein p is a predetermined integer stored in a memory of the computing apparatus;
computing a signature that includes the data elements F and H, where:
F
=
R
q
-
1
×
[
α
f
(
x
0
)
mod
p
]
mod
S
q
H
=
R
p
-
1
×
[
α
h
(
x
0
)
mod
p
]
mod
S
p
,
wherein
f(·) is a first polynomial;
h(·) is a second polynomial;
R p and S p are a first co-prime pair; and
R q and S q are a second co-prime pair; and
transmitting a signed message to the second computing apparatus over a communication channel, wherein the signed message includes the digital asset x 0 and the signature.
24 . A process for operating a computing apparatus to generate a private-public key pair, the private key for use in a signing process for creating a signed message from a digital asset, the signed message including the digital asset and a signature, and the public key for use in a verification process for authenticating the signature based on the public key, the signature and the digital asset, the process comprising:
a) selecting coefficients of a multivariate base polynomial B(x 0 , x 1 , . . . , x m ) of order n for x 0 , where n and m are selected integers stored in the memory of the computing apparatus;
b) selecting polynomials f(·) and h(·) of degree λ, where λ is a selected integer stored in the memory of the computing apparatus;
c) constructing a pair of polynomials, p(x 0 , x 1 , . . . , x m ) and q(x 0 , x 1 , . . . , x m ), by multiplying the base polynomial B(x 0 , x 1 , . . . , x m ) with the polynomials f(·) and h(·), respectively:
p
(
x
0
,
x
1
,
...
,
x
m
)
=
B
(
x
0
,
x
1
,
...
,
x
m
)
f
(
x
0
)
=
∑
j
=
1
m
p
j
(
x
0
)
x
j
q
(
x
0
,
x
1
,
...
,
x
m
)
=
B
(
x
0
,
x
1
,
...
,
x
m
)
h
(
x
0
)
=
∑
j
=
1
m
q
j
(
x
0
)
x
j
where
p
j
(
x
0
)
=
∑
i
=
0
n
+
λ
p
ij
x
0
i
and
q
j
(
x
0
)
=
∑
i
=
0
n
+
λ
q
ij
x
0
i
such that p ij and q ij are defined as follows:
p
ij
=
∑
s
+
t
=
i
f
s
b
tj
q
ij
=
∑
s
+
t
=
i
h
s
b
tj
d) selecting two co-prime pairs (s p , Rp) and (s q , Rq)
e) computing the following:
P ij =R p p ij mod S p
Q ij =R q q ij mod S q
f) creating the private key as including the following data elements:
the coefficients of the polynomial f(·)
the coefficients of the polynomial h(·)
s p , s q , R p and R q
g) composing the public key as including the following data elements:
s
p
=
β
S
p
mod
p
s
q
=
β
S
q
mod
p
p
′
ij
=
β
P
ij
mod
p
q
′
ij
=
β
Q
ij
mod
p
μ
ij
=
⌊
RP
ij
S
p
⌋
v
ij
=
⌊
RQ
ij
S
q
⌋
where:
R is a power of 2, and
β is arbitrarily selected over the finite field GF(p).
25 . The process of claim 24 , wherein S p and S q are selected to have a bit length l s >=2*log 2 p+log 2 [m(n+λ+1)].
26 . The process of claim 25 , wherein R=2 K and K is selected to be >>l s .
27 . The process of claim 24 , further comprising storing the private key and the public key in memory of the computing apparatus.
28 . The process of claim 24 , further causing the private key to be securely stored in a memory of a computing device for execution of the signing process.
29 . The process of claim 28 , further causing the public key to be made available to a second computing device for execution of the verification process.
30 . A non-transitory computer-readable medium storing computer-readable instructions which, when read and executed by at least one processing unit associated with a computing apparatus, cause the processing unit to carry out the method of claim 24 .