Quantum Computing & NPUs

• CRQC = cryptographically relevant quantum computer
• PQC = Post-Quantum Cryptography

Shor’s Algorithm

• Purpose: Efficiently factors large integers and computes discrete logarithms.
• Impact: Breaks RSA, ECC, and other public-key cryptosystems.
• How It Works:
  • Uses quantum Fourier transform to find the period of a function related to modular exponentiation.
  • This period reveals factors of large numbers.
• Complexity: Runs in polynomial time on a quantum computer, versus exponential time on classical machines.
• Example: RSA-2048, which would take billions of years to break classically, could be cracked in hours with a sufficiently large quantum computer.

Grover’s Algorithm

• Purpose: Speeds up unstructured search problems (e.g., brute-force key search).
• Impact: Weakens symmetric cryptography (AES, SHA).
• How It Works:
  • Uses amplitude amplification to increase the probability of the correct solution.
  • Reduces search complexity from O(N) to O(√N).
• Example: AES-128 brute force goes from 2128 operations to about 264, so doubling key sizes mitigates this.

Key Difference:

• Shor’s: Targets asymmetric cryptography (public-key systems).
• Grover’s: Targets symmetric cryptography (block ciphers, hashes).

Current Questions

Warning

Without a sufficiently capable NPU, edge devices will not be able to maintain security in the quantum era.

Estimates put the first application specific fault-tolerant quantum computers from IBM, Google and Microsoft around 2030, with more broad versatile deployment from 2034 onwards. With this in mind, would you still consider clients with update cycles in the next 5 years or so should still consider NPU's for this purpose? What would be our case for promoting the security benefits of NPUs with this in mind?

Harvest Now, Decrypt Later: Adversaries can store encrypted data today and decrypt it later when quantum computers mature, making long-lived sensitive data (health records, government secrets) especially vulnerable

The U.S. National Institute of Standards and Technology (NIST) are finalizing three Post-Quantum Cryptography (PQC) standards: ML-KEM for encryption, ML-DSA for signatures, and SLH-DSA as a hash-based fallback. These lattice and hash-based algorithms anchor the NSA’s Commercial National Security Algorithm Suite 2.0 (CNSA 2.0), mandating federal PQC adoption by 2030.

Industry adoption:

• Finance: Major banks now use hybrid post-quantum and classical encryption for interbank transfers, citing a surge in quantum-targeted attacks.
• Healthcare: Leading hospitals deploy quantum key distribution (QKD) for patient data, combining photonic quantum states with post-quantum digital signatures.
• Tech: Major cloud providers enable automated crypto-agility, allowing clients to switch between classical and PQC algorithms dynamically.

Despite progress, challenges persist. NIST’s algorithms face scrutiny for larger key sizes, straining IoT devices. Moreover, new discoveries of side-channel attacks against some PQC candidates underscore the need for ongoing research and vigilance.

PQC Cryptography methods

Why They Will Be Required

• Quantum Threat:
  Shor’s algorithm will break RSA and ECC, which secure most of today’s internet.
• Standards:
  NIST selected Kyber and Dilithium as part of its official PQC standards (FIPS 203–205). Migration is expected by 2030–2035 for critical systems.
• Security Lifespan:
  Data encrypted today may need to remain secure for decades—so adopting PQC early prevents “harvest now, decrypt later” attacks.
  

Kyber (Key Encapsulation Mechanism)

• Type: Lattice-based algorithm for secure key exchange.
• How It Works:
  Uses module learning-with-errors (MLWE) problem, which is believed to be hard even for quantum computers.
• Purpose:
  Replaces RSA/ECC for establishing shared secrets between parties.
• Why Important:
  Quantum computers running Shor’s algorithm can break RSA/ECC, so Kyber ensures confidentiality in the post-quantum era.

Dilithium (Digital Signature Scheme)

• Type: Lattice-based signature algorithm.
• How It Works:
  Based on structured lattices and the hardness of the MLWE problem.
• Purpose:
  Provides authentication and integrity (like RSA/ECC signatures today).
• Why Important:
  Digital signatures underpin everything from software updates to secure transactions. Without PQC, these would be forgeable by quantum computers.

Role of NPUs and Hardware Acceleration

Why NPUs?

PQC algorithms like Kyber and Dilithium involve:

Role of NPUs and Hardware Acceleration

• Why NPUs?
  PQC algorithms like Kyber and Dilithium involve:

  • Large matrix multiplications
  • Polynomial arithmetic
  • Random sampling
    These operations resemble workloads in AI/ML, which NPUs are optimized for (parallelism, low-power compute).

• Benefits of NPUs for PQC:

  • Energy Efficiency: NPUs can handle these operations with lower power than CPUs/GPUs.
  • Latency Reduction: Dedicated hardware accelerators can cut PQC signature verification from hundreds of milliseconds to under 10 ms on constrained devices (as shown in OpenTitan research).

PQC Accelerators

• Definition: Specialized hardware blocks designed to accelerate post-quantum cryptographic operations such as key encapsulation (Kyber) and digital signatures (Dilithium).
• Focus: Optimized for integer arithmetic, modular reductions, and polynomial operations under lattice-based schemes.
• Goal: Reduce latency and energy consumption for PQC, especially on constrained devices like IoT and laptops.

How PQC Accelerators Differ from NPUs

Aspect	NPUs (Neural Processing Units)	PQC Accelerators
Primary Use	AI/ML inference (matrix/tensor ops)	Cryptographic operations (Kyber, Dilithium)
Data Types	Floating-point, low precision (FP16/INT8)	Integer arithmetic, modular math, high precision
Security Needs	Not security-critical	Must be tamper-resistant and side-channel safe
Workload Pattern	Dense linear algebra, predictable	Sparse polynomial ops, random sampling

Key Point: While both involve matrix-like operations, PQC requires exact integer math and strong security guarantees, which NPUs are not designed for.

Why PQC Accelerators Matter for Kyber and Dilithium

• Kyber:

• Heavy use of polynomial multiplication and modular reductions.

• PQC accelerators can implement Number Theoretic Transform (NTT) efficiently.

• Dilithium:

• Requires sampling from discrete distributions and hash-based commitments.

• Accelerators can offload these steps to reduce CPU load and latency.

• Performance Gains:

• Research shows PQC accelerators can cut signature verification from hundreds of ms to <10 ms on constrained devices.

• Energy savings up to 90% compared to CPU-only implementations.

Why Not Just Use NPUs?

• NPUs excel at approximate math for AI, not exact modular arithmetic.
• PQC accelerators need constant-time operations to prevent timing attacks.
• Security certification (FIPS, Common Criteria) requires dedicated crypto hardware.