Tree-Based Ring-LWE Group Key Exchanges with Logarithmic Complexity

This is a post-peer-review, pre-copyedit version of an article published in Information and Communications Security. The final authenticated version is available online at: https://doi.org/10.1007/978-3-030-61078-4_6.
22nd International Conference, ICICS 2020 [Copenhagen, Denmark, August 2020]
We present the first constant-round, multicast, tree-based Ring-LWE group key exchange protocol with logarithmic communication and memory complexity. Our protocol achieves post-quantum security through a reduction to a Diffie-Hellman-like decisional analogue to the decisional Ring-LWE problem. We also present a sequential, multicast, tree-based Ring-LWE group key exchange protocol with constant communication and memory complexity but a logarithmic number of rounds.