intel::hexl Namespace Reference

Classes
class	AlignedAllocator
	Allocates memory aligned to Alignment-byte sized boundaries. More...
struct	AllocatorBase
	Base class for custom memory allocator. More...
struct	AllocatorInterface
	Helper memory allocation struct which delegates implementation to AllocatorImpl. More...
struct	MallocStrategy
	Allocater implementation using malloc and free. More...
class	MultiplyFactor
	Pre-computes a Barrett factor with which modular multiplication can be performed more efficiently. More...
class	NTT
	Performs negacyclic forward and inverse number-theoretic transform (NTT), commonly used in RLWE cryptography. More...

Typedefs
using	AllocatorStrategyPtr = std::shared_ptr< AllocatorBase >
template<typename T >
using	AlignedVector64 = std::vector< T, AlignedAllocator< T, 64 > >
	64-byte aligned memory allocator More...

Enumerations
enum	CMPINT {   CMPINT::EQ = 0, CMPINT::LT = 1, CMPINT::LE = 2, CMPINT::FALSE = 3,   CMPINT::NE = 4, CMPINT::NLT = 5, CMPINT::NLE = 6, CMPINT::TRUE = 7 }
	Represents binary operations between two boolean values. More...

Functions
void	EltwiseAddMod (uint64_t *result, const uint64_t *operand1, const uint64_t *operand2, uint64_t n, uint64_t modulus)
	Adds two vectors elementwise with modular reduction. More...
void	EltwiseAddMod (uint64_t *result, const uint64_t *operand1, uint64_t operand2, uint64_t n, uint64_t modulus)
	Adds a vector and scalar elementwise with modular reduction. More...
void	EltwiseCmpAdd (uint64_t *result, const uint64_t *operand1, uint64_t n, CMPINT cmp, uint64_t bound, uint64_t diff)
	Computes element-wise conditional addition. More...
void	EltwiseCmpSubMod (uint64_t *result, const uint64_t *operand1, uint64_t n, uint64_t modulus, CMPINT cmp, uint64_t bound, uint64_t diff)
	Computes element-wise conditional modular subtraction. More...
void	EltwiseFMAMod (uint64_t *result, const uint64_t *arg1, uint64_t arg2, const uint64_t *arg3, uint64_t n, uint64_t modulus, uint64_t input_mod_factor)
	Computes fused multiply-add (arg1 * arg2 + arg3) mod modulus element-wise, broadcasting scalars to vectors. More...
void	EltwiseMultMod (uint64_t *result, const uint64_t *operand1, const uint64_t *operand2, uint64_t n, uint64_t modulus, uint64_t input_mod_factor)
	Multiplies two vectors elementwise with modular reduction. More...
void	EltwiseReduceMod (uint64_t *result, const uint64_t *operand, uint64_t n, uint64_t modulus, uint64_t input_mod_factor, uint64_t output_mod_factor)
	Performs elementwise modular reduction. More...
void	EltwiseSubMod (uint64_t *result, const uint64_t *operand1, const uint64_t *operand2, uint64_t n, uint64_t modulus)
	Subtracts two vectors elementwise with modular reduction. More...
void	EltwiseSubMod (uint64_t *result, const uint64_t *operand1, uint64_t operand2, uint64_t n, uint64_t modulus)
	Subtracts a scalar from a vector elementwise with modular reduction. More...
void	CkksMultiply (uint64_t *result, const uint64_t *operand1, const uint64_t *operand2, uint64_t n, const uint64_t *moduli, uint64_t num_moduli)
	Computes CKKS multiplication. More...
void	CkksSwitchKey (uint64_t *result, const uint64_t *t_target_iter_ptr, uint64_t n, uint64_t decomp_modulus_size, uint64_t key_modulus_size, uint64_t rns_modulus_size, uint64_t key_component_count, uint64_t *moduli, const uint64_t **kswitch_keys, uint64_t *modswitch_factors)
	Computes CKKS key switching in-place. More...
bool	IsPowerOfTwo (uint64_t num)
	Returns whether or not num is a power of two. More...
uint64_t	Log2 (uint64_t x)
	Returns floor(log2(x)) More...
bool	IsPowerOfFour (uint64_t num)
uint64_t	MaximumValue (uint64_t bits)
	Returns the maximum value that can be represented using bits bits. More...
uint64_t	ReverseBits (uint64_t x, uint64_t bit_width)
	Reverses the bits. More...
uint64_t	InverseMod (uint64_t x, uint64_t modulus)
	Returns x^{-1} mod modulus. More...
uint64_t	MultiplyMod (uint64_t x, uint64_t y, uint64_t modulus)
	Returns (x * y) mod modulus. More...
uint64_t	MultiplyMod (uint64_t x, uint64_t y, uint64_t y_precon, uint64_t modulus)
	Returns (x * y) mod modulus. More...
uint64_t	AddUIntMod (uint64_t x, uint64_t y, uint64_t modulus)
	Returns (x + y) mod modulus. More...
uint64_t	SubUIntMod (uint64_t x, uint64_t y, uint64_t modulus)
	Returns (x - y) mod modulus. More...
uint64_t	PowMod (uint64_t base, uint64_t exp, uint64_t modulus)
	Returns base^exp mod modulus. More...
bool	IsPrimitiveRoot (uint64_t root, uint64_t degree, uint64_t modulus)
	Returns whether or not root is a degree-th root of unity mod modulus. More...
uint64_t	GeneratePrimitiveRoot (uint64_t degree, uint64_t modulus)
	Tries to return a primitive degree-th root of unity. More...
uint64_t	MinimalPrimitiveRoot (uint64_t degree, uint64_t modulus)
	Returns whether or not root is a degree-th root of unity. More...
template<int BitShift>
uint64_t	MultiplyModLazy (uint64_t x, uint64_t y_operand, uint64_t y_barrett_factor, uint64_t modulus)
	Computes (x * y) mod modulus, except that the output is in [0, 2 * modulus]. More...
template<int BitShift>
uint64_t	MultiplyModLazy (uint64_t x, uint64_t y, uint64_t modulus)
	Computes (x * y) mod modulus, except that the output is in [0, 2 * modulus]. More...
unsigned char	AddUInt64 (uint64_t operand1, uint64_t operand2, uint64_t *result)
	Adds two unsigned 64-bit integers. More...
bool	IsPrime (uint64_t n)
	Returns whether or not the input is prime. More...
std::vector< uint64_t >	GeneratePrimes (size_t num_primes, size_t bit_size, bool prefer_small_primes, size_t ntt_size=1)
	Generates a list of num_primes primes in the range [2^(bit_size),. More...
uint64_t	BarrettReduce64 (uint64_t input, uint64_t modulus, uint64_t q_barr)
	Returns input mod modulus, computed via 64-bit Barrett reduction. More...
template<int InputModFactor>
uint64_t	ReduceMod (uint64_t x, uint64_t modulus, const uint64_t *twice_modulus=nullptr, const uint64_t *four_times_modulus=nullptr)
	Returns x mod modulus, assuming x < InputModFactor * modulus. More...
CMPINT	Not (CMPINT cmp)
	Returns the logical negation of a binary operation. More...

Variables
AllocatorStrategyPtr	mallocStrategy

Typedef Documentation

AlignedVector64

template<typename T >

using intel::hexl::AlignedVector64 = typedef std::vector<T, AlignedAllocator<T, 64> >

64-byte aligned memory allocator

AllocatorStrategyPtr

using intel::hexl::AllocatorStrategyPtr = typedef std::shared_ptr<AllocatorBase>

Enumeration Type Documentation

CMPINT

enum intel::hexl::CMPINT

strong

Represents binary operations between two boolean values.

Enumerator
EQ	Equal.
LT	Less than.
LE	Less than or equal.
FALSE	False.
NE	Not equal.
NLT	Not less than.
NLE	Not less than or equal.
TRUE	True.

Function Documentation

AddUInt64()

unsigned char intel::hexl::AddUInt64 ( uint64_t  operand1, uint64_t  operand2, uint64_t *  result  )

inline

Adds two unsigned 64-bit integers.

Parameters

operand1	Number to add
operand2	Number to add
result	Stores the sum

Returns

The carry bit

AddUIntMod()

uint64_t intel::hexl::AddUIntMod	(	uint64_t	x,
		uint64_t	y,
		uint64_t	modulus
	)

Returns (x + y) mod modulus.

Assumes x, y < modulus

BarrettReduce64()

uint64_t intel::hexl::BarrettReduce64	(	uint64_t	input,
		uint64_t	modulus,
		uint64_t	q_barr
	)

Returns input mod modulus, computed via 64-bit Barrett reduction.

Parameters

[in]	input
[in]	modulus
[in]	q_barr	floor(2^64 / modulus)

CkksMultiply()

void intel::hexl::CkksMultiply	(	uint64_t *	result,
		const uint64_t *	operand1,
		const uint64_t *	operand2,
		uint64_t	n,
		const uint64_t *	moduli,
		uint64_t	num_moduli
	)

Computes CKKS multiplication.

Parameters

[in,out]	result	Ciphertext data. Will be over-written with result. Has (2 * n * num_moduli) elements
[in]	operand1	First ciphertext argument. Has (2 * n * num_moduli) elements.
[in]	operand2	Second ciphertext argument. Has (2 * n * num_moduli) elements.
[in]	n	Number of coefficients in each polynomial
[in]	moduli	Pointer to contiguous array of num_moduli word-sized coefficient moduli
[in]	num_moduli	Number of word-sized coefficient moduli

CkksSwitchKey()

void intel::hexl::CkksSwitchKey	(	uint64_t *	result,
		const uint64_t *	t_target_iter_ptr,
		uint64_t	n,
		uint64_t	decomp_modulus_size,
		uint64_t	key_modulus_size,
		uint64_t	rns_modulus_size,
		uint64_t	key_component_count,
		uint64_t *	moduli,
		const uint64_t **	kswitch_keys,
		uint64_t *	modswitch_factors
	)

Computes CKKS key switching in-place.

Parameters

[in,out]	result	Ciphertext data. Will be over-written with result. Has (n * decomp_modulus_size * key_component_count) elements
[in]	t_target_iter_ptr	TODO(fboemer)
[in]	n	Number of coefficients in each polynomial
[in]	decomp_modulus_size	Number of moduli in the ciphertext at its current level, excluding one auxiliary prime.
[in]	key_modulus_size	Number of moduli in the ciphertext at its top level, including one auxiliary prime.
[in]	rns_modulus_size	Number of moduli in the ciphertext at its current level, including one auxiliary prime. rns_modulus_size == decomp_modulus_size + 1
[in]	key_component_count	TODO(fboemer)
[in]	moduli	Array of word-sized coefficient moduli. There must be key_modulus_size moduli in the array
[in]	kswitch_keys	Array of evaluation key data. Has decomp_modulus_size entries, each with coeff_count * ((key_modulus_size - 1)+ (key_component_count - 1) * (key_modulus_size) + 1) entries
[in]	modswitch_factors	Array of modulus switch factors

EltwiseAddMod() [1/2]

void intel::hexl::EltwiseAddMod	(	uint64_t *	result,
		const uint64_t *	operand1,
		const uint64_t *	operand2,
		uint64_t	n,
		uint64_t	modulus
	)

Adds two vectors elementwise with modular reduction.

Parameters

[out]	result	Stores result
[in]	operand1	Vector of elements to add. Each element must be less than the modulus
[in]	operand2	Vector of elements to add. Each element must be less than the modulus
[in]	n	Number of elements in each vector
[in]	modulus	Modulus with which to perform modular reduction. Must be in the range \([2, 2^{63} - 1]\)

Computes \( operand1[i] = (operand1[i] + operand2[i]) \mod modulus \) for \( i=0, ..., n-1\).

EltwiseAddMod() [2/2]

void intel::hexl::EltwiseAddMod	(	uint64_t *	result,
		const uint64_t *	operand1,
		uint64_t	operand2,
		uint64_t	n,
		uint64_t	modulus
	)

Adds a vector and scalar elementwise with modular reduction.

Parameters

[out]	result	Stores result
[in]	operand1	Vector of elements to add. Each element must be less than the modulus
[in]	operand2	Scalar to add. Must be less than the modulus
[in]	n	Number of elements in each vector
[in]	modulus	Modulus with which to perform modular reduction. Must be in the range \([2, 2^{63} - 1]\)

Computes \( operand1[i] = (operand1[i] + operand2) \mod modulus \) for \( i=0, ..., n-1\).

EltwiseCmpAdd()

void intel::hexl::EltwiseCmpAdd	(	uint64_t *	result,
		const uint64_t *	operand1,
		uint64_t	n,
		CMPINT	cmp,
		uint64_t	bound,
		uint64_t	diff
	)

Computes element-wise conditional addition.

Parameters

[out]	result	Stores the result
[in]	operand1	Vector of elements to compare; stores result
[in]	n	Number of elements in operand1
[in]	cmp	Comparison operation
[in]	bound	Scalar to compare against
[in]	diff	Scalar to conditionally add

Computes result[i] = cmp(operand1[i], bound) ? operand1[i] + diff : operand1[i] for all \(i=0, ..., n-1\).

EltwiseCmpSubMod()

void intel::hexl::EltwiseCmpSubMod	(	uint64_t *	result,
		const uint64_t *	operand1,
		uint64_t	n,
		uint64_t	modulus,
		CMPINT	cmp,
		uint64_t	bound,
		uint64_t	diff
	)

Computes element-wise conditional modular subtraction.

Parameters

[out]	result	Stores the result
[in]	operand1	Vector of elements to compare
[in]	n	Number of elements in operand1
[in]	modulus	Modulus to reduce by
[in]	cmp	Comparison function
[in]	bound	Scalar to compare against
[in]	diff	Scalar to subtract by

Computes operand1[i] = (cmp(operand1, bound)) ? (operand1 - diff) mod modulus : operand1 for all i=0, ..., n-1

EltwiseFMAMod()

void intel::hexl::EltwiseFMAMod	(	uint64_t *	result,
		const uint64_t *	arg1,
		uint64_t	arg2,
		const uint64_t *	arg3,
		uint64_t	n,
		uint64_t	modulus,
		uint64_t	input_mod_factor
	)

Computes fused multiply-add (arg1 * arg2 + arg3) mod modulus element-wise, broadcasting scalars to vectors.

Parameters

[out]	result	Stores the result
[in]	arg1	Vector to multiply
[in]	arg2	Scalar to multiply
[in]	arg3	Vector to add. Will not add if arg3 == nullptr
[in]	n	Number of elements in each vector
[in]	modulus	Modulus with which to perform modular reduction. Must be in the range \( [2, 2^{61} - 1]\)
[in]	input_mod_factor	Assumes input elements are in [0, input_mod_factor * modulus). Must be 1, 2, 4, or 8.

EltwiseMultMod()

void intel::hexl::EltwiseMultMod	(	uint64_t *	result,
		const uint64_t *	operand1,
		const uint64_t *	operand2,
		uint64_t	n,
		uint64_t	modulus,
		uint64_t	input_mod_factor
	)

Multiplies two vectors elementwise with modular reduction.

Parameters

[in]	result	Result of element-wise multiplication
[in]	operand1	Vector of elements to multiply. Each element must be less than the modulus.
[in]	operand2	Vector of elements to multiply. Each element must be less than the modulus.
[in]	n	Number of elements in each vector
[in]	modulus	Modulus with which to perform modular reduction
[in]	input_mod_factor	Assumes input elements are in [0, input_mod_factor * p) Must be 1, 2 or 4.

Computes result[i] = (operand1[i] * operand2[i]) mod modulus for i=0, ..., n - 1

EltwiseReduceMod()

void intel::hexl::EltwiseReduceMod	(	uint64_t *	result,
		const uint64_t *	operand,
		uint64_t	n,
		uint64_t	modulus,
		uint64_t	input_mod_factor,
		uint64_t	output_mod_factor
	)

Performs elementwise modular reduction.

Parameters

[out]	result	Stores the result
[in]	operand	Data on which to compute the elementwise modular reduction
[in]	n	Number of elements in operand
[in]	modulus	Modulus with which to perform modular reduction
[in]	input_mod_factor	Assumes input elements are in [0, input_mod_factor * p) Must be 0, 1, 2 or 4. input_mod_factor=0 means, no knowledge of input range. Barrett reduction will be used in this case. input_mod_factor >= output_mod_factor unless input_mod_factor == 0
[in]	output_mod_factor	output elements will be in [0, output_mod_factor * modulus) Must be 1 or 2. For input_mod_factor=0, output_mod_factor will be set to 1.

EltwiseSubMod() [1/2]

void intel::hexl::EltwiseSubMod	(	uint64_t *	result,
		const uint64_t *	operand1,
		const uint64_t *	operand2,
		uint64_t	n,
		uint64_t	modulus
	)

Subtracts two vectors elementwise with modular reduction.

Parameters

[out]	result	Stores result
[in]	operand1	Vector of elements to subtract from. Each element must be less than the modulus
[in]	operand2	Vector of elements to subtract. Each element must be less than the modulus
[in]	n	Number of elements in each vector
[in]	modulus	Modulus with which to perform modular reduction. Must be in the range \([2, 2^{63} - 1]\)

Computes \( operand1[i] = (operand1[i] - operand2[i]) \mod modulus \) for \( i=0, ..., n-1\).

EltwiseSubMod() [2/2]

void intel::hexl::EltwiseSubMod	(	uint64_t *	result,
		const uint64_t *	operand1,
		uint64_t	operand2,
		uint64_t	n,
		uint64_t	modulus
	)

Subtracts a scalar from a vector elementwise with modular reduction.

Parameters

[out]	result	Stores result
[in]	operand1	Vector of elements to subtract from. Each element must be less than the modulus
[in]	operand2	Elements to subtract. Each element must be less than the modulus
[in]	n	Number of elements in each vector
[in]	modulus	Modulus with which to perform modular reduction. Must be in the range \([2, 2^{63} - 1]\)

Computes \( operand1[i] = (operand1[i] - operand2) \mod modulus \) for \( i=0, ..., n-1\).

GeneratePrimes()

std::vector<uint64_t> intel::hexl::GeneratePrimes	(	size_t	num_primes,
		size_t	bit_size,
		bool	prefer_small_primes,
		size_t	ntt_size = 1
	)

Generates a list of num_primes primes in the range [2^(bit_size),.

Parameters

[in]	num_primes	Number of primes to generate
[in]	bit_size	Bit size of each prime
[in]	prefer_small_primes	When true, returns primes starting from 2^(bit_size); when false, returns primes starting from 2^(bit_size+1)
[in]	ntt_size	N such that each prime q satisfies q % (2N) == 1. N must be a power of two less than 2^bit_size.

GeneratePrimitiveRoot()

uint64_t intel::hexl::GeneratePrimitiveRoot	(	uint64_t	degree,
		uint64_t	modulus
	)

Tries to return a primitive degree-th root of unity.

Returns 0 or throws an error if no root is found

InverseMod()

uint64_t intel::hexl::InverseMod	(	uint64_t	x,
		uint64_t	modulus
	)

Returns x^{-1} mod modulus.

Requires x % modulus != 0

IsPowerOfFour()

bool intel::hexl::IsPowerOfFour ( uint64_t  num )

inline

IsPowerOfTwo()

bool intel::hexl::IsPowerOfTwo ( uint64_t  num )

inline

Returns whether or not num is a power of two.

IsPrime()

bool intel::hexl::IsPrime

(

uint64_t

n

)

Returns whether or not the input is prime.

IsPrimitiveRoot()

bool intel::hexl::IsPrimitiveRoot	(	uint64_t	root,
		uint64_t	degree,
		uint64_t	modulus
	)

Returns whether or not root is a degree-th root of unity mod modulus.

Parameters

[in]	root	Root of unity to check
[in]	degree	Degree of root of unity; must be a power of two
[in]	modulus	Modulus of finite field

Log2()

uint64_t intel::hexl::Log2 ( uint64_t  x )

inline

Returns floor(log2(x))

MaximumValue()

uint64_t intel::hexl::MaximumValue ( uint64_t  bits )

inline

Returns the maximum value that can be represented using bits bits.

MinimalPrimitiveRoot()

uint64_t intel::hexl::MinimalPrimitiveRoot	(	uint64_t	degree,
		uint64_t	modulus
	)

Returns whether or not root is a degree-th root of unity.

Parameters

[in]	degree	Must be a power of two
[in]	modulus	Modulus of finite field

MultiplyMod() [1/2]

uint64_t intel::hexl::MultiplyMod	(	uint64_t	x,
		uint64_t	y,
		uint64_t	modulus
	)

Returns (x * y) mod modulus.

Assumes x, y < modulus

MultiplyMod() [2/2]

uint64_t intel::hexl::MultiplyMod	(	uint64_t	x,
		uint64_t	y,
		uint64_t	y_precon,
		uint64_t	modulus
	)

Returns (x * y) mod modulus.

Parameters

[in]	x
[in]	y
[in]	y_precon	64-bit precondition factor floor(2**64 / modulus)
[in]	modulus

MultiplyModLazy() [1/2]

template<int BitShift>

uint64_t intel::hexl::MultiplyModLazy ( uint64_t  x, uint64_t  y_operand, uint64_t  y_barrett_factor, uint64_t  modulus  )

inline

Computes (x * y) mod modulus, except that the output is in [0, 2 * modulus].

Parameters

[in]	x
[in]	y_operand	also denoted y
[in]	modulus
[in]	y_barrett_factor	Pre-computed Barrett reduction factor floor((y << BitShift) / modulus)

MultiplyModLazy() [2/2]

template<int BitShift>

uint64_t intel::hexl::MultiplyModLazy ( uint64_t  x, uint64_t  y, uint64_t  modulus  )

inline

Computes (x * y) mod modulus, except that the output is in [0, 2 * modulus].

Parameters

[in]	x
[in]	y
[in]	modulus

Not()

CMPINT intel::hexl::Not ( CMPINT  cmp )

inline

Returns the logical negation of a binary operation.

Parameters

[in]

cmp

The binary operation to negate

PowMod()

uint64_t intel::hexl::PowMod	(	uint64_t	base,
		uint64_t	exp,
		uint64_t	modulus
	)

Returns base^exp mod modulus.

ReduceMod()

template<int InputModFactor>

uint64_t intel::hexl::ReduceMod	(	uint64_t	x,
		uint64_t	modulus,
		const uint64_t *	twice_modulus = nullptr,
		const uint64_t *	four_times_modulus = nullptr
	)

Returns x mod modulus, assuming x < InputModFactor * modulus.

Parameters

[in]	x
[in]	modulus	also denoted q
[in]	twice_modulus	2 * q; must not be nullptr if InputModFactor == 4 or 8
[in]	four_times_modulus	4 * q; must not be nullptr if InputModFactor == 8

ReverseBits()

uint64_t intel::hexl::ReverseBits	(	uint64_t	x,
		uint64_t	bit_width
	)

Reverses the bits.

Parameters

[in]	x	Input to reverse
[in]	bit_width	Number of bits in the input; must be >= MSB(x)

Returns

The bit-reversed representation of x using bit_width bits

SubUIntMod()

uint64_t intel::hexl::SubUIntMod	(	uint64_t	x,
		uint64_t	y,
		uint64_t	modulus
	)

Returns (x - y) mod modulus.

Assumes x, y < modulus

Variable Documentation

mallocStrategy

AllocatorStrategyPtr intel::hexl::mallocStrategy