Struct Cl15p 

pub struct Cl15p<Up, Up2, Udk, Udp> {
    fundamental: Cl15k<Up, Udk>,
    p_square: Up2,
    absolute_value: Udp,
}

A non-fundamental discriminant as part of the CL15 cryptosystem.

This is constructed as detailed in Linearly Homomorphic Encryption from DDH by Guilhem Castagnos and Fabien Laguillaumie (https://eprint.iacr.org/2025/047), correspond to $\Delta_p$.

Up is the numeric type used to represent the prime p. Udk is the numeric type used to represent the fundamental discriminant’s absolute value, the product $q * p$. Udp is the numeric type used to represent the non-fundamental discriminant’s absolute value, the product $q * p^3$.

Fields

fundamental: Cl15k<Up, Udk>

p_square: Up2

absolute_value: Udp

Implementations

impl<Up: Clone + AsRef<[Limb]> + AsMut<[Limb]> + CtAssign + Zero + One + NegMod<Output = Up> + MulMod<Output = Up> + SquareMod<Output = Up> + ConcatenatingSquare + BitOps, Udk: Clone + AsRef<[Limb]> + AsMut<[Limb]> + CtGt + One + CheckedAdd + CheckedSub<Udk> + for<'a> Mul<&'a Up, Output = Udk> + ConcatenatingMul<<Up as ConcatenatingSquare>::Output> + for<'a> Div<&'a NonZero<Up>, Output = Udk> + for<'a> Rem<&'a NonZero<Up>, Output = Up> + BitOps + Encoding + RandomBits + RandomMod + UnsignedWithMontyForm> Cl15p<Up, <Up as ConcatenatingSquare>::Output, Udk, <Udk as ConcatenatingMul<<Up as ConcatenatingSquare>::Output>>::Output>

pub fn sample( rng: impl CryptoRng, bits_of_security: u32, fundamental_discriminant_bit_length: u32, p: Odd<Up>, ) -> Result<Self, Cl15Error>

Sample a fundamental discriminant as described by the Gen algorithm of CL15.

This function runs in variable time.

bits_of_security DOES NOT correspond to the hardness of finding the order of the resulting group. bits_of_security is used to configure the primality tests and for the requirement $p > 2^{bits_of_security}$, as (loosely) required for a $2^{-bits_of_security}$ likelihood the that unknown order is divisible by p (a requirement of the cryptosystem). The relation of bits_of_security to fundamental_discriminant_bit_length is completely unchecked.

fundamental_discriminant_bit_length will the bit-length of the fundamental discriminant. 1827 is SUGGESTED as the bit-length of the fundamental discriminant for 128-bit security. Please review https://eprint.iacr.org/2020/196 for context on choices.

p MUST be an odd prime and is specified by its little-endian encoding. It is undefined behavior to specify a p which is not actually an odd prime.

impl<Up, Up2, Udk, Udp> Cl15p<Up, Up2, Udk, Udp>

pub fn fundamental_discriminant(&self) -> &Cl15k<Up, Udk>

The fundamental discriminant.

impl<Up: Encoding, Up2: Encoding, Udk: Clone + AsMut<[Limb]> + Encoding, Udp: Encoding> Cl15p<Up, Up2, Udk, Udp>

pub fn f<E: Element>(&self) -> E

The element of p-order with an easy discrete-log problem.

This runs in time variable to the bit-length of the discriminant.

impl<Up: BitOps + Encoding, Up2, Udk: Clone + AsMut<[Limb]> + Encoding, Udp: Encoding> Cl15p<Up, Up2, Udk, Udp>

pub fn surject<E: Element>(&self, element: impl Element) -> E

Available on crate feature alloc only.

Take an element of the class group with non-fundamental discriminant and apply the surjection such that it is mapped to an element of the class group with fundamental discriminant.

This implements Algorithm 3, GoToMaxOrder. We specify it as follows for primitive forms of negative discriminants where discriminant / (p * p) is fundamental:

fn surject(a, b, c, p) {
  discriminant = (b * b) - (4 * a * c)
  fundamental_discriminant = discriminant / (p * p)
  assert (fundamental_discriminant * p * p) == discriminant
  (a, b) = coprime_form(a, b, c, p)
  (mu, lambda, _one) = xgcd(p, a)
  return reduce(
    a,
    (b * mu) + (a * (fundamental_discriminant % 2) * lambda),
    discriminant / (p * p)
  )
}

As with FundamentalDiscriminant::inject, we do not specify the reduction of $b \mod 2 a$. Instead, we again assume the existence of a reduction function, reduce, which inputs the a, b coefficients of an unreduced form and its discriminant before yielding a reduced form. We also assume an xgcd function, which for xgcd(x, y), returns (u, v, d) such that u x + v y = d.

This function MAY panic or return an incorrect result if element is not of this discriminant. This function runs in time only variable to this discriminant and E::a_b_c_discriminant (which may or may not be implemented in constant-time).

pub fn coset_labeling_function<E: Element>(&self, element: impl Element) -> E

Available on crate feature alloc only.

Apply the coset labeling function to an element of this discriminant.

This is equivalent to the following:

fn coset_labeling_function(a, b, c, p) {
  return inject(surject(a, b, c, p), p)
}

This function MAY panic or return an incorrect result if element is not of this discriminant. This function runs in time only variable to this discriminant and E::a_b_c_discriminant (which may or may not be implemented in constant-time).

impl<Up: Clone + CtSelect + Zero + NegMod<Output = Up> + InvertMod<Output = Up> + BitOps + Encoding, Up2: Encoding, Udk, Udp: Clone + CtEq + for<'a> Mul<&'a Up, Output = Udp> + for<'a> Div<&'a NonZero<Up>, Output = Udp> + Encoding> Cl15p<Up, Up2, Udk, Udp>

pub fn discrete_logarithm(&self, element: impl Element) -> CtOption<Up>

Solve for the discrete logarithm of an element of order-p.

We specify this as follows, for a reduced form’s a, b coefficients and the prime p:

fn discrete_logarithm(a, b, p) {
  if (a, b) == (1, 1) {
    return 0
  }
  assert a == p^2
  x_tilde = (b / p)
  assert (x_tilde * p) == b
  (u, _v, _one) = xgcd(x_tilde, p)
  return u
}

The if is used to check if the element is identity and therefore has a discrete-logarithm of 0. Else, we apply the defined methodology of Solve (presented in Figure 2) from Linearly Homomorphic Encryption from DDH by Guilhem Castagnos and Fabien Laguillaumie (https://eprint.iacr.org/2025/047). We explicitly specify the calculation of $\tilde{x}^{-1} \mod p$ via xgcd(x_tilde, p) as we’ve already assumed the existence of an xgcd function elsewhere in our specification, though other methods would work as well and MAY be used instead (such as by Fermat’s Little Theorem or a Bernstein-Yang inversion).

This function runs time only variable to this discriminant and E::a_b_c_discriminant (which may or may not be implemented in constant-time).

Trait Implementations

impl<Up: Clone, Up2: Clone, Udk: Clone, Udp: Clone> Clone for Cl15p<Up, Up2, Udk, Udp>

fn clone(&self) -> Cl15p<Up, Up2, Udk, Udp>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<Up, Up2, Udk, Udp> Discriminant for Cl15p<Up, Up2, Udk, Udp>

impl<Up: BitOps, Up2, Udk: Encoding, Udp: Encoding> NegativeDiscriminant for Cl15p<Up, Up2, Udk, Udp>

fn upper_bound_on_order(&self) -> u32

This runs in variable time to this discriminant.

fn absolute_value(&self) -> impl AsRef<[u8]>

This runs in time variable to the bit-length of the discriminant.

impl<Up, Up2, Udk, Udp> OddDiscriminant for Cl15p<Up, Up2, Udk, Udp>