1
$\begingroup$

I'm reading the paper "How to Leak a Secret" (Rivest, Shamir, Tauman; 2001).

On page 8/14, in chapter 3.4, the authors present the following "combining function":

$$C_{k,v}(y_1, y_2,\ldots,y_r) = E_k(y_r \oplus E_k(y_{r−1} \oplus E_k(y_{r−2} \oplus E_k(\ldots \oplus E_k(y_1 \oplus v)\ldots)))) .$$

Is there any explanation for why this function satisfies the second one of the three properties listed on the previous page:

  1. Efficiently solvable for any single input: For each $s, 1 \leq s \leq r$, given a $b$-bit value $z$ and values for all inputs $y_i$ except $y_s$, it is possible to efficiently find a $b$-bit value for $y_s$ such that $C_{k,v}(y_1, y_2,\ldots,y_r) = z$.

A concrete example of how to solve it would be ideal.

$\endgroup$
1
$\begingroup$

From the paper, $E$ is a cipher, i.e., $E_k$ is a permutation. That is, given a secret key $k$, one can compute both the encryption $y=E_k(x)$ (for any $x$) and the decryption $x=E^{-1}_k(y)$ (for any $y$). Therefore, if you know $z$ and all but one $y_i$, you can pick a $v$ (which equals $z$ in the context of ring signature) and get the missing $y_s$ by computing the XOR of $s-1$ $E_k$ encryptions starting from "inside" of the $E(E(...))$ expression and $r-s$ $E_k^{-1}$ decryptions starting from "outside". For instance, if $r=3$ and $s=2$, then $y_2=E_k(y_1\oplus v)\oplus E^{-1}_k(E^{-1}_k(z)\oplus y_3)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.