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.