Order-preserving encryption (OPE) is a fundamental cryptographic tool for enabling efficient range queries on encrypted data in outsourced databases. Despite its importance, existing OPE schemes face critical limitations that hinder their practicality. Stateful designs require clients to maintain plaintext-to-ciphertext mappings, imposing significant storage and management overhead. Stateless designs often rely on interactive protocols between the client and server, leading to high communication latency and limited scalability. These limitations make existing schemes unsuitable for real-world applications that demand simplicity, efficiency, and scalability. In this work, we present Homomorphic OPE (HOPE), a new OPE scheme that eliminates client-side storage and avoids additional client-server interaction during query execution. HOPE leverages the additive property of homomorphic encryption to introduce a novel comparison key mechanism, which transforms ciphertext comparison into a randomized difference computation. This mechanism ensures that only the sign of the comparison is preserved while fully masking the underlying plaintext values, enabling secure and efficient range queries without leaking additional information about the data. We provide a formal cryptographic analysis of HOPE, proving its security under the widely accepted IND-OCPA model. Our proofs rigorously demonstrate that the comparison key mechanism reveals no information beyond the order of the plaintexts and ensures resistance to both chosen-plaintext attacks and frequency analysis. To validate the practicality of HOPE, we conduct extensive experiments comparing it with state-of-the-art OPE schemes. The results demonstrate that HOPE achieves competitive query performance while addressing the key limitations of existing designs, making it a scalable and secure solution for outsourced database systems.

翻译：保序加密（OPE）是一种基础密码学工具，用于在外包数据库中对加密数据执行高效的范围查询。尽管其重要性显著，现有OPE方案仍面临阻碍实用性的关键局限：有状态设计需要客户端维护明文到密文的映射，带来显著的存储与管理开销；无状态设计通常依赖客户端与服务器之间的交互协议，导致高通信延迟和有限的可扩展性。这些局限使得现有方案难以满足现实应用对简洁性、效率与可扩展性的需求。本文提出同态保序加密（HOPE），一种新型OPE方案，该方案消除了客户端存储需求，并在查询执行过程中避免了额外的客户端-服务器交互。HOPE利用同态加密的加法性质，引入了一种新颖的比较密钥机制，将密文比较转化为随机化差值计算。该机制确保仅保留比较结果的符号，同时完全掩盖底层明文数值，从而在不泄露数据额外信息的前提下实现安全高效的范围查询。我们对HOPE进行了形式化的密码学分析，证明其在广泛接受的IND-OCPA模型下具有安全性。我们的证明严格表明，比较密钥机制除明文顺序外不泄露任何信息，并能同时抵抗选择明文攻击和频率分析。为验证HOPE的实用性，我们进行了大量实验，将其与前沿OPE方案进行对比。结果表明，HOPE在实现具有竞争力的查询性能的同时，解决了现有设计的关键局限，为外包数据库系统提供了一种可扩展且安全的解决方案。