Compression of matrices for digital security
Systems and techniques are described herein for compressing data used in cryptographic operations. For example, a process may include obtaining a first data structure, wherein the first data structure comprises polynomials; generating a second data structure based on the first data structure, wherein the second data structure comprises coefficients of the polynomials; sorting the second data structure in an ascending order to obtain a sorted second data structure; updating the sorted second data structure based on differences between elements of the sorted second data structure to obtain a delta-encoded data structure; performing an entropy coding on the delta-encoded data structure to obtain an entropy-encoded output; recovering an updated first data structure using the entropy-encoded output, wherein the updated first data structure corresponds to the first data structure with a different order of first data structure elements; and performing a cryptographic operation using the updated first data structure.
1. A method for compressing data used in cryptographic operations, the method comprising:
obtaining a first data structure for performing a cryptographic operation, wherein the first data structure comprises polynomials;
generating a second data structure based on the first data structure, wherein the second data structure comprises coefficients of the polynomials;
sorting the second data structure in an order to obtain a sorted second data structure;
updating the sorted second data structure based on differences between elements of the sorted second data structure to obtain a delta-encoded data structure;
performing an entropy coding on the delta-encoded data structure to obtain an entropy-encoded output;
performing an entropy decoding of the entropy-encoded output to obtain an entropy-decoded output;
performing a delta decoding of the entropy-decoded output to obtain a delta-decoded output to recover an updated first data structure, wherein the updated first data structure corresponds to the first data structure with a different order of first data structure elements;
performing the cryptographic operation using the updated first data structure; and
outputting a result of the cryptographic operation.
2. The method of claim 1 , wherein recovering the updated first data structure further comprises:
shuffling the delta-decoded output using a shuffling algorithm to obtain a shuffled output, wherein the delta-decoded output and an output of a pseudo-ransom number generator are used as input to the shuffling algorithm to obtain the shuffled output; and
using the shuffled output to obtain the updated first data structure.
3. The method of claim 1 , wherein recovering the updated first data structure further comprises:
shuffling the delta-decoded output using a shuffling algorithm to obtain a shuffled output, wherein the delta-decoded output and a hash of the entropy-encoded output are used as input to the shuffling algorithm to obtain the shuffled output; and
using the shuffled output to obtain the updated first data structure.
4. The method of claim 1 , wherein the entropy coding is performed using an asymmetric numeral system.
5. The method of claim 1 , wherein the cryptographic operation includes encryption or decryption of data.
6. The method of claim 1 , further comprising storing the entropy-encoded output.
7. The method of claim 1 , wherein the first data structure is a matrix, and the polynomials are elements of the matrix.
8. The method of claim 7 , wherein the matrix is a Dilithium matrix.
9. The method of claim 7 , wherein the matrix is a four by four matrix of polynomial functions.
10. The method of claim 1 , wherein the second data structure is an array.
11. The method of claim 1 , wherein the entropy-encoded output is an integer with a size less than the first data structure.
12. An apparatus for compressing data used in cryptographic operations, the apparatus comprising:
at least one memory; and
at least one processor coupled to the at least one memory and configured to:
obtain a first data structure for performing a cryptographic operation, wherein the first data structure comprises polynomials;
generate a second data structure based on the first data structure, wherein the second data structure comprises coefficients of the polynomials;
sort the second data structure in an order to obtain a sorted second data structure;
update the sorted second data structure based on differences between elements of the sorted second data structure to obtain a delta-encoded data structure;
perform an entropy coding on the delta-encoded data structure to obtain an entropy-encoded output;
perform an entropy decoding of the entropy-encoded output to obtain an entropy-decoded output;
perform a delta decoding of the entropy-decoded output to obtain a delta-decoded output to recover an updated first data structure, wherein the updated first data structure corresponds to the first data structure with a different order of first data structure elements;
perform the cryptographic operation using the updated first data structure; and
output a result of the cryptographic operation.
13. The apparatus of claim 12 , wherein, to recover the updated first data structure, the at least one processor is further configured to:
shuffle the delta-decoded output using a shuffling algorithm to obtain a shuffled output, wherein the delta-decoded output and an output of a pseudo-ransom number generator are used as input to the shuffling algorithm to obtain the shuffled output; and
use the shuffled output to obtain the updated first data structure.
14. The apparatus of claim 12 , wherein, to recover the updated first data structure, the at least one processor is further configured to:
shuffle the delta-decoded output using a shuffling algorithm to obtain a shuffled output, wherein the delta-decoded output and a hash of the entropy-encoded output are used as input to the shuffling algorithm to obtain the shuffled output; and
use the shuffled output to obtain the updated first data structure.
15. The apparatus of claim 12 , wherein the entropy coding is performed using an asymmetric numeral system.
16. The apparatus of claim 12 , wherein the cryptographic operation includes encryption or decryption of data.
17. The apparatus of claim 12 , further comprising storing the entropy-encoded output.
18. The apparatus of claim 12 , wherein the first data structure is a matrix, and the polynomials are elements of the matrix.
19. The apparatus of claim 18 , wherein the matrix is a Dilithium matrix.
20. The apparatus of claim 18 , wherein the matrix is a four by four matrix of polynomial functions.
21. The apparatus of claim 12 , wherein the second data structure is an array.
22. The apparatus of claim 12 , wherein the entropy-encoded output is an integer with a size less than the first data structure.
23. A non-transitory computer-readable medium having stored thereon instructions that, when executed by one or more processors, cause the one or more processors to:
obtain a first data structure for performing a cryptographic operation, wherein the first data structure comprises polynomials;
generate a second data structure based on the first data structure, wherein the second data structure comprises coefficients of the polynomials;
sorting the second data structure in an order to obtain a sorted second data structure;
update the sorted second data structure based on differences between elements of the sorted second data structure to obtain a delta-encoded data structure;
perform an entropy coding on the delta-encoded data structure to obtain an entropy-encoded output;
perform an entropy decoding of the entropy-encoded output to obtain an entropy-decoded output;
perform a delta decoding of the entropy-decoded output to obtain a delta-decoded output to recover an updated first data structure, wherein the updated first data structure corresponds to the first data structure with a different order of first data structure elements;
perform the cryptographic operation using the updated first data structure; and
output a result of the cryptographic operation.
24. The non-transitory computer-readable medium of claim 23 , wherein the instructions further cause the one or more processors to:
shuffle the delta-decoded output using a shuffling algorithm to obtain a shuffled output, wherein the delta-decoded output and an output of a pseudo-ransom number generator are used as input to the shuffling algorithm to obtain the shuffled output; and
use the shuffled output to obtain the updated first data structure.
25. The non-transitory computer-readable medium of claim 23 , wherein the instructions further cause the one or more processors to:
shuffle the delta-decoded output using a shuffling algorithm to obtain a shuffled output, wherein the delta-decoded output and a hash of the entropy-encoded output are used as input to the shuffling algorithm to obtain the shuffled output; and
use the shuffled output to obtain the updated first data structure.
26. The non-transitory computer-readable medium of claim 23 , wherein the first data structure is a matrix and the second data structure is an array.
27. The non-transitory computer-readable medium of claim 23 , wherein the entropy-encoded output is an integer with a size less than the first data structure.
28. The non-transitory computer-readable medium of claim 23 , wherein the entropy coding is performed using an asymmetric numeral system.
29. The non-transitory computer-readable medium of claim 23 , wherein the cryptographic operation includes encryption or decryption of data.
30. The non-transitory computer-readable medium of claim 23 , wherein the instructions further cause the one or more processors to store the entropy-encoded output.