Crypto.Lol.Cyclotomic.Cyc

\( \def\Z{\mathbb{Z}} \) \( \def\F{\mathbb{F}} \) \( \def\Q{\mathbb{Q}} \) \( \def\Tw{\text{Tw}} \) \( \def\Tr{\text{Tr}} \) \( \def\O{\mathcal{O}} \)

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 Crypto.Lol.Cyclotomic.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_m]\), \(\Z_q[\zeta_m]\), and \(\Q[\zeta_m]\) 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\), \(\Z_q\)).

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

Methods

correct :: Tagged gad (Cyc t m zq) [u] -> (u, [LiftOf u])

(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

Associated Types

type DecompOf u :: *

Methods

decompose :: u -> Tagged gad (Cyc t m zq) [DecompOf u]

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

promoted from base ring

Methods

gadget :: Tagged gad (Cyc t m zq) [u]

encode :: u -> Tagged gad (Cyc t m zq) [u]

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

Methods

rescaleCyc :: Fact m => Basis -> Cyc t m a -> Cyc t m 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

specialized instance for product rings of \(\Z_q\)s: ~2x faster algorithm

Methods

rescaleCyc :: Fact m => Basis -> Cyc t m (a, b) -> Cyc t m b

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

Methods

(==) :: Cyc t m r -> Cyc t m r -> Bool

(/=) :: Cyc t m r -> Cyc t m r -> Bool

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

Methods

randomR :: RandomGen g => (Cyc t m r, Cyc t m r) -> g -> (Cyc t m r, g)

random :: RandomGen g => g -> (Cyc t m r, g)

randomRs :: RandomGen g => (Cyc t m r, Cyc t m r) -> g -> [Cyc t m r]

randoms :: RandomGen g => g -> [Cyc t m r]

randomRIO :: (Cyc t m r, Cyc t m r) -> IO (Cyc t m r)

randomIO :: IO (Cyc t m r)

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

Methods

arbitrary :: Gen (Cyc t m r)

shrink :: Cyc t m r -> [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)

Methods

rnf :: Cyc t m r -> ()

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

Methods

(*) :: Cyc t m r -> Cyc t m r -> Cyc t m r

one :: Cyc t m r

fromInteger :: Integer -> Cyc t m r

(^) :: Cyc t m r -> Integer -> Cyc t m r

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

Methods

isZero :: Cyc t m r -> Bool

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

Methods

zero :: Cyc t m r

(+) :: Cyc t m r -> Cyc t m r -> Cyc t m r

(-) :: Cyc t m r -> Cyc t m r -> Cyc t m r

negate :: Cyc t m r -> Cyc t m r

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

Associated Types

type ProtoType (Cyc t m r) :: *

Methods

toProto :: Cyc t m r -> ProtoType (Cyc t m r)

fromProto :: MonadError String m => ProtoType (Cyc t m r) -> m (Cyc t m r)

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

\(R_p\) is an \(\F_{p^d}\)-module when \(d\) divides \(\varphi(m)\), by applying \(d\)-dimensional \(\F_p\)-linear transform on \(d\)-dim chunks of powerful basis coeffs.

Methods

(*>) :: GF k fp d -> Cyc t m fp -> Cyc t m fp

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

Methods

reduce :: Cyc t m a -> Cyc t m b

type ProtoType (Cyc t m r)

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

type LiftOf (Cyc t m r)

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

type DecompOf (Cyc t m zq)

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 :: (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 \(m\)th 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\cdot 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, ToRational v, MonadRandom rnd) => v -> Cyc t m zp -> rnd (Cyc t m z)

Generate an LWE error term with given scaled variance \(v \cdot 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) = (\hat{m} / \hat{m}') \cdot \Tr((g' / g) \cdot 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.