| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Crypto.Lol.Cyclotomic.UCyc
Contents
Description
A low-level implementation of cyclotomic rings that allows (and requires) the programmer to control the underlying representation of ring elements, i.e., powerful, decoding, or CRT basis.
WARNING: as with all fixed-point arithmetic, the functions
associated with UCyc 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 UCyc t m rep r
- data P
- data D
- data C
- type UCElt t r = (Tensor t, CRTEmbed r, CRTElt t r, CRTElt t (CRTExt r))
- type NFElt r = (NFData r, NFData (CRTExt r))
- toPow :: (Fact m, UCElt t r) => UCyc t m rep r -> UCyc t m P r
- toDec :: (Fact m, UCElt t r) => UCyc t m rep r -> UCyc t m D r
- toCRT :: forall t m rep r. (Fact m, UCElt t r) => UCyc t m rep r -> UCyc t m C r
- fmapPow :: (Tensor t, Fact m, TElt t a, TElt t b) => (a -> b) -> UCyc t m P a -> UCyc t m P b
- fmapDec :: (Tensor t, Fact m, TElt t a, TElt t b) => (a -> b) -> UCyc t m D a -> UCyc t m D b
- unzipCyc :: (Tensor t, Fact m) => UCyc t m rep (a, b) -> (UCyc t m rep a, UCyc t m rep b)
- unzipUCElt :: (Tensor t, Fact m, UCElt t (a, b), UCElt t a, UCElt t b) => UCyc t m rep (a, b) -> (UCyc t m rep a, UCyc t m rep b)
- scalarPow :: (Tensor t, Fact m, Ring r, TElt t r) => r -> UCyc t m P r
- scalarCRT :: (Fact m, UCElt t r) => r -> UCyc t m C r
- mulG :: (Tensor t, Fact m, UCElt t r) => UCyc t m rep r -> UCyc t m rep r
- divG :: (Tensor t, Fact m, UCElt t r) => UCyc t m rep r -> Maybe (UCyc t m rep r)
- gSqNorm :: (Ring r, Tensor t, Fact m, TElt t r) => UCyc t m D r -> r
- tGaussian :: (Tensor t, Fact m, OrdFloat q, Random q, TElt t q, ToRational v, MonadRandom rnd) => v -> rnd (UCyc t m D q)
- errorRounded :: forall v rnd t m z. (ToInteger z, Tensor t, Fact m, TElt t z, ToRational v, MonadRandom rnd) => v -> rnd (UCyc t m D z)
- errorCoset :: forall t m zp z v rnd. (Mod zp, z ~ ModRep zp, Lift zp z, Tensor t, Fact m, TElt t zp, TElt t z, ToRational v, MonadRandom rnd) => v -> UCyc t m D zp -> rnd (UCyc t m D z)
- embedPow :: (Additive r, Tensor t, m `Divides` m', TElt t r) => UCyc t m P r -> UCyc t m' P r
- embedDec :: (Additive r, Tensor t, m `Divides` m', TElt t r) => UCyc t m D r -> UCyc t m' D r
- embedCRT :: forall t m m' r. (m `Divides` m', UCElt t r) => UCyc t m C r -> Either (UCyc t m' P r) (UCyc t m' C r)
- twacePow :: (Ring r, Tensor t, m `Divides` m', TElt t r) => UCyc t m' P r -> UCyc t m P r
- twaceDec :: (Ring r, Tensor t, m `Divides` m', TElt t r) => UCyc t m' D r -> UCyc t m D r
- twaceCRT :: forall t m m' r. (m `Divides` m', UCElt t r) => UCyc t m' C r -> Either (UCyc t m P r) (UCyc t m C r)
- coeffsPow :: (Ring r, Tensor t, m `Divides` m', TElt t r) => UCyc t m' P r -> [UCyc t m P r]
- coeffsDec :: (Ring r, Tensor t, m `Divides` m', TElt t r) => UCyc t m' D r -> [UCyc t m D r]
- powBasis :: (Ring r, Tensor t, m `Divides` m', TElt t r) => Tagged m [UCyc t m' P r]
- crtSet :: forall t m m' r p mbar m'bar. (m `Divides` m', ZPP r, p ~ CharOf (ZpOf r), mbar ~ PFree p m, m'bar ~ PFree p m', UCElt t r, TElt t (ZpOf r)) => Tagged m [UCyc t m' P r]
Data types 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; rep is the representation (P, D, or C);
r is the base ring of the coefficients (e.g., Z, Zq).
The Functor, Applicative, Foldable and Traversable
instances all work coefficient-wise (in the specified basis).
Instances
Nullary index type representing the powerful basis.
Instances
Nullary index type representing the decoding basis.
Instances
| (Ring r, Tensor t, Fact m, TElt t r) => C r (UCyc Factored t m D r) Source | |
| (Tensor t, Fact m) => Functor (UCyc Factored t m D) Source | |
| (Tensor t, Fact m) => Applicative (UCyc Factored t m D) Source | |
| (Tensor t, Fact m) => Foldable (UCyc Factored t m D) Source | |
| (Tensor t, Fact m) => Traversable (UCyc Factored t m D) Source | |
| (Eq r, Tensor t, Fact m, TElt t r) => Eq (UCyc Factored t m D r) Source | |
| Arbitrary (t m r) => Arbitrary (UCyc k t m D r) Source | |
| (ZeroTestable r, Tensor t, Fact m, TElt t r) => C (UCyc Factored t m D r) Source | |
| (Additive r, Tensor t, Fact m, TElt t r) => C (UCyc Factored t m D r) Source | |
| (Lift' r, Tensor t, Fact m, TElt t r, TElt t (LiftOf r)) => Lift' (UCyc Factored t m D r) Source | |
| (Rescale a b, Tensor t, Fact m, TElt t a, TElt t b) => Rescale (UCyc Factored t m D a) (UCyc Factored t m D b) Source | |
| (Reduce a b, Tensor t, Fact m, TElt t a, TElt t b) => Reduce (UCyc Factored t m D a) (UCyc Factored t m D b) Source | |
| type LiftOf (UCyc k t m D r) = UCyc k t m D (LiftOf r) Source |
Nullary index type representing a CRT basis.
Instances
| (Ring r, Fact m, UCElt t r) => C r (UCyc Factored t m C r) Source | |
| (Random r, Tensor t, Fact m, CRTElt t r) => Random (Either (UCyc Factored t m P r) (UCyc Factored t m C r)) Source | |
| (Eq r, Fact m, UCElt t r) => Eq (UCyc Factored t m C r) Source | |
| Arbitrary (t m r) => Arbitrary (UCyc k t m C r) Source | |
| (Fact m, UCElt t r) => C (UCyc Factored t m C r) Source | |
| (ZeroTestable r, Fact m, UCElt t r) => C (UCyc Factored t m C r) Source | |
| (Fact m, UCElt t r) => C (UCyc Factored t m C r) Source |
type NFElt r = (NFData r, NFData (CRTExt r)) Source
Convenient synonym for deepseq-able element type.
Changing representation
toPow :: (Fact m, UCElt t r) => UCyc t m rep r -> UCyc t m P r Source
Convert to powerful-basis representation.
toDec :: (Fact m, UCElt t r) => UCyc t m rep r -> UCyc t m D r Source
Convert to decoding-basis representation.
toCRT :: forall t m rep r. (Fact m, UCElt t r) => UCyc t m rep r -> UCyc t m C r Source
Convert to a CRT-basis representation.
fmapPow :: (Tensor t, Fact m, TElt t a, TElt t b) => (a -> b) -> UCyc t m P a -> UCyc t m P b Source
Type-restricted (and potentially more efficient) map for powerful-basis representation.
fmapDec :: (Tensor t, Fact m, TElt t a, TElt t b) => (a -> b) -> UCyc t m D a -> UCyc t m D b Source
Type-restricted (and potentially more efficient) map for decoding-basis representation.
unzipCyc :: (Tensor t, Fact m) => UCyc t m rep (a, b) -> (UCyc t m rep a, UCyc t m rep b) Source
Unzip for unrestricted types.
unzipUCElt :: (Tensor t, Fact m, UCElt t (a, b), UCElt t a, UCElt t b) => UCyc t m rep (a, b) -> (UCyc t m rep a, UCyc t m rep b) Source
Type-restricted (and potentially more efficient) unzip.
Scalars
scalarPow :: (Tensor t, Fact m, Ring r, TElt t r) => r -> UCyc t m P r Source
Embed a scalar from the base ring.
Basic operations
mulG :: (Tensor t, Fact m, UCElt t r) => UCyc t m rep r -> UCyc t m rep r Source
Multiply by the special element g.
divG :: (Tensor t, Fact m, UCElt t r) => UCyc t m rep r -> Maybe (UCyc t m rep r) Source
Divide by the special element g.
gSqNorm :: (Ring r, Tensor t, Fact m, TElt t r) => UCyc t m D 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 .
Error sampling
tGaussian :: (Tensor t, Fact m, OrdFloat q, Random q, TElt t q, ToRational v, MonadRandom rnd) => v -> rnd (UCyc t m D 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 :: forall v rnd t m z. (ToInteger z, Tensor t, Fact m, TElt t z, ToRational v, MonadRandom rnd) => v -> rnd (UCyc t m D z) Source
Generate an LWE error term from the "tweaked" Gaussian with given scaled variance, deterministically rounded using the decoding basis.
errorCoset :: forall t m zp z v rnd. (Mod zp, z ~ ModRep zp, Lift zp z, Tensor t, Fact m, TElt t zp, TElt t z, ToRational v, MonadRandom rnd) => v -> UCyc t m D zp -> rnd (UCyc t m D z) Source
Generate an LWE error term from the "tweaked" Gaussian with
scaled variance v * p^2, deterministically rounded to the given
coset of R_p using the decoding basis.
Inter-ring operations and values
embedPow :: (Additive r, Tensor t, m `Divides` m', TElt t r) => UCyc t m P r -> UCyc t m' P r Source
Embed into an extension ring, for the powerful basis.
embedDec :: (Additive r, Tensor t, m `Divides` m', TElt t r) => UCyc t m D r -> UCyc t m' D r Source
Embed into an extension ring, for the decoding basis.
embedCRT :: forall t m m' r. (m `Divides` m', UCElt t r) => UCyc t m C r -> Either (UCyc t m' P r) (UCyc t m' C r) Source
twacePow :: (Ring r, Tensor t, m `Divides` m', TElt t r) => UCyc t m' P r -> UCyc t m P r Source
Twace into a subring, for the powerful basis.
twaceDec :: (Ring r, Tensor t, m `Divides` m', TElt t r) => UCyc t m' D r -> UCyc t m D r Source
Twace into a subring, for the decoding basis.
twaceCRT :: forall t m m' r. (m `Divides` m', UCElt t r) => UCyc t m' C r -> Either (UCyc t m P r) (UCyc t m C r) Source
coeffsPow :: (Ring r, Tensor t, m `Divides` m', TElt t r) => UCyc t m' P r -> [UCyc t m P r] Source
Yield the O_m-coefficients of an O_m'-element, with respect to
the relative powerful O_m-basis.
coeffsDec :: (Ring r, Tensor t, m `Divides` m', TElt t r) => UCyc t m' D r -> [UCyc t m D r] Source
Yield the O_m-coefficients of an O_m' element, with respect to
the relative decoding O_m-basis.
powBasis :: (Ring r, Tensor t, m `Divides` m', TElt t r) => Tagged m [UCyc t m' P r] Source
The relative powerful basis of O_m' / O_m.
crtSet :: forall t m m' r p mbar m'bar. (m `Divides` m', ZPP r, p ~ CharOf (ZpOf r), mbar ~ PFree p m, m'bar ~ PFree p m', UCElt t r, TElt t (ZpOf r)) => Tagged m [UCyc t m' P r] Source
The relative mod-r CRT set of O_m' / O_m, represented with
respect to the powerful basis (which seems to be the best choice
for typical use cases).