Bitcoin Forum

I read the paper on threshold signatures and I thought it would be a fun project -- and immense challenge, since I'm not an expert programmer or cryptographer! -- to try to write a Python module to implement it.

However, one aspect required is deriving shares of a random number (the K value, and also the initial private key) without ever having or revealing the fully constructed value.  They mention this is possible but don't show the protocol for it.

Instead, they reference the paper "A robust threshold elliptic curve digital signature providing a new verifiable secret sharing scheme" by the authors M.H. Ibrahim, I. Ali, I. Ibrahim, and A. El-sawi.  This paper supposedly includes the protocol for JRSS

I cannot find a copy of that paper online, and I was hoping somebody else might be able to find it, or already have it, or simply know the protocol for generating shares of a random value without anybody knowing the random value (aka JRSS).

Here is the link (http://www.researchgate.net/profile/Ihab_Ali/publication/4205262_A_robust_threshold_elliptic_curve_digital_signature_providing_a_new_verifiable_secret_sharing_scheme/links/02e7e538f15726323a000000.pdf) to the paper (via google scholars)

Excellent, thank you!  I consider myself pretty decent with my google-fu but I could not get it.  I will have to learn to navigate google scholar.  Thank you!!

No problem. You're welcome. Google Scholar is very handy for research papers, especially if like me, you aren't an academic and can't access specialized libraries.

I could be misunderstanding it but I don't think you can actually use the JRSS method for a t-of-n threshold scheme as described in their paper. I'm not sure what dealer-less method you can use. I've asked a question on their blog so maybe they'll clarify.

EDIT I've looked a it a bit more and I think I probably was mis-understanding it

The JRSS isn't for the signature itself, it's for deriving dealer-less shares of a random k value among the t-of-n participants without revealing k.  (And can also be used to create shares of a new random private key without a dealer and hence without anybody ever knowing the private key.)

Yes, I understand this.
I've looked a bit more and I'm still not clear on how they are constructing the t of n threshold scheme.

in their scheme the private key must be multiplicatively shared and they mention the secret sharing scheme used by MacKenzie and Reiter. Have a look at Appendix A here https://www.cs.unc.edu/~reiter/papers/2004/IJIS.pdf
That’s just for the two party case!

 As far as I understand the JRSS protocol doesn’t provide multiplicative sharing and isn’t suitable in this case.

 Their scheme works for t of t signers and then is extended to t of n signers.
 With the t of t case all of the signers hold a share of the secret that can be multiplied together to give the entire secret and they must all participate in the signing process.

 To extend this to a t of n case they must make sure that each and all of the possible subsets of t signers hold the same multiplicative secret. I can see how this could possibly be done with a dealer but I can’t understand how it is done without a dealer.

 Of course this could just be due to my lack of understanding but I reserve the right to keep asking stupid questions in order to try and improve my understanding. :)

I don't see it either, except by repeating the process for each of the the m choose n satisfactions; which you can't do for a single secret without a dealer. Thats why I was asking in the other thread where this was implemented when someone said it was.

 Glad to see you detected there might be a problem too, I had a bit of self doubt after I first posted a comment and blog question (hence the edit) but then the more I look at it the more I am convinced that their scheme does not extend to the t-of-n case in the way that they described.
 I don't think it will work with or without a dealer for t-of-n. The methods I imagined might be used with a dealer scheme seem to have security problems.

 I'll see if I get a response to my last blog question that will provide any clarification.