安全兩方計算是否有不同的定義？
在閱讀有關兩方計算的教程時，我遇到了兩個（至少在形式上）不同的安全定義（與半誠實的對手）。我想知道的是這些定義是否實際上不同或可以證明是等效的。我懷疑它們是不同的，但考慮到我沒有讀過任何關於不同定義的文章，我可能會遺漏一些東西。
在Lindell (2016)中，安全的兩方計算是這樣定義的：對於每一方，模擬的聯合分佈和理想結果在計算上必須與對抗視圖和計算輸出的聯合分佈在計算上無法區分。正式地，對於每個 $ i \in {1, 2} $ , 必然存在 ppt 算法 $ S_i $ 這樣 $$ {\lbrace (S_i(1^n, x, f_1(x, y)), f(x, y)) \rbrace}{x, y, n} \stackrel{c}{\equiv} {\lbrace (\operatorname{view}^\pi_i(x, y, n), \operatorname{output}^\pi_i(x, y, n)) \rbrace}{x, y, n} ,\text{.} $$ 這個定義對我來說很有意義，因為作者定義了由安全參數和輸入索引的機率集合的計算不可區分性：
兩個機率集合 $ X = {X(a, n)}{a \in {{0, 1}}^*; n \in \mathbb{N}} $ 和 $ Y = {Y(a, n)}{a \in {{0, 1}}^; n \in \mathbb{N}} $ 被認為在計算上是不可區分的，表示為 $ X \stackrel{c}{\equiv} Y $ , 如果對於每個非均勻多項式時間算法 $ D $ 存在一個可忽略的函式 $ \mu(\cdot) $ 這樣對於每個 $ a \in {0, 1}^ $ 和每一個 $ n \in \mathbb{N} $ , $$ \lvert \Pr[D(X(a, n)) = 1] - \Pr[D(Y(a, n)) = 1] \rvert \leq \mu(n) ,\text{.} $$
這意味著必須有一個可以忽略不計的函式 $ \mu $ 用於管理安全性的所有輸入。
相比之下，埃文斯等人。（2018）定義僅由安全參數索引的機率集合的計算不可區分性。我還在其他地方看到過這樣的計算不可區分性的定義。然後，在定義安全性時，他們要求聯合分佈對於所有輸入在計算上是不可區分的。至少在形式上這向我表明，在這裡，可忽略的函式可能取決於輸入。
非常感謝您回答以下問題：
- 我是否遺漏了什麼或誤解了定義？利用對手的不均勻性，所顯示的定義是否可以等效？
- 如果不是，是不是在後一個定義中，不需要有一個可忽略不計的函式對所有輸入都“起作用”？如果我沒記錯的話，這是否意味著這兩個定義實際上是不同的？
- 如果它們不同：應該首選哪個定義？
定義不可區分性非常棘手。我實際上認為埃文斯等人在書中的定義。太弱了，但也許 Mike Rosulek 會參與進來。如果您通過說對於每個輸入，REAL/IDEAL 的分佈是不可區分的來定義安全性，那麼您實際上在說的是：對於每個輸入和每個區分器都存在微不足道的功能 $ \mu $ 所以區分器最多以機率成功 $ \mu(n) $ . 這意味著您可能需要為每個輸入使用不同的可忽略函式。更具體地說，如果我們進一步打開它，這個定義的意思是，對於每個輸入，每個區分器 $ D $ 和每個多項式 $ p $ 存在一個值 $ n_0 $ 這樣對於每個 $ n>n_0 $ 鑑別器成功的機率小於 $ 1/p(n) $ . 這意味著 $ n $ 可以取決於輸入，特別是沒有 $ n_0 $ 以至於超越 $ n_0 $ 所有輸入都無法區分。換句話說，您可能必須為不同的輸入採用不同的安全參數。這不是您想要做的事情（甚至不可能，因為您如何在不知道輸入的情況下就安全參數達成一致，以及您如何確定該安全參數應該是什麼）。相反，在輸入是集成的一部分的定義中，有一個 $ n_0 $ 對於所有輸入。我們如何確定的問題 $ n_0 $ 在實踐中很簡單——它是我們使用的所有原語安全所需要的。不用說，埃文斯等人。在他們的結構中沒有做任何不同的事情。然而，據我所知，這個定義是有缺陷的。
[在旁注中，Mihir Bellare 有一篇名為A Note on Negligible Functions的短論文，它使您能夠反轉對手和可忽略函式的量詞。但是，據我所知，這不適用於輸入。]