malleable.go raw
1 // Anti-malleability defenses for homomorphic ciphertexts.
2 //
3 // Homomorphic encryption is inherently malleable: anyone can transform
4 // ciphertexts without knowing the plaintext. This is a feature (enables
5 // computation on encrypted data) but also a vulnerability (enables
6 // ciphertext manipulation attacks).
7 //
8 // Defense layers:
9 //
10 // 1. Rerandomization: add Enc(0) to break ciphertext linkability.
11 // Already implemented in he.go. This prevents tracking a ciphertext
12 // through a computation graph.
13 //
14 // 2. Noise flooding: inject large noise into computation results.
15 // The "circuit noise" from homomorphic operations carries information
16 // about intermediate values. Flooding with fresh noise drowns this out.
17 // Cost: reduces remaining noise budget.
18 //
19 // 3. CCA2 session wrapping: wrap HE ciphertexts in a CCA2-secure
20 // session using the FO-transformed KEM from kem.go. An adversary
21 // who modifies the outer layer gets caught by the FO check.
22 //
23 // 4. Signed computation: attach a GPV signature to computation results,
24 // proving the computation was performed by an authorized party.
25 // Without the signing key, an adversary can't forge valid results.
26 //
27 // The combination: rerandomize after each operation, noise-flood before
28 // returning results, wrap in CCA2 for transport, sign to prove provenance.
29
30 package ring
31
32 import (
33 "crypto/rand"
34 "io"
35
36 "golang.org/x/crypto/sha3"
37 )
38
39 // NoiseFlood adds a large amount of fresh noise to a ciphertext.
40 // This drowns out any information leaked through the noise pattern.
41 //
42 // The flood noise must be much larger than the circuit noise but still
43 // smaller than the decryption threshold (q/4 for BGV).
44 //
45 // floodBits controls the magnitude: flood noise ∈ [-2^floodBits, 2^floodBits].
46 func NoiseFlood(pk *KEMPublicKey, ct *HECiphertext, floodBits int) *HECiphertext {
47 return NoiseFloodFrom(pk, ct, floodBits, rand.Reader)
48 }
49
50 // NoiseFloodFrom adds flood noise using the given randomness source.
51 func NoiseFloodFrom(pk *KEMPublicKey, ct *HECiphertext, floodBits int, rng io.Reader) *HECiphertext {
52 p := pk.P.Ring
53 q := p.Q
54
55 // Generate flood noise polynomial with coefficients in [-2^floodBits, 2^floodBits].
56 // Must be even (divisible by 2) to preserve the BGV parity structure.
57 floodU := New(p)
58 floodV := New(p)
59
60 bound := uint32(1) << floodBits
61
62 var buf [4]byte
63 for i := range p.N {
64 // u noise
65 io.ReadFull(rng, buf[:])
66 val := uint32(buf[0])<<16 | uint32(buf[1])<<8 | uint32(buf[2])
67 val = val % (2 * bound)
68 noise := int64(val) - int64(bound)
69 // Make even (BGV structure).
70 noise = noise & ^1
71 if noise >= 0 {
72 floodU.Coeffs[i] = uint32(noise) % q
73 } else {
74 floodU.Coeffs[i] = q - (uint32(-noise) % q)
75 }
76
77 // v noise
78 io.ReadFull(rng, buf[:])
79 val = uint32(buf[0])<<16 | uint32(buf[1])<<8 | uint32(buf[2])
80 val = val % (2 * bound)
81 noise = int64(val) - int64(bound)
82 noise = noise & ^1
83 if noise >= 0 {
84 floodV.Coeffs[i] = uint32(noise) % q
85 } else {
86 floodV.Coeffs[i] = q - (uint32(-noise) % q)
87 }
88 }
89
90 return &HECiphertext{
91 U: Add(ct.U, floodU),
92 V: Add(ct.V, floodV),
93 NoiseEstimate: ct.NoiseEstimate + float64(bound),
94 params: ct.params,
95 }
96 }
97
98 // SecureHEResult wraps a homomorphic computation result with all defenses.
99 type SecureHEResult struct {
100 // Ciphertext is the rerandomized + noise-flooded result.
101 Ciphertext *HECiphertext
102
103 // Tag is a MAC-like binding: H(ciphertext || session_id).
104 // Detects any modification during transport.
105 Tag []byte
106
107 // Signature is an optional GPV signature on the tag,
108 // proving the computation was performed by a specific party.
109 Signature *GPVSignature
110 }
111
112 // WrapResult applies the full anti-malleability stack to a computation result.
113 //
114 // Steps:
115 // 1. Rerandomize (fresh Enc(0))
116 // 2. Noise flood (drown circuit noise)
117 // 3. Compute binding tag
118 // 4. Optionally sign
119 func WrapResult(pk *KEMPublicKey, ct *HECiphertext, sessionID []byte, gpvSK *GPVSecretKey) *SecureHEResult {
120 return WrapResultFrom(pk, ct, sessionID, gpvSK, rand.Reader)
121 }
122
123 // WrapResultFrom wraps with the given randomness source.
124 func WrapResultFrom(pk *KEMPublicKey, ct *HECiphertext, sessionID []byte, gpvSK *GPVSecretKey, rng io.Reader) *SecureHEResult {
125 // Step 1: Rerandomize.
126 ct = RerandomizeFrom(pk, ct, rng)
127
128 // Step 2: Noise flood with moderate noise.
129 // For HE64 (q ≈ 10M), we can afford ~10 bits of flood noise
130 // after one multiplication (noise budget ≈ 22 bits, mul uses ~20).
131 floodBits := 8
132 ct = NoiseFloodFrom(pk, ct, floodBits, rng)
133
134 // Step 3: Compute binding tag.
135 tag := computeTag(ct, sessionID)
136
137 // Step 4: Sign (optional).
138 var sig *GPVSignature
139 if gpvSK != nil {
140 sig = GPVSignFrom(gpvSK, tag, rng)
141 }
142
143 return &SecureHEResult{
144 Ciphertext: ct,
145 Tag: tag,
146 Signature: sig,
147 }
148 }
149
150 // VerifyResult checks the anti-malleability protections.
151 //
152 // Checks:
153 // 1. Tag matches the ciphertext (integrity)
154 // 2. Signature verifies (authenticity, if present)
155 func VerifyResult(result *SecureHEResult, sessionID []byte, gpvPK *GPVPublicKey) bool {
156 // Check tag.
157 expectedTag := computeTag(result.Ciphertext, sessionID)
158 if len(result.Tag) != len(expectedTag) {
159 return false
160 }
161 for i := range result.Tag {
162 if result.Tag[i] != expectedTag[i] {
163 return false
164 }
165 }
166
167 // Check signature (if present).
168 if result.Signature != nil {
169 if gpvPK == nil {
170 return false
171 }
172 if !GPVVerify(gpvPK, result.Tag, result.Signature) {
173 return false
174 }
175 }
176
177 return true
178 }
179
180 // computeTag creates a binding tag from a ciphertext and session ID.
181 func computeTag(ct *HECiphertext, sessionID []byte) []byte {
182 h := sha3.NewShake256()
183 h.Write([]byte("he-result-tag-v1"))
184 h.Write(sessionID)
185
186 // Encode ciphertext components.
187 uBytes := Serialize(ct.U)
188 vBytes := Serialize(ct.V)
189 h.Write(uBytes)
190 h.Write(vBytes)
191
192 tag := make([]byte, 32)
193 h.Read(tag)
194 return tag
195 }
196
197 // SessionWrapper provides CCA2-secure transport for HE ciphertexts.
198 // Uses the KEM to establish a session key, then wraps each result.
199 type SessionWrapper struct {
200 // SessionID is the unique session identifier.
201 SessionID []byte
202
203 // HEPK is the homomorphic encryption public key.
204 HEPK *KEMPublicKey
205
206 // GPVPK is the optional signing public key.
207 GPVPK *GPVPublicKey
208
209 // GPVSK is the optional signing secret key (only for the sender).
210 GPVSK *GPVSecretKey
211 }
212
213 // NewSession creates a new session for wrapping HE results.
214 func NewSession(hePK *KEMPublicKey, gpvPK *GPVPublicKey, gpvSK *GPVSecretKey) *SessionWrapper {
215 sessionID := make([]byte, 32)
216 rand.Read(sessionID)
217
218 return &SessionWrapper{
219 SessionID: sessionID,
220 HEPK: hePK,
221 GPVPK: gpvPK,
222 GPVSK: gpvSK,
223 }
224 }
225
226 // Wrap applies anti-malleability defenses to a computation result.
227 func (sw *SessionWrapper) Wrap(ct *HECiphertext) *SecureHEResult {
228 return WrapResult(sw.HEPK, ct, sw.SessionID, sw.GPVSK)
229 }
230
231 // Verify checks the anti-malleability protections on a received result.
232 func (sw *SessionWrapper) Verify(result *SecureHEResult) bool {
233 return VerifyResult(result, sw.SessionID, sw.GPVPK)
234 }
235