遗忘数据结构的下界
1月29日 · 2 分钟阅读
Riko Jacob，Kasper Green Larsen和Jesper Buus Nielsen
遗忘数据结构是一种数据结构，其中的内存访问模式不显示有关在其上执行的操作的信息。
这样的数据结构由Wang等人[ACM SIGSAC'14]引入的，适用于希望将数据结构存储在不受信任的服务器上的情况。
获得遗忘数据结构的一种方法就是简单地在遗忘RAM（ORAM）上运行一个经典的数据结构。
直到最近，对于最自然的参数设置，这还导致ω（lg n）的开销。此外，Larsen和Nielsen [CRYPTO'18] 最近对ORAM的下界显示，如果以黑匣子方式使用，它们总是会产生至少Ω（lg n）的开销。
绕过ω（lg n）开销，研究人员们更直接地研究了经典数据结构问题，并获得了诸如堆栈，队列，双端队列，优先级队列和搜索树之类的许多此类问题的有效解决方案。
但是，这些数据结构处理操作都没有比Θ（lg n）更快的速度，这为我们留下了一个问题，即是否存在更快的解决方案。
在本文中，我们通过证明遗忘堆栈，队列，双端队列，优先级队列和搜索树的Ω（lg n）下界来排除这种可能性。
要获取此科学论文的完整版本，请单击此处。
快来发现Concordium并加入我们的社区！
开发人员中心：https：//development.concordium.com/tech
Gitter：https : //gitter.im/concordium_official/community
