Safe Haskell | None |
---|---|
Language | Haskell2010 |
\( \def\Z{\mathbb{Z}} \) \( \def\F{\mathbb{F}} \) \( \def\Q{\mathbb{Q}} \) \( \def\O{\mathcal{O}} \)
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
- data E
- type UCycEC t m r = Either (UCyc t m E r) (UCyc t m C r)
- type UCycPC t m r = Either (UCyc t m P r) (UCyc t m C r)
- type UCRTElt t r = (Tensor t, CRTEmbed r, CRTrans Maybe r, TElt t r, CRTrans Identity (CRTExt r), TElt t (CRTExt r))
- type NFElt r = (NFData r, NFData (CRTExt r))
- toPow :: (Fact m, UCRTElt t r) => UCyc t m rep r -> UCyc t m P r
- toDec :: (Fact m, UCRTElt t r) => UCyc t m rep r -> UCyc t m D r
- toCRT :: forall t m rep r. (Fact m, UCRTElt t r) => UCyc t m rep r -> UCycEC t m 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
- 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)
- 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)
- unzipCRTC :: (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))
- unzipCRTE :: (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))
- scalarPow :: (Tensor t, Fact m, Ring r, TElt t r) => r -> UCyc t m P r
- scalarCRT :: (Fact m, UCRTElt t r) => r -> UCycEC t m r
- mulG :: (Fact m, UCRTElt t r) => UCyc t m rep r -> UCyc t m rep r
- divGPow :: (Fact m, UCRTElt t r, ZeroTestable r, IntegralDomain r) => UCyc t m P r -> Maybe (UCyc t m P r)
- divGDec :: (Fact m, UCRTElt t r, ZeroTestable r, IntegralDomain r) => UCyc t m D r -> Maybe (UCyc t m D r)
- divGCRTC :: (Fact m, UCRTElt t r) => UCyc t m C r -> UCyc t m C 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, 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
- embedCRTC :: (m `Divides` m', UCRTElt t r) => UCyc t m C r -> Either (UCyc t m' P r) (UCyc t m' C r)
- 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)
- 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
- twaceCRTC :: (m `Divides` m', UCRTElt t r) => UCyc t m' C r -> UCycPC t m r
- 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)
- 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', UCRTElt 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_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; rep
is the representation (P
, D
, or C
);
r
is the base ring of the coefficients (e.g., \(\Z\), \(\Z_q\)).
The Functor
, Applicative
, Foldable
and Traversable
instances all work coefficient-wise (in the specified basis).
(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 # | |
(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 # | |
(Random r, UCRTElt t r, Fact m) => Random (UCycPC 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 |
(GFCtx k fp d, Fact m, Tensor t, TElt t fp) => C (GF k fp d) (UCyc t m P 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. |
(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 # | |
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) Source # | |
type LiftOf (UCyc t m D r) Source # | |
type LiftOf (UCyc t m P r) Source # | |
Nullary index type representing the powerful basis.
(Ring r, Tensor t, Fact m, TElt t r) => C r (UCyc t m P 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 # | |
(Random r, UCRTElt t r, Fact m) => Random (UCycPC t m r) Source # | |
(GFCtx k fp d, Fact m, Tensor t, TElt t fp) => C (GF k fp d) (UCyc t m P 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. |
(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) Source # | |
Nullary index type representing the decoding basis.
(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 # | |
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) Source # | |
type LiftOf (UCyc t m D r) Source # | |
Nullary index type representing the CRT basis over base ring.
(Ring r, Fact m, UCRTElt t r) => C r (UCycEC t m r) Source # | |
(Tensor t, Fact m) => Foldable (UCyc t m C) Source # | |
(Random r, UCRTElt t r, Fact m) => Random (UCycPC 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 |
(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 # | |
Nullary index type representing the CRT basis over extension of base ring.
type UCycEC t m r = Either (UCyc t m E r) (UCyc t m C r) Source #
Convenient synonym for either CRT representation.
type UCycPC t m r = Either (UCyc t m P r) (UCyc t m C r) Source #
Convenient synonym for random sampling.
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 :: (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 #
unzipCRTE :: (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 #
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 :: (Fact m, UCRTElt t r) => UCyc t m rep r -> UCyc t m rep r Source #
Multiply by the special element \(g_m\).
divGPow :: (Fact m, UCRTElt t r, ZeroTestable r, IntegralDomain r) => UCyc t m P r -> Maybe (UCyc t m P r) Source #
Divide by the special element \(g_m\). WARNING: this implementation is not a constant-time algorithm, so information about the argument may be leaked through a timing channel.
divGDec :: (Fact m, UCRTElt t r, ZeroTestable r, IntegralDomain r) => UCyc t m D r -> Maybe (UCyc t m D r) Source #
Similar to divGPow
.
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\cdot 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, 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 \cdot 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 #
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 #
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.
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 #
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).