1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
// Copyright (c) Microsoft Corporation. All rights reserved.
// Licensed under the MIT license.
#pragma once
#include "seal/context.h"
#include "seal/plaintext.h"
#include "seal/util/defines.h"
#include <vector>
#ifdef SEAL_USE_MSGSL
#include "gsl/span"
#endif
namespace seal
{
/**
Provides functionality for CRT batching. If the polynomial modulus degree is N, and
the plaintext modulus is a prime number T such that T is congruent to 1 modulo 2N,
then BatchEncoder allows the plaintext elements to be viewed as 2-by-(N/2)
matrices of integers modulo T. Homomorphic operations performed on such encrypted
matrices are applied coefficient (slot) wise, enabling powerful SIMD functionality
for computations that are vectorizable. This functionality is often called "batching"
in the homomorphic encryption literature.
@par Mathematical Background
Mathematically speaking, if the polynomial modulus is X^N+1, N is a power of two, and
plain_modulus is a prime number T such that 2N divides T-1, then integers modulo T
contain a primitive 2N-th root of unity and the polynomial X^N+1 splits into n distinct
linear factors as X^N+1 = (X-a_1)*...*(X-a_N) mod T, where the constants a_1, ..., a_n
are all the distinct primitive 2N-th roots of unity in integers modulo T. The Chinese
Remainder Theorem (CRT) states that the plaintext space Z_T[X]/(X^N+1) in this case is
isomorphic (as an algebra) to the N-fold direct product of fields Z_T. The isomorphism
is easy to compute explicitly in both directions, which is what this class does.
Furthermore, the Galois group of the extension is (Z/2NZ)* ~= Z/2Z x Z/(N/2) whose
action on the primitive roots of unity is easy to describe. Since the batching slots
correspond 1-to-1 to the primitive roots of unity, applying Galois automorphisms on the
plaintext act by permuting the slots. By applying generators of the two cyclic
subgroups of the Galois group, we can effectively view the plaintext as a 2-by-(N/2)
matrix, and enable cyclic row rotations, and column rotations (row swaps).
@par Valid Parameters
Whether batching can be used depends on whether the plaintext modulus has been chosen
appropriately. Thus, to construct a BatchEncoder the user must provide an instance
of SEALContext such that its associated EncryptionParameterQualifiers object has the
flags parameters_set and enable_batching set to true.
@see EncryptionParameters for more information about encryption parameters.
@see EncryptionParameterQualifiers for more information about parameter qualifiers.
@see Evaluator for rotating rows and columns of encrypted matrices.
*/
class BatchEncoder
{
public:
/**
Creates a BatchEncoder. It is necessary that the encryption parameters
given through the SEALContext object support batching.
@param[in] context The SEALContext
@throws std::invalid_argument if the encryption parameters are not valid for batching
@throws std::invalid_argument if scheme is not scheme_type::bfv
*/
BatchEncoder(const SEALContext &context);
/**
Creates a plaintext from a given matrix. This function "batches" a given matrix
of integers modulo the plaintext modulus into a plaintext element, and stores
the result in the destination parameter. The input vector must have size at most equal
to the degree of the polynomial modulus. The first half of the elements represent the
first row of the matrix, and the second half represent the second row. The numbers
in the matrix can be at most equal to the plaintext modulus for it to represent
a valid plaintext.
If the destination plaintext overlaps the input values in memory, the behavior of
this function is undefined.
@param[in] values The matrix of integers modulo plaintext modulus to batch
@param[out] destination The plaintext polynomial to overwrite with the result
@throws std::invalid_argument if values is too large
*/
void encode(const std::vector<std::uint64_t> &values, Plaintext &destination) const;
/**
Creates a plaintext from a given matrix. This function "batches" a given matrix
of integers modulo the plaintext modulus into a plaintext element, and stores
the result in the destination parameter. The input vector must have size at most equal
to the degree of the polynomial modulus. The first half of the elements represent the
first row of the matrix, and the second half represent the second row. The numbers
in the matrix can be at most equal to the plaintext modulus for it to represent
a valid plaintext.
If the destination plaintext overlaps the input values in memory, the behavior of
this function is undefined.
@param[in] values The matrix of integers modulo plaintext modulus to batch
@param[out] destination The plaintext polynomial to overwrite with the result
@throws std::invalid_argument if values is too large
*/
void encode(const std::vector<std::int64_t> &values, Plaintext &destination) const;
#ifdef SEAL_USE_MSGSL
/**
Creates a plaintext from a given matrix. This function "batches" a given matrix
of integers modulo the plaintext modulus into a plaintext element, and stores
the result in the destination parameter. The input must have size at most equal
to the degree of the polynomial modulus. The first half of the elements represent the
first row of the matrix, and the second half represent the second row. The numbers
in the matrix can be at most equal to the plaintext modulus for it to represent
a valid plaintext.
If the destination plaintext overlaps the input values in memory, the behavior of
this function is undefined.
@param[in] values The matrix of integers modulo plaintext modulus to batch
@param[out] destination The plaintext polynomial to overwrite with the result
@throws std::invalid_argument if values is too large
*/
void encode(gsl::span<const std::uint64_t> values, Plaintext &destination) const;
/**
Creates a plaintext from a given matrix. This function "batches" a given matrix
of integers modulo the plaintext modulus into a plaintext element, and stores
the result in the destination parameter. The input must have size at most equal
to the degree of the polynomial modulus. The first half of the elements represent the
first row of the matrix, and the second half represent the second row. The numbers
in the matrix can be at most equal to the plaintext modulus for it to represent
a valid plaintext.
If the destination plaintext overlaps the input values in memory, the behavior of
this function is undefined.
@param[in] values The matrix of integers modulo plaintext modulus to batch
@param[out] destination The plaintext polynomial to overwrite with the result
@throws std::invalid_argument if values is too large
*/
void encode(gsl::span<const std::int64_t> values, Plaintext &destination) const;
#endif
/**
Inverse of encode. This function "unbatches" a given plaintext into a matrix
of integers modulo the plaintext modulus, and stores the result in the destination
parameter. The input plaintext must have degrees less than the polynomial modulus,
and coefficients less than the plaintext modulus, i.e. it must be a valid plaintext
for the encryption parameters. Dynamic memory allocations in the process are
allocated from the memory pool pointed to by the given MemoryPoolHandle.
@param[in] plain The plaintext polynomial to unbatch
@param[out] destination The matrix to be overwritten with the values in the slots
@param[in] pool The MemoryPoolHandle pointing to a valid memory pool
@throws std::invalid_argument if plain is not valid for the encryption parameters
@throws std::invalid_argument if plain is in NTT form
@throws std::invalid_argument if pool is uninitialized
*/
void decode(
const Plaintext &plain, std::vector<std::uint64_t> &destination,
MemoryPoolHandle pool = MemoryManager::GetPool()) const;
/**
Inverse of encode. This function "unbatches" a given plaintext into a matrix
of integers modulo the plaintext modulus, and stores the result in the destination
parameter. The input plaintext must have degrees less than the polynomial modulus,
and coefficients less than the plaintext modulus, i.e. it must be a valid plaintext
for the encryption parameters. Dynamic memory allocations in the process are
allocated from the memory pool pointed to by the given MemoryPoolHandle.
@param[in] plain The plaintext polynomial to unbatch
@param[out] destination The matrix to be overwritten with the values in the slots
@param[in] pool The MemoryPoolHandle pointing to a valid memory pool
@throws std::invalid_argument if plain is not valid for the encryption parameters
@throws std::invalid_argument if plain is in NTT form
@throws std::invalid_argument if pool is uninitialized
*/
void decode(
const Plaintext &plain, std::vector<std::int64_t> &destination,
MemoryPoolHandle pool = MemoryManager::GetPool()) const;
#ifdef SEAL_USE_MSGSL
/**
Inverse of encode. This function "unbatches" a given plaintext into a matrix
of integers modulo the plaintext modulus, and stores the result in the destination
parameter. The input plaintext must have degrees less than the polynomial modulus,
and coefficients less than the plaintext modulus, i.e. it must be a valid plaintext
for the encryption parameters. Dynamic memory allocations in the process are
allocated from the memory pool pointed to by the given MemoryPoolHandle.
@param[in] plain The plaintext polynomial to unbatch
@param[out] destination The matrix to be overwritten with the values in the slots
@param[in] pool The MemoryPoolHandle pointing to a valid memory pool
@throws std::invalid_argument if plain is not valid for the encryption parameters
@throws std::invalid_argument if plain is in NTT form
@throws std::invalid_argument if destination has incorrect size
@throws std::invalid_argument if pool is uninitialized
*/
void decode(
const Plaintext &plain, gsl::span<std::uint64_t> destination,
MemoryPoolHandle pool = MemoryManager::GetPool()) const;
/**
Inverse of encode. This function "unbatches" a given plaintext into a matrix
of integers modulo the plaintext modulus, and stores the result in the destination
parameter. The input plaintext must have degrees less than the polynomial modulus,
and coefficients less than the plaintext modulus, i.e. it must be a valid plaintext
for the encryption parameters. Dynamic memory allocations in the process are
allocated from the memory pool pointed to by the given MemoryPoolHandle.
@param[in] plain The plaintext polynomial to unbatch
@param[out] destination The matrix to be overwritten with the values in the slots
@param[in] pool The MemoryPoolHandle pointing to a valid memory pool
@throws std::invalid_argument if plain is not valid for the encryption parameters
@throws std::invalid_argument if plain is in NTT form
@throws std::invalid_argument if destination has incorrect size
@throws std::invalid_argument if pool is uninitialized
*/
void decode(
const Plaintext &plain, gsl::span<std::int64_t> destination,
MemoryPoolHandle pool = MemoryManager::GetPool()) const;
#endif
/**
Returns the number of slots.
*/
SEAL_NODISCARD inline auto slot_count() const noexcept
{
return slots_;
}
private:
BatchEncoder(const BatchEncoder ©) = delete;
BatchEncoder(BatchEncoder &&source) = delete;
BatchEncoder &operator=(const BatchEncoder &assign) = delete;
BatchEncoder &operator=(BatchEncoder &&assign) = delete;
void populate_roots_of_unity_vector(const SEALContext::ContextData &context_data);
void populate_matrix_reps_index_map();
void reverse_bits(std::uint64_t *input);
MemoryPoolHandle pool_ = MemoryManager::GetPool();
SEALContext context_;
std::size_t slots_;
util::Pointer<std::uint64_t> roots_of_unity_;
util::Pointer<std::size_t> matrix_reps_index_map_;
};
} // namespace seal