is OPE able to produce different cyphertext for same plaintext?

Given a plaintext p, is OPE (Boldyreva et al.) able to produce n different cyphertext c1...cn for the n occurrences of p? If not, there exists an order-preserving encryption scheme able to do that?

• No, but you can make an ore scheme that is not deterministic. Jan 10 '17 at 22:25

Boldyreva et al.'s scheme is not randomized. However, there is a folklore way to "randomize" it by choosing randomly from the range gap in the last recursive step of the algorithm. It's not clear what security improvement this buys you, though, since it only really randomizes the last few bits of the ciphertext.

There are schemes meeting a randomized version of Boldyreva et al.'s IND-OCPA definition (q.v. Kerschbaum, CCS'15) but they require large client storage.

The definition of OPE used in Boldyreva's work (section 3.1) is basically

$$\forall m_0, m_1 \in \mathcal{M}, m_0 > m_1 \Leftrightarrow E(m_0) > E(m_1)$$

and any scheme satisfying this definition is deterministic.

To understand it, consider that $m_0$ and $m_1$ are equal messages. Then, $E(m_0) \not > E(m_1)$, otherwise we would have $m_0 > m_1$. Also, $E(m_1) \not > E(m_0)$, otherwise we would have $m_1 > m_0$. Therefore, $E(m_0) = E(m_1)$.

That said, the answer to your second question is "no, there is no OPE scheme able to do that, unless you consider another definition of OPE".

Maybe you would be better using Order-revealing encryption schemes instead.