Findex

Findex旨在解决以下问题

如何安全地恢复与给定关键字匹配的加密数据的位置？

这是一个设计用于在不受信任的云服务器上安全执行搜索查询的加密协议。由于其加密索引，大型数据库可以在不损害可用性的情况下安全地外包。

Findex是Cosmian Cloudproof加密的一部分。

• 入门
• 构建和测试
• Findex索引
  • 两种索引策略
• 基准测试
• 文档

入门

Findex允许通过关键字进行值索引。这些值可以是位置（加密数据库的UID、URL、路径等）。

使用Findex API，可以通过以下方式

• 通过FindexUpsert特质按关键字索引或取消索引值；
• 通过FindexSearch特质搜索关键字；
• 通过FindexCompact特质压缩索引。

这些特质可以自动实现，并提供一个宏来帮助语法。默认参数（宏使用的参数）在parameters.rs中定义。

Findex将回调的实现委托给用户以操作索引。这使得Findex与任何数据库技术兼容，因为它不包含任何特定于数据库的代码。实现是通过

请参阅in_memory_example.rs以获取实现的示例。

构建和测试

要构建Findex，只需运行

cargo build --release

要测试，运行

cargo test --release --all-features

要启动基准测试，运行

cargo bench --all-features

Findex索引

Findex依赖于两个服务器端索引

• 条目表：提供从链表表获取正确位置所需的数据。每个索引关键字匹配条目表中的一行。
• 链表：安全存储索引值。这些索引值可以是位置或其他关键字的指针。位置通常是数据库UID，但Findex可以用于索引任何类型的位置（URL、路径等）。为了使行不可区分，可变长度的索引值以固定长度的块存储，并且每行存储相同数量的块（必要时添加填充）。

Findex索引是键值存储，其结构如下表所示，其中$K_{w_i}$是与关键字$w_i$相关联的临时密钥，$H_{w_i}$是$w_i$的哈希值，$UID_{last}$是与$w_i$关联的索引值链的最后一个UID。

链表值的序列化如下（大小以字节为单位）

存储时，索引值使用AEAD进行对称加密。我们的实现使用16字节MAC标签和12字节nonce。

标志用于标记块为添加或删除。每个位对应一个块，这限制了单个链表值内部可能包含的块数最多为8。前缀用于写入块内部存储的数据的实际长度。

因此

• 给定$N$为使用的关键字数量，条目表的大小由以下公式给出（以字节为单位）

L_{entry~table} = (L_{uid} + C_e + L_{K_{w_i}} + L_{H_{w_i}} + L_{uid}) \cdot N
                = 140 \cdot N

• 给定$V(w_i)$为关键字$w_i$的体积（即由该关键字索引的值数）链表的大小由以下公式给出（以字节为单位）

L_{chain~table} = \left(L_{uid} + C_e + 1 + B * (1 + L_{block})\right) \sum\limits_{i~\in~[1,N]}\left\lceil \frac{V(w_i)}{B}\right\rceil
                = 146 \sum\limits_{i~\in~[1;N]}\left\lceil \frac{V(w_i)}{5}\right\rceil

其中

• UID的长度：$L_{uid} = 32~\textnormal{bytes}$
• 临时密钥的长度：$K_{w_i} = 16~\textnormal{bytes}$
• 关键字哈希的长度：$H_{w_i} = 32~\textnormal{bytes}$
• 链表宽度：$B = 5$
• 块长度：$L_{block} = 16~\textnormal{bytes}$
• 加密开销：$C_e = 28~\textnormal{bytes}$

两种索引策略

天真（对所有可能的切片进行索引位置）

• mar -> {位置}
• mart -> {位置}
• marti -> {位置}
• martin -> {位置}
• martine -> {位置}

混合

• mar -> martine
• mart -> martine
• marti -> martine
• martin -> martine
• martine -> {位置}

图

• mar -> mart
• mart -> marti
• marti -> martin
• martin -> martine
• martine -> {位置}

对于图解决方案，需要更多的客户端/服务器交互：与天真解决方案的1相比，本例中的图深度为4，与混合解决方案的2相比。

另一方面，图解决方案优化了链表的大小。

基准测试

本节中展示的基准测试是在Intel(R) Xeon(R) Platinum 8171M CPU @ 2.60GHz上运行的。

• 内存中的Findex（无数据库）

文档

Findex支持的论文可以在Findex 白皮书中找到。

开发文档可在doc.rs上找到。