path-ORAM 及其他的tree-based ORAM

終於考完了final和導師meeting了本學期的最後一次。俏咪咪地來填坑了～

上次講到了square-root ORAM 。在square-root ORAM 之後，研究者們提出了一種基於二叉樹的ORAM的構造方法。基本的思想是，每一個數據塊被隨機分配了一個葉子結點，（注意這是一個多對一的映射， 即多個數據塊可能會對應到相同的葉子結點），假設一共有N個數據塊， 那麼N個數據塊儲存在高度為 的二叉樹的各個節點上。數據塊儲存的位置需要滿足的一個很重要的點是，如果一個數據塊對應的葉子節點是 ， 那麼從根結點到這個葉子結點的路徑上，一定有某個節點存著這個數據塊：）

可是看到這裡，很多人會發現一個問題--為什麼這個是安全的呢？首先，每個數據塊一開始只是被分配了一個隨機數而已，因此，當客戶第一次要求讀取這個節點，傳給伺服器（server）也只是一個隨機數而已。但是伺服器可以俏咪咪的記住這個信息，如果客戶下一次再讀一樣的路徑，那麼伺服器可以猜測客戶重複讀了相同的數據塊。

解決的的方法就是每次讀取完一個數據塊，就給它一個新的葉子節點，然後把它重新插入原來的路徑里。 未來保證協議的正確性，這個讀取的數據塊應該插入根結點到最小共同祖先之間的節點上。同時為了隱藏是哪一個數據塊被讀取的，所有的數據塊都應該被重新插入。

當然，方案中還有一些關於怎麼用遞歸的方法存儲葉子節點和數據塊之間的關係，以及計算這個方案溢出從而失敗的概率。牽涉到具體點細節，感興趣的同學可以去看一下論文。 覺得看論文太枯燥的同學，相關的論文也有對應的視頻，大家可以去找一下：）

寒假回來更多方安全計算和ORAM

Reference

https://eprint.iacr.org/2011/407.pdf

https://www.youtube.com/watch?v=jGr7Nj3KJ3c

推薦閱讀：