)

Implementing and Benchmarking Number Theoretic Transform in Lattice-based Post-Quantum Cryptography using SW/HW Codesign and High Level Synthesis

*Duc T. Nguyen*, Viet B. Dang and Kris Gaj <dnguye69,vdang6,[email protected]>

Introduction

  • Post-Quantum Cryptography (PQC) is cryptography scheme run in classical computers, replacement of modern Cryptography such as RSA, ECC…​ due to the threat of Quantum Computer

NIST PQC Round 2
  • 12 Lattice-base PQC candidates

  • 5 of them implement Number Theoretic Transform (NTT) for polynomial multiplication

  • Polynomial multiplication is major execution function

  • ⇒ We implement NTT as hardware accelerator for NewHope and Kyber.

Number Theoretic Transform (NTT)

  • NTT is similar to FFT and has complexity of O(n log n)

  • To multiply 2 polynomials, we do:

\$C = A \times B = \text{NTT}^{-1}(\text{NTT}(A) \circ \text{NTT}(B))\$

\$\circ\$ point-wise multiplication ⇒ straight forward

\$\text{NTT}, \text{NTT}^{-1}\$ Forward and Inverse NTT operation ⇒ not easy

High Level Synthesis (HLS)

Pragmas are heavily depend on the code structure and algorithm, most important pragmas:

  • Pipeline

  • Unroll

  • Array Partition

Implement Number Theoretic Transform in HLS

  • In [12] Kawamura, K., et. al., 8 strategies were applied at 1st, 2nd, 3rd loops.

ntt

Block Diagram vs. Space Exploration Development

Block Diagram/HLS (BD/HLS)

Develop presumed optimal hardware architecture, write HLS code follow this block diagram.

Space Exploration/HLS (SE/HLS)

Use design space exploration based on HLS directives, the final hardware architecture is unknown until the best result is achieved

SE/HLS and BD/HLS inherit the advantages of HLS

Shorter development and verification time compare to traditional RTL.

BD/HLS vs. SE/HLS

BDHLS

BD/HLS vs. SE/HLS: Resources

[12] Kawamura, K., et. al.

Lower is better

BD/HLS vs. SE/HLS: Speedup

[12] Kawamura, K., et. al.

Lower is better

Transfer Overhead

Bare Metal versus SDSoc transfer overhead affect over total execution time.

  • Bare Metal used in-house DMA kernel

  • SDSoC transfer driver handled by tool

  • Same transfer size between CPU and FPGA in Bare Metal and SDSoc

Transfer Overhead: Encapsulation

Smaller is better

Transfer Overhead: Decapsulation

Smaller is better

Resources utilization for HLS and RTL

  • RTL and HLS implementation use the same number of DSP and BRAM

  • RTL achieved 500 Mhz in Kyber-R1 and Kyber-R2 implementation

  • Result benchmark on Zynq UltraScale ZCU104

HLS vs RTL resources utilization

  • HLS increases resources in range 3-70% in LUT, Slices, FF and decrease frequency about 5-11%.

Speedup of Software/Hardware Co-Design vs Software Only

RTL and SDSoC implementation run at their maximum frequency

  • Both has similar clock cycles

  • RTL + Bare Metal: High frequency and minimal transfer overhead

  • SDSoC + HLS: Slower frequency and higher transfer overhead

  • Both approaches give very close result.

Speedup: Encapsulation

Higher is better

Speedup: Decapsulation

Higher is better

Conclusion

  • BD/HLS approach give similar speedup as traditional RTL implementation.

  • BD/HLS has smaller in term of resources utilization and faster in term of cycle count than SE/HLS

  • BD/HLS is much more efficient than SE/HLS in NTT implementation

References

  • [1] F. Farahmand, V. B. Dang, D. T. Nguyen, and K. Gaj, “Evaluating the potential for hardware acceleration of Four NTRU-based key encapsulation mechanisms using Software/Hardware Codesign,” in PQCrypto, 2019, pp. 23–43.

  • [2] E. C.-h. Chu and A. George, Inside the FFT Black Box: Serial and Parallel Fast Fourier Transform Algorithms, ser. Computational Mathematics Series.

  • [3] C. Du, G. Bai, and X. Wu, “High-Speed Polynomial Multiplier Architecture for Ring-LWE Based Public Key Cryptosystems,”

References

  • [4] P. Longa, M. Naehrig, P. Longa, and M. Naehrig, “Speeding up the Number Theoretic Transform for Faster Ideal Lattice-Based Cryptography,” in Cryptology and Network Security - CANS 2016, vol. 10052.

  • [5] T. Poppelmann and T. Guneysu, “Towards Efficient Arithmetic for Lattice-Based Cryptography on Reconfigurable Hardware,” in LATINCRYPT 2012.

  • [6] T. Oder and T. Guneysu, “Implementing the NewHope-Simple Key Exchange on Low-Cost FPGAs,” in LATINCRYPT 2017, Havana, Cuba, Sep. 2017

References

  • [7] P.-C. Kuo et al., “High Performance Post-Quantum Key Exchange on FPGAs,”Cryptology ePrint Archive 2017/690, Feb. 2018

  • [8] E. Homsirikamol and K. Gaj, “Hardware Benchmarking of Cryptographic Algorithms Using HLS Tools: The SHA-3 Contest Case Study” in ARC 2015

  • [9] E. Homsirikamol and K. Gaj, "A new HLS-based methodology for FPGA benchmarking of candidates in cryptographic competitions: The CAESAR contest case study” inFPT 2017