class_groups/
table.rs

1use core::ops::Index;
2use alloc::vec::Vec;
3
4use crate::Element;
5
6/// TODO
7pub trait ElementExt: Element {
8  /// The maximum amount of bits to create a table with.
9  ///
10  /// This allows backends which won't use larger tables to prevent redundant creation of such
11  /// large tables;
12  const MAX_TABLE_BITS: u32 = 16;
13
14  /// Perform a multiexponentation.
15  ///
16  /// The implementation provided by this trait runs in variable time.
17  #[must_use]
18  fn multiexp(identity: &Self, pairs: &[(&Table<Self>, &[u8])]) -> Self {
19    let mut longest_scalar_bits = 0;
20    for (_table, scalar) in pairs {
21      longest_scalar_bits = longest_scalar_bits.max(scalar.len() * 8);
22    }
23
24    let mut res: Option<Self> = None;
25    for i in 0 .. longest_scalar_bits {
26      // Shift over the existing result by a bit
27      if let Some(res) = res.as_mut() {
28        *res = res.double();
29      }
30
31      for (table, scalar) in pairs {
32        let scalar_bits = scalar.len() * 8;
33        // Transform the index of the bit in our longest scalar to the index of the bit in this one
34        let Some(i) = i.checked_sub(longest_scalar_bits - scalar_bits) else {
35          // If we're indexing a bit which doesn't exist in this scalar, continue
36          continue;
37        };
38
39        // If it's time to add this entry, do so
40        let table_bits = table.bits();
41        if ((i + 1) % table_bits) == 0 {
42          let mut accum = 0usize;
43          debug_assert_eq!(i - (i + 1 - table_bits) + 1, table_bits);
44          for i in (i + 1 - table_bits) ..= i {
45            accum <<= 1;
46            accum |= (usize::from(scalar[i / 8] >> (7 - (i % 8)))) & 1;
47          }
48
49          if accum != 0 {
50            let to_add = &table[accum];
51            res = Some(res.as_ref().map(|res| res.add(to_add)).unwrap_or_else(|| to_add.clone()));
52          }
53        }
54      }
55    }
56
57    // Perform the final step of the accumulator
58    for (table, scalar) in pairs {
59      let scalar_bits = scalar.len() * 8;
60
61      let table_bits = table.bits();
62      let mut accum = 0usize;
63      for i in ((scalar_bits / table_bits) * table_bits) .. scalar_bits {
64        accum <<= 1;
65        accum |= (usize::from(scalar[i / 8] >> (7 - (i % 8)))) & 1;
66      }
67
68      if accum != 0 {
69        let to_add = &table[accum];
70        res = Some(res.as_ref().map(|res| res.add(to_add)).unwrap_or_else(|| to_add.clone()));
71      }
72    }
73
74    res.unwrap_or_else(|| identity.clone())
75  }
76
77  /// Perform a multiplication with a `Table`.
78  ///
79  /// The scalar is expected to be represented by its big-endian bytes.
80  ///
81  /// The implementation provided by this trait is as-constant-time as `multiexp` is.
82  #[must_use]
83  fn mul(table: &Table<Self>, scalar: &[u8]) -> Self {
84    Self::multiexp(&table[0], &[(table, scalar)])
85  }
86}
87
88/// A table to perform multiplications with.
89#[derive(Clone)]
90pub struct Table<E: ElementExt>(usize, Vec<E>);
91impl<E: ElementExt> Table<E> {
92  /// Create a new table.
93  ///
94  /// This function executes in constant-time w.r.t. `element` if `double, add` are constant-time.
95  #[must_use]
96  pub fn new(bits: u32, identity: E, element: E) -> Self {
97    let bits = bits.clamp(1, E::MAX_TABLE_BITS);
98    let len = 2usize.pow(bits);
99    let mut res = Vec::with_capacity(len);
100    res.push(identity);
101    res.push(element);
102
103    for i in 2 .. len {
104      // Check if we can calculate this with solely a doubling
105      if (i % 2) == 0 {
106        res.push(res[i / 2].double());
107      } else {
108        let next = res[i - 1].add(&res[1]);
109        res.push(next);
110      }
111    }
112    Self(usize::try_from(bits).unwrap(), res)
113  }
114
115  /// Create a new table of size optimal for a scalar-length.
116  ///
117  /// This is usable in ad-hoc multiplications where creating the table, and performing the
118  /// multiplication with it, should not cost more than performing the multiplication out-right.
119  #[must_use]
120  pub fn new_for_scalar_bits(scalar_bits: usize, identity: E, element: E) -> Self {
121    let mut bits = 0u32;
122    let mut adds = usize::MAX;
123    while {
124      let new_bits = bits + 1;
125      let new_adds =
126        2usize.pow(new_bits) + (scalar_bits.min(8192) / usize::try_from(new_bits).unwrap());
127      if new_adds <= adds {
128        bits = new_bits;
129        adds = new_adds;
130        true
131      } else {
132        false
133      }
134    } {}
135    Self::new(bits, identity, element)
136  }
137
138  /// The bits preprocessed by this table.
139  #[must_use]
140  pub fn bits(&self) -> usize {
141    self.0
142  }
143}
144
145impl<E: ElementExt> AsRef<[E]> for Table<E> {
146  fn as_ref(&self) -> &[E] {
147    self.1.as_slice()
148  }
149}
150
151impl<E: ElementExt> Index<usize> for Table<E> {
152  type Output = E;
153  fn index(&self, i: usize) -> &E {
154    &self.1[i]
155  }
156}
class_groups/table.rs

class_groups/
table.rs
