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.

  • Does reading this question make it understandable? – Ruben De Smet Aug 10 at 8:11
  • It does, thank you! – tusing Aug 10 at 17:05
  • 1
    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$). – tusing Aug 10 at 17:26
  • 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. – Ruben De Smet Aug 11 at 9:10
  • Thanks, that looks good! – tusing Aug 12 at 12:32

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.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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