高级检索

    一种基于近似陷门采样的可搜索加密方案

    A Searchable Encryption Scheme Based on Approximate Trapdoor Sampling

    • 摘要: 格上的公钥可搜索加密在确保外包数据的隐私性、机密性和灵活性方面发挥着重要作用,同时能够抵抗量子攻击. 大多数格上的公钥可搜索加密受限于底层原像采样算法,存在高存储开销或低效率的问题. 为了解决上述问题,首先提出了一种优化的公钥可搜索加密方案. 方案使用一种新的近似陷门采样算法提高计算效率,该算法能够输出1个近似的而不是精确的原像. 然后,结合非球面高斯采样技术和理想可扩展输出函数来降低密钥和陷门的存储开销. 进一步地,引入了具有前向安全和后向安全的扩展方案来解决基础方案中的更新和搜索操作泄露. 为了避免新更新的密文与以前的陷门匹配,即前向安全,通过基于格的委托机制来定期更新密钥. 为了防止后续搜索泄露有关已删除文件的信息,即后向安全性,通过结合位图索引和格同态加密方案实现文件的添加和删除. 理论分析和实验结果表明,相较于高效的可搜索加密方案,所提方案在公钥存储开销和陷门存储开销上分别降低了4.6%和50.1%. 同时,该方案在加密、陷门生成以及搜索上的效率分别实现了11.11%,2.5%,26.15%的提升.

       

      Abstract: Public key encryption with keyword search (PEKS) over lattice plays an important role in ensuring the privacy, confidentiality, and flexibility of outsourced data while resisting quantum attacks. However, most existing lattice-based PEKS schemes are limited by the underlying preimage sampling algorithm, which suffers from high storage overhead or low efficiency issues. To address the above problems, an optimized public key encryption with keyword search scheme is first proposed. The scheme utilizes a new approximate trapdoor sampling algorithm to improve the computational efficiency. The algorithm outputs an approximate rather than an exact preimage. Then, a combination of non-spherical Gaussian sampling technique and an ideal extendable-output function is used to reduce key and trapdoor storage. Furthermore, an extended scheme with forward security and backward security is introduced to address the basic scheme’s update and search operation leakage. To avoid newly updated ciphertexts matching previous trapdoors, i.e., forward security, the key is periodically updated through a lattice-based delegation mechanism. To prevent subsequent searches from leaking information about deleted files, i.e., backward security, the addition and deletion of files is achieved by combining the bitmap index and lattice-based homomorphic encryption scheme. Theoretical analysis and experimental results exhibit that, compared with the efficient PEKS scheme, the proposed scheme reduces the public key storage overhead by 4.6% and the trapdoor storage overhead by 50.1%, and improves the efficiency of encryption, trapdoor generation, and search by 11.11%, 2.5%, and 26.15%, respectively.

       

    /

    返回文章
    返回