Efficient and Unbounded Public-Key Encryption With Keyword Search Based on Arithmetic Span Programs in Cloud Storage

Public-key Encryption with Keyword Search (PEKS) enables users to search encrypted data stored on an untrusted server without revealing any sensitive information. However, existing PEKS schemes are typically inefficient and lack the flexibility to support complex search policies. To address this, a novel PEKS scheme based on Arithmetic Span Programs (PEKS-ASP) is proposed in this paper. This is the first scheme to enable flexible and efficient search policies by using directed acyclic graphs. This approach enhances the efficiency of complex search queries that implement AND, OR, and NOT gates, enabling a more efficient representation of complicated search policies without redundancy in keyword usage. And our proposed PEKS-ASP scheme guarantees constant-size public parameters regardless of the number of keywords. Additionally, the proposed scheme achieves adaptive security under the matrix decisional Diffie-Hellman (MDDH) assumption, employing dual system encryption techniques. Both theoretical analysis and experimental results demonstrate that PEKS-ASP significantly improves efficiency and practicality, making it well-suited for practical applications in various cloud environments.