Safe Haskell | None |
---|---|
Language | Haskell2010 |
\( \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 Cyc t m r
- type CElt t r = (UCRTElt t r, ZeroTestable r)
- type NFElt r = (NFData r, NFData (CRTExt r))
- scalarCyc :: r -> Cyc t m r
- cycPow :: UCyc t m P r -> Cyc t m r
- cycDec :: UCyc t m D r -> Cyc t m r
- cycCRT :: UCycEC t m r -> Cyc t m r
- cycCRTC :: UCyc t m C r -> Cyc t m r
- cycCRTE :: UCyc t m E r -> Cyc t m r
- cycPC :: Either (UCyc t m P r) (UCyc t m C r) -> Cyc t m r
- cycPE :: Either (UCyc t m P r) (UCyc t m E r) -> Cyc t m r
- uncycPow :: (Fact m, CElt t r) => Cyc t m r -> UCyc t m P r
- uncycDec :: (Fact m, CElt t r) => Cyc t m r -> UCyc t m D r
- uncycCRT :: (Fact m, CElt t r) => Cyc t m r -> UCycEC t m r
- 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)
- mulG :: (Fact m, CElt t r) => Cyc t m r -> Cyc t m r
- divG :: (Fact m, CElt t r, IntegralDomain r) => Cyc t m r -> Maybe (Cyc t m r)
- gSqNorm :: forall t m r. (Fact m, CElt t r) => Cyc t m r -> r
- liftCyc :: (Lift b a, Fact m, TElt t a, CElt t b) => Basis -> Cyc t m b -> Cyc t m a
- liftPow :: (Lift b a, Fact m, TElt t a, CElt t b) => Cyc t m b -> Cyc t m a
- liftDec :: (Lift b a, Fact m, TElt t a, CElt t b) => Cyc t m b -> Cyc t m a
- advisePow :: (Fact m, CElt t r) => Cyc t m r -> Cyc t m r
- adviseDec :: (Fact m, CElt t r) => Cyc t m r -> Cyc t m r
- adviseCRT :: (Fact m, CElt t r) => Cyc t m r -> Cyc t m r
- tGaussian :: (Fact m, OrdFloat q, Random q, Tensor t, TElt t q, ToRational v, MonadRandom rnd) => v -> rnd (Cyc t m q)
- errorRounded :: (ToInteger z, Tensor t, Fact m, TElt t z, ToRational v, MonadRandom rnd) => v -> rnd (Cyc t m z)
- 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)
- embed :: forall t m m' r. m `Divides` m' => Cyc t m r -> Cyc t m' r
- twace :: forall t m m' r. (m `Divides` m', UCRTElt t r, ZeroTestable r) => Cyc t m' r -> Cyc t m r
- coeffsCyc :: (m `Divides` m', CElt t r) => Basis -> Cyc t m' r -> [Cyc t m r]
- coeffsPow :: (m `Divides` m', CElt t r) => Cyc t m' r -> [Cyc t m r]
- coeffsDec :: (m `Divides` m', CElt t r) => Cyc t m' r -> [Cyc t m r]
- powBasis :: (m `Divides` m', CElt t r) => Tagged m [Cyc t m' r]
- crtSet :: (m `Divides` m', ZPP r, CElt t r, TElt t (ZpOf r)) => Tagged m [Cyc t m' r]
Data type and constraints
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\)).
(Correct k gad zq, Fact m, CElt t zq) => Correct k gad (Cyc t m zq) Source # | 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) Source # | 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) Source # | promoted from base ring |
(Rescale a b, CElt t a, TElt t b) => RescaleCyc (Cyc t) a b Source # | |
(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 Source # | specialized instance for product rings of \(\Z_q\)s: ~2x faster algorithm |
(Eq r, Fact m, CElt t r) => Eq (Cyc t m r) Source # | |
(Random r, Tensor t, Fact m, UCRTElt t r) => Random (Cyc t m r) Source # | |
Arbitrary (UCyc t m P r) => Arbitrary (Cyc t m r) Source # | |
(Tensor t, Fact m, NFData r, TElt t r, NFData (CRTExt r), TElt t (CRTExt r)) => NFData (Cyc t m r) Source # | |
(Fact m, CElt t r) => C (Cyc t m r) Source # | |
(Fact m, CElt t r) => C (Cyc t m r) Source # | |
(Fact m, CElt t r) => C (Cyc t m r) Source # | |
(Fact m, CElt t r, Protoable (UCyc t m D r)) => Protoable (Cyc t m r) Source # | |
(GFCtx k fp d, Fact m, CElt t fp) => C (GF k fp d) (Cyc t m fp) Source # | \(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. |
(Reduce a b, Fact m, CElt t a, CElt t b) => Reduce (Cyc t m a) (Cyc t m b) Source # | |
type ProtoType (Cyc t m r) Source # | |
type LiftOf (Cyc t m r) Source # | |
type DecompOf (Cyc t m zq) Source # | |
type CElt t r = (UCRTElt t r, ZeroTestable r) Source #
Constraints needed for most operations involving Cyc
data.
type NFElt r = (NFData r, NFData (CRTExt r)) Source #
Convenient synonym for deepseq
-able element type.
Constructors/deconstructors
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) Source #
Unzip for a pair base ring.
Core cyclotomic operations
mulG :: (Fact m, CElt t r) => Cyc t m r -> Cyc t m r Source #
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) Source #
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 Source #
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 Source #
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 Source #
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 Source #
Lift using the decoding basis.
Representation advice
advisePow :: (Fact m, CElt t r) => Cyc t m r -> Cyc t m r Source #
Same as adviseCRT
, but for the powerful-basis representation.
adviseDec :: (Fact m, CElt t r) => Cyc t m r -> Cyc t m r Source #
Same as adviseCRT
, but for the powerful-basis representation.
adviseCRT :: (Fact m, CElt t r) => Cyc t m r -> Cyc t m r Source #
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) Source #
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) Source #
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) Source #
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 Source #
Embed (lazily) into an extension ring.
twace :: forall t m m' r. (m `Divides` m', UCRTElt t r, ZeroTestable r) => Cyc t m' r -> Cyc t m r Source #
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
).
coeffsPow :: (m `Divides` m', CElt t r) => Cyc t m' r -> [Cyc t m r] Source #
Specialized version of coeffsCyc
for powerful basis.
coeffsDec :: (m `Divides` m', CElt t r) => Cyc t m' r -> [Cyc t m r] Source #
Specialized version of coeffsCyc
for decoding basis.