Cryptography Reference
In-Depth Information
Table 4.
Performance of the QD-McEliece encryption including KIC-
γ
on the AVR
μC
ATxmega256@32 MHz
Operation
Sub-operation
Clock cycles
Hash
15,083
CWencoding
50,667
Other
8,927
QD-McEliece
encryption
Vector-matrix multiplication
6,279,662
Add error vector
4,613
Table 5.
Performance of the QD-McEliece decryption on the AVR
μC
ATxmega256@
32 MHz
Operation
Sub-operation
Clock cycles
Syndrome computation on-the-fly
25,745,284
QD-
McEliece
decryption
Syndrome computation with
S
9,118,828
Syndrome inversion
3,460,823
Computing
σ
(
x
)
1,625,090
Error correction (HS)
31,943,688
Error correction (HS with PD)
19,234,171
CWdecoding
61,479
Hash
15,111
Other
19,785
Table 5 presents the results of the operations and sub-operations of the QD-
McEliece decryption function including KIC-
γ
.
Table 5 shows clearly that the error correction using the Horner scheme with
polynomial division (PD) is about 40% faster then the Horner scheme with-
out polynomial division. Considering the fact that the error correction is one
of the most computationally expensive functions within the decryption algo-
rithm the polynomial division provides a significant speed gain for this opera-
tion. In the case that the syndrome is computed using the precomputed matrix
S
and the error correction is performed using the Horner scheme with poly-
nomial division decoding of a 2312 bits ciphertext requires 33,535,287 cycles.
Running at 32 MHz the decryption takes 1.0480 seconds while the ciphertext
rate is 2206 bits/second
2
. Decryption with the on-the-fly syndrome computa-
tion method takes 50,161,743 cycles. Hence, running at 32 MHz the decryption
of a ciphertext takes 1.5676 seconds in this case while the ciphertext rate is
1475 bits/second. Although the on-the-fly decryption is about 1.5 times slower,
no additional Flash memory is required so that a migration to cheaper devices
is possible.
2
Chiphertext rate denotes number of ciphertext bits processed per second.
