Digital Log

    Choosing Smudge Variance

    What follows is a brief outline of the argument presented in Efficient Threshold FHE with Application to Real-Time Systems, and questions regarding its asymptotic parameter bounds.

    Summary: As long as an adversary's views of real and simulated partial decryptions are publicly sampleable and have bounded Renyi divergence, then it cannot distinguish between encryptions of $\textbf{m}_0, \textbf{m}_1$ with non-negligible probability without breaking the original security of the underlying FHE scheme.

    The game: Adversary chooses $\textbf{m}0 = (m^0_1,\ldots,m^0\ell), \textbf{m}1 = (m^1_1,\ldots,m^1\ell)$ and $Q$ circuits ${C_i: M^\ell \to M}_{i \in [Q]}$ such that $C_i(\textbf{m}_0) = C_i(\textbf{m}_1)$ for all $i$.

    • Note: In this game, because the adversary can generate the decryption shares of the corrupted parties and gets to see the honest parties' decryption shares, it can compute the resulting decryption. The objective is for the adversary to determine the original inputs, i.e. $\textbf{m}_0$ vs. $\textbf{m}_1$.
      Thus, the challenger randomly samples $b \leftarrow {0, 1}$ to choose $\textbf{m}_b$ and provides the adversary with:
    • $ct^* := {ct^b_i}{i \in [\ell]} = {TFHE.Enc(pk, m^b_i)}{i \in [\ell]}$
    • the ciphertexts resulting from the evaluated circuits: ${\hat{ct}j}:= {TFHE.Eval(pk, C_j, ct^*}{j \in [Q]}$
    • the partial decryptions of those ciphertexts by the honest parties
      Assume $t = T$ for now (extending to general case is simple given the Renyi multiplicative property), and deal with a single circuit output $\hat{ct} = (A,B)$. The adversary has corrupted all but one party, WLOG $P_1$, and thus has access to:
    • the secret key shares ${SH_2,\ldots,SH_T}$
    • the honest partial decryption $part_decrypt_1 := A \cdot SH_1 + e_{sm}$

    The simulation: As mentioned in the summary, we wish to bound the difference between the real and simulated partial decryption distributions. The simulator does not know any more than the adversary does. But recall, the adversary does know the underlying plaintext $m$ in this case (it can perform the threshold decryption accurately). The simulator outputs:
    $$ part_decrypt_1^{Sim} := B - m - \sum_{i = 2}^T A \cdot SH_i + e_{sm} $$
    Defining $\gamma := B - m - \sum_{i = 2}^T A \cdot SH_i$, we have
    $$ part_decrypt_1^{Sim} = \gamma + e_{sm} \qquad \text{ and }\qquad part_decrypt_1 = \gamma - e + e_{sm} $$
    Analysis: Relating back to the game, for each circuit/query $i$, the honest party $P_1$'s partial decryption is computed as $\gamma + r_i$, where noise values $r = {r_i}{i \in [Q]}$ are either drawn from distribution $e{sm}$ or $(e_{sm} - e)$, depending on whether the challenger is providing real or simulated partial decryptions. Let

    • $r = {r_i}{i \in [Q]}$ be the noise values drawn from real distribution $e{sm} - e$
    • $r' = {r'i}{i \in [Q]}$ be the noise values drawn from simulated distribution $e_{sm}$
    • $D_b(r)$ be the distribution representing the view of the adversary when challenger samples bit $b$ with real partial decryptions.
    • $D_b(r')$ be the distribution representing the view of the adversary when challenger samples bit $b$ with simulated partial decryptions.
    • $P$ be the problem of distinguishing $D_0(r)$ vs. $D_1(r)$
    • $P'$ be the problem of distinguishing $D_0(r')$ vs. $D_1(r')$
    • $\delta$ denote the advantage with which adversary distinguishes $P$.
    • $\delta'$ denote the advantage with which adversary distinguishes $P'$.
    • $\Psi$ denote the distribution of $e_{sm} - e$
    • $\Psi'$ denote the distribution of $e_{sm}$
    • $R_a(\Psi||\Psi')$ denote the Renyi divergence of order $a$ between $\Psi$ and $\Psi$'.

    Because $D_b(r)$ is "publicly sampleable" (see argument on p25), we have:
    If there existed a non-negligible real distinguisher for problem $P$ with distinguishing probability $\delta$, then there would also be a distinguisher for the simulated problem $P'$ with distinguishing probability $\delta'$ such that
    $$ \delta' \ge \frac{\delta}{4 R_a(\Psi||\Psi')}\left(\frac{\delta}{2}\right)^{\frac{a}{a-1}}$$
    It follows from previous work (ref TT15) that

    $$ R_a(\Psi||\Psi') \le \exp\left(\frac{a \pi Q (T-t+1)N c^2 \alpha^2}{\sigma^2}\right) $$
    hence
    $$ \delta' \ge \frac{\delta}{4 }\left(\frac{\delta}{2}\right)^{\frac{a}{a-1}} \exp\left(\frac{-a \pi Q (T-t+1)N c^2 \alpha^2}{\sigma^2}\right)$$
    The Conclusion: the argument is by contradiction. It essentially says suppose the adversary did have some non-negligible advantage $\delta$ when the challenger uses real partial decryption samples. If so, then there would also be a non-negligible advantage $\delta'$ in the simulated problem - but the advantage of the simulated problem has to be negligible by the binary ring-LWE assumption; hence $\delta$ must be negligible.

    The paper recommends (asymptotic?) parameter bound $\sigma \ge c\alpha\sqrt{QN(T-t+1)}$. Then you have $\delta' \ge \frac{1}{2}\left(\frac{\delta}{2}\right)^{\frac{2a - 1}{a-1}}\exp(-a \cdot \pi)$ for all $a > 1$.

    Questions: Given the logic of the argument above, as $\sigma$ grows, the difference between $\delta$ and $\delta'$ shrinks. I would think the way to choose $\sigma$ in terms of a desired advantage $\delta$ is as follows:

    1. Assume a $\delta'$ based on the RLWE hardness assumption, let's say $\delta' = 2^{-128}$.
    2. Define a target $\delta = 2^{-50}$ for distinguishing advantage for problem $P$.
    3. Pick $Q$ according to application needs: for example $Q = 2^{10}$.
    4. Pick an arbitrary $a$ value for the Renyi divergence? For example $a = 2$.
    5. Find $\sigma$ based on the bound above

    However, I don't think the above inequality can be used in this way. Perhaps this is due to the contrapositive argument, but if you pick ideal values for $\delta$ and solve for $\sigma$, you end up with an upper bound for $\sigma$, not a lower bound.

    scratch below

    General attempt one:
    $$\begin{align}
    \delta' &\ge \frac{\delta}{4 }\left(\frac{\delta}{2}\right)^{\frac{a}{a-1}} \exp\left(\frac{-a \pi Q (T-t+1)N c^2 \alpha^2}{\sigma^2}\right) \\&= \frac{1}{2 }\left(\frac{\delta}{2}\right)^{\frac{2a-1}{a-1}} \exp\left(\frac{-a \pi Q (T-t+1)N c^2 \alpha^2}{\sigma^2}\right) \\\implies 2\delta'\left(\frac{\delta}{2}\right)^{\frac{1-2a}{a-1}} &\ge \exp\left(\frac{-a \pi Q (T-t+1)N c^2 \alpha^2}{\sigma^2}\right) \\\implies \ln\left(2\delta'\left(\frac{\delta}{2}\right)^{\frac{1-2a}{a-1}}\right) &\ge \frac{-a \pi Q (T-t+1)N c^2 \alpha^2}{\sigma^2} \\\implies \sigma^2 &\ge \frac{-a \pi Q (T-t+1)N c^2 \alpha^2}{\ln\left(2\delta'\left(\frac{\delta}{2}\right)^{\frac{1-2a}{a-1}}\right)} \qquad\text{ FUCK THIS IS NEGATIVE} \\\implies \sigma &\ge \sqrt{\frac{-a \pi Q (T-t+1)N c^2 \alpha^2}{\ln\left(2\delta'\left(\frac{\delta}{2}\right)^{\frac{1-2a}{a-1}}\right)}} \\\end{align}$$
    Result: useless bound on sigma^2 > something negative.

    General attempt two:
    $$\begin{align}
    \delta' &\ge \frac{\delta}{4 }\left(\frac{\delta}{2}\right)^{\frac{a}{a-1}} \exp\left(\frac{-a \pi Q (T-t+1)N c^2 \alpha^2}{\sigma^2}\right) \\&= \frac{1}{2 }\left(\frac{\delta}{2}\right)^{\frac{2a-1}{a-1}} \exp\left(\frac{-a \pi Q (T-t+1)N c^2 \alpha^2}{\sigma^2}\right) \\\implies \exp\left(\frac{a \pi Q (T-t+1)N c^2 \alpha^2}{\sigma^2}\right) &\ge \frac{1}{2}\frac{1}{\delta'}\left(\frac{\delta}{2}\right)^{\frac{2a-1}{a-1}} \\\implies \frac{a \pi Q (T-t+1)N c^2 \alpha^2}{\sigma^2} &\ge \ln\left(\frac{1}{2}\frac{1}{\delta'}\left(\frac{\delta}{2}\right)^{\frac{2a-1}{a-1}}\right) \\\implies \sigma^2 &\le \frac{a \pi Q (T-t+1)N c^2 \alpha^2}{\ln\left(\frac{1}{2}\frac{1}{\delta'}\left(\frac{\delta}{2}\right)^{\frac{2a-1}{a-1}}\right)} \\\end{align}$$

    Result: This is an upper bound for $\sigma$, not a lower bound. Shit

    Note: in the inequality
    $$\delta' \ge \frac{1}{2}\left(\frac{\delta}{2}\right)^{\frac{2a-1}{a-1}} \exp\left(\frac{-a \pi Q (T-t+1)N c^2 \alpha^2}{\sigma^2}\right)$$
    the RHS gets bigger as $\sigma$ gets bigger. I guess you are "closing the gap" between $\delta'$ and $\delta$. But for the inequality to be valid, you need to start with valid possibilities for the $\delta, \delta'$; the fact that the exponent will never be greater than one limits the values.

    $$ \delta' = \delta = 2^{-128} $$
    $$ \frac{\delta'}{\left(\frac{\delta}{2}\right)^{\frac{2a-1}{a-1}}} $$
    $$ \frac{2^{-128}}{\left(\frac{2^{-128}}{2}\right)^{3}} = (2^{128})^2 $$

    scratch

    Short note on the security game: the adversary knows the resulting plaintext $m$ since it can perform the threshold decryption with control over the corrupted parties and with the honest parties' partial decryptions. What the adversary tries to distinguish is which input $\textbf{m}0 = (m^0_1,\ldots,m^0\ell), \textbf{m}1 = (m^1_1,\ldots,m^1\ell)$ were fed to a homomorphically evaluated circuit $C$, where $m = C(\textbf{m}_0) = C(\textbf{m}_1)$.