lwe.go raw
1 package gnarlring
2
3 import (
4 "crypto/rand"
5 "io"
6 )
7
8 // LWEPublicKey is a Ring-LWE public key: (A, B = A·S + E).
9 type LWEPublicKey struct {
10 A *Poly27 // uniform ring element (coefficient form)
11 B *Poly27 // B = A·S + E (coefficient form)
12 }
13
14 // LWESecretKey is a Ring-LWE secret key.
15 type LWESecretKey struct {
16 S *Poly27 // secret (ternary or Gaussian)
17 PK *LWEPublicKey
18 }
19
20 // LWECiphertext is a Ring-LWE encryption: (U, V).
21 type LWECiphertext struct {
22 U *Poly27 // U = A·R + E1
23 V *Poly27 // V = B·R + E2 + encode(m)
24 }
25
26 // LWEKeyGen generates a Ring-LWE key pair with ternary secret.
27 func LWEKeyGen() (*LWEPublicKey, *LWESecretKey) {
28 return LWEKeyGenFrom(rand.Reader)
29 }
30
31 // LWEKeyGenFrom generates a key pair from the given randomness source.
32 func LWEKeyGenFrom(rng io.Reader) (*LWEPublicKey, *LWESecretKey) {
33 if rng == nil {
34 rng = rand.Reader
35 }
36 gs := NewGaussSamplerFrom(DefaultSigma(), rng)
37
38 // A ← uniform in R_q.
39 a := NewPoly27()
40 for i := 0; i < N; i++ {
41 var buf [2]byte
42 io.ReadFull(rng, buf[:])
43 a.Coeffs[i] = uint16(uint32(buf[0])<<8|uint32(buf[1])) % Q
44 }
45
46 // S ← ternary (coefficients in {0, 1, Q-1}).
47 s := ternaryPoly(rng)
48
49 // E ← small Gaussian.
50 e := gs.SamplePoly()
51 for i := range e.Coeffs {
52 // Scale down to ternary-like noise.
53 if e.Coeffs[i] > Q/2 {
54 e.Coeffs[i] = Q - 1 // -1 mod Q
55 } else if e.Coeffs[i] != 0 {
56 e.Coeffs[i] = 1
57 }
58 }
59
60 // B = A·S + E.
61 as := Mul(a, s)
62 b := Add(as, e)
63
64 pk := &LWEPublicKey{A: a, B: b}
65 sk := &LWESecretKey{S: s, PK: pk}
66 return pk, sk
67 }
68
69 // LWEEncrypt encrypts a single bit using the public key.
70 // Returns (U, V) ciphertext.
71 func LWEEncrypt(pk *LWEPublicKey, bit int) *LWECiphertext {
72 return LWEEncryptFrom(pk, bit, rand.Reader)
73 }
74
75 // LWEEncryptFrom encrypts with a given randomness source.
76 func LWEEncryptFrom(pk *LWEPublicKey, bit int, rng io.Reader) *LWECiphertext {
77 if rng == nil {
78 rng = rand.Reader
79 }
80
81 // R ← ternary.
82 r := ternaryPoly(rng)
83
84 // E1, E2 ← ternary noise.
85 e1 := ternaryPoly(rng)
86 e2 := ternaryPoly(rng)
87
88 // U = A·R + E1.
89 ar := Mul(pk.A, r)
90 u := Add(ar, e1)
91
92 // V = B·R + E2 + encode(bit).
93 br := Mul(pk.B, r)
94 enc := encodeBit(bit)
95 v := Add(br, e2)
96 v = Add(v, enc)
97
98 return &LWECiphertext{U: u, V: v}
99 }
100
101 // LWEDecrypt decrypts a ciphertext using the secret key.
102 // Returns 0 or 1.
103 func LWEDecrypt(sk *LWESecretKey, ct *LWECiphertext) int {
104 // V - S·U = B·R + E2 + encode(m) - S·(A·R + E1)
105 // = (A·S + E)·R + E2 + encode(m) - S·A·R - S·E1
106 // = A·S·R + E·R + E2 + encode(m) - S·A·R - S·E1
107 // = encode(m) + (E·R + E2 - S·E1)
108 // Noise = E·R + E2 - S·E1
109
110 su := Mul(sk.S, ct.U)
111 noisy := Sub(ct.V, su)
112
113 return decodeBit(noisy)
114 }
115
116 // LWEAdd homomorphically adds two ciphertexts.
117 func LWEAdd(ct1, ct2 *LWECiphertext) *LWECiphertext {
118 return &LWECiphertext{
119 U: Add(ct1.U, ct2.U),
120 V: Add(ct1.V, ct2.V),
121 }
122 }
123
124 func encodeBit(bit int) *Poly27 {
125 p := NewPoly27()
126 if bit == 1 {
127 p.Coeffs[0] = uint16(Q / 2) // 135
128 }
129 return p
130 }
131
132 func decodeBit(p *Poly27) int {
133 c := p.Coeffs[0]
134 half := uint16(Q / 2) // 135
135 quarter := uint16(Q / 4) // 67
136 if c > half {
137 c = Q - c
138 }
139 if c > quarter {
140 return 1
141 }
142 return 0
143 }
144
145 func ternaryPoly(rng io.Reader) *Poly27 {
146 p := NewPoly27()
147 var buf [1]byte
148 for i := 0; i < N; i++ {
149 io.ReadFull(rng, buf[:])
150 switch buf[0] % 3 {
151 case 0:
152 p.Coeffs[i] = 0
153 case 1:
154 p.Coeffs[i] = 1
155 case 2:
156 p.Coeffs[i] = Q - 1
157 }
158 }
159 return p
160 }
161
162 // Serialize for public key: 2 × PolyBytes = 62 bytes.
163 func (pk *LWEPublicKey) MarshalBinary() []byte {
164 buf := make([]byte, 2*PolyBytes)
165 copy(buf[:PolyBytes], pk.A.MarshalBinary())
166 copy(buf[PolyBytes:], pk.B.MarshalBinary())
167 return buf
168 }
169
170 func UnmarshalLWEPK(data []byte) (*LWEPublicKey, error) {
171 if len(data) < 2*PolyBytes {
172 return nil, errShortData
173 }
174 a, err := UnmarshalBinary(data[:PolyBytes])
175 if err != nil {
176 return nil, err
177 }
178 b, err := UnmarshalBinary(data[PolyBytes : 2*PolyBytes])
179 if err != nil {
180 return nil, err
181 }
182 return &LWEPublicKey{A: a, B: b}, nil
183 }
184
185 // Ciphertext: 2 × PolyBytes = 62 bytes.
186 func (ct *LWECiphertext) MarshalBinary() []byte {
187 buf := make([]byte, 2*PolyBytes)
188 copy(buf[:PolyBytes], ct.U.MarshalBinary())
189 copy(buf[PolyBytes:], ct.V.MarshalBinary())
190 return buf
191 }
192
193 func UnmarshalLWECT(data []byte) (*LWECiphertext, error) {
194 if len(data) < 2*PolyBytes {
195 return nil, errShortData
196 }
197 u, err := UnmarshalBinary(data[:PolyBytes])
198 if err != nil {
199 return nil, err
200 }
201 v, err := UnmarshalBinary(data[PolyBytes : 2*PolyBytes])
202 if err != nil {
203 return nil, err
204 }
205 return &LWECiphertext{U: u, V: v}, nil
206 }
207