Trait Element 

pub trait Element:
    Sized
    + Send
    + Sync
    + Clone
    + PartialEq
    + Eq
    + Debug
    + Neg<Output = Self>
    + Coefficients {
    // Required methods
    fn identity(discriminant_abs: impl AsRef<[u8]>) -> Self;
    fn is_identity(&self) -> Choice;
    fn double(&self) -> Self;
    fn add(&self, other: &Self) -> Self;
    fn sub(&self, other: Self) -> Self;
    unsafe fn from_coefficients(
        a: impl AsRef<[u8]>,
        b: (Choice, impl AsRef<[u8]>),
        c: impl AsRef<[u8]>,
        discriminant_abs: impl AsRef<[u8]>,
    ) -> Self;
    fn uncompressed_encode(self) -> impl AsRef<[u8]>;
    fn uncompressed_decode(
        buf: impl AsRef<[u8]>,
        discriminant_abs: impl AsRef<[u8]>,
    ) -> CtOption<Self>;

    // Provided methods
    fn compress(self, writer: impl Write) -> Result<()> { ... }
    fn decompress(
        reader: impl Read,
        discriminant_abs: impl AsRef<[u8]>,
    ) -> Result<Self> { ... }
    fn from(source: impl Element) -> Self { ... }
    fn next_prime_ideal_squared(
        rng: impl CryptoRng,
        seed: BoxedUint,
        discriminant_abs: impl AsRef<[u8]>,
        bits_of_security: u32,
    ) -> Self { ... }
}

An binary quadratic form corresponding to an element of a class group.

This binary quadratic form is bound to being a primitive positive definite binary quadratic form of negative odd discriminant (not necessarily fundamental). We bound to primitive forms to ensure forms are invertible and for faster composition. We bound to positive definite (of negative discriminant) forms to ensure there’s a single reduced form, and as the theory sufficiently diverges it doesn’t make practical sense to attempt to simultaneously support both in a single optimized library. We bound to odd discriminants as specializing enables ~5% faster reduction. Additionally, all of these bounds are allowed by the currently desired use cases.

This binary quadratic form has a specific discriminant. Operations between binary quadratic forms with distinct discriminants are always undefined behavior (and technically considered unsafe even if not so annotated) and MUST NOT be done.

Operations with the binary quadratic forms are not notated multiplicatively but additively. The composition of two forms is referred to as addition, and the composition of a form with itself is referred to as doubling. The inverse of an element is notated as its negation.

Implementations of this trait MAY run in variable time.

Required Methods

fn identity(discriminant_abs: impl AsRef<[u8]>) -> Self

The identity element.

The negative discriminant is specified by the little-endian encoding of its absolute value.

This MUST panic if the discriminant is not a valid odd discriminant.

fn is_identity(&self) -> Choice

If this element is the identity.

fn double(&self) -> Self

Double this element.

This is generally faster than adding an element to itself as it’s allowed to specialize on this special case.

fn add(&self, other: &Self) -> Self

Add two elements.

fn sub(&self, other: Self) -> Self

Subtract one element from another.

unsafe fn from_coefficients( a: impl AsRef<[u8]>, b: (Choice, impl AsRef<[u8]>), c: impl AsRef<[u8]>, discriminant_abs: impl AsRef<[u8]>, ) -> Self

Load a form from its coefficients.

The coefficients and absolute value of the discriminant are little-endian encoded. b is represented by a sign bit, if b is positive (greater than or equal to zero), and the encoding of its absolute value. Values MAY have trailing zeroes.

Safety

The coefficients MUST specify a primitive reduced positive definite binary quadratic form of negative odd discriminant, the one specified via discriminant_abs. Implementations MAY exhibit undefined behavior if any of these requirements aren’t satisfied, hence this being marked unsafe. This MUST NOT be unsafe for any other reason (such as if the coefficients exceed the type’s bounds) but MAY panic if documented bounds on the discriminant aren’t met.

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

Encode an element without compression.

This SHOULD NOT be used by protocols. The compressed encoding SHOULD be used unless there’s an explicit reason to use uncompressed encodings (such as the stronger bounds on termination or amenability for constant-time implementations).

This MUST implement the defined specification for the uncompressed encoding of binary quadratic forms.

fn uncompressed_decode( buf: impl AsRef<[u8]>, discriminant_abs: impl AsRef<[u8]>, ) -> CtOption<Self>

Decode an element of the specified discriminant without compression.

This SHOULD NOT be used by protocols. The compressed encoding SHOULD be used unless there’s an explicit reason to use uncompressed encodings (such as the stronger bounds on termination or amenability for constant-time implementations).

This MUST implement the defined specification for the uncompressed decoding of binary quadratic forms. The discriminant MUST be negative and odd, specified by the little-endian encoding of its absolute value. Implementations MUST return None if buf.len() is not exactly 2 * ((floor(log_2(-discriminant)) / 2) + 1).div_ceil(8) OR if the discriminant is even. Implementations MAY not support discriminants whose absolute values are encoded with trailing zero bytes.

Provided Methods

fn compress(self, writer: impl Write) -> Result<()>

Available on crate feature std only.

Compress an element.

This MUST implement the defined specification for the compression of binary quadratic forms. Implementations MUST only error if the underlying IO errors, being error-free themselves. This allows callers to unwrap this result when the underlying IO is known to be error-free (such as when a Vec).

The provided implementation runs in variable time and MAY panic for absurdly large coefficients.

fn decompress( reader: impl Read, discriminant_abs: impl AsRef<[u8]>, ) -> Result<Self>

Available on crate feature std only.

Decompress an element of the specified discriminant.

This MUST implement the defined specification for the decompression of binary quadratic forms. The discriminant MUST be negative and odd, specified by the little-endian encoding of its absolute value.

The provided implementation runs in variable time and MAY error for absurdly large discriminants.

fn from(source: impl Element) -> Self

Create an element of this type from another element.

fn next_prime_ideal_squared( rng: impl CryptoRng, seed: BoxedUint, discriminant_abs: impl AsRef<[u8]>, bits_of_security: u32, ) -> Self

Available on crate feature alloc only.

Sample a uniform element from a subgroup of the class group and return its square.

The discriminant MUST be negative and is specified by the little-endian encoding of its absolute value. The discriminant MUST be odd.

This element is deterministic to the seed, has an unknown relationship to other elements of the class group, and may be presumed to be a generator of (most of) the squares of the class group. These properties make this function suitable for use as a hash-to-element for some use cases, and we claim most of the desirable use cases. This function MUST NOT be assumed to output uniform elements of the class group or to be indistinguishable. The element is squared as the Decisional Diffie-Hellman problem is easy over the entire class group and it’s its squares which form a generally-desirable subgroup (“Linearly Homomorphic Encryption from DDH” by Guilhem Castagnos and Fabien Laguillaumie, https://eprint.iacr.org/2015/047, Appendix B.4).

Implementations MUST implement the specification for sampling a random element of the class group, as the provided implementation does, with identical results. The provided implementation executes in variable time and all implementations SHOULD be assumed to execute in variable time due to the specification only having a statistical bound for its termination (requiring sampling a prime number).

“How (not) to hash into class groups of imaginary quadratic fields?”, by István András Seres, Péter Burcsi, and Péter Kutas (https://eprint.iacr.org/2024/034), is referred to as primary academic reference for the analysis and justification of such hash functions. We specify (and implement) the second construction, attributed to the conference version of “Efficient verifiable delay functions” by Benjamin Wesolowski, and not the “Improved version”. This is not uniform over the class group as a whole, solely the binary quadratic forms of prime ideal, assuming the underlying hash-to-prime function is itself uniform. This is presented as sufficient for most purposes and is remarkably straightforward to implement, hence it being the reasonable choice for specification.

fn next_prime_ideal_squared(seed, discriminant) {
  # Assert the discriminant is negative and sufficiently large there is such a prime ideal
  assert discriminant < -200
  # Assert the seed is within the expected bound
  assert 0 <= seed
  assert seed <= sqrt((-discriminant) / 4)

  i = 0
  seed = next_odd_prime(seed)
  if seed > sqrt((-discriminant) / 4) {
    # Increment modulo our upper bound to the first odd prime
    seed = 3
  }
  while jacobi(discriminant, seed) != 1 {
    i += 1
    seed = next_odd_prime(seed + 1)
    if seed > sqrt((-discriminant) / 4) {
      seed = 3
    }
  }

  b = mod_sqrt(delta, p)
  if (i % 2) == 1 {
    b = -b
  }

  # Return the composition of the sampled prime ideal with itself
  prime_ideal = (p, b)
  return composition(prime_ideal, prime_ideal)
}

seed is required to be a uniform element in the range $[0, sqrt(|discriminant| / 4)]$. next_odd_prime tests if seed is an odd prime, incrementing it if it is not, until it is. jacobi(x, y) yields the Jacobi symbol of x over y where as y is an odd prime, this is equivalent to the Lagrange symbol. mod_sqrt(x, y) returns the odd square root of x modulo y such that $mod_sqrt(x, y)^2 \cong x \mod y$ if one exists, which our precondition of checking the Jacobi symbol ensures. mod_sqrt is RECOMMENDED to be implemented via the Tonelli-Shanks algorithms but MAY be implemented with alternatives such as Cipolla’s. composition returns the composition (the result of the group operation, the product in multiplicative notation, the sum in additive notation as this library generally prefers) of two binary quadratic forms (corresponding to NUCOMP or similar, or as the first form is equal to the second form, NUDUPL or similar).

For the validity of the results, we primarily defer to “How (not) to hash into class groups of imaginary quadratic fields?” (which did prove this construction secure and uniform to the prime ideals for primes in the range $[0, sqrt(|discriminant| / 4)]$). We choose our sign differently from the suggested negative if $p % 3 = 2$, as for any prime $p$, that would fix a single $b$ coefficient (despite it naturally having two potential solutions as $|b| < a$). We intead use the amount of rejected non-residues to decide the sign of $b$, which is uniform modulo 2 if the distribution of prime quadratic residues to prime quadratic non-residues in a prime field is itself uniform. The ordinality of the set of non-zero quadratic residues is equivalent to the ordinality of the set of non-zero quadratic non-residues, so this isn’t impossible, though exact analysis regarding the distribution of primes and the distribution of quadratic non-residues within a prime field have been open problems with decades (if not centuries, if not millenia) of literature. Even though we can’t prove a tight bound for the bias of this method, we do claim this method sufficient for our purposes.

The provided implementation MAY panic upon invalid or absurdly large inputs. It accepts an RNG to perform primality tests against the prime numbers with though the RNG is not used to sample potential coefficients for the binary quadratic form and will not impact the result (except if a primality test fails). bits_of_security parameterizes the statistical odds of a sampled prime number actually being prime. The provided implementation MAY panic if bits_of_security causes there to be no recognized configuration for the Miller-Rabin primality tests, for the prime numbers considered as candidates.

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety".

Implementors

impl<U: Limbs> Element for CryptoBigintElement<U>