High-Speed Hardware Implementation of Rainbow Signature on FPGAs - Post-Quantum Cryptography - page 236

The schematic diagram of normalization is shown in Fig. 4, where R i for the i -
th element in the pivot row, and NOR i for the normalizing result, respectively.
Then, we have the expressions

S 1 = ThreeMult ( β 2 ,β 4 ,β 8 ) ,
S 2 = ThreeMult ( β 16 ,β 32 ,β 64 ) ,
S 4 = TwoMult ( β 128 ,R i ) ,
NOR i = ThreeMult ( S 1 ,S 2 ,S 4 ) .

(5)

S 1 and S 2 are executed in I cell for partial multiplicative inversion while S 4 and
NOR i are executed in N i cells for normalization. Thus one two-input multiplier
as well as another three-input multiplier are included in N i cells. Since S 1 ,S 2
and S 4 can be implemented in parallel in each iteration, the critical path of
normalizing consists of only two multiplications of three elements.

Eliminating Operation. The schematic diagram of normalization is shown in
Fig. 5, where R j stands for the j i-th element in the pivot row, C i for the i -th
element in the pivot column, and ELI ij is the eliminated result of a ij .

a ii +ELI ii a ij +ELI ij

S 1 S 2

S 3

S 3

£ 4 £ 4

£ 8

£ 16

£ 16 £ 32

£ 64

R j

£ 2 £ 128

R j C i

Fig. 5. Optimized Elimination in Solving System of Linear Equations

Then, we have the expressions

S 1 = ThreeMult ( β 2 ,β 4 ,β 8 ) ,
S 2 = ThreeMult ( β 16 ,β 32 ,β 64 ) ,
S 3 = ThreeMult ( β 128 ,R j ,C i ) ,
ELI ij = a ij + ThreeMult ( S 1 ,S 2 ,S 3 ) .

(6)

S 1 and S 2 are executed in I cell for partial multiplicative inversion while S 3 and
ELI ij are executed in E ij cells for elimination. Thus two three-input multipliers
and one adder are included in E ij cells. Since S 1 ,S 2 and S 3 can be implemented
in parallel in each iteration, the critical path of elimination consists of only two
multiplications of three elements and one addition.