[cryptography] Fwd: The Wandering Music Band
It has been a while, but I think I know now about an idea to solve this
problem.
I really appreciate all the help I got from your responses.
I wrote a document that explains it here:
https://www.newtolife.net/the-trusted-supernode-and-distributed-banking.html
Abstract:
The Trusted Supernode is an abstract idea for a distributed secure and
efficient banking system. This system allows payment operations that
disturb only small amount of participants. It overcomes adversarial attacks
by applying a useful proof of work, combined with node mixing.
The Trusted Supernode bank system relies at its core on a special form of
trusted entity called the supernode. In addition to its ability to manage
payments, the supernode should allow to securely exchange computation and
storage services for money.
real.
-- Forwarded message --
From: realcr <rea...@gmail.com>
Date: Wed, Jan 7, 2015 at 5:40 PM
Subject: The Wandering Music Band
To: cryptography@randombit.net
Hi,
I am looking for some crypto primitive to solve a problem I have.
Assume that I meet a group of people. call it S. I get to talk to them a
bit, and
then they are gone.
This group of people walk together in the world. Sometimes they add a
person to
their group, and sometimes they remove one person. (You can assume it's a
music
band, then it all makes sense). Generally, though, you may assume that they
have
at least k people in the group at all times.
Assume that I meet the resulting group at some time in the future, after
many
members were added or removed. How can the new group S' prove to me that
they
are the descendants of the original group S?
I include here some of my thoughts about this.
1. Naive Solution: Remembering lots of signatures.
Every person in the world will have a key pair (of some asymmetric crypto)
to
represent his identity. When I first meet the group S, I collect all their
public keys and keep them.
Whenever a new member x is added to the group S, all the current members of
S
sign over the new list: S U {x}. Whenever a member x is removed from the
group
S, all the current members of S sign over the new list S \ {x}. The group
members always have to carry with them all the signatures since the
beginning of
time.
When I meet the group at some point in the future, I can just ask them to
prove
their current public keys, and also to show me all the signatures since the
beginning.
My issue with this solution is that the group has to remember more and more
signatures as time goes by. I wonder if there is a more efficient way.
2. Using "Transitive Signatures"
I have seen two articles about a concept called Transitive Signatures.
Shortly: Given a signature of x over y, and of y over z, any participant
will be
able to generate a signature where x signs over z.
http://people.csail.mit.edu/rivest/MicaliRivest-TransitiveSignatureSchemes.pdf
https://eprint.iacr.org/2004/215.pdf
I didn't manage to apply this method to my problem though.
I will appreciate any idea or hint about how to solve this.
Regards,
real.
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] The Wandering Music Band
You still don't get any meaningful security if old band members are assumed to be untrusted and you don't use a public checkpointing mechanism. Transfer of the title of being the real group must be a one-time only thing for each version of the group, and must be impossible to backtrack from. Bitcoin enforces this by design. If you are worried about Synchronization issues within the band itself: I don't need Bitcoin to solve it. The Band is small, and it has a majority of correct members. Therefore I can use some secure multiparty computation to take decisions within the band, and also remove and add members securely. I think you overestimate the impact of using Bitcoin. My problem was that the naive solution makes every band keep a linear amount of signatures with respect to time, which is too much. As a solution you proposed Bitcoin, where all the network participants will remember everything from the beginning of time. That's the opposite of what I'm trying to do. I made sure that every operation in the network result in no more than O(polylog(n)) operations. I am definitely not going to use Bitcoin on it, where every transaction costs O(n) network complexity. (Not mentioning the proof of work calculations). It doesn't make sense to me. It isn't all our nothing as not all members need to be full nodes, in fact none of them have to be. What if everyone did that? Bitcoin will stop working properly. (Or it will become central, and that is what Bitcoin tries to avoid from the first place.) The Bitcoin developers is constantly working on scalability, and the network is meant to one day be able to handle thousands of transactions per second I It might be true, but it is still O(n) network complexity per transaction, and lots of proof of work calculations. The naive solution proposed in my first message will still outperform the most efficient Bitcoin based solution. (Because it is O(log(n)) network complexity). On Thu, Jan 8, 2015 at 1:12 PM, Natanael natanae...@gmail.com wrote: Den 8 jan 2015 11:54 skrev realcr rea...@gmail.com: Hey, thanks again for the reply. The only notable difference is that in my version you are checkpointing the change in th blockchain. You still have the very same form of signing, but you sign a slightly different message (transfer of a colored coin, one Satoshi worth of Bitcoin, to a new address) instead of group members XYZ are now the official group instead of ABC. I disagree with you, or maybe I have misunderstood you idea. I think that Bitcoin is not related here. Bitcoin is all or nothing. If I want to use it, all the participants of the network have to be part of it. That means that all the participants of the network have to compute hashes all the time. In addition, every Bitcoin transaction involves all the participants of the network. I think you overestimate the impact of using Bitcoin. It isn't all our nothing as not all members need to be full nodes, in fact none of them have to be. While it is true that all full nodes must store all the transactions, and that it gets forwarded in the network among most online nodes as it gets published, only the latest one would need to be kept in their index of the unspent outputs (UTXO set) from the blockchain. The Bitcoin developers is constantly working on scalability, and the network is meant to one day be able to handle thousands of transactions per second (this is years off, though). The blockchain can easily be stored on MicroSD cards! Verifying the headers alone for decades worth of hashes takes at most minutes on smartphones. And that's a one-time job per header hash, per device. Each new header takes much less than a second to process. Publishing and verifying the colored coin transactions is trivial too. Secrecy is not required. I meant to say that the band has the responsibility of keeping the signatures and show them on demand. You still don't get any meaningful security if old band members are assumed to be untrusted and you don't use a public checkpointing mechanism. Transfer of the title of being the real group must be a one-time only thing for each version of the group, and must be impossible to backtrack from. Bitcoin enforces this by design. Other standard public checkpointing mechanisms don't verify if there's conflicting messages or not, so then ALL messages that has been checkpointed must be stored. There are cryptocurrencies with similar functionality (doublespend protection, conflicting assignments not allowed) and other trust models (no proof-of-work for chain selection). As an example, Ripple is federated, a set of trusted nodes agree on the order of transactions. This removes most of your performance related issues. But I don't trust it if security is important, it seems too ad-hoc. Then there's proof-of-stake which is very problematic for a million different reasons (no guarantee there will be concensus
Re: [cryptography] The Wandering Music Band
Hey, thanks again for the reply. The only notable difference is that in my version you are checkpointing the change in th blockchain. You still have the very same form of signing, but you sign a slightly different message (transfer of a colored coin, one Satoshi worth of Bitcoin, to a new address) instead of group members XYZ are now the official group instead of ABC. I disagree with you, or maybe I have misunderstood you idea. I think that Bitcoin is not related here. Bitcoin is all or nothing. If I want to use it, all the participants of the network have to be part of it. That means that all the participants of the network have to compute hashes all the time. In addition, every Bitcoin transaction involves all the participants of the network. Assume that there are n participants in the network, and k band members. using Bitcoin, every change in the band involves O(n) network complexity, O(n) memory usage to the network (Every participant in the network has to remember O(1) more data). I can't really talk about computational complexity here, as the Bitcoin algorithm never really terminates. We can just say that it costs a lot of computational power. In the proposed naive solution, every time a change happens, the band S has to remember a few more signatures. (About O(k)). So every change requires O(poly(k)) network complexity (Some protocol between the band members), O(poly(k)) memory usage to the network (Each of the band members should remember all the signatures), and O(poly(k)) computational power (For generating the signatures, and protocol between the band members). In my case k is pretty small (You may assume k = O(logn)). I think that the naive solution outperforms Bitcoin in every way in this case. Correct me if I'm wrong here. The band S doesn't publish the signatures. They only show the signatures whenever I ask them. Is secrecy a requirement? If so, take a look at Zerocoin/Zerocash (not yet released, though). It uses Zero-knowledge proofs for secure mixing of coins to preserve privacy. You could also chose to have the group periodically rekey and transfer the colored coin even if there's no change, just to hide when the change actually happens. Secrecy is not required. I meant to say that the band has the responsibility of keeping the signatures and show them on demand. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] The Wandering Music Band
Now the original members b,c,d create an alternative history:
I assume that the original band has a majority of correct members.
Therefore at least two out of {b,c,d} are correct, and they will not create
alternate history.
The original formulation is included:
Assume that the world contains correct people (People you can trust) and
corrupt people (Those you can't trust).
Also assume that the world has a majority of correct people (If it helps,
you may assume 3/4 correct people).
I am given a set S which contains k members (The music band). Assume that
a majority of this set is correct.
From time to time:
- A random person (From the world) joins the band. (With good probability
this new member is correct).
- A random person (From the band) leaves the band.
On Thu, Jan 8, 2015 at 2:38 PM, Michael Rogers mich...@briarproject.org
wrote:
-BEGIN PGP SIGNED MESSAGE-
Hash: SHA256
On 08/01/15 07:03, realcr wrote:
I think the naive solution I proposed in my first message is more
efficient than using Bitcoin, because it does not involve proof of
work or flooding stuff.
Shortly: Whenever a person is added to the band, all the members
sign on the new list. Whenever a member leaves the band, all the
members sign on the new list. The band members keep the signatures
forever, so they can always prove they where formed originally from
the original band S.
I think there might be a problem if a majority of members leave the
band one by one and then construct an alternative history:
band_0 = {a,b,c,d} // original lineup
band_1 = {a,b,c}// d leaves
band_2 = {a,b,c,e} // e joins
band_3 = {a,b,e}// c leaves
band_4 = {a,b,e,f} // f joins
band_5 = {a,e,f}// b leaves
band_6 = {a,e,f,g} // g joins
Now the original members b,c,d create an alternative history:
band_0 = {a,b,c,d} // original lineup
band_1' = {b,c,d} // a leaves
band_2' = {b,c,d,h} // h joins
Which is the true lineup, band_6 or band_2'?
A verifier who's seen both histories can tell that b and c have signed
inconsistent statements. But how can a verifier know whether they've
seen all histories that might exist?
Cheers,
Michael
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.12 (GNU/Linux)
iQEcBAEBCAAGBQJUrnpiAAoJEBEET9GfxSfMEqIIAK8ZHAE4XzAmVYg3A7z2kWJA
mUHNoNMHf7198NLH9ddMrLOmKbGYWRko/6VY6dStx8Na3E0O1nAZVO2vdK9oTlBJ
v6O6mmgAuAnG4oKAn3+KQHhGIxIUmsOn7vHTgF6X6l7JlgEnEhwNQ2GZ5azbyEnb
iSxAjy1cnH4uWV8On8nFrBRfv1BkcizoclX1hBxF9b2v0+psNLbS0/EIFuGkonfx
CYGRC117saH9t//kwEZEAk2b8PeNENb/memS4beBJdQNe0oMaiKV/rxXgf2IwnpX
1AdDopBU84EnICiwuB8lwSqhdlKBO07fJ6Slki/l6Fjie9lUlFU/4+rpSNQnzOE=
=98M3
-END PGP SIGNATURE-
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] The Wandering Music Band
Sorry, I should've read your formulation more carefully. Don't worry about it :) We wrote lots of stuff since the first message, it's hard to trace it back to the original message. @Natanael: I think I understand now that our different opinions are due to different concepts of adversarial model. You are implicitly assuming that NONE of the previous versions of the group will ever have a majority of members that are dishonest and pretend the later reassignments didn't happen. Michael wrote: the same problem exists if any version of the band contains a dishonest majority. My short answer to this: (The long answer follows below) - You have to wait a very long time until there is not a majority of correct nodes in the band. - The network is maintained in such a way that you pay for membership. Therefore the Adversary will not be able to stay long enough. The long Answer: Assume that there is some network of nodes. Some of those nodes are correct, and some of them are corrupt. Correct nodes are honest. They run your code. Corrupt nodes can do anything. (They can collude, etc). All the corrupt nodes are controlled by one Adversary. Also assume that it costs something to be in the network. Something that you pay periodically. (It will take me some time to explain what is that thing, so just assume it's true). In addition, it is given that the Adversary is bounded. More specifically, the Adversary can maintain (1/4)n corrupt nodes for some time. The rest (3/4)n nodes are correct. Let S be the band. It is some set of k nodes, where at least (2/3)k are correct nodes. In every step one of the following happens: - A random node (from the set S) leaves the set. - A random node (from the world) joins the set. The set is always of size at least k. k ~ polylog(n). You can think of k as log(n)^2, for example. I conjecture that the amount of correct nodes in the band will stay above (2/3)k for many steps. To make this conjecture more rigorous, I include here a very approximate calculation. Assume that in every step we get a random set, chosen uniformly from all the nodes in the world. If we assume that the world is really big, a binomial distribution should be a good approximation. We should calculate the probability of having less than (2/3)k correct nodes in a random set of size k. That would be about p_f := Pr[ B(k,3/4) = (2/3)k ]. (p_f stands for probability for failure). By Chernoff's inequality, we get that p_f = Pr[ B(k,3/4) = (2/3)k ] = exp(-C * (1/k) * ((3/4)k - (2/3)k)^2) = exp(-C * k) If we pick k = log(n)^2, we get p = exp(-C * log(n)^2) = 1 / ( n^( log(n)*C ) ). If I have not made any fatal mistake here (I might have, I calculated it just now :) ), then we conclude the following: If the network is of size n=2^30, then one have to wait about (2^30)^30 = 2^900 steps until there is no majority of correct nodes in the band. I consider 2^900 steps to be never happens. Of course this is not the real calculation. The real one involves some Markov chain, and I don't know how to solve it. But I think it does give some idea regarding what I should expect. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] The Wandering Music Band
Hey Natanael, Thanks for your response.
It's the chain of signatures always published in an accessible way so that
the original members can't doublespend and claim to be the task group?
Otherwise the blockchain approach is useful for you.
I think the naive solution I proposed in my first message is more efficient
than using Bitcoin, because it does not involve proof of work or flooding
stuff.
Shortly: Whenever a person is added to the band, all the members sign on
the new list. Whenever a member leaves the band,
all the members sign on the new list. The band members keep the signatures
forever, so they can always prove they where formed originally
from the original band S.
Example:
If the original band, band_0 = {a_0,a_1,a_2,a_3}, and a new member (a_4)
joins, we get a new band {a_1,a_2,a_3,a_4}.
If we denote the new list as band_1 := (a_0, a_1,a_2,a_3,a_4) then we need
the following signatures to prove the change:
sign[a_0](band_1), sign[a_1](band_1), sign[a_2](band_1), sign[a_3](band_1)
If the member a_1 now leaves the band, we denote band_2 =
(a_0,a_2,a_3,a_4), and we need the following signatures to prove the change:
sign[a_0](band_2), sign[a_2](band_2), sign[a_3](band_2), sign[a_4](band_2)
(Note that we might not be able to get a_1's signature, because maybe he
just failed somehow).
So far, after those two changes, we have to carry about 8 signatures.
If someone asks the group to prove that they have a majority of correct
nodes, they can just prove their current
identities, and send the 8 signatures.
(I can probably get away with less than 8 signatures, but the asymptotic
nature of the amount of signatures needed doesn't really change).
The band S doesn't publish the signatures. They only show the signatures
whenever I ask them.
The group setting is also solved as-is thanks to both the multisignature
support (m-of-n for up to 15 people), and thanks to ECDSA threshold group
signatures if you prefer these (I'm assuming they also don't limit you to
15 members).
Using a multisignature scheme I can probably get much shorter signatures,
which is cool.
I will still have to remember the identities of all the signers, and the
set of signatures to be remembered grows linearly with respect to time.
Assuming that I use some kind of Threshold signature scheme, how can I
transfer the secret parts to the next members in the band, so that parts of
the secret don't leak to previous members?
Most of what I read about threshold signatures assumes that some that some
trusted dealer deals the secret parts to the participants.
How can I move the secret parts to the new band without a trusted dealer?
Someone in this thread has mentioned Shamir secret sharing. Considering
this idea,
How can I avoid the possibility that some set of corrupt ex-band members
will gather and combine their secret parts?
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] The Wandering Music Band
Hey, Thank you for all the responses. I figured out that I left some important details out, probably because I thought about it for a long time. I'm sorry about that. I will try to formulate it again: Assume that the world contains correct people (People you can trust) and corrupt people (Those you can't trust). Also assume that the world has a majority of correct people (If it helps, you may assume 3/4 correct people). I am given a set S which contains k members (The music band). Assume that a majority of this set is correct. From time to time: - A random person (From the world) joins the band. (With good probability this new member is correct). - A random person (From the band) leaves the band. ( The band always have at least k people. The full story is that if the band becomes too big, it is splits into two bands. If the band becomes too small, it dies. But you can forget about all this and just assume that the band always have at least k people. ). Note that those steps leave the set with a majority of correct people with high probability. Assume that I met the original band. At some point in the future I meet some group of people (Maybe none of them was in the original band). How can they prove to me that they were formed from the original band by a set of steps as described above? And the real question I care about: How can they prove to me that a majority of them is correct? It's pretty important that the amount of data the band keeps should be no more than logarithmic in the amount of steps that have occurred. I think that linear is just too much data to store. @Jonathan: I think the threat model here is the Byzantine model. I hope that it answers your question. @Dave: Your point of view is interesting :) @Alexandre: I still haven't read the article. I will check it out. thanks. @Andrew: The trusted majority is about what I meant. I didn't know about the ship of theseus. cool :) real http://www.freedomlayer.org On Wed, Jan 7, 2015 at 6:48 PM, andrew cooke and...@acooke.org wrote: On Thu, Jan 08, 2015 at 03:33:24AM +1100, Dave Horsfall wrote: On Wed, 7 Jan 2015, realcr wrote: I am looking for some crypto primitive to solve a problem I have. [...] I guess, if it is really a band application as opposed to something more abstract, it boils down to what you mean by descendants. At least one founding member left? Are the offspring of same OK? Some musos can be really purist about this. i'd suggest that you can assume that there is always a majority of members who can be trusted. so you need something that can follow a trusted majority, even if they include no-one who is original. fwiw, when searching for previous work, this kind of problem is often referred to as the ship of theseus (preserving identity of the whole when all parts are replaced) - http://en.wikipedia.org/wiki/Ship_of_Theseus andrew ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
[cryptography] The Wandering Music Band
Hi,
I am looking for some crypto primitive to solve a problem I have.
Assume that I meet a group of people. call it S. I get to talk to them a
bit, and
then they are gone.
This group of people walk together in the world. Sometimes they add a
person to
their group, and sometimes they remove one person. (You can assume it's a
music
band, then it all makes sense). Generally, though, you may assume that they
have
at least k people in the group at all times.
Assume that I meet the resulting group at some time in the future, after
many
members were added or removed. How can the new group S' prove to me that
they
are the descendants of the original group S?
I include here some of my thoughts about this.
1. Naive Solution: Remembering lots of signatures.
Every person in the world will have a key pair (of some asymmetric crypto)
to
represent his identity. When I first meet the group S, I collect all their
public keys and keep them.
Whenever a new member x is added to the group S, all the current members of
S
sign over the new list: S U {x}. Whenever a member x is removed from the
group
S, all the current members of S sign over the new list S \ {x}. The group
members always have to carry with them all the signatures since the
beginning of
time.
When I meet the group at some point in the future, I can just ask them to
prove
their current public keys, and also to show me all the signatures since the
beginning.
My issue with this solution is that the group has to remember more and more
signatures as time goes by. I wonder if there is a more efficient way.
2. Using Transitive Signatures
I have seen two articles about a concept called Transitive Signatures.
Shortly: Given a signature of x over y, and of y over z, any participant
will be
able to generate a signature where x signs over z.
http://people.csail.mit.edu/rivest/MicaliRivest-TransitiveSignatureSchemes.pdf
https://eprint.iacr.org/2004/215.pdf
I didn't manage to apply this method to my problem though.
I will appreciate any idea or hint about how to solve this.
Regards,
real.
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
[cryptography] Practical Threshold Signatures
Hi, I recently read the article Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme, written by Alexandra Boldyreva. Link can be found here: https://www.iacr.org/archive/pkc2003/25670031/25670031.pdf. (Note: If you are going to read this, my question refers to the first parts of the article - until part 3 and including it.) Does anyone here have any past experience with working implementations of Threshold Signature mechanisms, or can point me somehow on the path to implementing this the right way? I will elaborate a bit about what I already know: About Threshold Signatures: --- There are n parties, and we want that k out of those n parties will have the ability to sign in the name of the whole group of n parties. The naive solution could be to collect enough regular signatures from k participants, and the concatenated result could serve us as a crude Threshold Signature. A more advanced solution might be able to produce a final signature which is of smaller size, or even of the same size of a regular signature. Very short summary of the first part of Alexandra's article: - There are some groups where the Gap Diffie Hellman property is assumed (It is easy to solve the Decisional Diffie Hellman problem, but hard to solve the Computational Diffie Hellman problem). - Given that g is some (known to all parties) element of the group G, in order to generate an identity to sign with, a party randomizes some x, and defines y = g^x to be the public key. - In order to sign a message m, the party calculates (H(m))^x, where H is a hash function into G. - A secret x could be shared (For example using Shamir secret sharing), and every party gets a private share of the secret. Thus party P_i for example gets its share x_i of the secret. - Because of the very simple structure of the signature, it is possible to combine signature shares of the form (H(m))^x_i together using lagrange interpolation to get the signature over the message m, which will result in (H(m))^x. My question about this scheme is as follows: Do you guys know any good GDH (Gap diffie hellman) groups that we can actually count on? I didn't manage to find anything myself. In addition, I notice that the signature proposed does not involve any randomness in it. (It looks like ElGamal without the extra part), what do you think about it? Modified ElGamal Alternative: - If you managed to read so far, you must be interested enough to hear about another alternative. I found the article Group-oriented (t,n) threshold signature scheme and digital multisignature by L.Harn. This article proposes some kind of modified ElGamal algorithm to be able to do a similar trick, in order to acheive threshold signatures. My problem here is that I'm not sure whether this modification is something that I can actually trust, and what is the right way to generate keys for this modified algorithm. Victor Shoup's RSA Threshold Signatures: I read a bit about Victor Shoup's idea for Threshold signatures in the article Practical Threshold Signatures. I really liked it, though I can't put that into use because it requires a trusted party to set up the secrets before the protocols begin. The other two options I discussed above have the following very attractive property: The secret is just a random number, not a pair of prime numbers or any special number theoretical object. Thus it is far easier to share the secrets between the parties in the protocol in a distributed manner. I am aware of some attempts in other articles to remove the trusted party out of the pre-setting of secrets in Victor Shoup's Threshold Signature, however it seems to be very communication Expensive, much more than the actual protocol I want to run later. Thus I prefer not the use this schema, and I really want to make one of the former discussed schemas work. If you happen to know about working code on this subject, or an idea about implementing a nice one, please make sure to drop a message. I would probably like to participate if you are coding something of this type. Regards, real. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Practical Threshold Signatures
Hey. I want to thank everyone for the helpful answers. They were very interesting to read. From what I understand, the group I'm looking for is an elliptic cure with a weil pairing. (Jonathan mentioned bilinear map, I assume that means the same thing?) The C code for the Pairing based cryptography seems to be very useful for this purpose. I have two questions regarding the answers I received: 1. I feel not very smart in the domain of elliptic curves and Weil pairing. Before jumping into the code I want to make sure I understand what I'm doing. Do you have a recommendation of something I should read? I'm not afraid of heavy math, though at the same time I can spend only so much time on this. 2. Can I actually trust the elliptic curve with weil pairing to do its cryptographic job? Maybe better asked: Can I trust it like I trust that it is hard to factor numbers? (Maybe even more?) I really appreciate your time reading this. Thank you for your help, real. On Tue, Nov 12, 2013 at 10:12 PM, James A. Donald jam...@echeque.comwrote: My understanding is that Gap Diffie Helman is the only solution for threshold signatures that is actually workable (no trusted party, normal signatures, looks the same as an individual signature.) I base this on having looked around for workable solutions. Maybe there is one I missed. Everything else I looked at was impractical when closely examined. I am not sure what the scaling is, but is not obviously and intolerably horrid. Signature evaluation is fast - it looks and acts just like a normal signature, and we can tolerate large costs for a large group to generate signature. Next problem, find your Gap Diffie Helman group, which in practice means an elliptic curve that supports the Weil Pairing. For source code in C, see http://crypto.stanford.edu/pbc/ Samuel Neves, on the mailing list cryptography@randombit.net claimed For pairing-friendly curves to achieve the 128-bit security level, it is a good idea to increase the characteristic to prevent FFS-style attacks, and to increase the embedding degree to something higher than 6. Barreto-Naehrig curves are defined over (large) prime fields, have embedding degree 12, and are generally a good choice for the 128-bit level. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
