遺忘算法與非遺忘算法的效率？

最近，許多研究人員正在研究設計高效的數據忽略算法。粗略地說，如果一個算法的數據訪問模式獨立於輸入，即算法的數據訪問模式不會洩露任何關於算法輸入的資訊，則稱該算法是數據不可知的。很少有已經研究過的算法包括排序、BFS、最小生成樹和凸包。這些不經意的算法在雲和高效安全計算方面有各種應用。我對此的疑問如下：

• ORAM 是一種將任何非遺忘算法轉換為其遺忘算法的通用方法嗎？
• 是否總是可以構造一個與非遺忘算法具有相同漸近複雜度的遺忘算法？請向我提供有關相同討論的作品的指示。

1. 是的。有一個 $ \Omega(\log n) $ ORAM 的下限。因此，直接使用 ORAM 將 non-oblivious 算法轉換為 oblivious 算法會產生 logN 成本。設計一個匹配下限的 ORAM 是一個懸而未決的問題。
2. 不，存在沒有更有效解決方案的算法。作為一個明顯的例子，訪問 N 個儲存單元中的一個儲存單元需要 $ O(1) $ 時間在非遺忘的情況下，但 $ \Omega(\log n) $ 時間在不經意的情況下，由下限暗示。我想不出更多“有用”的算法，因為沒有多少下限被證明。

我發布了兩個相關的引文：

• Nicholas Pippenger 和 Michael J. Fischer。複雜性度量之間的關係。ACM 雜誌，卷。26，第 2 期，1979 年 4 月，第 361-381 頁。ACM PDF
• Oded Goldreich 和 Rafail Ostrovsky。在不經意的 RAM 上進行軟體保護和模擬。ACM 雜誌，卷。43，第 3 期，1996 年 5 月，第 431-473 頁。doi:10.1.1.44.8961 ACM PDF

$$ follow up $$ 添加更多相關（但不完整的列表）論文。

• Goodrich, Michael T. “隨機化 shellsort：一種簡單的無意識排序算法。” 在第 21 屆 ACM-SIAM 離散算法年度研討會論文集上，第 1262-1277 頁。工業和應用數學學會，2010。
• 米切爾、約翰 C. 和喬齊默爾曼。“數據無視資料結構。” 在 LIPIcs-Leibniz 國際資訊學論文集，卷。25. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik，2014 年。
• 扎胡爾、薩米和大衛·埃文斯。“提高安全和隱私工具效率的電路結構。” 在安全和隱私 (SP) 中，2013 年 IEEE 研討會，第 493-507 頁。IEEE，2013 年。
• 古德里奇、邁克爾 T. 和邁克爾米岑馬赫。“通過不經意的 RAM 模擬保護對外包數據的訪問。” In International Colloquium on Automata, Languages, and Programming，第 576-587 頁。施普林格柏林海德堡，2011。
• Blanton、Marina、Aaron Steele 和 Mehrdad Alisagari。“用於安全計算和外包的數據忽略圖算法。” 在第 8 屆 ACM SIGSAC 資訊、電腦和通信安全研討會論文集上，第 207-218 頁。ACM，2013 年。
• Nikolaenko、Valeria、Stratis Ioannidis、Udi Weinsberg、Marc Joye、Nina Taft 和 Dan Boneh。“保護隱私的矩陣分解。” 在 2013 年 ACM SIGSAC 電腦與通信安全會議記錄中，第 801-812 頁。ACM，2013 年。
• 凱勒、馬塞爾和彼得·舒爾。“用於 MPC 的高效、無意識資料結構。” 在密碼學和資訊安全理論與應用國際會議上，第 506-525 頁。施普林格柏林海德堡，2014 年。
• Wang、肖肖恩、Kartik Nayak、Chang Liu、TH Chan、Elaine Shi、Emil Stefanov 和 Yan Huang。“不經意的資料結構。” 在 2014 年 ACM SIGSAC 電腦和通信安全會議記錄中，第 215-226 頁。ACM，2014 年。

引用自：https://crypto.stackexchange.com/questions/37273