hash_based_signatures/signature/winternitz/
domination_free_function.rs

1use crate::signature::winternitz::d::D;
2use crate::signature::HashType;
3use crate::utils::{bits_to_unsigned_int, get_least_significant_bits};
4
5fn bitstring_to_integers(bit_string: &Vec<bool>, d: &D) -> Vec<u8> {
6    let n_elements = bit_string.len() / d.bits_to_combine();
7    (0..n_elements)
8        .map(|i| {
9            let start_bit = i * d.bits_to_combine();
10            let end_bit = start_bit + d.bits_to_combine();
11            bits_to_unsigned_int(&bit_string[start_bit..end_bit])
12        })
13        .collect()
14}
15
16/// A "domination-free function", as described in section 14.3.1 of the
17/// [textbook](http://toc.cryptobook.us/) by Boneh & Shoup (version 0.5).
18pub fn domination_free_function(input: HashType, d: &D) -> Vec<u8> {
19    let bit_string: Vec<bool> = input
20        .map(|x| get_least_significant_bits(x as usize, 8))
21        .into_iter()
22        .flatten()
23        .collect();
24
25    let mut result = Vec::new();
26    let n0 = 256 / d.bits_to_combine();
27    let mut c = d.d * (n0 as u64);
28    for x in bitstring_to_integers(&bit_string, d) {
29        result.push(x);
30        c -= x as u64;
31    }
32
33    let c_bitstring = get_least_significant_bits(c as usize, d.bits_c() as usize);
34
35    result.append(&mut bitstring_to_integers(&c_bitstring, d));
36
37    result
38}
39
40#[cfg(test)]
41mod tests {
42    use crate::signature::winternitz::domination_free_function::{domination_free_function, D};
43    use rand::prelude::*;
44    use rand_chacha::ChaCha20Rng;
45
46    #[test]
47    fn test_domination_free_function_0s_d1() {
48        let result = domination_free_function([0; 32], &D::new(1));
49        let mut expected = vec![0u8; 256];
50
51        // Maximal value of c is 2^8
52        expected.extend([1, 0, 0, 0, 0, 0, 0, 0, 0]);
53
54        assert_eq!(result, expected);
55    }
56
57    #[test]
58    fn test_domination_free_function_0s_d3() {
59        let result = domination_free_function([0; 32], &D::new(3));
60        let mut expected = vec![0u8; 128];
61
62        // bits_to_combine is 2
63        // Maximal value of c is 3 * 128 = 0x180 = 12000 (base 4)
64        // Which should be encoded in 5 2-bit integers
65        expected.extend([1, 2, 0, 0, 0]);
66
67        assert_eq!(result, expected);
68    }
69
70    #[test]
71    fn test_domination_free_function_0s_d15() {
72        let result = domination_free_function([0; 32], &D::new(15));
73        let mut expected = vec![0u8; 64];
74
75        // bits_to_combine is 4
76        // Maximal value of c is 15 * 64 = 0x3c0
77        // Which should be encoded in 3 4-bit integers
78        expected.extend([0x3, 0xc, 0x0]);
79
80        assert_eq!(result, expected);
81    }
82
83    #[test]
84    fn test_domination_free_function_0s_d255() {
85        let result = domination_free_function([0; 32], &D::new(255));
86        let mut expected = vec![0u8; 32];
87
88        // bits_to_combine is 8
89        // Maximal value of c is 255 * 32 = 0x1FE0
90        // Which should be encoded in 2 16-bit integers
91        expected.extend([0x1f, 0xe0]);
92
93        assert_eq!(result, expected);
94    }
95
96    #[test]
97    fn test_domination_free_function_1s_d255() {
98        let result = domination_free_function([255; 32], &D::new(255));
99        let mut expected = vec![255u8; 32];
100
101        // bits_to_combine is 16
102        // c should be 0, encoded in 2 16-bit integers
103        expected.extend([0, 0]);
104
105        assert_eq!(result, expected);
106    }
107
108    fn get_domination_free_vectors_on_random_data(d: &D, count: usize) -> Vec<Vec<u8>> {
109        let mut rng = ChaCha20Rng::from_seed([0; 32]);
110        let mut hash = [0u8; 32];
111        (0..count)
112            .map(|_| {
113                rng.fill_bytes(&mut hash);
114                domination_free_function(hash, d)
115            })
116            .collect()
117    }
118
119    fn assert_no_domination(domination_free_vectors: &Vec<Vec<u8>>) {
120        for i in 0..domination_free_vectors.len() {
121            for j in 0..domination_free_vectors.len() {
122                if i != j {
123                    // The two vectors should be distinct with overwhelming probability and
124                    // at least one value should of vec1 should be higher than the corresponding
125                    // value in vec2.
126                    let vec1 = &domination_free_vectors[i];
127                    let vec2 = &domination_free_vectors[j];
128
129                    let v1_dominates_sometimes =
130                        vec1.iter().zip(vec2).map(|(v1, v2)| v1 > v2).max().unwrap();
131                    assert!(v1_dominates_sometimes);
132                }
133            }
134        }
135    }
136
137    #[test]
138    fn domination_free_on_random_data_d1() {
139        let domination_free_vectors = get_domination_free_vectors_on_random_data(&D::new(1), 1000);
140        assert_no_domination(&domination_free_vectors);
141    }
142
143    #[test]
144    fn domination_free_on_random_data_d3() {
145        let domination_free_vectors = get_domination_free_vectors_on_random_data(&D::new(3), 1000);
146        assert_no_domination(&domination_free_vectors);
147    }
148
149    #[test]
150    fn domination_free_on_random_data_d15() {
151        let domination_free_vectors = get_domination_free_vectors_on_random_data(&D::new(15), 1000);
152        assert_no_domination(&domination_free_vectors);
153    }
154
155    #[test]
156    fn domination_free_on_random_data_d255() {
157        let domination_free_vectors =
158            get_domination_free_vectors_on_random_data(&D::new(255), 1000);
159        assert_no_domination(&domination_free_vectors);
160    }
161}
hash_based_signatures/signature/winternitz/domination_free_function.rs

hash_based_signatures/signature/winternitz/
domination_free_function.rs
