s0l0ist
using smaller key sizes and adjusting the calculation (continued)
Apologies - couldnt' work out if I can re-open a ticket that has been closed. (https://github.com/morfix-io/node-seal/issues/133)
So continuing the conversation there, basically I have data that is larger than i can store in a a single array (each array can't be bigger than the PolyModulusDegree)
So to start, assuming the parameters are:
const heConfig = {
keySize: 4096,
bitSize: 20
}
then in each array of data to process I can store 4096 bits of data. With regards to my algorithm then:
for (let i = 0, l = arraysToSend.length; i < l; i++) {
const image3232Chunk = seal.CipherText()
image3232Chunk.load(context, arraysToSend[i]) //load the current image chunk
const encryptedFillArray = seal.CipherText()
encryptedFillArray.load(context, savedFillArray) //encrypted load of zeros to store the result
for (let j = 0, end = kernels.length; j < end; j++) {
const tmp = evaluator.multiplyPlain(image3232Chunk, kernels[j])
evaluator.add(encryptedFillArray, tmp, encryptedFillArray)
}
const send = encryptedFillArray.save()
convEncArray.push(send)
}
- I am loading in the first 4096 bits of data here
image3232Chunk.load(context, arraysToSend[i]) - I create a "place" to store the answer,
encryptedFillArray.load(context, savedFillArray)(sendFillArray is an encrypted set of zeros that I am cloning into encryptedFillArray) - then I have a array of plain texts (kernels) each is nine 1s and the rest zeros, each entry in the array is shifted nine along from the last:
[0]: 1, 1 ,1 ,1 ,1 ,1 ,1 ,1 ,1, 0, 0, 0, 0, 0, 0, 0, 0, 0...... (to 4096 in total)
[1]: 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1 ,1 ,1 ,1 ,1 ,1 ,1 ,1...... (to 4096 in total)
etc, until all 4096 places have been a 1 in an entry.
Reason being, I want to multiply the each set of 9 values of image3232Chunk by the kernel value (which in practice won't be 1's, thats just for testing) - then its stored in tmp. Then tmp is added to encryptedFillArray - the reason for the zeros will then mean the other values in encryptedFillArray are not affected during the addition here: evaluator.add(encryptedFillArray, tmp, encryptedFillArray)
I.e adding
0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1 ,1 ,1 ,1 ,1 ,1 ,1 ,1......
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ....
will not affect the first nine 2s so I can keep adding them and only affecting the correct nine slots.
Then i save that result in convEncArray and do it again for the next arrayToSend.
This works nicely except that I can't use a smaller keySize than 4096 because evaluator.add corrupts the data with smaller key sizes however using 4096 to encrypt the data means I have about half a MB of data to send over HTTP, whereas with 1024 key size, I have about 25kb to send over HTTP.
However I reckon either, I can use a relin key on evaluator.add(encryptedFillArray, tmp, encryptedFillArray) with a smaller keySize, or a more efficient algorithm to do the addition.
So....
My question then is, is there a "neat" way to add all the tmps I have together in one go so not to corrupt encrytpedFilleArray with smaller keys (1024, 2048), or can I relin after every loop round (or somehow work out when to relin so not to do it every time around the loop) and will relin key that I have to send with the request over HTTP just make it as big and therefore be pointless?
Hopefully that makes some more sense?
Thank you!
Hmm I think Microsoft Seal has an add_many - is this reflected in node seal anywhere? Does this solve my problem if it were to exist?
Hi @s0l0ist , I've done further research to try to pin my issue down and I think its not quite what I thought it was as add shouldn't cause an issue based on keySize. I have created a working snippet here which I would appreciate if you might be able to look at.
The important bits; Lines 4-12:
const heConfig = {
keySize: 4096,
bitSize: 20
}
// const heConfig = {
// keySize: 1024,
// bitSize: 16
// }
this is where I am setting the polymod keySize. you can change them over to test the difference. The code calculates the same thing with and without homomorphic encryption. It finally prints out the two tables that should match. With polymodulus 4096 they match, with keySize 1024 they dont. You can see the values are corrupted. Lines 205-210:
for (let j = 0, end = kernels.length; j < end; j++) {
//by multiplying the encrypted array by the kernel, the zeros in the kernel will result in a zero in the answer so only the values non zero will be affected
const tmp = evaluator.multiplyPlain(encryptedArray, kernels[j])
//now we add the multiplication to the answer array. Again, zeros added to zeros will stay as zeros and zeros added to values won't change.
evaluator.add(encryptedFillArray, tmp, encryptedFillArray) //stored in encryptedFillArray
}
This is where the homomorphic encryption bit is. I am sure (but I might be wrong) the error occurs when I am adding all the tmp values to the encryptedFillArray. When I do this with 4096 it seems fine. I printed tmp with both 1024 and 4096 and I think it is correct so I don't think the multiplication is the issue. I have put the tables output here as I can't paste them in discord.
Basically, it's hard to explain but I am trying to efficiently use each array position in encryptedFillArray to store groups of 9 values. Each multiplication calculates the next 9 values, and by storing those in a (keySize) array, and at the correct position, by adding them all together (the other values all being zero, encryptedFillArray ends up holding all the groups of 9 in the least amount of space. This helps minimise the amount of space used, and if I can use smaller key sizes than 4096 I can use even less space overall.
However looking further to try and see where the issue is occuring, on lines 226-234:
for (let i = 0, l = encryptedResults.length; i < l; i++) {
const cipherText = seal.CipherText()
cipherText.load(context, encryptedResults[i]) //heConfig.keySize bits of data
const decryptedPlainText = decryptor.decrypt(cipherText)
console.log("Print", decryptedPlainText.saveArray())
const decodedArray = encoder.decode(decryptedPlainText)
console.log("decrypted", decodedArray)
concatenatedEncryptedResults = concatenatedEncryptedResults.concat(...decodedArray)
}
Then I get an output with 4096:
Print Uint8Array(13319) [
94, 161, 16, 4, 0, 2, 0, 0, 7, 52, 0, 0,
0, 0, 0, 0, 40, 181, 47, 253, 96, 72, 127, 109,
159, 1, 154, 72, 158, 139, 47, 16, 104, 60, 6, 36,
53, 79, 48, 77, 216, 150, 67, 210, 121, 204, 0, 113,
21, 244, 231, 68, 105, 64, 66, 238, 85, 181, 72, 200,
148, 128, 240, 161, 58, 248, 148, 120, 164, 51, 51, 51,
51, 51, 51, 51, 165, 31, 143, 8, 169, 8, 179, 8,
247, 204, 117, 40, 79, 120, 157, 71, 13, 220, 16, 56,
101, 179, 41, 220,
... 13219 more items
]
decrypted Int32Array(4096) [
1, 2, 3, 9, 8, 7, 1, 8, 3, 2, 3, 4,
8, 7, 6, 8, 3, 6, 3, 4, 5, 7, 6, 5,
3, 6, 5, 4, 5, 6, 6, 5, 4, 6, 5, 4,
5, 6, 7, 5, 4, 3, 5, 4, 7, 6, 7, 8,
4, 3, 2, 4, 7, 2, 7, 8, 9, 3, 2, 1,
7, 2, 9, 9, 8, 7, 1, 8, 3, 9, 8, 7,
8, 7, 6, 8, 3, 6, 8, 7, 6, 7, 6, 5,
3, 6, 5, 7, 6, 5, 6, 5, 4, 6, 5, 4,
6, 5, 4, 5,
... 3996 more items
]
With 1024:
Print Uint8Array(2354) [
94, 161, 16, 4, 0, 2, 0, 0, 50, 9, 0, 0,
0, 0, 0, 0, 40, 181, 47, 253, 96, 72, 31, 197,
72, 0, 132, 132, 0, 0, 4, 0, 240, 63, 94, 161,
16, 24, 32, 219, 178, 0, 0, 119, 233, 0, 86, 179,
0, 144, 63, 0, 198, 149, 0, 173, 113, 0, 223, 62,
0, 179, 152, 0, 163, 135, 0, 204, 226, 0, 6, 219,
0, 27, 69, 0, 211, 158, 0, 45, 238, 0, 245, 232,
0, 45, 227, 0, 36, 186, 0, 127, 129, 0, 198, 103,
0, 40, 234, 0,
... 2254 more items
]
decrypted Int32Array(1024) [
-3162, -4767, 10928, -6801, 13379, -26780, -14359, -12386,
-21727, -25469, -7653, 8925, 27850, 27146, -23232, 15632,
-12531, -14929, -15674, 12321, 21509, -1884, -8209, 2473,
16614, 26637, -7392, 692, -581, 26260, -19108, 15306,
-2427, -11649, 5642, -10869, -12109, -9840, 25091, 9237,
19718, 20099, 3477, 23584, 2997, -15995, 4985, -12582,
8868, 3991, -30448, -30530, -14739, 26929, 1279, -25277,
-23463, 2891, 17269, -16591, -15638, -592, -23793, -3289,
15580, 19335, -23376, 11558, 14680, 15793, 12594, -10549,
12499, -30675, 3567, -21212, 23358, 21138, -13080, -18256,
-17970, 28483, 15689, 3714, 13201, 1426, 15478, -23135,
-20101, 984, 9918, 9161, 5906, 22241, -12275, -16530,
-11425, 7926, 13345, -15459,
... 924 more items
]
I am struggling to understand as I don't think each multiplication is enough to cause an issue with 1024 bit looking at the values that end up in the encrypted array (very similar to with 4096) and add shouldn't cause the issue because the degree of the polynomial will remain the same as I understand it.
Yeah sounds like the noise budget can't take it. Try with 2048 poly mod degree.
