Cryptography Reference
In-Depth Information
a
ij
+ELI
ij
a
ii
+ELI
ij
C
i
NOR
i
NOR
i
C
i
R
j
R
Inv
Inv
S
6
£
128
S
6
S
4
S
5
S
4
S
5
S
1
S
2
S
3
S
1
S
2
S
3
£
2
£
4
£
32
£
64
£
2
£
4
£
8
£
16
£
32
£
64
Fig. 6.
Original Design of Gauss-Jordan Elimination
Overall Optimization.
By integrating the optimizations above, Fig. 7 shows
that the critical path of our design is reduced from five multiplications and one
addition to two multiplications and one addition, compared with the original
principle of Gauss-Jordan elimination illustrated in Fig. 6.
a
ij
+ELI
ij
NOR
i
NOR
i
a
ii
+ELI
ij
S
1
S
2
S
3
S
4
£
4
£
32
£
2
£
4
£
16
£
32
£
64
£
8
£
128
R
j
C
i
Fig. 7.
Optimized Design of Gauss-Jordan Elimination
Therefore, our design takes one clock cycle to perform the operations in each
iteration of solving system of linear equations. In the end, it takes only 12 clock
cycles to solve a system of linear equations where the matrix size is 12
×
12.
3.6 Designs of Ane Transformations and Polynomial Evaluations
L
1
−
1
:
k
24
→ k
24
and
L
2
−
1
:
k
42
→ k
42
ane transformations are computed by
invoking vector addition and vector-multiplication over a finite field. Two-layer
Oil-Vinegar constructions including 24 multivariate polynomials are evaluated by
invoking multiplication over a finite field. Thus multiplication over a finite field is
