Low-memory masked Dilithium with alternative signing algorithm
A method of performing a Dilithium signature operation on a message M using a secret key sk, including: generating a polynomial y using an ExpandMask function; calculating a polynomial z based upon y, c, and s 1 ; performing a bound check on z based upon γ 1 and β; performing a bound check on ct 0 based upon γ 2 ; calculating a polynomial {tilde over (r)} based upon A, z, c, t, α, and w 1 ; performing a bound check on {tilde over (r)} based upon γ 2 and β; calculating a hint polynomial h based on the {tilde over (r)}; and returning a digital signature of the message M where the digital signature includes z and h.
1. A method of performing, using a hardware processor of a computing device, a Dilithium signature operation on a message M using a secret key sk, the method comprising:
generating a polynomial y using an ExpandMask function;
calculating a polynomial z based upon y, c, and s 1 , where s 1 is part of the secret key sk and replacing y with z in a memory;
performing a bound check on z based upon γ 1 and β, where γ 1 and β are parameters of the Dilithium signature operation;
performing a bound check on ct 0 based upon γ 2 , where γ 2 is a parameter of the Dilithium signature operation, c is based upon a hash of the message M, and polynomial t 0 is part of the secret key sk;
calculating a polynomial {tilde over (r)} based upon A, z, c, t, α, and w 1 , where A and w 1 are calculated as part of the Dilithium signature operation, α is a parameter of the Dilithium signature operation, and polynomial t is an addition of a polynomial t 1 scaled by 2 d and the polynomial t 0 where polynomial t 1 is part of a public key pk;
performing a bound check on {tilde over (r)} based upon γ 2 and β;
calculating a hint polynomial h based on the {tilde over (r)}; and
returning a digital signature of the message M where the digital signature includes z and h.
2. The method of claim 1 , wherein calculating z includes calculating z=y+cs 1 .
3. The method of claim 1 , wherein performing a bound check on z includes determining if ∥z∥ ∞ ≥γ 1 −β.
4. The method of claim 1 , wherein performing a bound check on ct 0 includes determining if ∥ct 0 ∥ ∞ ≥γ 2 .
5. The method of claim 1 , wherein calculating a polynomial {tilde over (r)} includes repeating for each polynomial vector element of the polynomial {tilde over (r)} the steps of:
calculating one polynomial vector element of the polynomial {tilde over (r)} based upon A, z, c, t, α, and w 1 ;
performing a bound check on the one polynomial vector element of {tilde over (r)} based upon γ 2 and β; and
calculating one polynomial vector element of the hint polynomial h based on the {tilde over (r)}.
6. The method of claim 1 , wherein calculating a polynomial {tilde over (r)} includes calculating {tilde over (r)}[i]=Az[i]−ct[i]−αw 1 [i] where i is an integer index specifying a polynomial of the vectors {tilde over (r)}, z, t, and w 1 .
7. The method of claim 6 , wherein performing a bound check on {tilde over (r)} includes determining if ∥{tilde over (r)}[i] ├ ┤∥_∞≥γ_2−β.
8. The method of claim 6 , wherein calculating a hint polynomial h is further based on c, t 0 , w 1 , and γ 2 , where t 0 is part of the secret key sk, where w 1 is calculated as part of the Dilithium signature operation, and where γ 2 is a parameter of the Dilithium signature operation.
9. The method of claim 1 , wherein calculating a polynomial {tilde over (r)} includes calculating {tilde over (r)}[i]=Az[i]−c(As 1 [i]+s 2 [i])−αw 1 [i] where i is an integer index specifying a polynomial of the vectors {tilde over (r)}, z, s 1 , s 2 , and w 1 .
10. The method of claim 1 , wherein calculating a polynomial {tilde over (r)} includes calculating {tilde over (r)}[i]=A(z[i]−cs 1 [i])−cs 2 [i]−αw 1 [i] where i is an integer index specifying a polynomial of the vectors {tilde over (r)}, z, s 1 , s 2 , and w 1 .
11. The method of claim 1 , further comprising determining if a number of 1's in h is greater than ω, where ω is a parameter of the Dilithium signature operation.
12. The method of claim 1 , wherein {tilde over (r)}, z, and y are masked using a plurality of shares.
13. A data processing system comprising instructions embodied in a non-transitory computer readable medium, the instructions for a method of performing a Dilithium signature operation on a message M using a secret key sk, the instructions, comprising:
generating a polynomial y using an ExpandMask function;
calculating a polynomial z based upon y, c, and s 1 , where s 1 is part of the secret key sk and replacing y with z in a memory;
performing a bound check on z based upon γ 1 and β, where γ 1 and β are parameters of the Dilithium signature operation;
performing a bound check on ct 0 based upon γ 2 , where γ 2 is a parameter of the Dilithium signature operation, c is based upon a hash of the message M, and polynomial t 0 is part of the secret key sk;
calculating a polynomial {tilde over (r)} based upon A, z, c, t, α, and w 1 , where A and w 1 are calculated as part of the Dilithium signature operation, α is a parameter of the Dilithium signature operation, and polynomial t is an addition of a polynomial t 1 scaled by 2 d and the polynomial t 0 where polynomial t 1 is part of a public key pk;
performing a bound check on {tilde over (r)} based upon γ 2 and β;
calculating a hint polynomial h based on the {tilde over (r)}; and
returning a digital signature of the message M where the digital signature includes z and h.
14. The data processing system of claim 13 , wherein calculating z includes calculating z=y+cs 1 .
15. The data processing system of claim 13 , wherein performing a bound check on z includes determining if ∥z∥ ∞ ≥γ 1 −β.
16. The data processing system of claim 13 , wherein performing a bound check on ct 0 includes determining if ∥ct 0 ∥ ∞ ≥γ 2 .
17. The data processing system of claim 13 , wherein calculating a polynomial {tilde over (r)} includes repeating for each polynomial vector element of the polynomial {tilde over (r)} the steps of:
calculating one polynomial vector element of the polynomial {tilde over (r)} based upon A, z, c, t, α, and w 1 ;
performing a bound check on the one polynomial vector element of {tilde over (r)} based upon γ 2 and β; and
calculating one polynomial vector element of the hint polynomial h based on the {tilde over (r)}.
18. The data processing system of claim 13 , wherein calculating a polynomial {tilde over (r)} includes calculating {tilde over (r)}[i]=Az[i]−ct[i]−αw 1 [i] where i is an integer index specifying a polynomial of the vectors {tilde over (r)}, z, t, and w 1 .
19. The data processing system of claim 18 , wherein performing a bound check on {tilde over (r)} includes determining if ∥{tilde over (r)}[i] ├ ┤∥_∞≥γ_2−β.
20. The data processing system of claim 18 , wherein calculating a hint polynomial h is further based on c, t 0 , w 1 , and γ 2 , where t 0 is part of the secret key sk, where w 1 is calculated as part of the Dilithium signature operation, and where γ 2 is a parameter of the Dilithium signature operation.
21. The data processing system of claim 13 , wherein calculating a polynomial {tilde over (r)} includes calculating {tilde over (r)}[i]=Az[i]−c(As 1 [i]+s 2 [i])−αw 1 [i] where i is an integer index specifying a polynomial of the vectors {tilde over (r)}, z, s 1 , s 2 , and w 1 .
22. The data processing system of claim 13 , wherein calculating a polynomial {tilde over (r)} includes calculating {tilde over (r)}[i]=A(z[i]−cs 1 [i])−cs 2 [i]−αw 1 [i] where i is an integer index specifying a polynomial of the vectors {tilde over (r)}, z, s 1 , s 2 , and w 1 .
23. The data processing system of claim 13 , further comprising determining if a number of 1's in h is greater than ω, where ω is a parameter of the Dilithium signature operation.
24. The data processing system of claim 13 , wherein {tilde over (r)}, z, and y are masked using a plurality of shares.