High-performance loop polynomial multiplier based on 22MDC NTT structure

Abstract

The invention discloses a high-performance loop polynomial multiplier based on a 22MDC NTT structure. The high-performance loop polynomial multiplier comprises a plurality of delay switching circuits used for carrying out NTT conversion. The multi-path delay switching circuit is of a four-input-output access structure and is composed of y-level processing units. Each stage of processing unit comprises a butterfly unit, a plurality of data delay units with different delay periods, a plurality of storage units used for storing twiddle factors required by NTT conversion and an exchange unit used for transmitting data downwards according to a correct time sequence according to an NTT algorithm; according to the invention, the number of stages of NTT is reduced through the high-base NTT algorithm, the effects of reducing the time period and high throughput rate are achieved during hardware implementation, and a control unit is simplified at the same time.

Description

technical field [0001] The present invention relates to lattice cipher ring polynomial multiplication, proposes a method based on base 2 2 High performance ring polynomial multiplier of MDC NTT structure. Background technique [0002] After the birth of quantum computers, the security of existing public-key cryptosystems such as RSA and elliptic curves may be shaken, but the security of lattice cryptography is based on the lattice difficulty problem in the worst case, so its security is limited. Strong guarantee against quantum computer attacks. In addition, the calculations in lattice cryptography are very simple. For ideal lattices and modular lattices, all algorithms are performed in polynomial rings. In many cases, only polynomial product modulo accumulation operations are required. [0003] Conventional polynomial multiplication does not need to consider the number field problem, but the polynomial on the ring has restrictions on the coefficients and degrees of the po...

AI Technical Summary

Problems solved by technology

[0021] If the NTT / INTT transformation formula is directly used, the computational complexity is not reduced. According to the periodicity of the twiddle factor, the researchers proposed to decompose the input sequence or output sequence into a shorter sequence and extract it by domain or frequency domain (often referred to as A decomposition algorithm called butterfly transform) iterative radix 2NTT structure, but when the polynomial coefficient is large, the time period of radix 2NTT will increase exponentially, for example, when n=256=2 8 =4 4 When selecting radix-8 or radix-16, a large amount of resources will be consumed, and the utilization rate of the butterfly unit is low. Considering that the radix-4 algorithm is more complicated and the amount of calculation is also large, so when the high-radix NTT transform is used, the number of butterfly transformations significantly reduced, then it is very meaningful to use high-based NTT / INTT transformation for polynomial multiplication

Images