On 23/01/14 02:26, Ximin Luo wrote: > I haven't looked into this area much myself, but the people I > talked to so far seem to think a group key exchange in the style > of DenAKE would be O(n^2). I'd be interested in hearing more about > what you have.
Well, yes. As you're also discussing below, that raises the question as to how one defines big-O in this case. From a client's or overall perspective. The GDH, that I'm looking at, uses (n - 1) directed messages and one broadcast, therefore having each client process O(n) messages, and send O(1), which overall would lead to O(n^2) messages to process as well, while only having to transport O(n). From my point of view, the expensive part in these schemes is the network latency, so the message transports should be viewed particularly, leading to O(n). Side note: A Tree-based Group Diffie-Hellman (TGDH) would be still more efficient, but also more complicated to implement, so I didn't bother with it, yet. And GDH still seems well suited for the envisioned use case of around and below 10 users that I'm mostly worried about. Another potentially expensive part is generating new (private) secrets, particularly if it is for DSA or RSA. So another factor for consideration is to minimise the number of secrets that need to be generated individually. However, this factor can be mitigated by choosing crypto primitives that put much less load on the system in terms of number of bytes entropy required and the complexity of evaluating those secrets (thus my choice of Curve25519 and Ed25519 for my current considerations, with the additional side benefits of minimising message size). Another question raised for me is towards what extent deniability needs to go. mpOTR can be a complex beast, and with growing group sizes the chance of all participants being "well behaved" decreases (e. g. when publishing private signing keys for the session on termination). I'll have to have a closer look at denAKE again and see how that would compare. After all, denAKE doesn't *just* do the group key agreement, but also authentication of the parties. Anyway, as far as I recall, Goldberg's original mpOTR paper still left the group key agreement process pretty much unanswered, if I recall correctly. > In a pair-based system, the size might be technically O(n^2) but > you can group this into O(n) "broadcasts" if it suits the > primitives of the underlying protocol. In a typical multiparty > conversation, people join at different times anyway, so I think >this is acceptable. That is very true for the client's perspective, however any type of infrastructure will still have to handle O(n^2) messages, and clients have to process O(n^2) incoming messages. Though, this will likely be more efficient than doing them "on the raw" for the infrastructure, and the broadcasts don't have to be handled sequentially. > In my model, you don't need to re-key on join/part, so each join > is a constant number of broadcasts to key-agree with the new joiner > (details to be worked out), and each part/expiry is free. There is > additionally an n-step broadcast "decision making" step, total size > O(n^2); I'm not sure anyone has thought about this yet in the > context of a group-based system. That's the same when using GDH. You've got an IKA (initial key agreement) process to bootstrap your secret group key. With the set of intermediate keys, you can very easily join or disconnect group members with very limited effort (1 point-to-point message + 1 broadcast message to the group). Guy
signature.asc
Description: OpenPGP digital signature
_______________________________________________ OTR-dev mailing list [email protected] http://lists.cypherpunks.ca/mailman/listinfo/otr-dev
