Short Paper: Probabilistically Almost-Oblivious Computation
Short Paper: Probabilistically Almost-Oblivious Computation
复制标题
短论文：概率上几乎不经意的计算
DOI：
10.1145/3411506.3417598
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Hicks, Michael
中科院分区：
文献类型：
--
作者：
Sweet, Ian;Darais, David;Hicks, Michael
内存跟踪遗忘(MTO)是一种不受干扰的特性：享受它的程序既不会显式也不会隐式地泄露信息，即使攻击者可以观察到程序计数器和内存访问的地址跟踪。概率MTO将MTO放宽为接受概率规划。在以前的工作中，我们开发了λObiv，其类型系统旨在执行PMTO[2]。我们展示了λObiv可以类型检查(递归)Tree Oram[6]，这是一个复杂的算法，实现了概率忽略的键值存储。我们推测λObliv应该能够检查更优化的不经意数据结构[8]的类型，但它的类型系统仍然太弱。在这篇简短的论文中，我们证明了我们是错误的：因为它们实际上不是λ，所以它们不能在PMTO中实现，因为存在溢出的可能性，当ORAM_WRITE由于本地空间不足而静默失败时，就会发生溢出。这让我们很惊讶，因为Tree Oram也可以溢出，但仍然是PMTO。本文解释了正在发生的事情，并概述了修改PMTO属性和ODSOBIV的类型系统以表征λ安全的任务。
Memory-trace Obliviousness (MTO) is a noninterference property: programs that enjoy it have neither explicit nor implicit information leaks, even when the adversary can observe the program counter and the address trace of memory accesses. Probabilistic MTO relaxes MTO to accept probabilistic programs. In prior work, we developed λobliv, whose type system aims to enforce PMTO [2]. We showed that λobliv could typecheck (recursive) Tree ORAM [6], a sophisticated algorithm that implements a probabilistically oblivious key-value store. We conjectured that λobliv ought to be able to typecheck more optimized oblivious data structures (ODSs)[8], but that its type system was as yet too weak.In this short paper we show we were wrong: ODSs cannot be implemented in λobliv because they are not actually PMTO, due to the possibility of overflow, which occurs when a oram_write silently fails due to a local lack of space. This was surprising to us because Tree ORAM can also overflow but is still PMTO. The paper explains what is going on and sketches the task of adapting the PMTO property, and λobliv's type system, to characterize ODS security.
逐步发布：统一解密、加密和密钥发布策略
DOI：
10.1109/sp.2007.22
发表时间：
2007
期刊：
2007 IEEE Symposium on Security and Privacy (SP '07)
影响因子：
--
作者：
Aslan Askarov;A. Sabelfeld
通讯作者：
A. Sabelfeld
路径ORAM
DOI：
10.1145/3177872
发表时间：
2018
期刊：
Journal of the ACM (JACM)
影响因子：
--
作者：
Emil Stefanov;Marten van Dijk;Elaine Shi;T.;Christopher W. Fletcher;Ling Ren;Xiangyao Yu;Srinivas Devadas
通讯作者：
Srinivas Devadas