junyechen1996 / draft-chen-cfrg-vdaf-pine

VDAF to support aggregating real number vectors with L2-norm bound
Other
5 stars 0 forks source link

Bit lengths seem to be computed incorrectly #59

Closed cjpatton closed 8 months ago

cjpatton commented 8 months ago

We compute the bit length for the squared norm and wraparound range checks as math.ceil(math.log2(m)) where m is the largest, valid value:

https://github.com/junyechen1996/draft-chen-cfrg-vdaf-pine/blob/21c43447f9b3ed283cc44500001ab4e9411a72c7/poc/flp_pine.py#L82

https://github.com/junyechen1996/draft-chen-cfrg-vdaf-pine/blob/21c43447f9b3ed283cc44500001ab4e9411a72c7/poc/flp_pine.py#L101

This appears to be incorrect when m is a power of 2:

m bit encoding bit length
1 1 1
2 10 2
4 100 3
8 1000 4
16 10000 5

What we want instead is math.floor(math.log2(m)+1).

Thanks to @jhoyla for pointing out this bug.

junyechen1996 commented 8 months ago

Both look correct to me?

m = 1, math.ceil(math.log2(m + 1)) = 1, math.floor(math.log2(m) + 1) = 1 m = 2, math.ceil(math.log2(m + 1)) = 2, math.floor(math.log2(m) + 1) = 2 m = 4, math.ceil(math.log2(m + 1)) = 3, math.floor(math.log2(m) + 1) = 3

cjpatton commented 8 months ago

Ohhh right, the +1 is important.