Configurable lattice cryptography processor for the quantum-secure internet of things and related techniques

Patent metadata

Field	Value
Publication number	US-11416638-B2
Application number	US-202016794746-A
Country	US
Kind code	B2
Filing date	Feb 19, 2020
Priority date	Feb 19, 2019
Publication date	Aug 16, 2022
Grant date	Aug 16, 2022

Abstract

Described is a lattice cryptography processor with configurable parameters. The lattice cryptography processor includes a sampling circuit configured to operate in accordance with a Secure Hash Algorithm 3 (SHA-3)-based pseudo-random number generator (PRNG), a single-port random access memory (RAM)-based number theoretic transform (NTT) memory architecture and a modular arithmetic unit. The described lattice cryptography processor is configured to be programmed with custom instructions for polynomial arithmetic and sampling. The configurable lattice cryptography processor may operate with lattice-based CCA-secure key encapsulation and a variety of different lattice-based protocols including, but not limited to: 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.

First claim

What is claimed is:

1. A lattice cryptography processor comprising:
an instruction memory configured to have stored therein one or more of configurable parameters and/or custom instructions for polynomial sampling and/or arithmetic operations for controlling the operation of the lattice cryptography processor;
one or more cache memories;
a configurable modular arithmetic unit (MAU) coupled to the one or more cache memories, the configurable modular arithmetic unit to perform polynomial operations;
a core, coupled to the one or more cache memories, the core for hashing and pseudo-random number generation (PRNG); and
a discrete distribution sampler coupled to the core and configured to sample a polynomial sequence provided by the MAU, the discrete distribution sampler configured for operation in a plurality of different sampling modes and coupled to receive information from the instruction memory and wherein, in response to instructions provided by the instruction memory, the discrete distribution sampler operates in a selected one of the plurality of different sampling modes.

2. The lattice cryptography processor of claim 1 wherein the discrete distribution sampler can operate in any of: a uniform sampling mode; a binomial sampling mode; a Gaussian sampling mode; a trinary sampling mode; and a rejection sampling mode.

3. The lattice cryptography processor of claim 1 wherein the configurable modular arithmetic unit comprises a butterfly configured to operate in either of a decimation-in-frequency (DIF) mode or a decimation-in-time (DIT) mode.

4. The lattice cryptography processor of claim 1 wherein the one or more cache memories comprise one or more single port random access memories (RAMs).

5. The lattice cryptography processor of claim 1 wherein the configurable modular arithmetic unit, the cache, the core and the discrete distribution sampler are configured to operate in accordance with Ring-LWE and Module-LWE algorithms.

6. The lattice cryptography processor of claim 1 wherein the instruction memory is configured to be programmed with custom instructions to implement a plurality of lattice-based algorithms.

7. The lattice cryptography processor of claim 1 wherein the discrete distribution sampler samples polynomials via one of a: uniform sampling; or a discrete distribution sampling.

8. The lattice cryptography processor of claim 7 wherein the polynomials are generated, or sampled, either uniformly through rejection sampling or from a discrete binomial distribution.

9. The lattice cryptography processor of claim 1 wherein the configurable modular arithmetic unit is configured to perform polynomial operations including a number theoretic transform (NTT).

10. The lattice cryptography processor of claim 9 wherein computing a convolution of two polynomials comprises transforming the polynomials to the NTT domain followed by coefficient-wise multiplication and an inverse transform.

11. The lattice cryptography processor of claim 1 wherein the cache is provided as an LWE cache.

12. A quantum-secure internet of things (IoT) device comprising:
a configurable modular lattice cryptography processor comprising:
an instruction memory configured to have stored therein one or more of configurable parameters and/or custom instructions for polynomial sampling and/or arithmetic operations for controlling the operation of the configurable modular lattice cryptography processor;
a cache;
a modular arithmetic unit (MAU) coupled to the cache, the modular arithmetic unit to perform polynomial operations including a number theoretic transform (NTT);
a core, coupled to the cache, the core for hashing and pseudo-random number generation (PRNG);
a discrete distribution sampler coupled to the core wherein the cache, the core and the discrete distribution sampler have dedicated clock gates which can be independently configured for fine-grained power savings, and wherein the discrete distribution sampler is further configured to sample a polynomial sequence provided by the MAU, the discrete distribution sampler configured for operation in a plurality of different sampling modes and coupled to receive information from the instruction memory and wherein, in response to instructions provided by the instruction memory, the discrete distribution sampler operates in a selected one of the plurality of different sampling modes.

13. The IoT device of claim 12 wherein the lattice cryptography processor is provided as an integrated circuit.

14. The IoT device of claim 12 wherein the lattice cryptography integrated circuit comprises hardware-accelerated quantum-resistant lattice-based cryptographic protocols that can be used to secure the IoT device.

15. The IoT device of claim 12 wherein the discrete distribution sampler is configured to operate in any of: a uniform sampling mode, a binomial sampling mode, a Gaussian sampling mode, a trinary sampling mode and a rejection sampling mode.

16. The IoT device of claim 12 wherein the configurable modular arithmetic unit is provided in a butterfly configuration and may be configured to operate in either of: a DIF mode; or a DIT mode.

17. The IoT device of claim 12 wherein the lattice cryptography processor comprises one or more single port random access memories (RAMs).

18. A discrete distribution sampler comprising:
a pseudo-random number generator (PRNG) core;
means, coupled to an output of the PRNG core, for applying a bit mask to an output signal provided at the output of the PRNG core; and
a sampler circuit coupled to receive an output of the means for applying a bit mask and to provide a sampled output signal at a sampler circuit output, wherein the sampler circuit is configured for operation in a plurality of different sampling modes and is configured to receive information from an instruction memory and wherein, in response to instructions provided by the instruction memory, the discrete distribution sampler operates in a selected one of the plurality of different sampling modes; and
a combiner configured to receive and combine sampled output signals from the sampler circuit output and to provide a combiner output signal.

19. The discrete distribution sampler of claim 18 wherein the sampler circuit is configured to operate as any of:
a rejection sampler;
a binomial sampler;
a uniform sampler;
a Gaussian sampler; and
a trinary sampler.

Assignees

• Massachusetts Inst Technology

Inventors

• Banerjee Utsav
• Chandrakasan Anantha P

Classifications

• G06F7/582

  Pseudo-random number generators · CPC title

• G06F17/144

  Prime factor Fourier transforms, e.g. Winograd transforms, number theoretic transforms · CPC title

• H04L9/0631

  Substitution permutation network [SPN], i.e. cipher composed of a number of stages or rounds each involving linear and nonlinear transformations, e.g. AES algorithms · CPC title

• G06F21/72 Primary

  in cryptographic circuits · CPC title

• H04L9/3093

  involving Lattices or polynomial equations, e.g. NTRU scheme · CPC title