On Tue, 2018-01-09 at 22:44 +0000, Jonathan Millican wrote:
> Regarding merge operations, conflicting updates to a tree shouldn't be > commutative in the general case, but I think there may be > circumstances where limited merges could occur: > > > Take the following tree: > > > DH(DH(A, B), DH(C, D)) > / \ > DH(A, B) DH(C, D) > > / \ / \ > > A B C D > > > If A and B were to send simultaneous updates, ( [A', DH(A', B)] and > [B', DH(A, B')] ), then C and D are unable to merge them at all; as > this would require computing DH(A', B') without access to either > private key. I see. C and D could fold both those root keys into updates, but they could only directly advance one tree until either A or B completes the merge. In principle, C and D could incorporate both the DH(A', B) and DH(A', B) trees in some other way, like adding their points, or placing them as children of a new node. I suppose 3-way DHs arranged in a tree make this problem worse, but one could imagine maintaining a DAG outputs given by distinct hash functions, but only choosing a nicely merging subtree, and 3-way DHs could make you DAG shrink by 2/3 per level. I suspect all such schemes make private scalars live longer though, which sounds problematic. I suspect your optimal merge strategy would be for C and D to build on either the DH(A', B) or DH(A', B) tree, but recognize both by incorporating both root keys, and possibly change their mind later if they see a DH(A'', B') or whatever. In fact, this recognition might even help force a malicious A and B to actually do the merge. I think this strategy is optimal in the sense that A and B must to keep their old private scalar anyways until they merge. In general, it sounds like ART has larger compromise windows than pairwise 2-step DH, axolotl/signal, etc. due to the need for more members to confirm receipt before erasing private scalars. Inherently group chats are less secure though so this sounds appropriate. Jeff
signature.asc
Description: This is a digitally signed message part
_______________________________________________ Messaging mailing list Messaging@moderncrypto.org https://moderncrypto.org/mailman/listinfo/messaging
