Safe Haskell	None
Language	Haskell2010

Crypto.Lol.Cyclotomic.UCyc

Contents

Data types and constraints
Changing representation
Scalars
Basic operations
Error sampling
Inter-ring operations and values

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.

Synopsis

Data types and constraints

data UCyc t m rep r Source

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

(Ring r, Fact m, UCRTElt t r) => C r (UCycEC t m r) Source
(Ring r, Tensor t, Fact m, TElt t r) => C r (UCyc t m D r) Source
(Ring r, Tensor t, Fact m, TElt t r) => C r (UCyc t m P r) Source
(Random r, UCRTElt t r, Fact m) => Random (Either (UCyc t m P r) (UCyc t m C r)) Source
(Tensor t, Fact m) => Functor (UCyc t m D) Source	apply coefficient-wise (with respect to decoding basis)
(Tensor t, Fact m) => Functor (UCyc t m P) Source	apply coefficient-wise (with respect to powerful basis)
(Tensor t, Fact m) => Applicative (UCyc t m D) Source
(Tensor t, Fact m) => Applicative (UCyc t m P) Source
(Tensor t, Fact m) => Foldable (UCyc t m C) Source
(Tensor t, Fact m) => Foldable (UCyc t m D) Source
(Tensor t, Fact m) => Foldable (UCyc t m P) Source
(Tensor t, Fact m) => Traversable (UCyc t m D) Source
(Tensor t, Fact m) => Traversable (UCyc t m P) Source
(Fact m, UCRTElt t r) => C (UCycEC t m r) Source	only for appropriate CRT representation
(Fact m, UCRTElt t r) => C (UCycEC t m r) Source	only for appropriate CRT representation (otherwise `zero` would violate internal invariant)
(GFCtx k fp d, Fact m, Tensor t, TElt t fp) => C (GF k fp d) (UCyc t m P fp) Source	`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
(Eq r, Tensor t, Fact m, TElt t r) => Eq (UCyc t m C r) Source
(Eq r, Tensor t, Fact m, TElt t r) => Eq (UCyc t m D r) Source
(Eq r, Tensor t, Fact m, TElt t r) => Eq (UCyc t m P r) Source
(Random r, UCRTElt t r, Fact m) => Random (UCyc t m D r) Source
(Random r, UCRTElt t r, Fact m) => Random (UCyc t m P r) Source
Arbitrary (t m r) => Arbitrary (UCyc t m D r) Source
Arbitrary (t m r) => Arbitrary (UCyc t m P r) Source
(Tensor t, Fact m, NFElt r, TElt t r, TElt t (CRTExt r)) => NFData (UCyc t m rep r) Source
(ZeroTestable r, Tensor t, Fact m, TElt t r) => C (UCyc t m C r) Source
(ZeroTestable r, Tensor t, Fact m, TElt t r) => C (UCyc t m D r) Source
(ZeroTestable r, Tensor t, Fact m, TElt t r) => C (UCyc t m P r) Source
(Additive r, Tensor t, Fact m, TElt t r) => C (UCyc t m D r) Source
(Additive r, Tensor t, Fact m, TElt t r) => C (UCyc t m P r) Source
(Fact m, Protoable (t m r)) => Protoable (UCyc t m D r) Source
(Lift' r, Tensor t, Fact m, TElt t r, TElt t (LiftOf r)) => Lift' (UCyc t m D r) Source
(Lift' r, Tensor t, Fact m, TElt t r, TElt t (LiftOf r)) => Lift' (UCyc t m P r) Source
(Rescale a b, Tensor t, Fact m, TElt t a, TElt t b) => Rescale (UCyc t m D a) (UCyc t m D b) Source
(Rescale a b, Tensor t, Fact m, TElt t a, TElt t b) => Rescale (UCyc t m P a) (UCyc t m P b) Source
(Reduce a b, Tensor t, Fact m, TElt t a, TElt t b) => Reduce (UCyc t m D a) (UCyc t m D b) Source
(Reduce a b, Tensor t, Fact m, TElt t a, TElt t b) => Reduce (UCyc t m P a) (UCyc t m P b) Source
type ProtoType (UCyc t m D r) = ProtoType (t m r) Source
type LiftOf (UCyc t m D r) = UCyc t m D (LiftOf r) Source
type LiftOf (UCyc t m P r) = UCyc t m P (LiftOf r) Source

data P Source

Nullary index type representing the powerful basis.

Instances

(Ring r, Tensor t, Fact m, TElt t r) => C r (UCyc t m P r) Source
(Random r, UCRTElt t r, Fact m) => Random (Either (UCyc t m P r) (UCyc t m C r)) Source
(Tensor t, Fact m) => Functor (UCyc t m P) Source	apply coefficient-wise (with respect to powerful basis)
(Tensor t, Fact m) => Applicative (UCyc t m P) Source
(Tensor t, Fact m) => Foldable (UCyc t m P) Source
(Tensor t, Fact m) => Traversable (UCyc t m P) Source
(GFCtx k fp d, Fact m, Tensor t, TElt t fp) => C (GF k fp d) (UCyc t m P fp) Source	`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
(Eq r, Tensor t, Fact m, TElt t r) => Eq (UCyc t m P r) Source
(Random r, UCRTElt t r, Fact m) => Random (UCyc t m P r) Source
Arbitrary (t m r) => Arbitrary (UCyc t m P r) Source
(ZeroTestable r, Tensor t, Fact m, TElt t r) => C (UCyc t m P r) Source
(Additive r, Tensor t, Fact m, TElt t r) => C (UCyc t m P r) Source
(Lift' r, Tensor t, Fact m, TElt t r, TElt t (LiftOf r)) => Lift' (UCyc t m P r) Source
(Rescale a b, Tensor t, Fact m, TElt t a, TElt t b) => Rescale (UCyc t m P a) (UCyc t m P b) Source
(Reduce a b, Tensor t, Fact m, TElt t a, TElt t b) => Reduce (UCyc t m P a) (UCyc t m P b) Source
type LiftOf (UCyc t m P r) = UCyc t m P (LiftOf r) Source

data D Source

Nullary index type representing the decoding basis.

Instances

(Ring r, Tensor t, Fact m, TElt t r) => C r (UCyc t m D r) Source
(Tensor t, Fact m) => Functor (UCyc t m D) Source	apply coefficient-wise (with respect to decoding basis)
(Tensor t, Fact m) => Applicative (UCyc t m D) Source
(Tensor t, Fact m) => Foldable (UCyc t m D) Source
(Tensor t, Fact m) => Traversable (UCyc t m D) Source
(Eq r, Tensor t, Fact m, TElt t r) => Eq (UCyc t m D r) Source
(Random r, UCRTElt t r, Fact m) => Random (UCyc t m D r) Source
Arbitrary (t m r) => Arbitrary (UCyc t m D r) Source
(ZeroTestable r, Tensor t, Fact m, TElt t r) => C (UCyc t m D r) Source
(Additive r, Tensor t, Fact m, TElt t r) => C (UCyc t m D r) Source
(Fact m, Protoable (t m r)) => Protoable (UCyc t m D r) Source
(Lift' r, Tensor t, Fact m, TElt t r, TElt t (LiftOf r)) => Lift' (UCyc t m D r) Source
(Rescale a b, Tensor t, Fact m, TElt t a, TElt t b) => Rescale (UCyc t m D a) (UCyc t m D b) Source
(Reduce a b, Tensor t, Fact m, TElt t a, TElt t b) => Reduce (UCyc t m D a) (UCyc t m D b) Source
type ProtoType (UCyc t m D r) = ProtoType (t m r) Source
type LiftOf (UCyc t m D r) = UCyc t m D (LiftOf r) Source

data C Source

Nullary index type representing the CRT basis over base ring.

Instances

(Ring r, Fact m, UCRTElt t r) => C r (UCycEC t m r) Source
(Random r, UCRTElt t r, Fact m) => Random (Either (UCyc t m P r) (UCyc t m C r)) Source
(Tensor t, Fact m) => Foldable (UCyc t m C) Source
(Fact m, UCRTElt t r) => C (UCycEC t m r) Source	only for appropriate CRT representation
(Fact m, UCRTElt t r) => C (UCycEC t m r) Source	only for appropriate CRT representation (otherwise `zero` would violate internal invariant)
(Eq r, Tensor t, Fact m, TElt t r) => Eq (UCyc t m C r) Source
(ZeroTestable r, Tensor t, Fact m, TElt t r) => C (UCyc t m C r) Source

data E Source

Nullary index type representing the CRT basis over extension of base ring.

Instances

(Ring r, Fact m, UCRTElt t r) => C r (UCycEC t m r) Source
(Fact m, UCRTElt t r) => C (UCycEC t m r) Source	only for appropriate CRT representation
(Fact m, UCRTElt t r) => C (UCycEC t m r) Source	only for appropriate CRT representation (otherwise `zero` would violate internal invariant)

type UCycEC t m r = Either (UCyc t m E r) (UCyc t m C r) Source

Convenient synonym for either CRT representation.

type UCRTElt t r = (Tensor t, CRTEmbed r, CRTrans Maybe r, TElt t r, CRTrans Identity (CRTExt r), TElt t (CRTExt r)) Source

Constraints needed for CRT-related operations on UCyc data.

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

Convenient synonym for deepseq-able element type.

Changing representation

toPow :: (Fact m, UCRTElt t r) => UCyc t m rep r -> UCyc t m P r Source

Convert to powerful-basis representation.

toDec :: (Fact m, UCRTElt 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, UCRTElt t r) => UCyc t m rep r -> UCycEC t m 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) fmap 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) fmap for decoding-basis representation.

unzipPow :: (Tensor t, Fact m, TElt t (a, b), TElt t a, TElt t b) => UCyc t m P (a, b) -> (UCyc t m P a, UCyc t m P b) Source

Unzip in the powerful basis.

unzipDec :: (Tensor t, Fact m, TElt t (a, b), TElt t a, TElt t b) => UCyc t m D (a, b) -> (UCyc t m D a, UCyc t m D b) Source

Unzip in the decoding basis.

unzipCRTC :: (Tensor t, Fact m, UCRTElt t (a, b), UCRTElt t a, UCRTElt t b) => UCyc t m C (a, b) -> (Either (UCyc t m P a) (UCyc t m C a), Either (UCyc t m P b) (UCyc t m C b)) Source

Unzip in the CRT basis over the base ring. The output components are Either because each target base ring may not support C.

unzipCRTE :: (Tensor t, Fact m, UCRTElt t (a, b), UCRTElt t a, UCRTElt t b) => UCyc t m E (a, b) -> (Either (UCyc t m P a) (UCyc t m E a), Either (UCyc t m P b) (UCyc t m E b)) Source

Unzip in the CRT basis over the extension of the base ring. The output components are Either because each target base might instead support C.

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.

scalarCRT :: (Fact m, UCRTElt t r) => r -> UCycEC t m r Source

Embed a scalar from the base ring.

Basic operations

mulG :: (Tensor t, Fact m, UCRTElt t r) => UCyc t m rep r -> UCyc t m rep r Source

Multiply by the special element g.

divG :: (Tensor t, Fact m, UCRTElt t r, ZeroTestable r, IntegralDomain r) => UCyc t m rep r -> Maybe (UCyc t m rep r) Source

Divide by the special element g. WARNING: this implementation is not a constant-time algorithm, so information about the argument may be leaked through a timing channel.

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.

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

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

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.

embedCRTC :: (m `Divides` m', UCRTElt t r) => UCyc t m C r -> Either (UCyc t m' P r) (UCyc t m' C r) Source

Embed into an extension ring, for the CRT basis. (The output is an Either because the extension ring might not support C.)

embedCRTE :: forall m m' t r. (m `Divides` m', UCRTElt t r) => UCyc t m E r -> Either (UCyc t m' P r) (UCyc t m' E r) Source

Similar to embedCRTC. (The output is an Either because the extension ring might support C, in which case we never use E.)

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.

twaceCRTC :: (m `Divides` m', UCRTElt t r) => UCyc t m' C r -> Either (UCyc t m P r) (UCyc t m C r) Source

Twace into a subring, for the CRT basis. (The output is an Either because the subring might not support C.)

twaceCRTE :: forall t m m' r. (m `Divides` m', UCRTElt t r) => UCyc t m' E r -> Either (UCyc t m P r) (UCyc t m E r) Source

Similar to twaceCRTC. (The output is an Either because the subring might support C, in which case we never use E.)

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', UCRTElt 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).