New answers tagged

0

I think there is a confusion with the terminology "secure computation from secret sharing". Let me try to clarify. There are two major settings for secure computation: the honest majority setting (out of $n$ parties, at most $(n-1)/2$ are dishonest) and the dishonest majority setting (up to $n-1$ parties can be dishonest). The two settings have a ...


0

You must choose q so that the noise in the ciphertext doesn't overflow. For example, if $p = 2$ and $n = 256$ you can use $q = 7681$ (taken from Kyber). There are many possible instantiations, and the important point is that the norm $||c_0 - c_1 s||_\infty = ||p (e r + e_2 - e_1 s) + m||_\infty$ is less than $q/2$.


0

Are you trying to say that if the product is greater than the modulo then I can't get the true result in anyway? Yes. Pailler computes modulo $n$ even if the cryptograms are in $[0,n^2)$. Not coincidentally, $42\times15\equiv14\pmod{77}$. For Pailler to be secure, one needs $n$ of several hundred digits, so that's not necessarily an issue.


0

I am unfamiliar with the TFHE library; however my guess is that its execution time is bounded by DRAM accesses (that is, cache misses) and not by CPU computations (that is, the size of the memory it tries to access doesn't fit within the cache). If that were the case, then (consistent with what you observed) adding more threads wouldn't speed things up; each ...


2

It is not true that RLWE guarantees that $h_i$ is computationally indistinguishable from uniform for any fixed $p_1$: just consider the case of $p_1 = 0$. At the opposite end, if $p_1$ is invertible is $R_q$ (which is the generic case), then each $h_i$ is exactly uniformly distributed in $R_q$, and they are all independent, so the joint distribution is just ...


1

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 ...


1

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