3
$\begingroup$

I'm reading Rivest's How To Leak A Secret and am on the part where they describe their signature scheme ("Generating a ring signature").

Why is computing $C_{k, v}(y_1, ..., y_r) = v$ easy? The computation seems to be "linear" or single-threaded, i.e. of the form $E_k(y_r \oplus E_k(y_{r-1} \oplus E_k(...E_k(y_1 \oplus v))))$. So let's say $r_i=s$ -- we require the value of $y_i$ to proceed with the computation (i.e. we can't continue to encrypt if we don't know its value), and so wouldn't we just be stuck trying all values of $y_i$ until we hit one that results in $v$ when the computation finishes?

Wikipedia also says that $C_{k, v}$ is trivially invertible given $r - 1$ parameters. I'm blanking out - why is this the case?

I did look at this answer but I didn't understand the line

Start again at 12 o'clock and calculate going counter-clockwise until you arrive at 6 o'clock.

How can you "go counter-clockwise" when all the computations counter-clockwise have inputs dependent on all previous computation? All of the XORs have the previous computation as input.


Sorry if I've made any gaffs, this is my first *Exchange question.

$\endgroup$
  • $\begingroup$ Does reading this question make it understandable? $\endgroup$ – Ruben De Smet Aug 10 '18 at 8:11
  • 1
    $\begingroup$ I think there may be a bug in that OP @Ruben. For some pre-computed random value $v'$, the full formation of $v$ is: $$v = H(... \oplus H(y_s \oplus H(y_{s - 1} ...)))$$ $$ = H(... \oplus H(v'))$$ Following: $$v' = y_s \oplus H(y_{s - 1} ...)$$ $$h = H(y_{s-1} ...)$$ $$v' = y_s \oplus h$$ $$y_s = v' \oplus h$$ which works. But OP is defines $h = H(y_s ...)$ - not $H(y_{s-1}...)$. So their full computation looks like: $$v = H(... \oplus H(y_s \oplus H(y_{s} \oplus H(y_{s -1} ...))))$$ which doesn't match the algorithm RST describes (ring backtracks on $y_s$). $\endgroup$ – tusing Aug 10 '18 at 17:26
  • $\begingroup$ That's an amazing attention to detail there, have a vote. I'll edit the question to read $\mathcal{H}(y_{s-1})$. Could you confirm that I made the right edit? It's a real index madness. $\endgroup$ – Ruben De Smet Aug 11 '18 at 9:10
1
$\begingroup$

I think I might have a potential solution, anyone care to confirm this? Let's take an example with 5 public keys (including ours). Let's assume our $s = 3$.

Let's borrow from that previous Stack Overflow post. Let's define a left var as

$$l = E(E(E(v \oplus y_1) \oplus y_2) \oplus y_3 )$$

and we know that

$$ z = r = E(E(l \oplus y_4) \oplus y_5))$$

Now let's start decrypting $z$:

$$D(z) = E(l \oplus y_4) \oplus y_5$$ $$D(z) \oplus y_5 = E(l \oplus y_4)$$ $$D(D(z) \oplus y_5) = l \oplus y_4$$ $$D(D(z) \oplus y_5) \oplus y_4 = l$$

We've solved for $l$! Solving for $y_s = y_3$ is easy now:

$$l = E(E(E(v \oplus y_1) \oplus y_2) \oplus y_3 )$$

$$D(l) = E(E(v \oplus y_1) \oplus y_2) \oplus y_3$$

$$D(l) \oplus E(E(v \oplus y_1) \oplus y_2) = y_3$$

And then we just do $g^{-1}(y_3)=x_3$, giving us our full signature.

$\endgroup$
  • $\begingroup$ yes, you're right $\endgroup$ – Mikhail Koipish Dec 8 '18 at 13:22
1
$\begingroup$

You can "go counter-clockwise" because XOR and symmetric encryption E are both invertible functions.

Specifically, you have an equation $C_{k,v}(y_1, ..., y_r) = v$. You know only $s-th$ private key, right? so you can invert only $y_s$ (find $x_s$ so that $g_s(x_s) = y_s; here $g_i(x) means encryption of $x$ with $i$-th public key). So, by the algorithm, you choose just random $x_i$ for all $i \neq s$, and set $y_i = g_i(x_i)$. But it's not for $y_s$, which you will find from the equestion: $$C_{k,v}(y_1, ..., y_r) = v.$$ Worth to note, that in this equasion you know all variables (all $y_i$, $v$, $k$) except $y_s$. How you can solve it? You understand that it's simple in a forward direction to evaluate the function $C_{k,v}(y_1, ..., y_r)$, unless you comes to a position $s$, where you have:

$$ y_s \oplus E(y_{s-1} \oplus ...) = y_s \oplus V_1, $$ where $V_1$ is some easy calculated value.

Then, to find which value should the last expression equal, you need to evaluate that our equation ($C_{k,v}(y_1, ..., y_r) = v$) "from another end", or "counter clockwise". We have: $$E(y_r \oplus X_r) = v,$$ where $X_r$ stands for $E(y_{r-1} \oplus E(y_{r-2}...))$. Could we find $X_r$? Sure, because XOR is invertible, and encryption $E$ is invertible too: $$ X_r = E^{-1}(v) \oplus y_r. $$ Then, having $X_r$, you could solve the next equation $E(y_{r-1} \oplus X_{r-1}) = X_r$ in the same way. We repeat this "inverting of $C_{k,v}$" until we come to a position $s$. Now, combining results of "clockwise" and "counter-clockwise" evaluations, we have a fixed equation: $$ E(y_s \oplus V_1) = X_s. $$ Not worth to say that it's easy to solve. When you find $y_s$, you will find $x_s$ by reverting $g_s$, thanks for you having the secret key.

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