Crypto.Lol.Cyclotomic.Tensor

Interface for cyclotomic tensors, and helper functions for tensor indexing.

Documentation

class (TElt t Double, TElt t (Complex Double)) => Tensor t where

Tensor encapsulates all the core linear transformations needed for cyclotomic ring arithmetic.

The type t m r represents a cyclotomic coefficient tensor of index m over base ring r. Most of the methods represent linear transforms corresponding to operations in particular bases. CRT-related methods are wrapped in Maybe because they are well-defined only when a CRT basis exists over the ring r for index m.

The superclass constraints are for convenience, to ensure that we can sample error tensors of Doubles.

WARNING: as with all fixed-point arithmetic, the methods in Tensor may result in overflow (and thereby incorrect answers and potential security flaws) if the input arguments are too close to the bounds imposed by the base type. The acceptable range of inputs for each method is determined by the linear transform it implements.

Associated Types

type TElt t r :: Constraint

Constraints needed by t to hold type r.

Methods

entailIndexT :: Tagged (t m r) (Fact m :- (Applicative (t m), Traversable (t m)))

Properties that hold for any index. Use with \\.

entailEqT :: Tagged (t m r) ((Eq r, Fact m, TElt t r) :- Eq (t m r))

Properties that hold for any (legal) fully-applied tensor. Use with \\.

entailZTT :: Tagged (t m r) ((ZeroTestable r, Fact m, TElt t r) :- ZeroTestable (t m r))

entailNFDataT :: Tagged (t m r) ((NFData r, Fact m, TElt t r) :- NFData (t m r))

entailRandomT :: Tagged (t m r) ((Random r, Fact m, TElt t r) :- Random (t m r))

entailShowT :: Tagged (t m r) ((Show r, Fact m, TElt t r) :- Show (t m r))

entailModuleT :: Tagged (GF fp d, t m fp) ((GFCtx fp d, Fact m, TElt t fp) :- Module (GF fp d) (t m fp))

scalarPow :: (Additive r, Fact m, TElt t r) => r -> t m r

Convert a scalar to a tensor in the powerful basis.

l, lInv :: (Additive r, Fact m, TElt t r) => t m r -> t m r

l converts from decoding-basis representation to powerful-basis representation; lInv is its inverse.

mulGPow, mulGDec :: (Ring r, Fact m, TElt t r) => t m r -> t m r

Multiply by g in the powerful/decoding basis

divGPow, divGDec :: (ZeroTestable r, IntegralDomain r, Fact m, TElt t r) => t m r -> Maybe (t m r)

Divide by g in the powerful/decoding basis. The Maybe output indicates that the operation may fail, which happens exactly when the input is not divisible by g.

crtFuncs :: (CRTrans mon r, Fact m, TElt t r) => mon (r -> t m r, t m r -> t m r, t m r -> t m r, t m r -> t m r, t m r -> t m r)

A tuple of all the operations relating to the CRT basis, in a single Maybe value for safety. Clients should typically not use this method directly, but instead call the corresponding top-level functions: the elements of the tuple correpond to the functions scalarCRT, mulGCRT, divGCRT, crt, crtInv.

tGaussianDec :: (OrdFloat q, Random q, TElt t q, ToRational v, Fact m, MonadRandom rnd) => v -> rnd (t m q)

Sample from the "tweaked" Gaussian error distribution t*D in the decoding basis, where D has scaled variance v.

gSqNormDec :: (Ring r, Fact m, TElt t r) => t m r -> r

Given the coefficient tensor of e with respect to the decoding basis of R, yield the (scaled) squared norm of g_m cdot e under the canonical embedding, namely, hat{m}^{ -1 } cdot || sigma(g_m cdot e) ||^2 .

twacePowDec :: (Ring r, m `Divides` m', TElt t r) => t m' r -> t m r

The twace linear transformation, which is the same in both the powerful and decoding bases.

embedPow, embedDec :: (Additive r, m `Divides` m', TElt t r) => t m r -> t m' r

The embed linear transformations, for the powerful and decoding bases.

crtExtFuncs :: (CRTrans mon r, m `Divides` m', TElt t r) => mon (t m' r -> t m r, t m r -> t m' r)

A tuple of all the extension-related operations involving the CRT bases, for safety. Clients should typically not use this method directly, but instead call the corresponding top-level functions: the elements of the tuple correpond to the functions twaceCRT, embedCRT.

coeffs :: (Ring r, m `Divides` m', TElt t r) => t m' r -> [t m r]

Map a tensor in the powerful/decoding/CRT basis, representing an O_m' element, to a vector of tensors representing O_m elements in the same kind of basis.

powBasisPow :: (Ring r, TElt t r, m `Divides` m') => Tagged m [t m' r]

The powerful extension basis w.r.t. the powerful basis.

crtSetDec :: (m `Divides` m', PrimeField fp, Coprime (PToF (CharOf fp)) m', TElt t fp) => Tagged m [t m' fp]

A list of tensors representing the mod-p CRT set of the extension.

fmapT :: (Fact m, TElt t a, TElt t b) => (a -> b) -> t m a -> t m b

Potentially optimized version of fmap for types that satisfy TElt.

fmapTM :: (Monad mon, Fact m, TElt t a, TElt t b) => (a -> mon b) -> t m a -> mon (t m b)

Potentially optimized monadic fmap.

zipWithT :: (Fact m, TElt t a, TElt t b, TElt t c) => (a -> b -> c) -> t m a -> t m b -> t m c

Potentially optimized zipWith for types that satisfy TElt.

unzipT :: (Fact m, TElt t (a, b), TElt t a, TElt t b) => t m (a, b) -> (t m a, t m b)

Potentially optimized unzip for types that satisfy TElt.

Instances

Tensor CT

Tensor RT

Top-level CRT functions

hasCRTFuncs :: forall t m mon r. (CRTrans mon r, Tensor t, Fact m, TElt t r) => TaggedT (t m r) mon ()

Convenience value indicating whether crtFuncs exists.

scalarCRT :: (CRTrans mon r, Tensor t, Fact m, TElt t r) => mon (r -> t m r)

Yield a tensor for a scalar in the CRT basis. (This function is simply an appropriate entry from crtFuncs.)

mulGCRT :: (CRTrans mon r, Tensor t, Fact m, TElt t r) => mon (t m r -> t m r)

Multiply by g in the CRT basis. (This function is simply an appropriate entry from crtFuncs.)

divGCRT :: (CRTrans mon r, Tensor t, Fact m, TElt t r) => mon (t m r -> t m r)

Divide by g in the CRT basis. (This function is simply an appropriate entry from crtFuncs.)

crt :: (CRTrans mon r, Tensor t, Fact m, TElt t r) => mon (t m r -> t m r)

The CRT transform. (This function is simply an appropriate entry from crtFuncs.)

crtInv :: (CRTrans mon r, Tensor t, Fact m, TElt t r) => mon (t m r -> t m r)

The inverse CRT transform. (This function is simply an appropriate entry from crtFuncs.)

twaceCRT :: forall t m m' mon r. (CRTrans mon r, Tensor t, m `Divides` m', TElt t r) => mon (t m' r -> t m r)

The "tweaked trace" function for tensors in the CRT basis: For cyclotomic indices m | m', Tw(x) = (mhat/m'hat) * Tr(g'/g * x). (This function is simply an appropriate entry from crtExtFuncs.)

embedCRT :: forall t m m' mon r. (CRTrans mon r, Tensor t, m `Divides` m', TElt t r) => mon (t m r -> t m' r)

Embed a tensor with index m in the CRT basis to a tensor with index m' in the CRT basis. (This function is simply an appropriate entry from crtExtFuncs.)

Special vectors/matrices

data Matrix r

A Kronecker product of zero of more matrices over r.

indexM :: Ring r => Matrix r -> Int -> Int -> r

Extract the (i,j) element of a Matrix.

gCRTM :: (Fact m, CRTrans mon r) => TaggedT m mon (Matrix r)

A tot(m)-by-1 matrix of the CRT coefficients of g_m, for mth cyclotomic.

gInvCRTM :: (Fact m, CRTrans mon r) => TaggedT m mon (Matrix r)

A tot(m)-by-1 matrix of the inverse CRT coefficients of g_m, for mth cyclotomic.

twCRTs :: (Fact m, CRTrans mon r) => TaggedT m mon (Matrix r)

The "tweaked" CRT^* matrix: CRT^* . diag(sigma(g_m)).

Tensor indexing

zmsToIndexFact :: Fact m => Tagged m (Int -> Int)

Convert a Z_m^* index to a linear tensor index in [m].

indexInfo :: forall m m'. m `Divides` m' => Tagged `(m, m')` ([(Int, Int, Int)], Int, Int, [(Int, Int)])

A collection of useful information for working with tensor extensions. The first component is a list of triples (p,e,e') where e, e' are respectively the exponents of prime p in m, m'. The next two components are phi(m) and phi(m'). The final component is a pair (phi(p^e), phi(p^e')) for each triple in the first component.

extIndicesPowDec :: m `Divides` m' => Tagged `(m, m')` (Vector Int)

A vector of phi(m) entries, where the ith entry is the index into the powerful/decoding basis of O_m' of the ith entry of the powerful/decoding basis of O_m.

extIndicesCRT :: forall m m'. m `Divides` m' => Tagged `(m, m')` (Vector Int)

A vector of phi(m) blocks of phi(m')/phi(m) consecutive entries. Each block contains all those indices into the CRT basis of O_m' that "lie above" the corresponding index into the CRT basis of O_m.

extIndicesCoeffs :: forall m m'. m `Divides` m' => Tagged `(m, m')` (Vector (Vector Int))

The i0th entry of the i1th vector is fromIndexPair (i1,i0).

baseIndicesPow :: forall m m'. m `Divides` m' => Tagged `(m, m')` (Vector (Int, Int))

A lookup table for toIndexPair applied to indices [phi(m')].

baseIndicesDec :: forall m m'. m `Divides` m' => Tagged `(m, m')` (Vector (Maybe (Int, Bool)))

A lookup table for baseIndexDec applied to indices [phi(m')].

baseIndicesCRT :: forall m m'. m `Divides` m' => Tagged `(m, m')` (Vector Int)

Same as baseIndicesPow, but only includes the second component of each pair.

digitRev :: PP -> Int -> Int

Base-p digit reversal; input and output are in [p^e].