Single stage multiply-accumulate (MAC) butterfly multiplier circuit for number theoric transforms
Disclosed are systems, apparatuses, processes, and computer-readable media for sharing encrypted entropy. For example, a method includes determining a plurality of second coefficients from a plurality of first coefficients in association with a Numeric Theoric Transform (NTT), wherein each second coefficient of the plurality of second coefficients is generated based on a corresponding first coefficient of the plurality of first coefficients using a shared stage multiplier circuit; and generating an encryption key based on the plurality of second coefficients.
1 . An apparatus for Number Theoric Transform (NTT) computations, the apparatus comprising:
a butterfly multiply-accumulate (MAC) circuit for calculating output coefficients based on input coefficients and a polynomial value; and
a multiplexer for selecting the input coefficients and the polynomial value to input into the butterfly MAC circuit based on a computation stage of an NTT computation, wherein the butterfly MAC circuit is configured to output point-wise coefficients for the NTT computation based on the computation stage.
2 . The apparatus of claim 1 , wherein the butterfly MAC circuit comprises:
a modulo precompute circuit configured to generate a modulo associated with the polynomial value;
a partial multiplier configured to generate partial products of the modulo and a first input value; and
a MAC circuit configured to solve the partial products.
3 . The apparatus of claim 1 , wherein:
the NTT computation includes a first stage, a second stage, and a third stage; and
the butterfly MAC circuit is configured to output the point-wise coefficients at the third stage.
4 . The apparatus of claim 3 , wherein the multiplexer is configured to input coefficients generated by the butterfly MAC circuit during the first stage to the butterfly MAC circuit during the second stage.
5 . The apparatus of claim 3 , wherein the multiplexer is configured to input coefficients generated by the butterfly MAC circuit during the second stage to the butterfly MAC circuit during the third stage.
6 . The apparatus of claim 3 , wherein the polynomial value comprises a plurality of polynomial values and the multiplexer is configured to select a corresponding polynomial value of the plurality of polynomial values at each of the first stage, the second stage, and the third stage.
7 . The apparatus of claim 1 , wherein the butterfly MAC circuit is configured to concurrently compute two pairs of point-wise coefficients.
8 . The apparatus of claim 1 , further comprising:
a first delay disposed between the multiplexer and the butterfly MAC circuit; and
a second delay disposed between a feedback loop from the butterfly MAC circuit and the multiplexer.
9 . The apparatus of claim 1 , wherein the butterfly MAC circuit is configured to generate partial products corresponding to a Booth Radix 4 scheme and solve the partial products.
10 . The apparatus of claim 1 , further comprising:
a processor configured to generate an encryption key or a decryption key based on the point-wise coefficients.
11 . A method of performing a post quantum cryptography function, comprising:
determining a plurality of second coefficients from a plurality of first coefficients in association with a Numeric Theoric Transform (NTT), wherein each second coefficient of the plurality of second coefficients is generated based on a corresponding first coefficient of the plurality of first coefficients using a shared stage multiplier circuit; and
generating an encryption key based on the plurality of second coefficients.
12 . The method of claim 11 , further comprising:
encrypting content in a message based on the encryption key.
13 . The method of claim 11 , further comprising:
generating an encrypted signature to include in a message based on the encryption key.
14 . The method of claim 11 , further comprising:
decrypting content in a message based on the encryption key.
15 . The method of claim 11 , further comprising:
validating a signature in a message based on the encryption key.
16 . The method of claim 11 , further comprising:
performing a point-wise multiplication based on the plurality of second coefficients.
17 . The method of claim 11 , wherein determining the plurality of second coefficients comprises:
generating a first value based on a first coefficient using the shared stage multiplier circuit;
generating a second value based on the first value using the shared stage multiplier circuit; and
generating the plurality of second coefficients based on the second value using the shared stage multiplier circuit.
18 . The method of claim 11 , further comprising:
generating interim values based on the plurality of first coefficients using the shared stage multiplier circuit;
feeding the interim values back into the shared stage multiplier circuit based on computation stages; and
outputting the plurality of second coefficients when a last stage of the computation stages is reached.
19 . The method of claim 18 , wherein the generating of the interim values comprises:
generating first values based on encoding and performing a modulo operation on input values into the shared stage multiplier circuit; and
multiplying the first values using a MAC circuit.
20 . The method of claim 11 , further comprising:
joining mirrored second coefficients into the plurality of second coefficients based on a symmetry.