1 package ring
2 3 // Variable-width serialization for bounded-norm polynomial coefficients.
4 //
5 // The fixed Serialize/Deserialize functions pack at ceil(log2(Q)) bits per
6 // coefficient (14 for Falcon-512). When coefficients are known to be bounded
7 // by a smaller range — as in sigma protocol responses (Gaussian, bound ~σ·T)
8 // or gadget digit polynomials (bound ~base/2) — the bit width can be reduced.
9 //
10 // The packing order matches Serialize: coefficient 0 at bits [0:bitsPerCoeff),
11 // coefficient 1 at bits [bitsPerCoeff:2*bitsPerCoeff), etc., LE within each
12 // coefficient.
13 14 // SerializeBounded packs polynomial coefficients at the given bit width.
15 // Uses the same LE bitwise packing order as Serialize.
16 //
17 // If signed is true, coefficients are stored in two's complement:
18 // - Positive coefficients are stored directly
19 // - Negative coefficients (stored in centered form as Q - |v| in the Poly)
20 // are converted to signed two's complement before packing
21 //
22 // The caller must ensure |coefficient| < 2^(bitsPerCoeff-1) when signed,
23 // or 0 ≤ coefficient < 2^bitsPerCoeff when unsigned, or the result is
24 // truncated.
25 func SerializeBounded(a *Poly, bitsPerCoeff int, signed bool) []byte {
26 q := a.params.Q
27 half := q / 2
28 mask := uint32((1 << bitsPerCoeff) - 1)
29 30 totalBits := bitsPerCoeff * len(a.Coeffs)
31 out := make([]byte, (totalBits+7)/8)
32 33 bitPos := 0
34 for _, c := range a.Coeffs {
35 var v uint32
36 if signed && c > half {
37 // Negative in centered form: c = Q - |v|.
38 // Convert to two's complement: -|v| = (~|v| + 1) & mask.
39 abs := q - c
40 v = ((^abs) + 1) & mask
41 } else {
42 v = c & mask
43 }
44 for b := 0; b < bitsPerCoeff; b++ {
45 if v&(1<<uint(b)) != 0 {
46 out[bitPos/8] |= 1 << uint(bitPos%8)
47 }
48 bitPos++
49 }
50 }
51 return out
52 }
53 54 // DeserializeBounded unpacks a polynomial serialized by SerializeBounded.
55 func DeserializeBounded(p Params, data []byte, bitsPerCoeff int, signed bool) *Poly {
56 poly := New(p)
57 q := p.Q
58 mask := uint32((1 << bitsPerCoeff) - 1)
59 var signBit uint32
60 if signed {
61 signBit = uint32(1 << (bitsPerCoeff - 1))
62 }
63 64 bitPos := 0
65 for i := range poly.Coeffs {
66 var v uint32
67 for b := 0; b < bitsPerCoeff; b++ {
68 if bitPos/8 < len(data) && data[bitPos/8]&(1<<uint(bitPos%8)) != 0 {
69 v |= 1 << uint(b)
70 }
71 bitPos++
72 }
73 v &= mask
74 75 if signed && v >= signBit {
76 // Two's complement negative: extract magnitude.
77 abs := ((^v) + 1) & mask
78 poly.Coeffs[i] = q - abs
79 if poly.Coeffs[i] >= q {
80 poly.Coeffs[i] = 0
81 }
82 } else {
83 poly.Coeffs[i] = v
84 }
85 }
86 return poly
87 }
88