search

pq-crystals / dilithium

Other
374 stars 136 forks source link

Sampling procedure does not match with documentation #37

Closed 614n closed 3 years ago

614n commented 3 years ago

In the most recent documentation, page 20, paragraph "Sampling the vectors y", it is defined that gamma1-1 is subtracted from the uniform bits. The reference implementation, however, subtracts the uniform bits from gamma1.

gregorseiler commented 3 years ago

Thanks, this is indeed a mismatch between the spec and the code. The code is how we decided to want to do it and this is also consistent with other places, so we're going to change the spec.

614n commented 3 years ago

@gregorseiler Similar problem with sampling s1 and s2. Figure 4 in the documentation states that H is instantiated with SHAKE-256, the code uses SHAKE-128 in rej_eta.

gregorseiler commented 3 years ago

Hi,

You're right, thank you. The idea behind these changes in the spec for round 3 was to make the secret sampling in key generation more precise (before we just wrote that s1 and s2 are randomly sampled). The function H is the random oracle for the challenge and indeed uses SHAKE-256 in the code, see the corresponding C-function poly_challenge. For sampling s1 and s2 we don't use H (also the output domain would not be correct). These vectors need to look random but we don't need higher security properties like second preimage resistance here. So this is why we use SHAKE-128. I'm going to correct the spec.

Cheers, Gregor

On 01.02.21 12:47, 614n wrote:

@gregorseiler https://github.com/gregorseiler Similar problem with sampling s1 and s2. Figure 4 in the documentation states that H is instantiated with SHAKE-256, the code uses SHAKE-128 in |rej_eta|.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/pq-crystals/dilithium/issues/37#issuecomment-770797659, or unsubscribe https://github.com/notifications/unsubscribe-auth/AHXVKDGR4HZSKYWWIGEE4ALS42IE5ANCNFSM4WKWFX4Q.