| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Crypto.Lol.Cyclotomic.Cyc
Contents
Description
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 Cyc t m r
- type CElt t r = UCElt t r
- type NFElt r = (NFData r, NFData (CRTExt r))
- cycPow :: UCyc t m P r -> Cyc t m r
- cycDec :: UCyc t m D r -> Cyc t m r
- cycCRT :: UCyc t m C r -> Cyc t m r
- scalarCyc :: 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 -> UCyc t m C r
- unzipCyc :: (Tensor t, Fact m) => Cyc t m (a, b) -> (Cyc t m a, Cyc t m b)
- 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)
- mulG :: (Fact m, CElt t r) => Cyc t m r -> Cyc t m r
- divG :: (Fact m, CElt t 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, TElt t z, 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', CElt t 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]
- 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]
- class RescaleCyc c a b where
- rescaleCyc :: Fact m => Basis -> c m a -> c m b
- data Basis
Data type and constraints
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) Source | |
| (Decompose k gad zq, Fact m, CElt t zq, CElt t (DecompOf zq)) => Decompose k gad (Cyc t m zq) Source | |
| (Gadget k gad zq, Fact m, CElt t zq) => Gadget k gad (Cyc t m zq) Source | |
| (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 | |
| (Eq r, Fact m, CElt t r) => Eq (Cyc t m r) Source | |
| (Show r, Show (CRTExt r), Tensor t, Fact m, TElt t r, TElt t (CRTExt r)) => Show (Cyc t m r) Source | |
| (Random r, Tensor t, Fact m, CRTElt t r) => Random (Cyc t m r) Source | |
| Arbitrary (UCyc Factored 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 | |
| (GFCtx k fp d, Fact m, CElt t fp) => C (GF k fp d) (Cyc t m fp) Source | |
| (Reduce a b, Fact m, CElt t a, CElt t b) => Reduce (Cyc t m a) (Cyc t m b) Source | |
| type LiftOf (Cyc t m r) = Cyc t m (LiftOf r) Source | |
| type DecompOf (Cyc t m zq) = Cyc t m (DecompOf zq) Source |
type NFElt r = (NFData r, NFData (CRTExt r)) Source
Convenient synonym for deepseq-able element type.
Constructors/deconstructors
unzipCyc :: (Tensor t, Fact m) => Cyc t m (a, b) -> (Cyc t m a, Cyc t m b) Source
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) Source
Type-restricted (and potentially more efficient) unzip.
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 mth cyclotomic.
divG :: (Fact m, CElt t 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*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) Source
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) Source
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 Source
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 Source
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] Source
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] Source
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] Source
The relative mod-r CRT set of the extension.
Rescaling cyclotomic elements
class RescaleCyc c a b where Source
Represents cyclotomic rings that are rescalable over their base rings. (This is a class because it allows for more efficient specialized implementations.)