Timeline for Zero knowledge RSA public key
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 23, 2021 at 18:12 | comment | added | DeLorean88 | @jjj this is exactly what I was looking for. Thanks everyone! | |
| Jul 23, 2021 at 12:21 | vote | accept | DeLorean88 | ||
| Jul 23, 2021 at 6:35 | comment | added | fgrieu♦ | Yes, ring signature works for this. But a critical detail is missing in the Wikipedia article and the answer: the domain for the $r_i$ and $y_i$ must be made the same size even though the $n_i$ are different, in order to prevent leak of information about $j$. This is addressed in the Extending trap-door permutations to a common domain section of the Rivest-Shamir-Tauman paper. | |
| Jul 23, 2021 at 5:59 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Fix a remaning e
|
| Jul 22, 2021 at 20:57 | comment | added | jjj | @fgrieu Ok, I checked and noticed that I did not remember the algorithm correctly. The base Idea is still correct. I added a note to my answer. Thanks for checking. I still think ring signatures are really good for this problem | |
| Jul 22, 2021 at 20:53 | history | edited | jjj | CC BY-SA 4.0 |
added 321 characters in body; edited body
|
| Jul 22, 2021 at 19:27 | comment | added | fgrieu♦ | When the hash is $h$-bit, I'm told there is an attack of cost $\mathcal O(2^{h/(1+\log_2(k))})$, which can get worrying for large $k$. On another front, I find it non-trivial to prevent an adversary from gaining some (little) advantage on guessing $j$, especially when $h$ approaches the width of the smallest $n_i$. | |
| Jul 22, 2021 at 10:12 | history | edited | jjj | CC BY-SA 4.0 |
deleted 17 characters in body
|
| Jul 22, 2021 at 9:38 | comment | added | fgrieu♦ | Yes, masking out enough high order bits (just one if the $n_i$ are the same bit size) makes it possible to avoid any trial and error. Again, how the high order bit(s) of $y_j$ is chosen requires careful consideration. | |
| Jul 22, 2021 at 8:29 | comment | added | jjj | @fgrieu I changed the names von $e$ to $y$, thanks for that. You can just choose by xor-ing all other $y_i$ and $m$ to get $y_j$. There is no need for trial and error when you know the private key of $k_j$. The length problem can easily be fixed by limiting the bits to xor to the number of bits in m and ignore the others | |
| Jul 22, 2021 at 8:18 | history | edited | jjj | CC BY-SA 4.0 |
added 17 characters in body
|
| Jul 22, 2021 at 0:44 | history | edited | jjj | CC BY-SA 4.0 |
added 117 characters in body
|
| Jul 22, 2021 at 0:35 | history | answered | jjj | CC BY-SA 4.0 |