4
$\begingroup$

Nowadays the group key agreements are based upon tree-based ones such as Asynchronous Ratcheting tree. Especially the latter one is constructed upon left-balanced tree.

So I keep wondering what benefits has a left-balanced tree from any other binary tree structure to this application?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

In the asynchronous ratchet tree construction, intermediate group keys are constructed at each leaf of the tree. It's important that all parties agree on the exact structure of the tree so that they will all derive the same keys. An array is the canonical representation of an ordered list of items, and that array can be viewed as a binary tree. An array of length $2^n$ corresponds to a complete binary tree, while an array of any other length corresponds to a left-balanced binary tree.

You might find the Messaging Layer Security IETF working group of interest, as I believe at least one of the ART paper's authors is involved in the specification efforts. The current MLS protocol Internet-Draft restates the ART protocol from a more concrete engineering perspective, so it's very helpful for understanding how everything fits together.

Improve this answer
$\endgroup$
2
  • $\begingroup$ So it does not have to me nesessarily a left balanced minary tree, as long as the tree is the same for all nodes, right? $\endgroup$
    – Dimitrios Desyllas
    Commented Nov 11, 2018 at 10:10
  • 1
    $\begingroup$ Correct. In this case, viewing the ordered list of participants as a left-balanced binary tree is simply the most natural method for determining the order in which to pair the parties up with each other for deriving the intermediate keys. $\endgroup$
    – kiwidrew
    Commented Nov 11, 2018 at 10:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.