Bringing quantum computers online and to market could one day enable advances in areas such as medical research, but if hackers get access, they could potentially break through the powerful encryption schemes that currently protect data exchanged between devices.
Today’s most promising quantum-resistant encryption scheme is called “lattice-based cryptography,” which hides information in complex mathematical structures. To date, no known quantum algorithm can break through its defences. But these schemes are way too computationally intense for IoT devices, which can only spare enough energy for simple data processing.
Now, MIT researchers describe a new kind of circuit architecture and statistical optimisation tricks that can be used to efficiently compute lattice-based cryptography. The 2mm2 chips are said to be efficient enough for integration into any current IoT device.
The architecture is customisable to accommodate the multiple lattice-based schemes currently being studied in preparation for the day that quantum computers come online.
The researchers say the circuit is the first of its kind to meet standards for lattice-based cryptography set by the National Institute of Standards and Technology (NIST).
Generating random numbers is the most important part of all cryptography schemes, according to MIT. This is because those numbers are used to generate secure encryption keys that can’t be predicted. That’s calculated through a two-part process called “sampling.”
After analysing all available methods for sampling, the researchers found that one method, called SHA-3, can generate many pseudorandom numbers two or three times more efficiently than all others. They tweaked SHA-3 to handle lattice-based cryptography sampling. On top of this, they applied some mathematical tricks to make pseudorandom sampling, and the postprocessing conversion to new distributions, faster and more efficient.
They run this technique using energy-efficient custom hardware that takes up only 9 per cent of the surface area of their chip. In the end, this makes the process of sampling two orders of magnitude more efficient than traditional methods.
For their circuit design, the researchers modified a technique called “number theoretic transform” (NTT), which functions similarly to the Fourier transform mathematical technique that decomposes a signal into the multiple frequencies that make it up. The modified NTT splits vector data and allocates portions across four single-port RAM devices. Each vector can still be accessed in its entirety for sampling as if it were stored on a single multiport device. The benefit is the four single-port REM devices occupy about a third less total area than one multiport device.
“We basically modified how the vector is physically mapped in the memory and modified the data flow, so this new mapping can be incorporated into the sampling process. Using these architecture tricks, we reduced the energy consumption and occupied area, while maintaining the desired throughput,” said the first author of the paper, Utsav Banerjee, and a graduate student in electrical engineering and computer science.
The circuit also incorporates a small instruction memory component that can be programmed with custom instructions to handle different sampling techniques — such as specific probability distributions and standard deviations — and different vector sizes and operations. This is especially helpful, as lattice-based cryptography schemes will most likely change slightly in the coming years and decades.
