ORAM学习

# 0.参考
[1] [ORAM](http://blog.sina.com.cn/s/blog_13d7e94220102yltv.html)
[2] 吴鹏飞,沈晴霓等.[不经意随机访问机研究综](http://www.jos.org.cn/jos/ch/reader/create_pdf.aspx?file_no=5591&journal_id=jos)述[J].软件学报,2018,29(9).

# 1.ORAM基本概念
ORAM(Oblivious Random Access Machine,茫然随机访问)是一种可以用来完全隐藏IO操作的数据访问模式的加密方案。
访问模式是指IO操作访问文件的顺序、访问文件的频率、读写顺序等，当用户把数据存储在不可信的第三方时，即使数据时加密的，第三方仍能通过收集用户的访问模式信息推断出用户隐私，在ORAM方案中，若两次访问序列长度相同，则访问模式是相同的，使得第三方无法通过访问模式获取用户隐私。
简单来说，ORAM将一个用户的一个文件访问请求转换为多个文件访问请求，从而模糊化用户访问文件的概率、模式等信息。
ORAM研究较多的领域是云存储安全。

---

用户将数据存储在云服务器上，即使数据时加密的，用户向云服务商发送关键词查询文件，即使文件是加密的，云服务商仍然可以通过访问行为推断出用户隐私。

用户的IO操作可以定义为如下形式:((op1,arg1),(op2,arg2),...,(opn,argn)),其中opi表示读写操作,argi为访问文件的地址和一个数据值；
x和y分别是两组长度相同的IO操作序列，即|x|=|y|;A(x),A(y)(tips:mask x 和 y的操作序列)分别对应于x和y在第三方存储上的操作序列，对于用户自己外的任何人，这两个操作都是计算上难以区分的，这个ORAM就是茫然的Oblivious

ORAM防止一下信息泄露:

- 哪个数据被访问
 - 数据有多旧(数据最近一次被访问的时间)
 - 两次访问操作是否访问的是相同的数据(关联性)
 - 访问模式
 - 访问是读还是写操作

---

# 2.论文:不经意随机访问机研究综述

ORAM:加密手段并不能抵抗所有类型的攻击，攻击者可通过观察用户对数据的访问模式来推断隐私信息，其中包括数据的重要程度、数据的关联性，甚至是加密数据的内容等。不经意随机访问机是一种重要的保护访问模式的手段，它通过混淆每一次访问过程，使其与随机访问不可区分，从而保护真实访问中的访问操作、访问位置信息。
不经意随机访问机是目前保护访问模式的一种重要手段。这一技术的目的是隐藏对真实数据块的访问，使得攻击者不能区分每一次访问是真实的还是随机的。
**利用不经意随机访问机来模拟安全多方计算的执行过程已被证实比传统用电路模拟的方法更高效[Secure two-party computation in sublinear(amortized) time],它极大地提升了对于海量输入数据的安全计算性能，因此不经意随机访问机为多方安全计算应用于大数据场景提供了可能[Circuit ORAM:On tightness of the goldreich-ostrovsky lower bound]**

举例:

- 云存储场景，用户查询某一个数据块的内容，为了保证数据隐私性，通常会对数据库中的数据进行加密，但在执行查询请求过程中，数据库的索引并不能加密，这就泄露了用户访问数据库元素的位置，使得攻击者可以通过用户的访问模式来推断存储数据的重要性
 - 前后两个连续访问模式来推断数据查询之间的关联关系，甚至数据的加密内容
 - 安全计算领域，当用户将隐私数据和任务以加密方式存储在内存中，如果暴露了处理器对内存的访问模式，就可能泄露数据和任务本身的信息

为了隐藏访问模式，**需要对多个数据块进行访问**，这增大了客户端与服务器之间的**带宽**，客户端需要更大的缓存空间来存储从服务器返回的额外数据，所以不经意随机访问还面临很多挑战
 
## 2.1 不经意随机访问机概述
ORAM概念起源于RAM(random access machine)模型,RAM(主存/内存，**随机存取指的是当存储器中的数据被读取或写入时，所需要的时间与这段信息所在的位置或所写入的位置无关**)，处理器通过对存储器的读写来实现程序的执行，为了隐藏程序对内存的访问模式来避免软件的逆向工程，Goldriche等人在此基础上提出了ORAM，所谓访问模式指的是处理器访问内存的操作序列和地址序列。

- **ORAM保证了在存储器中的任意数据块不会永久驻留在某一个物理地址中，确保了任意两次访问不会产生关联。**
 - ORAM将每一次读写访问都细化成一次读取加一次写回的原子操作，其中**读访问**转化成**读取内容**再**写回相同内容**;其中**写访问**转化成**读取内容**再**写回更新后的内容**
<center>
![an overview of ORAM](https://leanote.com/api/file/getImage?fileId=6030ab51ab644124fe000ab5)
</center>

ORAM可以保护以下4种属性:

- (1) 访问数据块的位置
 - (2) 数据块请求的顺序
 - (3) 对相同数据块的访问频率
 - (4) 具体的读写访问方式

攻击者不能根据访问模式来区分任意两个相同长度的访问序列
状态交互两方(客户端/服务端)协议:((c_out,c_state),(s_out,s_state))<-protocol((c_in,c_state),(s_in,s_state)),c_in与c_out客户端的输入与输出,s_in与s_sout服务端的输入与输出，c_state与s_state表示协议执行前后客户端与服务器的状态

**定义 ORAM客户端与服务器之间的交互协议:**

<center>
![交互协议](https://leanote.com/api/file/getImage?fileId=6030b6faab644126fa000adf)
</center>

**定义ORAM的安全性**

<center>
![安全性](https://leanote.com/api/file/getImage?fileId=6030b7fbab644126fa000b03)
</center>

在ORAM的设计中，通常考虑两个重要组成部分:

- ORAM初始化
    - (1) 服务器为客户端创建ORAM空间
    - (2) 客户端通过安全参数获得用来加密数据库的密钥，然后利用语义安全的加密方式加密数据库中的每一个数据块，通常数据块中不但包含数据内容，还包括数据块索引以及数据块的位置、是否被访问过等属性信息；
    - (3) 客户端将加密好的数据块上传至ORAM
 - ORAM数据访问
    - 在正式访问前，执行预热过程(warm-up)
    - ORAM对服务器进行访问时，基本操作：读和写是ORAM的原子操作，为了维护访问的隐私性与ORAM系统稳定性(**其实为了保证任意数据块不会永久驻存在某一个物理地址内**)，不同设计模型还需要其他的**离线操作**。ORAM两种设计方法：
        - 平方根模型(一个访问周期结束后，需要将所有数据块的位置重新混淆，reshuffle)
        - 层次模型(不断的将数据块从一个物理地址移动到更大空间的物理地址，驱逐操作eviction)

ORAM缺点:

- 低效性(额外的操作来保护访问模式的隐私性，昂贵的开销，带宽/存储)

## 2.2 不经意随机访问研究的现状分析
依据服务器存储数据块的数据结构，ORAM设计模型可以分为5类:

- 1.简单模型
    - 服务器以数组的方式连续存储客户端的数据块，为了隐藏客户端访问了哪一个数据块，客户端每一次访问需要遍历所有数据块
 - 2.平方根模型
    - 将服务器划分成两个部分:排列数组(permuted)与缓冲区(shelter),排列数组中包含N个真实的数据块(real block)和$\sqrt{N}$个无效数据块(dummy block),客户端每次访问前将这些块混洗。在每一次访问中，客户端先查询目标数据块是否在缓冲区内，如果在，就从排列数组中读取一个无效数据块；如果没有在缓冲区内，就在排列数组内读取目标数据块，为了混淆数据块的访问位置，每一次访问周期($\sqrt{N}$次访问)需要重新混洗排列数组
 - 3.层次模型
    - 将服务器存储分层，第i层包含2<sup>i</sup>个数据块集合(bucket),当访问周期结束后(2<sup>i</sup>次)，要重新混洗
    - 对于每一层而言，当一个访问周期(2^i次访问)结束后，需要将当前层的数据块和下一层的数据块合并并且混洗后放入下一层
    - 每一层都会读取一个数据块，哪怕此层没有需要的target 数据块，也要读取无效区块(伪装)
    - 当客户端更新完数据块后，将其写入服务器最顶层，最顶层访问周期短，数据块会频繁地混洗到下一层，不用担心顶层数据块溢出问题
 - 4.分区模型
    - 将数据存储在$\sqrt{N}$个服务器(partitions)上,每个服务器利用平方根模型或层次模型构建
    - 客户端存储数据块索引到数据块在服务器位置之间的映射表查找数据块所在的服务器，然后使用ORAM模型访问方式读取数据块
 - 5.树状模型
 - 在层次模型上进行改进，每一个数据块集合分配到树的节点上，客户端本地存储每一个数据对应树的叶子节点的映射关系。
 - Tree ORAM，每一次访问先查询数据块所在的叶子节点，将从根节点至叶子节点上所有的数据块集合取回本地
 - 更新完后，将目标数据块写入根节点

>优缺点

<center>
![对比分析](https://leanote.com/api/file/getImage?fileId=6033514aab6441677c000491)
</center>

> 性能

<center>
![xingneng](https://leanote.com/api/file/getImage?fileId=6033529dab64416581000523)
</center>

---

**tips:ORAM常用操作**
**驱逐(eviction):**
为了保证数据块集合不溢出，需要不断的将数据块从一个物理地址移动到更大空间的物理地址。
**混洗(reshuffle)：**
在一个访问周期结束后，将所有的数据块位置重新混淆。

---

信息安全从业人员^_^

导航

最近发表

友情链接