ABSTRACT In order‐preserving encryption, it was discovered that utilising a hypergeometric probability distribution exposed information about half of the plaintext bits and their respective distances. To address this vulnerability, mutable order‐preserving encoding was introduced as a solution, but it still suffered from revealing the plaintext distribution and exhibiting high correlation. In an effort to overcome these limitations, Lee and Jho proposed a multi‐tree approach that utilises the binary tree invariant and its inverse, resulting in increased complexity for client operations. In this paper, we propose a novel multi‐tree approach to mutable order‐preserving encoding that, by introducing a secret offset at the client side, not only simplifies the server‐side structure but also reduces overall system complexity. To validate the effectiveness of our approach, we conducted comprehensive experiments using the TPC‐C benchmark dataset, evaluating encoding time and query performance across varying data scales. The results demonstrate that our scheme achieves 36% higher encoding efficiency compared to existing multi‐tree methods.
Bang et al. (Wed,) studied this question.