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)

promoted from base ring, using the decoding basis for best geometry

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

promoted from base ring, using the powerful basis for best geometry

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

promoted from base ring

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

generic instance

(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

specialized instance for product rings of Zqs: ~2x faster algorithm

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

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

Arbitrary (UCyc 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)

(Fact m, CElt t r, Protoable (UCyc t m D r)) => Protoable (Cyc t m r)

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

Rp is an F_{p^d}-module when d divides phi(m), by applying d-dimensional Fp-linear transform on d-dim chunks of powerful basis coeffs

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

type ProtoType (Cyc t m r) = ProtoType (UCyc t m D r)

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 = (UCRTElt t r, ZeroTestable r)

Constraints needed for most operations involving Cyc data.

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

Convenient synonym for deepseq-able element type.

Constructors/deconstructors

scalarCyc :: r -> Cyc t m r

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

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 :: UCycEC t m r -> Cyc t m r

Wrap a UCycEC as a Cyc.

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

Wrap a UCyc as a Cyc.

cycCRTE :: UCyc t m E r -> Cyc t m r

Wrap a UCyc as a Cyc.

cycPC :: Either (UCyc t m P r) (UCyc t m C r) -> Cyc t m r

Convenience wrapper.

cycPE :: Either (UCyc t m P r) (UCyc t m E r) -> Cyc t m r

Convenience wrapper.

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 -> UCycEC t m r

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

unzipCyc :: (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)

Unzip for a pair base ring.

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, IntegralDomain 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.

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. (Note: This implementation uses Double precision to generate the Gaussian sample, which may not be sufficient for rigorous proof-based security.)

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. (Note: This implementation uses Double precision to generate the Gaussian sample, which may not be sufficient for rigorous proof-based security.)

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. See also coeffsPow, coeffsDec.

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

Specialized version of coeffsCyc for powerful basis.

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

Specialized version of coeffsCyc for decoding basis.

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

generic instance

(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

specialized instance for product rings of Zqs: ~2x faster algorithm

data Basis

Represents the basis used to rescale a cyclotomic ring element.

Constructors

Pow

Dec