Skip to content

Generalize Zq struct to support arbitrary modulo and larger bit sizes #54

@omibo

Description

@omibo

Problem

In the current implementation of the Zq struct in zq.rs, the struct is defined as:

pub struct Zq {
    value: u32,
}

This design presents two significant limitations:

  1. The struct does not store the modulo value and implicitly assumes a modulo of $2^{32}$.

  2. In the aggregation of Falcon signatures with LaBRADOR, a larger bit size for value is necessary. For instance, for Falcon-512 when aggregating $N$ signatures, $41 + log_2(N)$ bits are needed (Aggregating Falcon Signatures with LaBRADOR, Section 6.2, page 23).

Proposed Solution

To address these issues, I propose the following enhancements:

  1. Modify the 'Zq' struct to use a 'u64' value.
  2. Store the modulus with a const generic parameter.

A possible implementation is:

pub struct Mod<const Q: u64> {
    value: u64,
}

impl<const Q: u64> Mod<Q> {
    pub fn new(v: u64) -> Self {
        Self { value: v % Q }
    }
}

type F = Mod<10>;
let a = F::new(9);
let b = F::new(2);
let c = a + b; // c = 1

All arithmetic operations defined for Zq (addition, multiplication, etc.) will need to be updated accordingly.

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or request

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions