Various embodiments relate to a method for multiplying a first and a second polynomial in a ring .sub.q[X]/(X.sup.n+1) to perform a cryptographic operation in a data processing system where q is a positive integer, the method for use in a processor of the data processing system, comprising: receiving the first polynomial and the second polynomial by the processor; mapping the first polynomial into k smaller third polynomials over k smaller rings based upon primitive roots of unity, where k is a positive integer; mapping the second polynomial into k smaller fourth polynomials over the k smaller rings based upon primitive roots of unity; applying an isomorphism to the k third polynomials resulting in k fifth polynomials; applying the isomorphism to the k fourth polynomials resulting in k sixth polynomials; applying a Kronecker substitution on the k fifth polynomials and the k sixth polynomials and perform the multiplication of the k fifth polynomials and the k sixth polynomials to produce a multiplication result; applying an inverse of the isomorphism to the multiplication result to obtain the multiplication of the first polynomial and the second polynomial; and mapping the k inverted polynomials to a single polynomial in the ring mapping the k inverted polynomials to a single polynomial in the ring .sub.q[X]/(X.sup.n+1.

A modular polynomial multiplier includes a plurality of processing elements. Each includes a multiplication unit, an addition unit and a delay unit. The addition unit has an input connected to the output of the multiplication unit. The delay unit is connected to the output of the addition unit delays values by one clock cycle. The first input of the multiplication unit of each processing element carries a respective coefficient of a first polynomial and the second input of the multiplication unit of each processing element is connected to one of an input line carrying a sequence of coefficients of a second polynomial having n coefficients and a delay line carrying the sequence of coefficients of the second polynomial delayed by n clock cycles and negated.

A circuit system for performing modular reduction of a modular multiplication includes multiplier circuits that receive a first subset of coefficients that are generated by summing partial products of a multiplication operation that is part of the modular multiplication. The multiplier circuits multiply the coefficients in the first subset by constants that equal remainders of divisions to generate products. Adder circuits add a second subset of the coefficients and segments of bits of the products that are aligned with respective ones of the second subset of the coefficients to generate sums.

Cryptographic-related processing is performed using an n-bit accelerator. The processing includes providing a binary operand to a multiply-and-accumulate unit of the n-bit accelerator. The multiply-and-accumulate unit performs an operation using the binary operand and a predetermined fractional constant F to obtain an operation result, and rounds the operation result by discarding x least-significant bits of the operation result to obtain a fractionally-scaled result, where x is a configurable number of bits to discard from the operation result, and the fractionally-scaled result facilitates performing the cryptographic-related processing.

Methods, apparatus, systems, and articles of manufacture are disclosed. An example apparatus includes: interface circuitry to receive a first value and a second value; selector circuitry to select a first subset of bits and a second subset of bits from the first value; multiplier circuitry to: multiply the first subset to the second value during a first compute cycle; and multiply the second subset to the second value during a second compute cycle; left shift circuitry to perform a bitwise shift with a product of the first subset and the second value during the second compute cycle; adder circuitry to add a product of the second subset and the second value to a result of the plurality of bitwise shift operations during the second compute cycle; and comparator circuitry to determine the result of the modular multiplication based on a result of the addition during the second compute cycle.

Disclosed is a ciphertext computation method. The ciphertext computation method includes: receiving a modular computation command for a plurality of ciphertexts; performing a modular computation for the plurality of ciphertexts by using a lookup table storing a plurality of predetermined prime number information; and outputting a result of the computation.

Disclosed herein is an apparatus for calculating a cryptographic component R.sup.2 mod n for a cryptographic function, where n is a modulo number and R is a constant greater than n. The apparatus comprises a processor configured to set a start value to be equal to R mod n, perform b iterations of a shift and subtract operation on the start value to produce a base value, wherein the start value is set to be equal to the base value after each iteration, set a multiplication operand to be equal to the base value, and perform k iterations of a Montgomery modular multiplication of the multiplication operand with the multiplication operand to produce an intermediate result, wherein the multiplication operand is set to be equal to the intermediate result after each iteration, wherein the shift and subtract operation comprises determining a shifted start value which is equivalent to the start value multiplied by two, and subtracting n from the shifted start value if the shifted start value is greater than or equal to n.

A method for generating a key stream according to an embodiment includes generating r round keys that are each N-dimensional integer vectors including elements of an integer set defined based on a prime number t, based on a random bit string, an encryption counter, and a secret key that is an N-dimensional integer vector consisting of elements of the integer set , generating a first round output vector x.sub.1 by performing a modular addition operation on an initial vector and a first round key RK.sub.1 of the r round keys with the prime number t as a modulus, and generating a key stream that is an N-dimensional integer vector consisting of elements of the integer set from the first round output vector x.sub.1 by using a second to r-th round keys of the r round keys, and one or more first round functions and a second round function.

Polynomial multiplication for side-channel protection in cryptography is described. An example of a apparatus includes one or more processors to process data; a memory to store data; and polynomial multiplier circuitry to multiply a first polynomial by a second polynomial, the first polynomial and the second polynomial each including a plurality of coefficients, the polynomial multiplier circuitry including a set of multiplier circuitry, wherein the polynomial multiplier circuitry is to select a first coefficient of the first polynomial for processing, and multiply the first coefficient of the first polynomial by all of the plurality of coefficients of the second polynomial in parallel using the set of multiplier circuits.

One embodiment provides a processor comprising first circuitry to decode an instruction into a decoded instruction, the instruction to indicate a first source operand and a second source operand and second circuitry including a processing resource to execute the decoded instruction, wherein responsive to the decoded instruction, the processing resource is to output a result of first source operand data minus second source operand data in response to a determination by the processing resource that the first source operand data is greater than or equal to the second source operand data, otherwise the processing resource is to output the first source operand data.