lol-0.4.0.0: A library for lattice cryptography.

Safe HaskellNone
LanguageHaskell2010

Crypto.Lol.Cyclotomic.UCyc

Contents

Description

\( \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.

Synopsis

Data types and constraints

data UCyc t m rep r Source #

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).

Instances

(Ring r, Fact m, UCRTElt t r) => C r (UCycEC t m r) Source # 

Methods

(*>) :: r -> UCycEC t m r -> UCycEC t m r #

(Ring r, Tensor t, Fact m, TElt t r) => C r (UCyc t m D r) Source # 

Methods

(*>) :: r -> UCyc t m D r -> UCyc t m D r #

(Ring r, Tensor t, Fact m, TElt t r) => C r (UCyc t m P r) Source # 

Methods

(*>) :: r -> UCyc t m P r -> UCyc t m P r #

(Random r, UCRTElt t r, Fact m) => Random (Either (UCyc t m P r) (UCyc t m C r)) Source # 

Methods

randomR :: RandomGen g => (Either (UCyc t m P r) (UCyc t m C r), Either (UCyc t m P r) (UCyc t m C r)) -> g -> (Either (UCyc t m P r) (UCyc t m C r), g) #

random :: RandomGen g => g -> (Either (UCyc t m P r) (UCyc t m C r), g) #

randomRs :: RandomGen g => (Either (UCyc t m P r) (UCyc t m C r), Either (UCyc t m P r) (UCyc t m C r)) -> g -> [Either (UCyc t m P r) (UCyc t m C r)] #

randoms :: RandomGen g => g -> [Either (UCyc t m P r) (UCyc t m C r)] #

randomRIO :: (Either (UCyc t m P r) (UCyc t m C r), Either (UCyc t m P r) (UCyc t m C r)) -> IO (Either (UCyc t m P r) (UCyc t m C r)) #

randomIO :: IO (Either (UCyc t m P r) (UCyc t m C r)) #

(Tensor t, Fact m) => Functor (UCyc t m D) Source #

apply coefficient-wise (with respect to decoding basis)

Methods

fmap :: (a -> b) -> UCyc t m D a -> UCyc t m D b #

(<$) :: a -> UCyc t m D b -> UCyc t m D a #

(Tensor t, Fact m) => Functor (UCyc t m P) Source #

apply coefficient-wise (with respect to powerful basis)

Methods

fmap :: (a -> b) -> UCyc t m P a -> UCyc t m P b #

(<$) :: a -> UCyc t m P b -> UCyc t m P a #

(Tensor t, Fact m) => Applicative (UCyc t m D) Source # 

Methods

pure :: a -> UCyc t m D a #

(<*>) :: UCyc t m D (a -> b) -> UCyc t m D a -> UCyc t m D b #

(*>) :: UCyc t m D a -> UCyc t m D b -> UCyc t m D b #

(<*) :: UCyc t m D a -> UCyc t m D b -> UCyc t m D a #

(Tensor t, Fact m) => Applicative (UCyc t m P) Source # 

Methods

pure :: a -> UCyc t m P a #

(<*>) :: UCyc t m P (a -> b) -> UCyc t m P a -> UCyc t m P b #

(*>) :: UCyc t m P a -> UCyc t m P b -> UCyc t m P b #

(<*) :: UCyc t m P a -> UCyc t m P b -> UCyc t m P a #

(Tensor t, Fact m) => Foldable (UCyc t m C) Source # 

Methods

fold :: Monoid m => UCyc t m C m -> m #

foldMap :: Monoid m => (a -> m) -> UCyc t m C a -> m #

foldr :: (a -> b -> b) -> b -> UCyc t m C a -> b #

foldr' :: (a -> b -> b) -> b -> UCyc t m C a -> b #

foldl :: (b -> a -> b) -> b -> UCyc t m C a -> b #

foldl' :: (b -> a -> b) -> b -> UCyc t m C a -> b #

foldr1 :: (a -> a -> a) -> UCyc t m C a -> a #

foldl1 :: (a -> a -> a) -> UCyc t m C a -> a #

toList :: UCyc t m C a -> [a] #

null :: UCyc t m C a -> Bool #

length :: UCyc t m C a -> Int #

elem :: Eq a => a -> UCyc t m C a -> Bool #

maximum :: Ord a => UCyc t m C a -> a #

minimum :: Ord a => UCyc t m C a -> a #

sum :: Num a => UCyc t m C a -> a #

product :: Num a => UCyc t m C a -> a #

(Tensor t, Fact m) => Foldable (UCyc t m D) Source # 

Methods

fold :: Monoid m => UCyc t m D m -> m #

foldMap :: Monoid m => (a -> m) -> UCyc t m D a -> m #

foldr :: (a -> b -> b) -> b -> UCyc t m D a -> b #

foldr' :: (a -> b -> b) -> b -> UCyc t m D a -> b #

foldl :: (b -> a -> b) -> b -> UCyc t m D a -> b #

foldl' :: (b -> a -> b) -> b -> UCyc t m D a -> b #

foldr1 :: (a -> a -> a) -> UCyc t m D a -> a #

foldl1 :: (a -> a -> a) -> UCyc t m D a -> a #

toList :: UCyc t m D a -> [a] #

null :: UCyc t m D a -> Bool #

length :: UCyc t m D a -> Int #

elem :: Eq a => a -> UCyc t m D a -> Bool #

maximum :: Ord a => UCyc t m D a -> a #

minimum :: Ord a => UCyc t m D a -> a #

sum :: Num a => UCyc t m D a -> a #

product :: Num a => UCyc t m D a -> a #

(Tensor t, Fact m) => Foldable (UCyc t m P) Source # 

Methods

fold :: Monoid m => UCyc t m P m -> m #

foldMap :: Monoid m => (a -> m) -> UCyc t m P a -> m #

foldr :: (a -> b -> b) -> b -> UCyc t m P a -> b #

foldr' :: (a -> b -> b) -> b -> UCyc t m P a -> b #

foldl :: (b -> a -> b) -> b -> UCyc t m P a -> b #

foldl' :: (b -> a -> b) -> b -> UCyc t m P a -> b #

foldr1 :: (a -> a -> a) -> UCyc t m P a -> a #

foldl1 :: (a -> a -> a) -> UCyc t m P a -> a #

toList :: UCyc t m P a -> [a] #

null :: UCyc t m P a -> Bool #

length :: UCyc t m P a -> Int #

elem :: Eq a => a -> UCyc t m P a -> Bool #

maximum :: Ord a => UCyc t m P a -> a #

minimum :: Ord a => UCyc t m P a -> a #

sum :: Num a => UCyc t m P a -> a #

product :: Num a => UCyc t m P a -> a #

(Tensor t, Fact m) => Traversable (UCyc t m D) Source # 

Methods

traverse :: Applicative f => (a -> f b) -> UCyc t m D a -> f (UCyc t m D b) #

sequenceA :: Applicative f => UCyc t m D (f a) -> f (UCyc t m D a) #

mapM :: Monad m => (a -> m b) -> UCyc t m D a -> m (UCyc t m D b) #

sequence :: Monad m => UCyc t m D (m a) -> m (UCyc t m D a) #

(Tensor t, Fact m) => Traversable (UCyc t m P) Source # 

Methods

traverse :: Applicative f => (a -> f b) -> UCyc t m P a -> f (UCyc t m P b) #

sequenceA :: Applicative f => UCyc t m P (f a) -> f (UCyc t m P a) #

mapM :: Monad m => (a -> m b) -> UCyc t m P a -> m (UCyc t m P b) #

sequence :: Monad m => UCyc t m P (m a) -> m (UCyc t m P a) #

(Fact m, UCRTElt t r) => C (UCycEC t m r) Source #

only for appropriate CRT representation

Methods

(*) :: UCycEC t m r -> UCycEC t m r -> UCycEC t m r #

one :: UCycEC t m r #

fromInteger :: Integer -> UCycEC t m r #

(^) :: UCycEC t m r -> Integer -> UCycEC t m r #

(Fact m, UCRTElt t r) => C (UCycEC t m r) Source #

only for appropriate CRT representation (otherwise zero would violate internal invariant)

Methods

zero :: UCycEC t m r #

(+) :: UCycEC t m r -> UCycEC t m r -> UCycEC t m r #

(-) :: UCycEC t m r -> UCycEC t m r -> UCycEC t m r #

negate :: UCycEC t m r -> UCycEC t m r #

(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.

Methods

(*>) :: GF k fp d -> UCyc t m P fp -> UCyc t m P fp #

(Eq r, Tensor t, Fact m, TElt t r) => Eq (UCyc t m C r) Source # 

Methods

(==) :: UCyc t m C r -> UCyc t m C r -> Bool #

(/=) :: UCyc t m C r -> UCyc t m C r -> Bool #

(Eq r, Tensor t, Fact m, TElt t r) => Eq (UCyc t m D r) Source # 

Methods

(==) :: UCyc t m D r -> UCyc t m D r -> Bool #

(/=) :: UCyc t m D r -> UCyc t m D r -> Bool #

(Eq r, Tensor t, Fact m, TElt t r) => Eq (UCyc t m P r) Source # 

Methods

(==) :: UCyc t m P r -> UCyc t m P r -> Bool #

(/=) :: UCyc t m P r -> UCyc t m P r -> Bool #

(Random r, UCRTElt t r, Fact m) => Random (UCyc t m D r) Source # 

Methods

randomR :: RandomGen g => (UCyc t m D r, UCyc t m D r) -> g -> (UCyc t m D r, g) #

random :: RandomGen g => g -> (UCyc t m D r, g) #

randomRs :: RandomGen g => (UCyc t m D r, UCyc t m D r) -> g -> [UCyc t m D r] #

randoms :: RandomGen g => g -> [UCyc t m D r] #

randomRIO :: (UCyc t m D r, UCyc t m D r) -> IO (UCyc t m D r) #

randomIO :: IO (UCyc t m D r) #

(Random r, UCRTElt t r, Fact m) => Random (UCyc t m P r) Source # 

Methods

randomR :: RandomGen g => (UCyc t m P r, UCyc t m P r) -> g -> (UCyc t m P r, g) #

random :: RandomGen g => g -> (UCyc t m P r, g) #

randomRs :: RandomGen g => (UCyc t m P r, UCyc t m P r) -> g -> [UCyc t m P r] #

randoms :: RandomGen g => g -> [UCyc t m P r] #

randomRIO :: (UCyc t m P r, UCyc t m P r) -> IO (UCyc t m P r) #

randomIO :: IO (UCyc t m P r) #

Arbitrary (t m r) => Arbitrary (UCyc t m D r) Source # 

Methods

arbitrary :: Gen (UCyc t m D r) #

shrink :: UCyc t m D r -> [UCyc t m D r] #

Arbitrary (t m r) => Arbitrary (UCyc t m P r) Source # 

Methods

arbitrary :: Gen (UCyc t m P r) #

shrink :: UCyc t m P r -> [UCyc t m P r] #

(Tensor t, Fact m, NFElt r, TElt t r, TElt t (CRTExt r)) => NFData (UCyc t m rep r) Source # 

Methods

rnf :: UCyc t m rep r -> () #

(ZeroTestable r, Tensor t, Fact m, TElt t r) => C (UCyc t m C r) Source # 

Methods

isZero :: UCyc t m C r -> Bool #

(ZeroTestable r, Tensor t, Fact m, TElt t r) => C (UCyc t m D r) Source # 

Methods

isZero :: UCyc t m D r -> Bool #

(ZeroTestable r, Tensor t, Fact m, TElt t r) => C (UCyc t m P r) Source # 

Methods

isZero :: UCyc t m P r -> Bool #

(Additive r, Tensor t, Fact m, TElt t r) => C (UCyc t m D r) Source # 

Methods

zero :: UCyc t m D r #

(+) :: UCyc t m D r -> UCyc t m D r -> UCyc t m D r #

(-) :: UCyc t m D r -> UCyc t m D r -> UCyc t m D r #

negate :: UCyc t m D r -> UCyc t m D r #

(Additive r, Tensor t, Fact m, TElt t r) => C (UCyc t m P r) Source # 

Methods

zero :: UCyc t m P r #

(+) :: UCyc t m P r -> UCyc t m P r -> UCyc t m P r #

(-) :: UCyc t m P r -> UCyc t m P r -> UCyc t m P r #

negate :: UCyc t m P r -> UCyc t m P r #

Protoable (t m r) => Protoable (UCyc t m D r) Source # 

Associated Types

type ProtoType (UCyc t m D r) :: * Source #

Methods

toProto :: UCyc t m D r -> ProtoType (UCyc t m D r) Source #

fromProto :: MonadError String m => ProtoType (UCyc t m D r) -> m (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 # 

Methods

lift :: UCyc t m D r -> LiftOf (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 # 

Methods

lift :: UCyc t m P r -> LiftOf (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 # 

Methods

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 # 

Methods

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 # 

Methods

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 # 

Methods

reduce :: UCyc t m P a -> UCyc t m P b Source #

type ProtoType (UCyc t m D r) Source # 
type ProtoType (UCyc t m D r) = ProtoType (t m r)
type LiftOf (UCyc t m D r) Source # 
type LiftOf (UCyc t m D r) = UCyc t m D (LiftOf r)
type LiftOf (UCyc t m P r) Source # 
type LiftOf (UCyc t m P r) = UCyc t m P (LiftOf r)

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 # 

Methods

(*>) :: r -> UCyc t m P r -> UCyc t m P r #

(Random r, UCRTElt t r, Fact m) => Random (Either (UCyc t m P r) (UCyc t m C r)) Source # 

Methods

randomR :: RandomGen g => (Either (UCyc t m P r) (UCyc t m C r), Either (UCyc t m P r) (UCyc t m C r)) -> g -> (Either (UCyc t m P r) (UCyc t m C r), g) #

random :: RandomGen g => g -> (Either (UCyc t m P r) (UCyc t m C r), g) #

randomRs :: RandomGen g => (Either (UCyc t m P r) (UCyc t m C r), Either (UCyc t m P r) (UCyc t m C r)) -> g -> [Either (UCyc t m P r) (UCyc t m C r)] #

randoms :: RandomGen g => g -> [Either (UCyc t m P r) (UCyc t m C r)] #

randomRIO :: (Either (UCyc t m P r) (UCyc t m C r), Either (UCyc t m P r) (UCyc t m C r)) -> IO (Either (UCyc t m P r) (UCyc t m C r)) #

randomIO :: IO (Either (UCyc t m P r) (UCyc t m C r)) #

(Tensor t, Fact m) => Functor (UCyc t m P) Source #

apply coefficient-wise (with respect to powerful basis)

Methods

fmap :: (a -> b) -> UCyc t m P a -> UCyc t m P b #

(<$) :: a -> UCyc t m P b -> UCyc t m P a #

(Tensor t, Fact m) => Applicative (UCyc t m P) Source # 

Methods

pure :: a -> UCyc t m P a #

(<*>) :: UCyc t m P (a -> b) -> UCyc t m P a -> UCyc t m P b #

(*>) :: UCyc t m P a -> UCyc t m P b -> UCyc t m P b #

(<*) :: UCyc t m P a -> UCyc t m P b -> UCyc t m P a #

(Tensor t, Fact m) => Foldable (UCyc t m P) Source # 

Methods

fold :: Monoid m => UCyc t m P m -> m #

foldMap :: Monoid m => (a -> m) -> UCyc t m P a -> m #

foldr :: (a -> b -> b) -> b -> UCyc t m P a -> b #

foldr' :: (a -> b -> b) -> b -> UCyc t m P a -> b #

foldl :: (b -> a -> b) -> b -> UCyc t m P a -> b #

foldl' :: (b -> a -> b) -> b -> UCyc t m P a -> b #

foldr1 :: (a -> a -> a) -> UCyc t m P a -> a #

foldl1 :: (a -> a -> a) -> UCyc t m P a -> a #

toList :: UCyc t m P a -> [a] #

null :: UCyc t m P a -> Bool #

length :: UCyc t m P a -> Int #

elem :: Eq a => a -> UCyc t m P a -> Bool #

maximum :: Ord a => UCyc t m P a -> a #

minimum :: Ord a => UCyc t m P a -> a #

sum :: Num a => UCyc t m P a -> a #

product :: Num a => UCyc t m P a -> a #

(Tensor t, Fact m) => Traversable (UCyc t m P) Source # 

Methods

traverse :: Applicative f => (a -> f b) -> UCyc t m P a -> f (UCyc t m P b) #

sequenceA :: Applicative f => UCyc t m P (f a) -> f (UCyc t m P a) #

mapM :: Monad m => (a -> m b) -> UCyc t m P a -> m (UCyc t m P b) #

sequence :: Monad m => UCyc t m P (m a) -> m (UCyc t m P a) #

(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.

Methods

(*>) :: GF k fp d -> UCyc t m P fp -> UCyc t m P fp #

(Eq r, Tensor t, Fact m, TElt t r) => Eq (UCyc t m P r) Source # 

Methods

(==) :: UCyc t m P r -> UCyc t m P r -> Bool #

(/=) :: UCyc t m P r -> UCyc t m P r -> Bool #

(Random r, UCRTElt t r, Fact m) => Random (UCyc t m P r) Source # 

Methods

randomR :: RandomGen g => (UCyc t m P r, UCyc t m P r) -> g -> (UCyc t m P r, g) #

random :: RandomGen g => g -> (UCyc t m P r, g) #

randomRs :: RandomGen g => (UCyc t m P r, UCyc t m P r) -> g -> [UCyc t m P r] #

randoms :: RandomGen g => g -> [UCyc t m P r] #

randomRIO :: (UCyc t m P r, UCyc t m P r) -> IO (UCyc t m P r) #

randomIO :: IO (UCyc t m P r) #

Arbitrary (t m r) => Arbitrary (UCyc t m P r) Source # 

Methods

arbitrary :: Gen (UCyc t m P r) #

shrink :: UCyc t m P r -> [UCyc t m P r] #

(ZeroTestable r, Tensor t, Fact m, TElt t r) => C (UCyc t m P r) Source # 

Methods

isZero :: UCyc t m P r -> Bool #

(Additive r, Tensor t, Fact m, TElt t r) => C (UCyc t m P r) Source # 

Methods

zero :: UCyc t m P r #

(+) :: UCyc t m P r -> UCyc t m P r -> UCyc t m P r #

(-) :: UCyc t m P r -> UCyc t m P r -> UCyc t m P r #

negate :: UCyc t m P r -> UCyc t m P r #

(Lift' r, Tensor t, Fact m, TElt t r, TElt t (LiftOf r)) => Lift' (UCyc t m P r) Source # 

Methods

lift :: UCyc t m P r -> LiftOf (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 # 

Methods

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 # 

Methods

reduce :: UCyc t m P a -> UCyc t m P b Source #

type LiftOf (UCyc t m P r) Source # 
type LiftOf (UCyc t m P r) = UCyc t m P (LiftOf r)

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 # 

Methods

(*>) :: r -> UCyc t m D r -> UCyc t m D r #

(Tensor t, Fact m) => Functor (UCyc t m D) Source #

apply coefficient-wise (with respect to decoding basis)

Methods

fmap :: (a -> b) -> UCyc t m D a -> UCyc t m D b #

(<$) :: a -> UCyc t m D b -> UCyc t m D a #

(Tensor t, Fact m) => Applicative (UCyc t m D) Source # 

Methods

pure :: a -> UCyc t m D a #

(<*>) :: UCyc t m D (a -> b) -> UCyc t m D a -> UCyc t m D b #

(*>) :: UCyc t m D a -> UCyc t m D b -> UCyc t m D b #

(<*) :: UCyc t m D a -> UCyc t m D b -> UCyc t m D a #

(Tensor t, Fact m) => Foldable (UCyc t m D) Source # 

Methods

fold :: Monoid m => UCyc t m D m -> m #

foldMap :: Monoid m => (a -> m) -> UCyc t m D a -> m #

foldr :: (a -> b -> b) -> b -> UCyc t m D a -> b #

foldr' :: (a -> b -> b) -> b -> UCyc t m D a -> b #

foldl :: (b -> a -> b) -> b -> UCyc t m D a -> b #

foldl' :: (b -> a -> b) -> b -> UCyc t m D a -> b #

foldr1 :: (a -> a -> a) -> UCyc t m D a -> a #

foldl1 :: (a -> a -> a) -> UCyc t m D a -> a #

toList :: UCyc t m D a -> [a] #

null :: UCyc t m D a -> Bool #

length :: UCyc t m D a -> Int #

elem :: Eq a => a -> UCyc t m D a -> Bool #

maximum :: Ord a => UCyc t m D a -> a #

minimum :: Ord a => UCyc t m D a -> a #

sum :: Num a => UCyc t m D a -> a #

product :: Num a => UCyc t m D a -> a #

(Tensor t, Fact m) => Traversable (UCyc t m D) Source # 

Methods

traverse :: Applicative f => (a -> f b) -> UCyc t m D a -> f (UCyc t m D b) #

sequenceA :: Applicative f => UCyc t m D (f a) -> f (UCyc t m D a) #

mapM :: Monad m => (a -> m b) -> UCyc t m D a -> m (UCyc t m D b) #

sequence :: Monad m => UCyc t m D (m a) -> m (UCyc t m D a) #

(Eq r, Tensor t, Fact m, TElt t r) => Eq (UCyc t m D r) Source # 

Methods

(==) :: UCyc t m D r -> UCyc t m D r -> Bool #

(/=) :: UCyc t m D r -> UCyc t m D r -> Bool #

(Random r, UCRTElt t r, Fact m) => Random (UCyc t m D r) Source # 

Methods

randomR :: RandomGen g => (UCyc t m D r, UCyc t m D r) -> g -> (UCyc t m D r, g) #

random :: RandomGen g => g -> (UCyc t m D r, g) #

randomRs :: RandomGen g => (UCyc t m D r, UCyc t m D r) -> g -> [UCyc t m D r] #

randoms :: RandomGen g => g -> [UCyc t m D r] #

randomRIO :: (UCyc t m D r, UCyc t m D r) -> IO (UCyc t m D r) #

randomIO :: IO (UCyc t m D r) #

Arbitrary (t m r) => Arbitrary (UCyc t m D r) Source # 

Methods

arbitrary :: Gen (UCyc t m D r) #

shrink :: UCyc t m D r -> [UCyc t m D r] #

(ZeroTestable r, Tensor t, Fact m, TElt t r) => C (UCyc t m D r) Source # 

Methods

isZero :: UCyc t m D r -> Bool #

(Additive r, Tensor t, Fact m, TElt t r) => C (UCyc t m D r) Source # 

Methods

zero :: UCyc t m D r #

(+) :: UCyc t m D r -> UCyc t m D r -> UCyc t m D r #

(-) :: UCyc t m D r -> UCyc t m D r -> UCyc t m D r #

negate :: UCyc t m D r -> UCyc t m D r #

Protoable (t m r) => Protoable (UCyc t m D r) Source # 

Associated Types

type ProtoType (UCyc t m D r) :: * Source #

Methods

toProto :: UCyc t m D r -> ProtoType (UCyc t m D r) Source #

fromProto :: MonadError String m => ProtoType (UCyc t m D r) -> m (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 # 

Methods

lift :: UCyc t m D r -> LiftOf (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 # 

Methods

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 # 

Methods

reduce :: UCyc t m D a -> UCyc t m D b Source #

type ProtoType (UCyc t m D r) Source # 
type ProtoType (UCyc t m D r) = ProtoType (t m r)
type LiftOf (UCyc t m D r) Source # 
type LiftOf (UCyc t m D r) = UCyc t m D (LiftOf r)

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 # 

Methods

(*>) :: r -> UCycEC t m r -> UCycEC t m r #

(Random r, UCRTElt t r, Fact m) => Random (Either (UCyc t m P r) (UCyc t m C r)) Source # 

Methods

randomR :: RandomGen g => (Either (UCyc t m P r) (UCyc t m C r), Either (UCyc t m P r) (UCyc t m C r)) -> g -> (Either (UCyc t m P r) (UCyc t m C r), g) #

random :: RandomGen g => g -> (Either (UCyc t m P r) (UCyc t m C r), g) #

randomRs :: RandomGen g => (Either (UCyc t m P r) (UCyc t m C r), Either (UCyc t m P r) (UCyc t m C r)) -> g -> [Either (UCyc t m P r) (UCyc t m C r)] #

randoms :: RandomGen g => g -> [Either (UCyc t m P r) (UCyc t m C r)] #

randomRIO :: (Either (UCyc t m P r) (UCyc t m C r), Either (UCyc t m P r) (UCyc t m C r)) -> IO (Either (UCyc t m P r) (UCyc t m C r)) #

randomIO :: IO (Either (UCyc t m P r) (UCyc t m C r)) #

(Tensor t, Fact m) => Foldable (UCyc t m C) Source # 

Methods

fold :: Monoid m => UCyc t m C m -> m #

foldMap :: Monoid m => (a -> m) -> UCyc t m C a -> m #

foldr :: (a -> b -> b) -> b -> UCyc t m C a -> b #

foldr' :: (a -> b -> b) -> b -> UCyc t m C a -> b #

foldl :: (b -> a -> b) -> b -> UCyc t m C a -> b #

foldl' :: (b -> a -> b) -> b -> UCyc t m C a -> b #

foldr1 :: (a -> a -> a) -> UCyc t m C a -> a #

foldl1 :: (a -> a -> a) -> UCyc t m C a -> a #

toList :: UCyc t m C a -> [a] #

null :: UCyc t m C a -> Bool #

length :: UCyc t m C a -> Int #

elem :: Eq a => a -> UCyc t m C a -> Bool #

maximum :: Ord a => UCyc t m C a -> a #

minimum :: Ord a => UCyc t m C a -> a #

sum :: Num a => UCyc t m C a -> a #

product :: Num a => UCyc t m C a -> a #

(Fact m, UCRTElt t r) => C (UCycEC t m r) Source #

only for appropriate CRT representation

Methods

(*) :: UCycEC t m r -> UCycEC t m r -> UCycEC t m r #

one :: UCycEC t m r #

fromInteger :: Integer -> UCycEC t m r #

(^) :: UCycEC t m r -> Integer -> UCycEC t m r #

(Fact m, UCRTElt t r) => C (UCycEC t m r) Source #

only for appropriate CRT representation (otherwise zero would violate internal invariant)

Methods

zero :: UCycEC t m r #

(+) :: UCycEC t m r -> UCycEC t m r -> UCycEC t m r #

(-) :: UCycEC t m r -> UCycEC t m r -> UCycEC t m r #

negate :: UCycEC t m r -> UCycEC t m r #

(Eq r, Tensor t, Fact m, TElt t r) => Eq (UCyc t m C r) Source # 

Methods

(==) :: UCyc t m C r -> UCyc t m C r -> Bool #

(/=) :: UCyc t m C r -> UCyc t m C r -> Bool #

(ZeroTestable r, Tensor t, Fact m, TElt t r) => C (UCyc t m C r) Source # 

Methods

isZero :: UCyc t m C r -> Bool #

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 # 

Methods

(*>) :: r -> UCycEC t m r -> UCycEC t m r #

(Fact m, UCRTElt t r) => C (UCycEC t m r) Source #

only for appropriate CRT representation

Methods

(*) :: UCycEC t m r -> UCycEC t m r -> UCycEC t m r #

one :: UCycEC t m r #

fromInteger :: Integer -> UCycEC t m r #

(^) :: UCycEC t m r -> Integer -> UCycEC t m r #

(Fact m, UCRTElt t r) => C (UCycEC t m r) Source #

only for appropriate CRT representation (otherwise zero would violate internal invariant)

Methods

zero :: UCycEC t m r #

(+) :: UCycEC t m r -> UCycEC t m r -> UCycEC t m r #

(-) :: UCycEC t m r -> UCycEC t m r -> UCycEC t m r #

negate :: UCycEC t m r -> UCycEC t m r #

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 :: (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 :: (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 :: (Fact m, UCRTElt t r) => UCyc t m rep r -> UCyc t m rep r Source #

Multiply by the special element \(g_m\).

divG :: (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_m\). 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\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 #

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).