Binary Tree Encryption with Constant-Size Public Key in the Standard Model

Binary tree encryption is an intriguing primitive that enables many practical applications to achieve an increasing important security feature, forward security. However, the public key size of existing constructions grows linearly with the depth of the underlying binary tree in the standard model. To support more secret keys associated with nodes, it is often expected that the tree has a sufficiently large depth. This places a burden on employing it implicitly or explicitly in real world. In this work, we show how to compress linear-size public key down to constant-size public key and give our construction featuring constant-size public key in the standard model. We prove that our construction achieves an improved security, adaptive security, under the matrix decision Diffie-Hellman assumption, which is a generalization of standard $k$-Lin assumption. Moreover, our key-generation, key-derivation and encryption algorithms have lower time complexity than that of the prior construction, leading to further efficiency improvements. To illustrate these improvements in practice, we give an implementation of our construction and the prior one and then evaluate the performance in the tree depth.