  Order-revealing encryption is a useful cryptographic primitive that provides
range queries on encrypted data since anyone can compare the order of
plaintexts by running a public comparison algorithm. Most studies on
order-revealing encryption focus only on comparing ciphertexts generated by a
single client, and there is no study on comparing ciphertexts generated by
multiple clients. In this paper, we propose the concept of multi-client
order-revealing encryption that supports comparisons not only on ciphertexts
generated by one client but also on ciphertexts generated by multiple clients.
We also define a simulation-based security model for multi-client
order-revealing encryption. The security model is defined with respect to the
leakage function which quantifies how much information is leaked from the
scheme. Next, we present two specific multi-client order-revealing encryption
schemes with different leakage functions in bilinear maps and prove their
security in the random oracle model. Finally, we give the implementation of the
proposed schemes and suggest methods to improve the performance of ciphertext
comparisons.
