来源
：ACM MMsys 2022

主讲人
：Yu Zheng

内容整理
：贾荣立

提出加密视频搜索的框架，利用视频独有的语义和内容相似性进行加密搜索，在搜索时间和搜索准确率上都达到了较好的效果，同时基于两次 SSE 的搜索也保证了搜索的安全性。
目录
  • 引言
  • 现有的搜索加密数据的加密工具
  • 从图像到视频的加密搜索
  • 安全性及性能分析
  • 总结

引言

现如今，互联网已经和我们的生活息息相关，我们在互联网上的一举一动都会留下或多或少的痕迹，与之相伴的是互联网用户对于隐私泄露问题的关注和对于隐私安全的重视。大家希望自己的自己的信息在云端是以密文的形式保存的，从而一定程度上防止信息泄露。但是这样同样会面临一个问题：当对于所需数据进行搜索时，我们不得不把所有的加密数据都进行解密后，再进行搜索，这样做的效率无疑是极其低下的。因此，可搜索加密技术就因此产生了。
可搜索加密技术是搜索技术和加密技术的结合。可搜索加密能够实现将用户的数据进行特殊的加密后上传到云服务器上, 并且可以实现根据关键字进行检索的功能, 在方便用户使用的过程中, 也保护了文件的隐私安全。
当然，进入多媒体时代后，需要进行加密搜索的内容已经逐步从文字、图像拓展到视频内容。当我们想通过如 youtube、bilibili 等视频平台和朋友分享视频时，就可以通过加密搜索技术实现视频隐私的保护。
有些人可能会说，我们可以解密全部的加密视频，然后使用各种检索算法进行搜索，这样就可以在没有信息泄露的前提下得到我们需要的结果。但是这样的计算和通信复杂度都是 O(N)，N 指的是视频的全部数量。理想情况下，可以在云上返回 top-k 个最相似的视频，此时再进行搜索，时空复杂度就会大大降低。
视频是一种基于内容的数据类型，它可以被分为时域和空域，时域可以归纳出该视频的高水平语义视频的高层次语义，而空域特征具有视觉属性，通常由高维特征向量编码组成。我们的问题就转化成如何根据查询图像搜索语义和视觉相似的视频，可以根据这个来简化我们的搜索。

现有的搜索加密数据的加密工具

  • （完全/部分）同态加密：允许使用最为基础的运算，如加法和乘法，但是对于大型视频数据库来说很容易出现冲突和重复，并不实用。
  • 可搜索对称加密（SSE）：由于我们想在消耗小的情况下进行加密搜索，因此使用轻量级对称密钥是一个不错的方案，通过预构建一个加密 index，然后使用“平等性测试”进行查询，这种查询方式大多数只支持精确的关键字搜索。
  • 通过 SSE 进行相似图像检索，这种方法先将视频分解成多个图像，然后利用相似图像进行检索，尽管搜索性能尚可，但是会导致大量冗余。

从图像到视频的加密搜索

在这里，我们提出了加密搜索的分层框架，如下图所示。对于从用户那里得来的图片/视频，我们先对其进行“大致搜索”。这部分是通过语义关键词进行的。初筛之后，我们进行下一步“细致搜索”，使用特征相似度 来进行视觉相似度的匹配。
加密搜索的分层框架
对于 building blocks，我们使用了一些图像处理算法用于预处理，如 SIFT，处理后我们得到了一些用于后续搜索的特征。在之后，我们使用一些哈希算法，如本地敏感哈希算法和深度算法等，将我们上一步提取出的特征进一步压缩到更短的哈希码中。
下图展示基于关键词的 SSE 是如何工作的。对于想要搜索加密视频的用户，首先需要发送一个基于语义 的令牌，服务端收到这个令牌后开始在所有加密视频数据库中进行搜索，然后将符合该令牌的内容返回给客户端。
基于关键词的 SSE 工作框架
举个例子，当我们想要进行加密搜索一个视频时，如内容是含宠物狗的短视频，首先在 coarse level 进行大致搜索，将包含狗这一语义信息的视频选出，之后，利用内容相似性进行进一步筛选并排序，直到选出符合要求的视频。
实例

安全性及性能分析

对于标准 SSE，满足自适应安全性，而我们的框架在大致搜索和细致搜索中都满足自适应安全性，使得在定位子集时不会造成额外的泄露。
我们的框架能够正确找到符合条件的子集，以及正确的 top-k 相似视频。在搜索复杂度上达到了 ，在存储空间复杂度上达到了 。
就视频搜索时间和搜索准确度进行了实验，发现搜索时间都在 0.1s 以内，而准确率在 90％ 以上。
实验结果

总结

提出了搜索加密视频的框架，使用了两次 SSE 分别基于语义和视觉信息进行“粗搜索”和“细搜索”，在时空复杂度很低的情况下达到了较高的搜索精度，同时保证了搜索的安全性。
附上演讲视频：
继续阅读
阅读原文