recognizer.mx raw
1 // Searchable encryption via homomorphic pattern matching.
2 package ring
3
4 import (
5 "crypto/rand"
6 "io"
7 )
8
9 type EncryptedBitVector struct {
10 Bits []*HECiphertext
11 PK *KEMPublicKey
12 params KEMParams
13 }
14
15 func EncryptBits(pk *KEMPublicKey, data []byte) (ebv *EncryptedBitVector) {
16 return EncryptBitsFrom(pk, data, rand.Reader)
17 }
18
19 func EncryptBitsFrom(pk *KEMPublicKey, data []byte, rng io.Reader) (ebv *EncryptedBitVector) {
20 bits := []*HECiphertext{:int32(len(data)) * 8}
21 for i := int32(0); i < int32(len(data)); i++ {
22 b := data[i]
23 for j := int32(0); j < 8; j++ {
24 bit := int32((b >> uint32(j)) & 1)
25 bits[i*8+j] = HEEncryptFrom(pk, bit, rng)
26 }
27 }
28 return &EncryptedBitVector{
29 Bits: bits,
30 PK: pk,
31 params: pk.P,
32 }
33 }
34
35 func DecryptBits(sk *KEMSecretKey, ebv *EncryptedBitVector) (result []byte) {
36 nBytes := (int32(len(ebv.Bits)) + 7) / 8
37 result = []byte{:nBytes}
38 for i := int32(0); i < int32(len(ebv.Bits)); i++ {
39 bit := HEDecrypt(sk, ebv.Bits[i])
40 if bit != 0 {
41 result[i/8] |= 1 << uint32(i%8)
42 }
43 }
44 return result
45 }
46
47 type EncryptedPattern struct {
48 PatternBits []*HECiphertext
49 Mask []bool
50 }
51
52 func EncryptPattern(pk *KEMPublicKey, pattern []byte, mask []bool) (ep *EncryptedPattern) {
53 bits := []*HECiphertext{:int32(len(pattern)) * 8}
54 for i := int32(0); i < int32(len(pattern)); i++ {
55 b := pattern[i]
56 for j := int32(0); j < 8; j++ {
57 bit := int32((b >> uint32(j)) & 1)
58 bits[i*8+j] = HEEncrypt(pk, bit)
59 }
60 }
61
62 var bitMask []bool
63 if mask != nil {
64 bitMask = []bool{:int32(len(pattern)) * 8}
65 for i := int32(0); i < int32(len(mask)); i++ {
66 for j := int32(0); j < 8; j++ {
67 bitMask[i*8+j] = mask[i]
68 }
69 }
70 }
71
72 return &EncryptedPattern{
73 PatternBits: bits,
74 Mask: bitMask,
75 }
76 }
77
78 func MatchBit(dataBit, patternBit *HECiphertext) (result *HECiphertext) {
79 xored := HEXOR(dataBit, patternBit)
80 return HENot(xored)
81 }
82
83 func MatchByte(dataBits, patternBits []*HECiphertext, rlk *RelinearizationKey) (result *HECiphertext) {
84 if int32(len(dataBits)) != 8 || int32(len(patternBits)) != 8 {
85 panic("MatchByte requires exactly 8 bits each")
86 }
87
88 matches := []*HECiphertext{:8}
89 for i := int32(0); i < 8; i++ {
90 matches[i] = MatchBit(dataBits[i], patternBits[i])
91 }
92
93 return andTree(matches, rlk)
94 }
95
96 func MatchByteSingle(dataBits, patternBits []*HECiphertext, rlk *RelinearizationKey) (results []*HECiphertext) {
97 if int32(len(dataBits)) != 8 || int32(len(patternBits)) != 8 {
98 panic("MatchByteSingle requires exactly 8 bits each")
99 }
100
101 xnors := []*HECiphertext{:8}
102 for i := int32(0); i < 8; i++ {
103 xnors[i] = MatchBit(dataBits[i], patternBits[i])
104 }
105
106 results = []*HECiphertext{:4}
107 for i := int32(0); i < 4; i++ {
108 results[i] = HEAND(xnors[2*i], xnors[2*i+1], rlk)
109 }
110 return results
111 }
112
113 func SearchAt(data *EncryptedBitVector, pattern *EncryptedPattern, pos int32, rlk *RelinearizationKey) (allResults []*HECiphertext) {
114 patLen := int32(len(pattern.PatternBits)) / 8
115 if pos*8+patLen*8 > int32(len(data.Bits)) {
116 return nil
117 }
118
119 for byteIdx := int32(0); byteIdx < patLen; byteIdx++ {
120 dataStart := (pos + byteIdx) * 8
121 patStart := byteIdx * 8
122
123 if pattern.Mask != nil {
124 isWild := true
125 for b := int32(0); b < 8; b++ {
126 if pattern.Mask[patStart+b] {
127 isWild = false
128 break
129 }
130 }
131 if isWild {
132 continue
133 }
134 }
135
136 pairs := MatchByteSingle(
137 data.Bits[dataStart:dataStart+8],
138 pattern.PatternBits[patStart:patStart+8],
139 rlk,
140 )
141 allResults = append(allResults, pairs...)
142 }
143
144 return allResults
145 }
146
147 func andTree(inputs []*HECiphertext, rlk *RelinearizationKey) (result *HECiphertext) {
148 if int32(len(inputs)) == 0 {
149 return nil
150 }
151 if int32(len(inputs)) == 1 {
152 return inputs[0]
153 }
154
155 for int32(len(inputs)) > 1 {
156 var next []*HECiphertext
157 for i := int32(0); i+1 < int32(len(inputs)); i += 2 {
158 next = append(next, HEAND(inputs[i], inputs[i+1], rlk))
159 }
160 if int32(len(inputs))%2 == 1 {
161 next = append(next, inputs[int32(len(inputs))-1])
162 }
163 inputs = next
164 }
165 return inputs[0]
166 }
167
168 type RecognizerResult struct {
169 MatchPairs []*HECiphertext
170 Position int32
171 }
172
173 func DecryptResult(sk *KEMSecretKey, result *RecognizerResult) (ok bool) {
174 for i := int32(0); i < int32(len(result.MatchPairs)); i++ {
175 if HEDecrypt(sk, result.MatchPairs[i]) != 1 {
176 return false
177 }
178 }
179 return true
180 }
181
182 func Recognize(pk *KEMPublicKey, sk *KEMSecretKey, rlk *RelinearizationKey,
183 data []byte, pattern []byte) (matches []int32) {
184
185 encData := EncryptBits(pk, data)
186 encPattern := EncryptPattern(pk, pattern, nil)
187
188 patLen := int32(len(pattern))
189
190 for pos := int32(0); pos <= int32(len(data))-patLen; pos++ {
191 pairs := SearchAt(encData, encPattern, pos, rlk)
192 if pairs == nil {
193 continue
194 }
195
196 result := &RecognizerResult{
197 MatchPairs: pairs,
198 Position: pos,
199 }
200
201 if DecryptResult(sk, result) {
202 matches = append(matches, pos)
203 }
204 }
205
206 return matches
207 }
208