论文阅读-ORAM相关
ORAM基础
使用场景
-
与不受信任的云存储交互，并在不泄露访问模式的情况下利用云存储
-
在安全Enclave中实现，从而"ORAM控制器/client"为enclave，而主内存为"server"
-
在编译器中实现，该编译器将任意代码转换为通过其内存访问模式不泄漏任何内容的代码，但运行速度更慢
constant-time/oblivious定义
对于一个函数，若对任意两个输入，代码和数据的访问模式是：
-
相同，或
-
同分布，或
-
服从计算不可区分的分布
不经意随机访问机研究综述
敌手：
- 通过用户的访问模式(access pattern)来推断存储数据的重要性
- 可以通过匹配前后两个连续的访问模式来推断数据查询之间的关联关系，甚至是加密数据的内容
ORAM：隐藏对真实数据块的访问，使得攻击者不能区分每一次访问是真实的还是随机的
ORAM
-
保证：
-
任意数据块不会永久驻留在某一个物理地址中，即确保任意两次访问不会产生关联
-
将每一次读写访问细化成一次读取加一次写回的原子操作
-
-
保护：
- 访问数据块的位置
- 数据块请求的顺序
- 对相同数据块的访问频率
- 具体的读写访问方式
-
定义：ORAM是客户端与服务器的交互协议
- 安全性：访问模式计算不可区分
- 正确性：使用ORAM和不使用的返回结果不同的概率是一个可忽略函数
-
设计重点：
- ORAM初始化
- ORAM数据访问
-
特性：
- 低效性
- 安全性
- 用途广
-
模型：
- 简单模型
- 平方根模型
- 层次模型
- 分区模型
- 树状模型
ORAM性能优化
客户端与服务器平均带宽优化
- 基于布谷鸟哈希的优化策略
- 基于服务器计算的优化策略
- 基于映射表的优化策略
- 基于k 叉树的优化策略
客户端与服务器最坏情况带宽优化
- 基于de-amortization 的优化策略
- 基于树状模型的优化策略
- 基于改进混洗操作的优化策略（优化不经意排序算法）
- 基于改进驱逐操作的优化策略
客户端存储开销优化
- 基于迭代构造的优化策略
- 基于隐私信息检索的优化策略
- 基于布隆过滤器的优化策略
服务器存储开销优化
通过设计可变大小的数据块集合或者是增加(减少)部分数据块集合大小
客户端与服务器交互轮数优化
- 基于映射表的优化策略
- 基于混淆分支函数的设计
Path-ORAM
An Introduction to Oblivious RAM (ORAM) – Kudelski Security Research
树的每个节点是一个bucket，其中包含固定个数的block，每个block使用 C 的对称密钥加密
position map初始化为随机值
开始执行data request
整个从根节点到叶子节点的branch返回给 C
每个block包含id和data，id在整棵树中唯一（但是dummy block的id都相同）
shuffle：
- position map保证我们需要的block在这个branch中
- 若block是空的，不对其操作
- 非空block与当前branch中距离root最远的空block交换，使得它的leaf path与当前branch有交集
- 若在操作过程中发现目标block，position map中它的id替换成一个新的随机值
- 若没有发现空block，则需要shuffle的block会暂时保存在 C 本地的overflow stash，并在branch中替换为空block
- 所有block操作完成后，将暂存在overflow stash中的block分配到branch中新创建的空block中，然后清空stash
- 最后，将整个branch重新加密并上传到 S
具体过程如下：C 从root开始扫描
第二个block非空，需要shuffle
C 从position map中找到对应的id
找到该block对应的leaf path，此时可以找到该leaf path与当前branch的最深公共节点，该节点一定在当前解密后的branch中，搜索该节点寻找一个空block
第一个block非空
第二个block也非空
第三个block为空
交换两个block，注意到此时空block被换到更接近root的位置
C 继续扫描和交换未被操作过的block
当 C 找到目标block，首先执行request中的op
然后 C 更新position map中对应block的leaf为新生成的随机leaf id
新的随机leaf id对应的branch会与当前branch有部分交集，同样，C 会查找最深公共节点，找寻空block来进行交换
此时，若找不到空block，C 会搜索其父节点，找寻空block来进行交换
在scan的过程中若碰到一个block，无法找到能与它交换的空block，则将其暂存在stash中
同时将该block覆写为空block
stash中的block会周期性地写回到branch中空block的位置，并分配合适的leaf id；最后，branch重新加密并上传到 S
Enclave-Based Oblivious RAM Using Intel’s SGX
Computers & Security 2020
Karolinska Institutet 卡罗林斯卡学院
Carnegie Mellon University in Qatar 卡内基·梅隆大学
Qatar University 卡塔尔大学
- 利用SGX构造了三种不同的oram：线性ORAM、平方根ORAM和路径ORAM