New answers tagged


As is stated in the book, the analogous theorem for public-key encryption is proven in Section 12.2.2. The reason why the proof is delayed until then is that it is more complex than all proofs until this point. In particular, it requires the use of a hybrid argument, and this is introduced only in Chapter 8.


Because you need 8 right pairs for the attack, it is natural to use $k=8$ as a reference point. Then, the median (by the Binomial distribution) is exactly $p k/p=k$ points, suggesting the success rate at least 50%. Then $k$ may indeed be varied (including fractional values) to decrease/increase the success probability, of course as long as the number of ...


Two things. It is simpler to target an integer number of right pairs in terms of implementation. Otherwise you might need to keep a running average. More importantly, it makes sense to round up to the next integer, to improve the probability of actually obtaining that average of right pairs since the procedure rests on statistical assumptions.


In most FHE schemes, the ciphertexts contain noise which grows after performing operations. Its growth for additions is usually negligible compared to multiplications. In addition, the cost of operations is different. Therefore, one wants to minimize the multiplicative depth but also the number of multiplications as they are more costly. For example, in the ...


In general, AND gates are no big deal. In practice however, many zero-knowledge systems are based on rank-1-constraint systems (R1CS, often "arithmetic circuits" in folklore), and the concern that LowMC tries to address is linked to this practicality. Note that I'm talking from the perspective of ZK, although the principles probably carry over to ...

Top 50 recent answers are included