自适应安全的支持模式匹配的流加密方案

Adaptive secure stream encryption supporting pattern matching

支持模式匹配的流加密方案为同时实现模式匹配以及用户隐私保护提供了解决思路。一方面,支持模式匹配的流加密方案可以对加密后的消息进行模式匹配操作,即通过密文查找某个关键字是否出现在明文中或出现在明文消息的哪些位置;另一方面,支持模式匹配的流加密方案的安全性保证了除模式匹配的结果外,不会泄露关于明文消息的任何额外信息。目前已经有很多关于支持模式匹配的流加密方案的工作,但尚没有支持模式匹配的流加密方案能够同时满足基于非交互式安全假设(特别是基于后量子假设)实现、具有自适应安全性以及支持带通配符的模式匹配。针对这一问题,首先,以函数加密方案为组件提出了一个支持模式匹配的流加密方案的通用构造方案。该通用构造方案具有自适应安全性且支持带通配符的模式匹配;进一步地,使用已有的基于容错学习假设的函数加密方案对支持模式匹配的流加密方案的通用构造方案进行实例化,并由此得到了一个基于非交互式后量子假设(容错学习假设)、具有自适应安全性和支持带通配符模式匹配的流加密实例化方案。

The stream encryption supporting pattern matching(SEPM)is a primitive proposed to provide privacy protection while doing pattern matching.On the one hand,one can use the SEPM to perform pattern matching on some ciphertext to find out whether and where a keyword exists in its corresponding plaintext.On the other hand,the security of the SEPM guarantees that no information about the plaintext will be revealed except for the results of pattern matching.Up to now,there have been several constructions of the SEPM,but none of them achieves the adaptive security from non-interactive assumptions(especially post-quantum assumptions),and supports pattern matching with the wildcard simultaneously.In this paper,we propose a new generic construction of the SEPM from a functional encryption(FE),achieving the adaptive security and supporting pattern matching with the wildcard.Further,we instantiate the generic construction of the SEPM by existing learning with error(LWE)-based instantiations of the FE.Finally,an SEPM scheme is obtained which could achieve the adaptive security from a non-interactive and post-quantum assumption(the LWE assumption)and could support pattern matching with the wildcard simultaneously.