SeaCQ: Secure and Efficient Authenticated Conjunctive Query in Hybrid-Storage Blockchains

Data has become a critical economic asset in recent years. To enable secure and reliable access to data assets, the combination of symmetric searchable encryption (SSE) and Hybrid-storage blockchains (HSB) offers a promising solution by storing the authenticated data structure (ADS) on-chain and encrypted data off-chain, thus enabling efficient and authenticated encrypted queries. However, existing encrypted query schemes in HSB either lack support for conjunctive queries, a commonly used and important query pattern in databases, or exhibit low query efficiency in conjunctive queries. vsChain was the first scheme to support secure and authenticated conjunctive queries in HSB but had drawbacks in terms of high query and authentication costs. To overcome these limitations, we introduce SeaCQ, a novel scheme for secure and efficient authenticated conjunctive queries. SeaCQ employs a meticulously designed two-stage authenticated query process to achieve optimal query efficiency. It also incorporates a customized double-layer authentication mechanism to ensure the correctness and completeness of query results efficiently while providing error localization. Additionally, we present an extension of SeaCQ, SeaCQ*, which is a gas-efficient version that utilizes a constant-size on-chain ADS. Our security analysis and experimental results validate the security and efficiency of the proposed schemes.