A leakage suppressor is a compiler that transforms a structured encryption (STE) scheme into a new scheme with an improved leakage profile. General-purpose suppressors for the query equality (qeq) pattern—which reveals if and when two queries are the same—were given for both static (Kamara et al., Crypto ’18) and dynamic (George et al., Eurocrypt ’19) encrypted structures. While the schemes that result from these suppressors are asymptotically efficient, they are not practical due to large constants in their query complexity. In this work, we propose a new query equality suppressor for dictionary encryption schemes that results in practical qeq-hiding encrypted dictionaries at the cost of revealing the distribution of the queries. The resulting constructions are distribution-aware, in the sense that they make use of the query distribution, and distribution-leaking in the sense that they also reveal it. We show how to instantiate and optimize our suppressor for query distributions that are Zipf-distributed, resulting in a scheme with O(1) online query complexity at the cost of a rebuild with \(O(m \log ^2 m/\log \log m)\) complexity, where m is the size of the input dictionary.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Structured Encryption and Distribution-Aware Leakage Suppression

  • Marilyn George,
  • Seny Kamara,
  • Tarik Moataz,
  • Zachary Espiritu

摘要

A leakage suppressor is a compiler that transforms a structured encryption (STE) scheme into a new scheme with an improved leakage profile. General-purpose suppressors for the query equality (qeq) pattern—which reveals if and when two queries are the same—were given for both static (Kamara et al., Crypto ’18) and dynamic (George et al., Eurocrypt ’19) encrypted structures. While the schemes that result from these suppressors are asymptotically efficient, they are not practical due to large constants in their query complexity. In this work, we propose a new query equality suppressor for dictionary encryption schemes that results in practical qeq-hiding encrypted dictionaries at the cost of revealing the distribution of the queries. The resulting constructions are distribution-aware, in the sense that they make use of the query distribution, and distribution-leaking in the sense that they also reveal it. We show how to instantiate and optimize our suppressor for query distributions that are Zipf-distributed, resulting in a scheme with O(1) online query complexity at the cost of a rebuild with \(O(m \log ^2 m/\log \log m)\) complexity, where m is the size of the input dictionary.