PaperlayerView exact revision on arXiv

Source-linked AI summary

Sapphire: A Configurable Crypto-Processor for Post-Quantum Lattice-based Protocols

Utsav Banerjee, Tenzin S. Ukyab, Anantha P. Chandrakasan

arXiv:1910.07557v2cs.CRcs.AR

TL;DR

Quantum algorithms threaten conventional public-key protocols, while the computational complexity of lattice-based schemes complicates deployment on low-power embedded devices. Sapphire addresses this gap with a configurable lattice cryptography processor integrating efficient arithmetic, sampling, NTT memory, and programmable control. Across demonstrated NIST Round 2 protocols, it achieves up to an order of magnitude improvement in performance and energy-efficiency, with timing and simple-power-analysis protections and programmable support for masking countermeasures.

  • Problem

    High computational complexity makes lattice-based cryptographic protocols challenging to implement efficiently on low-power embedded devices, despite their post-quantum promise.

  • Method

    Sapphire combines configurable low-power modular arithmetic, efficient SHA-3-based sampling, single-port SRAM-based NTT memory, and programmable custom instructions with a RISC-V processor.

  • Results

    Up to an order of magnitude improvement in performance and energy-efficiency is achieved across demonstrated NIST Round 2 lattice-based key encapsulation and signature protocols.

  • Takeaways & Limitations

    Sapphire supports multiple lattice-based protocol parameter sets in a low-power ASIC while providing constant-time timing and simple-power-analysis security.

  • Takeaways & Limitations

    The protocol implementations have no explicit DPA countermeasures, although masking-based protections can be implemented through the processor’s programmability.

Abstract

from arXiv · show

Public key cryptography protocols, such as RSA and elliptic curve cryptography, will be rendered insecure by Shor's algorithm when large-scale quantum computers are built. Cryptographers are working on quantum-resistant algorithms, and lattice-based cryptography has emerged as a prime candidate. However, high computational complexity of these algorithms makes it challenging to implement lattice-based protocols on low-power embedded devices. To address this challenge, we present Sapphire - a lattice cryptography processor with configurable parameters. Efficient sampling, with a SHA-3-based PRNG, provides two orders of magnitude energy savings; a single-port RAM-based number theoretic transform memory architecture is proposed, which provides 124k-gate area savings; while a low-power modular arithmetic unit accelerates polynomial computations. Our test chip was fabricated in TSMC 40nm low-power CMOS process, with the Sapphire cryptographic core occupying 0.28 mm2 area consisting of 106k logic gates and 40.25 KB SRAM. Sapphire can be programmed with custom instructions for polynomial arithmetic and sampling, and it is coupled with a low-power RISC-V micro-processor to demonstrate NIST Round 2 lattice-based CCA-secure key encapsulation and signature protocols Frodo, NewHope, qTESLA, CRYSTALS-Kyber and CRYSTALS-Dilithium, achieving up to an order of magnitude improvement in performance and energy-efficiency compared to state-of-the-art hardware implementations. All key building blocks of Sapphire are constant-time and secure against timing and simple power analysis side-channel attacks. We also discuss how masking-based DPA countermeasures can be implemented on the Sapphire core without any changes to the hardware.

1 Introduction

Sapphire addresses the implementation difficulty of lattice-based post-quantum cryptography on low-power embedded devices with a configurable processor. Its hardware techniques support multiple protocols while improving efficiency and maintaining timing and simple-power-analysis security.

  • Motivation: Large-scale quantum computers threaten RSA and ECC through Shor’s algorithm, motivating quantum-secure public-key cryptography.Lattice-based cryptography is presented as a promising post-quantum candidate.
  • Motivation: Existing ASIC implementations of lattice-based cryptography either lack configurability or incur power and area overheads.Sapphire addresses these challenges through combined architectural and algorithmic techniques.
  • Contributions: Sapphire combines configurable low-power modular arithmetic, a single-port SRAM-based NTT memory architecture, and efficient sampling.The processor integrates these blocks with instruction memory and decoding for programmable polynomial arithmetic and sampling.
  • Contributions: 124k-gate area savings are provided by the single-port SRAM-based NTT memory architecture without performance or energy-efficiency loss.The architecture targets the memory overhead of NTT computation.
  • Evaluation: More than an order of magnitude improvement in performance and energy-efficiency is achieved across several NIST Round 2 lattice-based protocols.Demonstrated protocols include Frodo, NewHope, qTESLA, CRYSTALS-Kyber, and CRYSTALS-Dilithium.

2 Background

This section introduces LWE and its Ring-LWE and Module-LWE variants, then explains NTT-based polynomial multiplication and constant-time sampling. These mathematical structures and computations motivate the processor’s arithmetic and sampling-oriented design.

  • LWE: LWE samples combine a public vector, an inner product with a secret vector, and an error term that should conceal the secret.The secret-recovery problem underlies several lattice-based cryptographic schemes.
  • Ring-LWE: Ring-LWE replaces expensive LWE matrix operations with polynomial operations in Rq, reducing computational and key-size costs.The ring is defined as Rq = Zq[x]/(x^n + 1).
  • Module-LWE: Module-LWE provides a middle ground by reducing Ring-LWE’s algebraic structure while retaining much of its computational efficiency.It uses module lattices and supports parameters used by CRYSTALS-Kyber.
  • Number Theoretic Transform: NTT arithmetic uses an n-th primitive root of unity in Zq, requiring a prime modulus satisfying q ≡ 1 mod n.The inverse NTT replaces the root with its inverse and divides the final result by n.
  • Number Theoretic Transform: The NTT computes polynomial products in O(n lg n) time instead of O(n^2) schoolbook time by transforming, multiplying coefficient-wise, and applying the inverse transform.The product is expressed as c = INTT(NTT(a) ⊙ NTT(b)).
  • Sampling: Accurate, constant-time sampling generates public values, secrets, and errors while preventing side-channel leakage of secret information.Public vectors use uniform sampling over Zq, whereas secrets and errors use the distribution χ.

3 Modular Arithmetic and NTT

Sapphire combines configurable modular arithmetic with a single-port SRAM-based NTT architecture to reduce energy, area, and implementation complexity for lattice-polynomial computations. The design supports configurable or pseudo-configurable moduli, single-cycle butterflies, and efficient polynomial storage while maintaining strong measured NTT efficiency.

  • Modular Arithmetic: Sapphire’s 24-bit ALU supports configurable-q modular addition, subtraction, multiplication, and bitwise operations for polynomial arithmetic.The modular arithmetic core combines a 24-bit adder, subtractor, multiplier, and reduction logic; conditional operations are computed in the same cycle to avoid timing side-channels.
  • Modular Arithmetic: Two Barrett-reduction multiplier architectures trade flexibility for efficiency: fully configurable q supports arbitrary primes, while pseudo-configurable q targets a fixed prime set.The fully configurable design uses inputs m and k and three multipliers; the pseudo-configurable design hard-codes reduction parameters and selects among dedicated blocks.
  • Modular Arithmetic: Up to 3× lower modular-multiplication energy is achieved by the pseudo-configurable reduction datapaths, with reduction energy up to 6× lower than in the fully configurable design.Multiplication energy is the same in both architectures; the reduction savings produce the reported overall improvement, while power gating limits activity in unused dedicated blocks.
  • NTT Computation: The unified butterfly supports both Cooley-Tukey and Gentleman-Sande NTT configurations, reusing modular arithmetic blocks for polynomial operations and negative-wrapped convolution.The DIT butterfly computes (a + ωb mod q, a −ωb mod q), while the DIF butterfly computes (a + b mod q, (a −b)ω mod q).
  • NTT Memory Architecture: The NTT twiddle-factor memory is reduced by 37.5% to 15 KB, while the hardware NTT reaches up to 11× software energy efficiency and 2.5× efficiency versus a fast ASIC design.The NTT computes one butterfly per cycle with single-port SRAMs and is almost twice as fast as the cited implementation, although it remains about 4× less energy-efficient than the most parallel design.

4 Discrete Distribution Sampler

Sapphire combines a configurable Keccak-based PRNG with specialized rejection, binomial, discrete Gaussian, and trinary samplers for lattice-based protocols. These designs reduce sampling overhead while supporting varied distribution parameters and constant-time operation.

  • Sampling is a major computational overhead in software implementations of ideal and module lattice-based protocols.
  • A 24-cycle Keccak-f[1600] core supports configurable SHA-3 modes and processes its 1600-bit state in parallel.The core consumes 2.33 nJ per round at 1.1 V and 0.89 nJ per round at 0.68 V.
  • Fast rejection sampling scales the acceptance bound from q to kq, reducing rejection probability for suitable primes.For q = 12289, the cited example reduces rejection probability from 25% to 6% using k = 5.
  • The binomial sampler configures k up to 32, enabling different standard deviations, and is more than two orders of magnitude more energy-efficient than ARM Cortex-M4 software.It is also reported as 14× more efficient than a hardware implementation using Knuth-Yao sampling with ChaCha20.
  • The discrete Gaussian sampler uses constant-time inversion over a configurable cumulative distribution table, achieving up to 40× improved energy-efficiency after voltage scaling.The implementation supports s ≤64 and r ≤32; the cited hardware comparisons target distributions with larger standard deviation and higher precision.
  • Trinary sampling supports fixed nonzero counts, separate +1 and −1 counts, and distributions with ρ from 1/2 to 1/128.

5 Chip Architecture

Sapphire integrates configurable polynomial arithmetic, NTT, and sampling hardware with custom instructions, internal memory, and a low-power RISC-V processor. The fabricated core emphasizes compact area, configurable protocol execution, and measured low-power operation.

  • A 1 KB instruction memory and decoder integrate Sapphire’s arithmetic, transform, and sampling blocks into a programmable crypto-processor.The processor uses 32-bit custom instructions for polynomial arithmetic, transforms, sampling, and simple branching.
  • Sapphire configures protocol parameters n and q and accesses cached polynomials through instruction arguments, supporting different lattice-protocol computations.The examples cover NewHope-1024 and CRYSTALS-Kyber-512, with just-in-time matrix generation used for Kyber to save memory.
  • The crypto-processor is coupled through a memory-mapped interface to a low-power RV32IM RISC-V processor with 32 KB instruction memory and 64 KB data memory.
  • The fabricated Sapphire core occupies 0.28 mm2 with 106k logic gates and 40.25 KB SRAM in TSMC 40nm LP CMOS.The chip supports supply-voltage scaling from 0.68 V to 1.1 V.
  • Measured average lattice crypto-processor power is around 8 mW at 1.1 V and 72 MHz, or 520 µW at 0.68 V and 12 MHz.Dedicated clock gates support submodule power measurement and fine-grained dynamic power savings.

6 Protocol Implementations and Measurement Results

Sapphire implements and measures configurable lattice-based protocols on a test chip, using custom hardware acceleration for arithmetic, sampling, transforms, and data movement. Across evaluated protocols, it reports substantial performance and energy-efficiency gains, while side-channel analysis supports SPA resistance and programmable masking remains a separate countermeasure path.

  • Protocol implementations: The test chip evaluates NIST Round 2 lattice-based protocols using Sapphire custom programs for polynomial arithmetic, transforms, sampling, and SHA-3.The RISC-V processor handles data and program transfers, randomness generation, encoding, and compression tasks.
  • Protocol implementations: 10–20% fewer cycles result from directly post-processing crypto-processor memory outputs and strategically gating internal clocks during execution.These techniques avoid intermediate temporary arrays and reduce energy consumption.
  • Measurement results: Frodo uses tiled arrays for non-power-of-two matrix dimensions, but Frodo-1344 decapsulation exceeds the 64 KB processor memory and is evaluated only in simulation.Its power is extrapolated from measured Frodo-640 and Frodo-976 power, and the tiling makes the implementation incompatible with reference software.
  • Measurement results: Up to an order of magnitude improvement in energy-efficiency and performance is achieved over assembly-optimized Cortex-M4 software for the evaluated implementations.The comparison uses average cycle counts for 100 executions, including crypto-processor input and output transfer overhead.
  • Measurement results: Two orders of magnitude higher efficiency distinguishes NewHope and CRYSTALS-Kyber from Frodo among the evaluated key encapsulation schemes.The paper attributes this difference to polynomial multiplication in ideal and module lattices versus matrix multiplication in standard lattices.
  • Side-channel analysis: Preliminary difference-of-means tests for NTT, coefficient-wise multiplication, and addition validate resistance to simple power-analysis attacks.The tests use n = 1024 and q = 12289 at 1.1 V and 10 MHz with 99.99% confidence intervals.
  • Side-channel analysis: Baseline protocol implementations lack explicit DPA countermeasures, while programmable custom programs can implement masking-based protection with about 3× lower efficiency for masked NewHope decryption.The reported penalty applies to both energy and performance relative to the unmasked version.

7 Conclusion and Future Work

Sapphire is a configurable lattice cryptography processor supporting multiple NIST Round 2 protocols, with reported improvements in performance and energy-efficiency. Future work includes broader protocol support and more concrete DPA-secure masked-implementation analysis.

  • Sapphire supports configurable parameters for NewHope, qTESLA, CRYSTALS-Kyber, CRYSTALS-Dilithium and Frodo.
  • An order of magnitude improvement in performance and energy-efficiency is reported against state-of-the-art software and hardware implementations.
  • The ASIC was fabricated in a 40nm low-power CMOS process, with measurements obtained from a test chip operating at 1.1 V and 72 MHz.
  • The protocol implementations are secure against timing and simple power analysis attacks, while masking countermeasures against differential power analysis are discussed.
  • Future work covers Saber and Round5, concrete masked implementations with leakage tests, and non-lattice post-quantum protocols.

Appendix A Modular Reduction Parameters

The appendix lists Barrett-reduction parameters and instruction fragments for selected prime moduli. Each reduction computes z = x mod q using modulus-specific constants, shifts, additions, subtractions, and conditional correction.

  • Barrett reduction uses coded parameters m, k and q for a set of chosen primes.
  • For q = 7681, the reduction uses m = 273 and k = 21 before conditional subtraction of q.
  • For q = 12289, the reduction uses m = 10921 and k = 27 before conditional subtraction of q.
  • For q = 65537, the special structure q = 2^16 + 1 enables reduction through x0 − x1 + x2 followed by conditional correction.

Appendix B Custom Instruction Set Summary

Sapphire exposes custom instructions for configuration, registers, polynomial operations, transforms, sampling, comparisons, and SHA-3 computations. These instructions support configurable polynomial arithmetic and distribution sampling through programmable parameters and seed registers.

  • Register and processor state: The processor provides internal polynomial memory, 256-bit seed registers r0 and r1, temporary registers, counters, and a comparison flag register.
  • Configuration: Configuration instructions set parameters and clock gates through clock_config (keccak, ntt, sampler).
  • Transforms: Transform instructions support DIF_NTT, DIF_INTT, DIT_NTT and DIT_INTT modes, including multiplication by ψ and ψ^-1.
  • Sampling: Sampling instructions generate polynomials from binomial, CDT, rejection, uniform and triangular distributions with configurable distribution parameters.
  • Polynomial computations: Polynomial instructions provide copying, arithmetic operations and shifts over rings x^N+1 or x^N−1.
  • SHA-3 computations: SHA-3 instructions absorb polynomial or seed-register data using SHA3-256 or SHA3-512, storing outputs in r0, r1 or both registers.
Loading 1910.07557v2…