Memory management in a computer system configured for generating a signature and apparatus for implementing the same
A computer-implemented method for memory management in a computer system configured for generating a signature of a binary data message m using a key B of a predetermined lattice-based structure is proposed, which comprises: determining coefficients of a 2×2 signature generation matrix SG, wherein the non-diagonal coefficients of the signature generation matrix SG are complex polynomials with a non-zero imaginary part, and the diagonal coefficients of the signature generation matrix SG are real polynomials; and determining a LDL representation of the signature generation matrix SG according to which SG is represented by a matrix product L.D.L*, wherein L is a 2×2 lower triangular matrix with ones on the diagonal, D is a 2×2 diagonal matrix, and L* is the adjoint of L; wherein the storing in a memory buffer of the computer system of the coefficients of the signature generation matrix SG and the coefficients of the matrices of the LDL representation is managed based on that the signature generation matrix SG has real diagonal coefficients, and the memory buffer is used alternatively to store the coefficients of the signature generation matrix SG or the coefficients of the matrix D of the LDL representation.
1 . A computer-implemented method for memory management in a computer system configured for generating a signature of a binary data message m using a key B of a predetermined lattice-based structure, the method comprising:
determining, based on the key B, coefficients of a 2×2 signature generation matrix SG, wherein non-diagonal coefficients of the signature generation matrix SG are complex polynomials with a non-zero imaginary part, and diagonal coefficients of the signature generation matrix SG are real polynomials;
determining a LDL representation of the signature generation matrix SG according to which SG is represented by a matrix product L.D.L*, wherein L is a 2×2 lower triangular matrix with ones as diagonal coefficients, D is a 2×2 diagonal matrix, and L* is the adjoint matrix of L, wherein matrix L is of form
(
1
0
l
1
0
1
)
,
the method further comprising: computing coefficient l 10 of the matrix L as
l
1
0
=
g
0
1
g
0
0
—
,
wherein the signature generation matrix SG is of form
(
g
0
0
g
0
1
g
1
0
g
1
1
)
,
where g 00 and g 11 are real polynomials, and g 10 and g 01 are complex polynomials and g 10 is equal to complex conjugate g 10 of g 01 , D is of form
(
d
0
0
0
0
d
1
1
)
and determined as:
(
g
0
0
0
0
g
1
1
-
|
g
0
1
|
2
g
0
0
)
,
and wherein computing the coefficient l 10 of the matrix L comprises: computing inverse 1/g 00 of real coefficient g 00 , and performing a real-complex multiplication of 1/g 00 with the complex polynomial g 01 ; and
managing storing in a memory buffer of the computer system of coefficients of the signature generation matrix SG and coefficients of the matrices of the LDL representation based on:
(a) the signature generation matrix SG is of form
(
g
0
0
g
0
1
g
1
0
g
1
1
)
,
where diagonal coefficients g 00 and g 11 are real polynomials, g 10 and g 01 are complex polynomials and g 10 is equal to complex conjugate g 10 of g 01 , D is of form
(
d
0
0
0
0
d
1
1
)
and determined as:
(
g
00
0
0
g
11
-
❘
"\[LeftBracketingBar]"
g
01
❘
"\[RightBracketingBar]"
2
g
00
)
,
and
where the memory buffer is used alternatively to store coefficients of the signature generation matrix SG or coefficients of the matrix D of the LDL representation, and the coefficient d 11 is stored in the memory buffer by overwriting one or more coefficients of the signature generation matrix SG.
2 . The method according to claim 1 , wherein the memory buffer is dimensioned for storing complex non-diagonal coefficients and real diagonal coefficients of the signature generation matrix SG.
3 . The method according to claim 1 , wherein the key B has a matrix structure, and the signature generation matrix is determined based on matrix product B.B*, wherein B* is the adjoint matrix of B.
4 . The method according to claim 1 , wherein the key B has a matrix structure, and the signature generation matrix is determined based on matrix product {circumflex over (B)}.{circumflex over (B)}*, wherein {circumflex over (B)}* is adjoint matrix of {circumflex over (B)}, and wherein {circumflex over (B)} is obtained based on a transform of matrix B in a frequency domain.
5 . The method according to claim 1 , wherein the signature generation matrix SG is of form:
(
g
0
0
g
0
1
g
0
1
g
0
0
)
,
wherein g 00 is a real polynomial, g 01 is a complex polynomial, and g 01 is complex conjugate of g 01 , and wherein the memory buffer is dimensioned for storing g 00 and real and imaginary parts of g 01 .
6 . The method according to claim 1 , wherein the signature generation matrix is a Gram matrix of size 2×2.
7 . The method according to claim 1 , further comprising: generating a signature s 2 of message m based on determination of coefficients of the signature generation matrix SG, and determination of the LDL representation of the signature generation matrix SG.
8 . The method according to claim 1 , wherein the key B is of form
(
g
-
f
G
-
F
)
,
wherein f, g, F, and G are polynomials of [x]/(φ k ), where Φ κ =x n +1∈ [x] for n=2 κ , and κ be a positive integer which verify equation f·G−g·F=q mod (φ κ ), where q is a constant equal to 12×2 10 +1.
9 . An apparatus, the apparatus comprising a processor and a memory operatively coupled to the processor, wherein the apparatus is configured to perform a method for memory management in a computer system configured for generating a signature of a binary data message m using a key B of a predetermined lattice-based structure, the method comprising:
determining, based on the key B, coefficients of a 2×2 signature generation matrix SG, wherein non-diagonal coefficients of the signature generation matrix SG are complex polynomials with a non-zero imaginary part, and diagonal coefficients of the signature generation matrix SG are real polynomials;
determining a LDL representation of the signature generation matrix SG according to which SG is represented by a matrix product L.D.L*, wherein L is a 2×2 lower triangular matrix with ones as diagonal coefficients, D is a 2×2 diagonal matrix, and L′ is the adjoint matrix of L, wherein matrix L is of form
(
1
0
l
1
0
1
)
,
the method further comprising: computing coefficient l 10 of the matrix L as l 10 = g 01 /g 00 , wherein the signature generation matrix SG is of form
(
g
10
g
11
)
,
where g 00 and g 11 are real polynomials, and g 10 and g 01 are complex polynomials, and g 10 is equal to complex conjugate g 10 of g 01 , the diagonal matrix D is of form
(
d
0
0
0
0
d
1
1
)
and determined as:
(
g
00
0
0
g
11
-
❘
"\[LeftBracketingBar]"
g
01
❘
"\[RightBracketingBar]"
2
g
00
)
,
and wherein computing the coefficient l 10 of the matrix L comprises: computing inverse 1/g 00 of real coefficient g 00 , and performing a real-complex multiplication of 1/g 00 with the complex polynomial g 01 ; and
managing storing in a memory buffer of the computer system of the coefficients of the signature generation matrix SG and coefficients of the matrices of the LDL representation based on:
where the memory buffer is used alternatively to store coefficients of the signature generation matrix SG or coefficients of the matrix D of the LDL representation and the coefficient d 11 is stored in the memory buffer by overwriting one or more coefficients of the signature generation matrix SG.
10 . A non-transitory computer-readable medium encoded with executable instructions which, when executed, causes an apparatus comprising a processor and a memory operatively coupled to the processor, to perform a method for memory management in a computer system configured for generating a signature of a binary data message m using a key B of a predetermined lattice-based structure, the method comprising:
determining, based on the key B, coefficients of a 2×2 signature generation matrix SG, wherein non-diagonal coefficients of the signature generation matrix SG are complex polynomials with a non-zero imaginary part, and diagonal coefficients of the signature generation matrix SG are real polynomials;
determining a LDL representation of the signature generation matrix SG according to which SG is represented by a matrix product L.D.L*, wherein L is a 2×2 lower triangular matrix with ones as diagonal coefficients, D is a 2×2 diagonal matrix, and L* is the adjoint matrix of L, wherein matrix L is of form
(
l
1
0
1
)
,
the method further comprising: computing coefficient l 10 of the matrix L as l 10 = g 01 /g 00 wherein the signature generation matrix SG is of form
(
g
0
0
g
0
1
g
1
0
g
1
1
)
,
where g 00 and g 11 are real polynomials, and g 10 and g 01 are complex polynomials, and g 10 is equal to complex conjugate g 10 of g 01 , D is of form
(
d
0
0
0
0
d
1
1
)
and determined as
(
g
0
0
0
0
g
1
1
-
|
g
0
1
|
2
g
0
0
)
,
and wherein computing the coefficient l 10 of the matrix L comprises: computing inverse 1/g 00 of real coefficient g 00 , and performing a real-complex multiplication of 1/g 00 with the complex polynomial g 01 ; and
managing storing in a memory buffer of the computer system of the coefficients of the signature generation matrix SG and coefficients of the matrices of the LDL representation based on:
where the memory buffer is used alternatively to store coefficients of the signature generation matrix SG or coefficients of the matrix D of the LDL representation and the coefficient d 11 is stored in the memory buffer by overwriting one or more coefficients of the signature generation matrix SG.
11 . The apparatus according to claim 9 , wherein the memory buffer is dimensioned for storing complex non-diagonal coefficients and real diagonal coefficients of the signature generation matrix SG.
12 . The apparatus according to claim 9 , wherein the key B has a matrix structure, and the signature generation matrix is determined based on matrix product B.B*, wherein B* is adjoint matrix of B.
13 . The apparatus according to claim 9 , wherein the key B has a matrix structure, and the signature generation matrix is determined based on matrix product {circumflex over (B)}.{circumflex over (B)}*, wherein {circumflex over (B)}* is adjoint matrix of {circumflex over (B)}, and wherein {circumflex over (B)} is obtained based on a transform of the matrix B in a frequency domain.
14 . The non-transitory computer-readable medium according to claim 10 , wherein the memory buffer is dimensioned for storing complex non-diagonal coefficients and real diagonal coefficients of the signature generation matrix SG.
15 . The non-transitory computer-readable medium according to claim 10 , wherein the key B has a matrix structure, and the signature generation matrix is determined based on the matrix product B.B*, wherein B* is adjoint matrix of B.