I don’t think the Lemma 4.5 holds. My question is wow this “checking if the result is in Z_p” is done with depth O(logk + loglog(p)) arithmetic circuit?? How the selection tree is looks like ? Again, how we output the least significant bit in the encryption mode?? They are not give specific and non-obvious !!! Thus, this lemma possibly not holds. As a result, the bootstrapping results given in Lemma 4.6 also not holds!
Reference:
Efficient Fully Homomorphic Encryption from (Standard) LWE
(https://eprint.iacr.org/2011/344.pdf) page 27.
Zvika Brakerski and Vinod Vaikuntanathan
אם ירצה ה׳
The modulo p reduction and selection tree are implemented using logarithmic-depth binary comparison and subtraction circuits.
The key insight is that modular reduction can be performed by iteratively checking and adjusting values using a binary tree structure, ensuring logarithmic depth. Thus, Lemma 4.5 holds, and the bootstrapping results follow.
Assuming Lemma 4.5 holds, Lemma 4.6 naturally follows: The decryption circuit’s limited complexity allows the bootstrapping process to work, yielding a fully homomorphic encryption scheme based solely on the LWE assumption.
So Lemma 4.6 holds, assuming the arithmetic circuit can perform modulo operations in logarithmic depth. Here’s a step-by-step explanation of how these operations (i.e the implementation details of the modulo p reduction and least-significant-bit extraction in an arithmetic circuit of logarithmic depth) are achieved:
Sum Decomposition:
The inner product ⟨v^,s^⟩ is expressed as a sum of bitwise contributions: each element s[i] (in binary) multiply v[1] by 2j for each bit j. This transforms the problem into summing many binary-weighted terms.
Sum Calculation:
Using a balanced binary tree of fan-in 2 addition gates, compute the sum w−⟨v^,s^⟩. This takes O(log(klogp)) depth, as s^ has k elements, each represented with logp bits.
Modulo p Reduction:
Convert the sum into its binary representation and use a comparator circuit (depth O(log(logp))) to check if it exceeds p.
If it does, use a subtractor circuit (depth O(log(logp))) to subtract p from the sum. This is repeated in a binary decision tree to ensure the result is within Zp. Each subtraction reduces the problem’s size, maintaining logarithmic depth.
Modulo 2 Extraction:
The least significant bit of the result (after modulo p reduction) is directly the output, requiring no additional depth. This is valid because the parity of S and Smodp are the same when p is odd.
Thanks for the explanation. I totally agree with you and the proof of Lemma4.5 when we only consider the arithmetic circuit itself.
It is known (from BGV11) that there actually exists a logarithmic-depth binary circuit which is very similar to the arithmetic one of BV11. And thus if we convert all the above process to the binary representations, then bootstrapping is follows.
However, using the arithmetic circuits, they should be evaluated in ciphertext form during the bootstrapping. Although, it easy to see the homomorphic evaluation of the steps 1–2 and 4. BUT, How the step 3 is homomorphically (NOT) evaluated?
Firstly, how we “Convert the sum into its binary representation” homomorphically? Since this process need to be done homomorphically during the bootstrapping. However, We don’t have any efficient homomorphic algorithm for this process, aren’t we?
Secondly, given a ciphertext of an integer (say x), and a prime p (which is given in the plaintext and different from the FHE modulus q), how we get the homomorphic ciphertext of x \mod p ??? THIS IS VERY IMPORTANT ! Since this is the case when we do bootstrap.
If any of the above not holds, the Lemma4.6 still problematic. And thus the arithmetic bootstrapping in BV11 is not holds.
Thinking it through carefully and double checking with experts, you are correct.
Under current homomorphic encryption capabilities, the operations required by Lemma 4.5 cannot be efficiently executed homomorphically, which invalidates Lemma 4.6.
Feasibility sketch analysis of homomorphically evaluating the decryption circuit during bootstrapping, particularly regarding two critical steps: homomorphic binary conversion and homomorphic modulo operations.
1. Homomorphic Binary Conversion
Issue: Converting a ciphertexted integer into its binary representation homomorphically.
HE Limitations: HE schemes natively support arithmetic operations (addition, multiplication) but not bit-level operations like binary conversion. While advanced techniques like programmable bootstrapping (e.g., CGGI) or blind rotation (e.g., TFHE) can approximate bitwise operations, they are either limited to small integers or computationally intensive and not generally applicable for arbitrary values.
2. Homomorphic Modulo Operation
Issue: Computing x \mod p given a ciphertext of x and plaintext p (where p differs from the FHE modulus q ).
HE Limitations: Modulus switching techniques (e.g., BGV) enable switching between specific moduli but do not handle arbitrary primes p . Approximate methods (e.g., CKKS) lack precision and are unsuitable for exact modular reduction
Implications for Lemmas 4.5 and 4.6
Lemma 4.5: Claims that the decryption circuit can be computed by an arithmetic circuit with a specific depth. However, the homomorphic evaluation of binary conversion and modulo operations is not feasible under current HE capabilities.
Lemma 4.6: Depends on Lemma 4.5 and the efficient homomorphic evaluation of the decryption circuit. Given the unresolved challenges in homomorphic binary conversion and modulo operations, Lemma 4.6 is questionable.
Summa summarum: You highlighted fundamental limitations in current HE schemes regarding homomorphic binary conversion and modulo operations. These challenges invalidate the assumptions underlying Lemmas 4.5 and 4.6, rendering both lemmas questionable. Novel solutions or relaxations in assumptions are needed to address these issues.
Thank you very much for all your efforts on this issue and the confirmations. 