隱藏鍵值儲存中鍵的存在
問題：我想以這樣一種方式建構一個鍵值儲存，即不可能通過檢查來檢測儲存中是否存在鍵。換句話說，任何使用任何有效鍵的讀取操作總是返回一個看起來有效的值，並且如果沒有關於值的額外知識，就不可能說這個鍵是否曾經被寫入儲存，或者它是一個普通的垃圾。
這種儲存是可能的。例如，一種簡單（但佔用空間）的方法是創建一個儲存並用隨機值預填充所有可能的有效密鑰。寫操作用新值替換現有值，刪除操作用隨機值替換現有值。然後僅僅通過查看儲存就不可能知道哪些鍵實際上包含寫入值，哪些只儲存隨機垃圾。但這對於足夠大的密鑰空間當然是不切實際的。
我懷疑可能有更實際的解決方案。
假設你有一組鍵值對 $ (k_1, v_1), (k_2,v_2), \ldots $ . 您可以儲存多項式的係數 $ P $ 滿足 $ P(k_i)=v_i $ . 可以在任何點對多項式進行評估以給出合理的輸出。
多項式的次數洩露了鍵值對的數量，但如果 $ v_i $ 是統一的，那麼多項式不會洩露任何關於 $ k_i $ 的。這是因為對於每種不同的固定方式 $ k_i $ ‘s，多項式的係數是 $ v_i $ ‘，所以係數是一致的，如果 $ v_i $ 是統一的。
唯一真正的缺點是多項式評估有點慢：如果有 $ n $ 鍵值對然後探測這個資料結構成本 $ \Theta(n) $ . 但是，多項式的替代方案具有您需要的安全屬性，而且價格更便宜 $ O(\kappa) $ 訪問時間（用於安全參數 $ \kappa $ ）。它們的儲存成本略高，而多項式在大小上是最佳的（確切地說 $ n $ 儲存空間 $ n $ 鍵值對）。這些資料結構的最佳參考實際上是我即將發表的一篇論文，它將在接下來的幾週內發表在 eprint 上。當它可用時，我可以在這裡發布更新。與此同時，“最好的”公開可用的不經意鍵值儲存是我們在ia.cr/2020/193中提出的 probe-and-XOR-of-strings 資料結構。它有 $ O(\kappa) $ 訪問時間和 $ \sim 2.5n $ 儲存大小 $ n $ 鍵值對。