Masked kronecker substitution for polynomial multiplication
A data processing system comprising instructions embodied in a non-transitory computer readable medium, the instructions for a cryptographic operation using polynomials for lattice-based cryptography in a processor, the instructions, including: applying a share-wise Kronecker substitution to arithmetic shares of a first polynomial; applying a Kronecker substitution to a second polynomial; multiplying share-wise the Kronecker substitution of the second polynomial and the arithmetic shares of the Kronecker substitution of the shares of the first polynomial to produce arithmetic shares of a first output; converting the shares of the first output to arithmetic shares of a polynomial representation; converting the arithmetic shares of the polynomial representation to Boolean shares of the polynomial representation; adding the Boolean shares of the polynomial representation to Boolean shares of a third polynomial to produce Boolean shares of a second output; and carrying out a cryptographic operation using the Boolean shares of the second output.
1 . A data processing system comprising instructions embodied in a non-transitory computer readable medium, the instructions for a cryptographic operation using polynomials for lattice-based cryptography, the instructions, when executed, are configured to cause a processor to perform a method comprising:
applying a share-wise Kronecker substitution to arithmetic shares of a first polynomial;
applying a Kronecker substitution to a second polynomial;
multiplying share-wise the Kronecker substitution of the second polynomial and the arithmetic shares of the Kronecker substitution of the shares of the first polynomial to produce arithmetic shares of a first output;
converting the shares of the first output to arithmetic shares of a polynomial representation;
converting the arithmetic shares of the polynomial representation to Boolean shares of the polynomial representation;
arithmetically adding the Boolean shares of the polynomial representation to Boolean shares of a third polynomial to produce Boolean shares of a second output; and
carrying out a cryptographic operation using the Boolean shares of the second output to digitally sign data, decrypt data, or authenticate data.
2 . The data processing system of claim 1 , wherein the instructions further comprise instructions that cause the processor to perform the method further comprising:
converting Boolean shares of the first polynomial into the arithmetic shares of the first polynomial.
3 . The data processing system of claim 2 , wherein converting Boolean shares of the first polynomial into the arithmetic shares of the first polynomial includes calculating:
s
1
ˆ
A
,
2
k
′
=
Sec
B
2
A
k
′
d
(
s
1
ˆ
B
,
⌈
log
2
(
2
η
+
1
)
⌉
)
,
where
s
1
ˆ
A
,
2
k
′
are arithmetic shares of the first polynomial, d is a number of shares,
Sec
B
2
A
k
′
b
is a secure Boolean to arithmetic shares conversion function, B,┌log 2 (2η+1)┐ are Boolean shares of the first polynomial, η defines a range [−η,η] of coefficients of the first polynomial ŝ 1 , and k′ is the arithmetic modulus.
4 . The data processing system of claim 1 , wherein the Kronecker substitution is a Kronecker plus substitution.
5 . The data processing system of claim 1 , wherein multiplying share-wise the Kronecker substitution of the second polynomial and the arithmetic shares of the Kronecker substitution of the shares of the first polynomial includes calculating
R
A
,
2
k
′
=
C
·
S
1
A
,
2
k
′
,
where
R
A
,
2
k
′
are the arithmetic shares of a first output, C is a Kronecker representation of the second polynomial, and
S
1
A
,
2
k
′
.
are the arithmetic shares of a Kronecker representation of the first polynomial.
6 . The data processing system of claim 1 , wherein adding the Boolean shares of the polynomial representation to Boolean shares of a third polynomial to produce Boolean shares of a second output includes calculating
R
^
B
,
l
o
g
2
(
4
γ
1
)
=
Sec
Add
l
o
g
2
(
4
γ
1
)
d
(
y
ˆ
B
,
l
o
g
2
(
2
γ
1
)
,
R
^
B
,
l
o
g
2
(
2
γ
1
)
)
,
where {circumflex over (R)} B,log 2 (4γ 1 ) are Boolean shares of the second output,
Sec
Add
l
o
g
2
(
4
γ
1
)
d
is a secure add function, ŷ B,log 2 (2γ 1 ) are the Boolean shares of a third polynomial, {circumflex over (R)} B,log 2 (2γ 1 ) are the Boolean shares of the polynomial representation, and Y1 defines a range [−γ 1 −1,γ 1 ] of the coefficients of the third polynomial ŷ.
7 . A data processing system comprising instructions embodied in a non-transitory computer readable medium, the instructions for a cryptographic operation using polynomials for lattice-based cryptography, the instructions, when executed, cause a processor to perform a method comprising:
applying a share-wise Kronecker substitution to arithmetic shares of a first polynomial;
applying a Kronecker substitution to a second polynomial;
multiplying share-wise the Kronecker substitution of the second polynomial and the arithmetic shares of the Kronecker substitution of the shares of the first polynomial to produce arithmetic shares of a first output;
converting the shares of the first output to arithmetic shares of a polynomial representation;
converting the arithmetic shares of the polynomial representation to Boolean shares of the polynomial representation;
subtracting the Boolean shares of the polynomial representation to Boolean shares of a third polynomial to produce Boolean shares of a second output; and
carrying out a cryptographic operation using the Boolean shares of the second output to digitally sign data, decrypt data, encrypt data, or authenticate data.
8 . The data processing system of claim 7 , wherein the instructions, when executed, cause the processor to perform the method further comprising:
converting Boolean shares of the first polynomial into the arithmetic shares of the first polynomial.
9 . The data processing system of claim 8 , wherein converting Boolean shares of the first polynomial into the arithmetic shares of the first polynomial includes calculating:
A
,
2
k
′
=
Sec
B
2
A
k
′
d
(
B
,
⌈
l
o
g
2
(
2
η
+
1
)
⌉
)
,
where
A
,
2
k
′
are arithmetic shares of the first polynomial, d is a number of shares,
Sec
B
2
A
k
′
b
is a secure Boolean to arithmetic shares conversion function, B,┌log 2 (2η+1)┐ are Boolean shares of the first polynomial, η defines a range [−η,η] of coefficients of the first polynomial ŝ 2 , and k′ is the arithmetic modulus.
10 . The data processing system of claim 7 , wherein the Kronecker substitution is a Kronecker plus substitution.
11 . The data processing system of claim 7 , wherein multiplying share-wise the Kronecker substitution of the second polynomial and the arithmetic shares of the Kronecker substitution of the shares of the first polynomial includes calculating
R
A
,
2
k
′
=
C
·
S
2
A
,
2
k
′
,
where
R
A
,
2
k
′
are the arithmetic shares of a first output, C is a Kronecker representation of the second polynomial, and
S
2
A
,
2
k
′
are the arithmetic shares of a Kronecker representation of the first polynomial.
12 . The data processing system of claim 7 , wherein subtracting the Boolean shares of the polynomial representation to Boolean shares of a third polynomial to produce Boolean shares of a second output includes calculating
R
^
B
,
l
o
g
2
(
4
γ
2
)
←
Sec
Sub
l
o
g
2
(
4
γ
2
)
d
(
B
,
l
o
g
2
(
2
γ
2
)
,
R
^
B
,
l
o
g
2
(
2
γ
2
)
)
,
where {circumflex over (R)} B,log 2 (4γ 2 ) are the Boolean shares of the second output,
Sec
Add
l
o
g
2
(
4
γ
1
)
)
d
is a secure add function, B,log 2 (2γ 2 ) are the Boolean shares of a third polynomial, {circumflex over (R)} B,log 2 (2γ 2 ) are the Boolean shares of the polynomial representation, and γ 2 defines a range (−γ 2 ,γ 2 ) of the coefficients of the third polynomial .
13 . A method for a cryptographic operation using polynomials for lattice- based cryptography, the method comprising:
applying, by a processor of a computing device, a share-wise Kronecker substitution to arithmetic shares of a first polynomial;
applying, by the processor, a Kronecker substitution to a second polynomial;
multiplying, by the processor, share-wise the Kronecker substitution of the second polynomial and the arithmetic shares of the Kronecker substitution of the shares of the first polynomial to produce arithmetic shares of a first output;
converting, by the processor, the shares of the first output to arithmetic shares of a polynomial representation;
converting, by the processor, the arithmetic shares of the polynomial representation to Boolean shares of the polynomial representation;
arithmetically adding, by the processor, the Boolean shares of the polynomial representation to Boolean shares of a third polynomial to produce Boolean shares of a second output; and
carrying out, by the processor, a cryptographic operation using the Boolean shares of the second output to digitally sign data, decrypt data, encrypt data, or authenticate data.
14 . The method of claim 13 , further comprising converting, by the processor, Boolean shares of the first polynomial into the arithmetic shares of the first polynomial.
15 . The method of claim 14 , wherein converting Boolean shares of the first polynomial into the arithmetic shares of the first polynomial includes calculating:
s
1
^
A
,
2
k
′
=
Sec
B2A
k
′
d
(
s
1
^
B
,
⌈
log
2
(
2
η
+
1
)
⌉
)
,
where
A
,
2
k
′
are arithmetic shares of the first polynomial, d is a number of shares,
Sec
B
2
A
k
′
b
is a secure Boolean to arithmetic shares conversion function, B,┌log 2 (2η+1)┐ are Boolean shares of the first polynomial, η defines a range [−η,η] of coefficients of the first polynomial ŝ 1 , and k′ is the arithmetic modulus.
16 . The method of claim 13 , wherein the Kronecker substitution is a Kronecker plus substitution.
17 . The method of claim 13 , wherein multiplying share-wise the Kronecker substitution of the second polynomial and the arithmetic shares of the Kronecker substitution of the shares of the first polynomial includes calculating
R
A
,
2
k
′
=
C
·
S
1
A
,
2
k
′
,
where
R
A
,
2
k
′
are the arithmetic shares of a first output, C is a Kronecker representation of the second polynomial, and
S
1
A
,
2
k
′
are the arithmetic shares of a Kronecker representation of the first polynomial.
18 . The method of claim 13 , wherein adding the Boolean shares of the polynomial representation to Boolean shares of a third polynomial to produce Boolean shares of a second output includes calculating
R
^
B
,
l
o
g
2
(
4
γ
1
)
=
Sec
Add
l
o
g
2
(
4
γ
1
)
d
(
y
ˆ
B
,
l
o
g
2
(
2
γ
1
)
,
R
^
B
,
l
o
g
2
(
2
γ
1
)
)
,
where {circumflex over (R)} B,log 2 (4γ 1 ) are Boolean shares of the second output,
Sec
Add
l
o
g
2
(
4
γ
1
)
d
is a secure add function, ŷ B,log 2 (2γ 1 ) are the Boolean shares of a third polynomial, {circumflex over (R)} B,log 2 (2γ 1 ) are the Boolean shares of the polynomial representation, and γ 1 defines a range [−γ 1 −1,γ 1 ] of the coefficients of the third polynomial ŷ.
19 . A method for a cryptographic operation using polynomials for lattice- based cryptography, the instructions, when executed, cause a processor to perform the method comprising:
applying a share-wise Kronecker substitution to arithmetic shares of a first polynomial;
applying a Kronecker substitution to a second polynomial;
multiplying share-wise the Kronecker substitution of the second polynomial and the arithmetic shares of the Kronecker substitution of the shares of the first polynomial to produce arithmetic shares of a first output;
converting the shares of the first output to arithmetic shares of a polynomial representation;
converting the arithmetic shares of the polynomial representation to Boolean shares of the polynomial representation;
subtracting the Boolean shares of the polynomial representation to Boolean shares of a third polynomial to produce Boolean shares of a second output; and
carrying out a cryptographic operation using the Boolean shares of the second output to digitally sign data, decrypt data, encrypt data, or authenticate data.
20 . The method of claim 19 , wherein the instructions, when executed, cause the processor to perform the method further comprising:
converting Boolean shares of the first polynomial into the arithmetic shares of the first polynomial.
21 . The method of claim 20 , wherein converting Boolean shares of the first polynomial into the arithmetic shares of the first polynomial includes calculating:
s
2
^
A
,
2
k
′
=
Sec
B
2
A
k
′
d
(
s
2
^
B
,
⌈
log
2
(
2
η
+
1
)
⌉
)
,
where
A
,
2
k
′
are arithmetic shares of the first polynomial, d is a number of shares,
Sec
B
2
A
k
′
b
is a secure Boolean to arithmetic shares conversion function, B,┌log 2 (2η+1)┐ are Boolean shares of the first polynomial, η defines a range [−η,η] of coefficients of the first polynomial ŝ 2 , and k′ is the arithmetic modulus.
22 . The method of claim 19 , wherein the Kronecker substitution is a Kronecker plus substitution.
23 . The method of claim 19 , wherein multiplying share-wise the Kronecker substitution of the second polynomial and the arithmetic shares of the Kronecker substitution of the shares of the first polynomial includes calculating
R
A
,
2
k
′
=
C
·
S
2
A
,
2
k
′
,
where
R
A
,
2
k
′
are the arithmetic shares of a first output, C is a Kronecker representation of the second polynomial, and
S
2
A
,
2
k
′
are the arithmetic shares of a Kronecker representation of the first polynomial.
24 . The method of claim 19 , wherein subtracting the Boolean shares of the polynomial representation to Boolean shares of a third polynomial to produce Boolean shares of a second output includes calculating
R
^
B
,
l
o
g
2
(
4
γ
2
)
←
Sec
Sub
l
o
g
2
(
4
γ
2
)
d
(
B
,
l
o
g
2
(
2
γ
2
)
,
R
^
B
,
l
o
g
2
(
2
γ
2
)
)
,
where {circumflex over (R)} B,log 2 (4γ 2 ) are the Boolean shares of the second output,
Sec
Add
l
o
g
2
(
4
γ
1
)
)
d
is a secure add function, B,log 2 (2γ 2 ) are the Boolean shares of a third polynomial, {circumflex over (R)} B,log 2 (2γ 2 ) are the Boolean shares of the polynomial representation, and γ 2 defines a range (−γ 2 ,γ 2 ) of the coefficients of the third polynomial .