Crypto.Lol.Cyclotomic.Cyc

An implementation of cyclotomic rings that hides the internal representations of ring elements (e.g., the choice of basis), and also offers more efficient storage and operations on subring elements (including elements from the base ring itself).

For an implementation that allows (and requires) the programmer to control the underlying representation, see UCyc.

WARNING: as with all fixed-point arithmetic, the functions associated with Cyc 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 function is determined by the internal linear transforms and other operations it performs.

Data type and constraints

data Cyc t m r

Represents a cyclotomic ring such as Z[zeta], Zq[zeta], and Q(zeta) in an explicit representation: t is the Tensor type for storing coefficient tensors; m is the cyclotomic index; r is the base ring of the coefficients (e.g., Z, Zq).

Instances

(Correct k gad zq, Fact m, CElt t zq) => Correct k gad (Cyc t m zq)

(Decompose k gad zq, Fact m, CElt t zq, CElt t (DecompOf zq)) => Decompose k gad (Cyc t m zq)

(Gadget k gad zq, Fact m, CElt t zq) => Gadget k gad (Cyc t m zq)

(Rescale a b, CElt t a, TElt t b) => RescaleCyc (Cyc t) a b

(Mod a, Field b, Lift a (ModRep a), Reduce (LiftOf a) b, CElt t (a, b), CElt t a, CElt t b, CElt t (LiftOf a)) => RescaleCyc (Cyc t) (a, b) b

(Eq r, Fact m, CElt t r) => Eq (Cyc t m r)

(Show r, Show (CRTExt r), Tensor t, Fact m, TElt t r, TElt t (CRTExt r)) => Show (Cyc t m r)

(Random r, Tensor t, Fact m, CRTElt t r) => Random (Cyc t m r)

Arbitrary (UCyc Factored t m P r) => Arbitrary (Cyc t m r)

(Tensor t, Fact m, NFData r, TElt t r, NFData (CRTExt r), TElt t (CRTExt r)) => NFData (Cyc t m r)

(Fact m, CElt t r) => C (Cyc t m r)

(Fact m, CElt t r) => C (Cyc t m r)

(Fact m, CElt t r) => C (Cyc t m r)

(GFCtx k fp d, Fact m, CElt t fp) => C (GF k fp d) (Cyc t m fp)

(Reduce a b, Fact m, CElt t a, CElt t b) => Reduce (Cyc t m a) (Cyc t m b)

type LiftOf (Cyc t m r) = Cyc t m (LiftOf r)

type DecompOf (Cyc t m zq) = Cyc t m (DecompOf zq)

type CElt t r = UCElt t r

Constraints needed for many operations involving Cyc data.

type NFElt r = (NFData r, NFData (CRTExt r))

Convenient synonym for deepseq-able element type.

Constructors/deconstructors

cycPow :: UCyc t m P r -> Cyc t m r

Wrap a UCyc as a Cyc.

cycDec :: UCyc t m D r -> Cyc t m r

Wrap a UCyc as a Cyc.

cycCRT :: UCyc t m C r -> Cyc t m r

Wrap a UCyc as a Cyc.

scalarCyc :: r -> Cyc t m r

Embed a scalar from the base ring as a cyclotomic element.

uncycPow :: (Fact m, CElt t r) => Cyc t m r -> UCyc t m P r

Unwrap a Cyc as a UCyc in powerful-basis representation.

uncycDec :: (Fact m, CElt t r) => Cyc t m r -> UCyc t m D r

Unwrap a Cyc as a UCyc in decoding-basis representation.

uncycCRT :: (Fact m, CElt t r) => Cyc t m r -> UCyc t m C r

Unwrap a Cyc as a UCyc in CRT-basis representation.

unzipCyc :: (Tensor t, Fact m) => Cyc t m (a, b) -> (Cyc t m a, Cyc t m b)

Unzip for unrestricted types.

unzipCElt :: (Tensor t, Fact m, CElt t (a, b), CElt t a, CElt t b) => Cyc t m (a, b) -> (Cyc t m a, Cyc t m b)

Type-restricted (and potentially more efficient) unzip.

Core cyclotomic operations

mulG :: (Fact m, CElt t r) => Cyc t m r -> Cyc t m r

Multiply by the special element g of the mth cyclotomic.

divG :: (Fact m, CElt t r) => Cyc t m r -> Maybe (Cyc t m r)

Divide by g, returning Nothing if not evenly divisible. WARNING: this implementation is not a constant-time algorithm, so information about the argument may be leaked through a timing channel.

gSqNorm :: forall t m r. (Fact m, CElt t r) => Cyc t m r -> 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 .

liftCyc :: (Lift b a, Fact m, TElt t a, CElt t b) => Basis -> Cyc t m b -> Cyc t m a

Lift using the specified basis.

liftPow :: (Lift b a, Fact m, TElt t a, CElt t b) => Cyc t m b -> Cyc t m a

Lift using the powerful basis.

liftDec :: (Lift b a, Fact m, TElt t a, CElt t b) => Cyc t m b -> Cyc t m a

Lift using the decoding basis.

Representation advice

advisePow :: (Fact m, CElt t r) => Cyc t m r -> Cyc t m r

Same as adviseCRT, but for the powerful-basis representation.

adviseDec :: (Fact m, CElt t r) => Cyc t m r -> Cyc t m r

Same as adviseCRT, but for the powerful-basis representation.

adviseCRT :: (Fact m, CElt t r) => Cyc t m r -> Cyc t m r

Yield an equivalent element that may be in a CRT representation. This can serve as an optimization hint. E.g., call adviseCRT prior to multiplying the same value by many other values.

Error sampling

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

Sample from the "tweaked" Gaussian error distribution t*D in the decoding basis, where D has scaled variance v. (Note: This implementation uses Double precision to generate the Gaussian sample, which may not be sufficient for rigorous proof-based security.)

errorRounded :: (ToInteger z, Tensor t, Fact m, TElt t z, ToRational v, MonadRandom rnd) => v -> rnd (Cyc t m z)

Generate an LWE error term with given scaled variance, deterministically rounded with respect to the decoding basis.

errorCoset :: (Mod zp, z ~ ModRep zp, Lift zp z, Fact m, CElt t zp, TElt t z, ToRational v, MonadRandom rnd) => v -> Cyc t m zp -> rnd (Cyc t m z)

Generate an LWE error term with given scaled variance * p^2 over the given coset, deterministically rounded with respect to the decoding basis.

Sub/extension rings

embed :: forall t m m' r. m `Divides` m' => Cyc t m r -> Cyc t m' r

Embed (lazily) into an extension ring.

twace :: forall t m m' r. (m `Divides` m', CElt t r) => Cyc t m' r -> Cyc t m r

The "tweaked trace" (twace) function Tw(x) = (mhat / m'hat) * Tr(g' / g * x), which fixes R pointwise (i.e., twace . embed == id).

coeffsCyc :: (m `Divides` m', CElt t r) => Basis -> Cyc t m' r -> [Cyc t m r]

Return the given element's coefficient vector with respect to the (relative) powerful/decoding basis of the cyclotomic extension O_m' / O_m.

powBasis :: (m `Divides` m', CElt t r) => Tagged m [Cyc t m' r]

The relative powerful basis of O_m' / O_m.

crtSet :: (m `Divides` m', ZPP r, CElt t r, TElt t (ZpOf r)) => Tagged m [Cyc t m' r]

The relative mod-r CRT set of the extension.

Rescaling cyclotomic elements

class RescaleCyc c a b where

Represents cyclotomic rings that are rescalable over their base rings. (This is a class because it allows for more efficient specialized implementations.)

Methods

rescaleCyc :: Fact m => Basis -> c m a -> c m b

Rescale in the given basis.

Instances

(Rescale a b, CElt t a, TElt t b) => RescaleCyc (Cyc t) a b

(Mod a, Field b, Lift a (ModRep a), Reduce (LiftOf a) b, CElt t (a, b), CElt t a, CElt t b, CElt t (LiftOf a)) => RescaleCyc (Cyc t) (a, b) b

data Basis

Constructors

Pow

Dec