Public Order Preserving Cipher Generation Scheme for Distributed Computing

Ordering is a widely used operation in distributed settings. However certain distributed settings like an on-line auction, place unique requirements on the protocol design. Firstly, all entities participate in the ordering with a communication channel(s) only with a coordinator(s), completely oblivious to other participants. This lack of intra-party communication channels makes traditional secure multi-party computations unsuitable for this scenario. Secondly, the security and functionality of the protocol should not depend on a single piece of secret information such as a secret symmetric key, ( as in the case of order-preserving encryption, OPE ). It is so because now every participating entity has to be communicated the secret key in order for them to encrypt their private data. However this means that even if just one of the entities is corrupt, the security of all the honest entities is compromised. These restrictions render both SMPC and OPE ill-suited for the above distributed setting. In this paper we propose a public order-preserving cipher generation scheme (POPC) that addresses the aforementioned challenges. POPC encodes a transform of the plaintext using a public order-preserving probabilistic encoding and generates the cipher in a two round interactive protocol. In POPC neither the correctness nor the security of the scheme depends on the possession of a single secret key. Moreover POPC needs no intra-party communication for its execution. We show POPC achieves the ideal security guarantee for any total order-preserving scheme, which is to reveal no information about the plaintexts beside the order, with a ciphertext space that is polynomial in size of the plaintext.