1
$\begingroup$

SMAUG-T is an efficient post-quantum key encapsulation mechanism (KEM). It is the winner of Korean PQC Competition.

SMAUG-T uses a Hamming Weight Sampler $HWT_h$ to sample secret polynomial vectors $s, r$ with hamming weight $h_s$ and $h_r$ respectively. The rationale behind $HWT_h$ is summarized in Section 3.2.2 Figure 2 of the official documentation https://github.com/hmchoe0528/SMAUG-T_public/blob/main/document/SMAUG-T_spec_24.03_v3.0.1.pdf

Our hamming weight sampler, HWTh , is a hybrid of the SampleInBall algorithm in Dilithium [31] and the CWW (constant weight word) sampler in BIKE [56], which have a constant running time. However, when applying the SampleInBall sampling from BIKE directly, there was a need to reduce the sampling error inevitably arising from the Fisher-Yates Shuffle. Therefore, we eliminate the cause of this deviation by using division operations and a rejection technique.

The C code for $HWT_h$ is

1 void hwt(uint8_t *res, uint8_t *cnt_arr, const uint8_t *input, const size_t input_size, const uint16_t hmwt) {   
2        uint32_t pos = 0, div = 0, remain = 0;
3        uint32_t buf[SHAKE256_RATE * 2] = {0};  
4        uint8_t xof_block = (hmwt == HS) ? HS_XOF : HR_XOF;
5        keccak_state state;
6        shake256_init(&state);
7        shake256_absorb_once(&state, input, input_size);
8        shake256_squeezeblocks((uint8_t *)buf, xof_block, &state);
9    
10        for (int i = 0; i < xof_block * 32; i++) {
11           uint32_t deg = buf[i];
12            div = 0xffffffff / (DIMENSION - hmwt + pos + 1);
13            remain = 0xffffffff - remain * (DIMENSION - hmwt + pos + 1);
14            remain++;
15            deg = deg / div;
16            if (((0xffffffff - remain) > deg) && pos < hmwt) {
17                res[DIMENSION - hmwt + pos] = res[deg];
18                res[deg] =
19                    ((buf[(xof_block * 32 + (i >> 4))] >> (i & 0x0f)) & 0x02) - 1;
20                pos++;
21            }
22        }

We do have a few questions regarding this code:

Q1 > Till now I have understood that deg in [0, 2**32-1] is scaled such that it lies in the range 0 <= deg <= DIMENSION-hmwt+pos+1. It is not clear to me why $2^{32} - 1$ is used instead of $2^{32}$? For example, if we want to scale number $x \in [0,9]$ to $[0,3]$ we will use $round((4/10)*x)$

Q2> Line 16 in the code above: if (((0xffffffff - remain) > deg). It is not entirely clear the purpose of the inequality used here.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.