Hello, I was wondering whether it was possible to change from on message modulus to another on lwe ciphertexts. For example I have values on the 2 most significant bits, and I would like to have them on the three MBS. For example if I have 3*2^(n-2) encrypted, I would like to change it to 3*2^(n-3).
That’s more or less a division by 2 for real numbers, so akin to a right shift but without the truncation of the LSB of the message. I thought about ways to do so with a sort of keyswitch, but I think there are always random bits appearing on the new top MSBs, above the original message.
Do I necessarily need a BS to do so? Would you be kind enough to provide some literature about how to do it?
Best.
hello @Norrin_Radix
I believe in that case that you need a bootstrap able to bootstrap 3 bits and give it the two bits input with a lookup table that will shift bits down by 1
another solution is to always have the three bits available and use only 2 bits when you need to potentially
Thanks, more or less what I thought. Too bad then. The probem with the second solution is I am using the MSB to make a modular operation. I don’t think I can do %4 on 3 bits for example without a PBS. (unless I know the value, which is then pointless)
not sure I understand, you use the most significant bit ? i.e. bit #63 in a 64 bits integer ?
I have 64 bits integer (u64) let’s say I can have 0 or 1 or 2 or 3 on the 2 MSB. if I multiply by 2, I end up with 0,2,0,2, if I divide then by 2, 0,1,0,1. and so I caught the parity of the bits. The problem is the division by 2, it can’t be done leveled.
Sorry wrote too fast
I’m asking because if that’s the case you cannot use a PBS potentially as it requires the most significant bit to be 0 because of the negacyclic nature of the polynomial product, as for the modular arithmetic, does not really matter if you do it in a larger modulus e.g. 8 if the smaller modulus divides the bigger modulus (in that case 4 divides 8) so you can resolve the modular op at decryption time
The problem is I want to make the modular operation during the computations. In any case the idea needs that division by 2, because the bit needs to go back where it was previously, after having erased the MSB. If I just do -1 I will end up with 3,1,3,1 instead of 0,1,0,1. I don’t think the MSB is reserved in the ciphertext I used.
let ciphertext_modulus =CiphertextModulus::new_native();
let mut seeder = new_seeder();
let seeder = seeder.as_mut();
let mut encryption_generator =
EncryptionRandomGenerator::<ActivatedRandomGenerator>::new(seeder.seed(), seeder);
let mut secret_generator =
SecretRandomGenerator::<ActivatedRandomGenerator>::new(seeder.seed());
let lwe_secret_key =
allocate_and_generate_new_binary_lwe_secret_key(lwe_dimension,&mut secret_generator);
//let two = 2;
let msg_1 = i;
let plaintext_1 = Plaintext(msg_1<<62);
//let two_plain_text = Plaintext(two<<62);
let mut lwe_1 = allocate_and_encrypt_new_lwe_ciphertext(
&lwe_secret_key,
plaintext_1,
lwe_noise_distribution,
ciphertext_modulus,
&mut encryption_generator,
);
do you use a PBS anywhere ?
edit: except for the potential division/right shift
no, I just add two numbers together (wrapping add). To be accurate I add one number to itself.
Then I suggest working on 3 bits at all times, you can make the modular behavior work with the larger modulus and apply the smaller one at decryption if needed
That’s not really the behavior I want, let me explain because I am now convince it’s impossible.
Let’s say on the 2 MSB I have either m = 0,1, 2 or 3.
if I do 2*m, the result is now 0 or 2 or 0 or 2.
If by miracle I was able to shift the MSB of the message to the LSB of the message, the encrypted value would be 0 or 1. That is we would have the parity, so the equivalent of m&1.
Now if I have m&1, I can compute m’ = m- m&1, m’ is 0,0,2,2. If I apply again that magical division to m’ we get 0,0,1,1.
So if m = b_1 b_0 in binary, we can extract b_0 and b_1, they are encrypted values on 2 different ciphertexts. c1(b_0 Delta) and c2(b_1 Delta).
Then if we can extract b_0 and b_1 in such fachion , there is a way to compute a russian peasant multiplication on arbitrarily sized integer. All would be leveled if there was a leveled way to do the right shift.
But let’s forget about it.
Ok I think I see what you wanted to try to do, unfortunately anything that’s not a linear operation (+, *) is going to require a PBS most likely