關於Gap SVP的定義

我對 GAP SVP 的定義感到困惑。問題指出，對於一個固定的 $ \gamma \geq 1 $ , 給定一個基礎 $ B $ 一個格子和一個 $ d>0 $ , GAPSVP 要求確定是否 $ \lambda\leq d $ 或者 $ \lambda > \gamma d $ . 我的困惑是，如果 $ d<\lambda\leq \gamma d $ ? 那麼 GAP SVP 的答案是什麼？我從 Miccincio 的 2021 年秋季CSE206A中讀到，在這種情況下任何答案都是可以接受的，但這意味著什麼？

Miccincio 的筆記是正確的，也是解釋事物的標準方式，所以讓我們詳細說明一下。

首先，值得一提的是，這與（Gap）SVP 無關，而與更普遍的所謂承諾問題有關。

承諾問題是標準決策問題的某種放寬。它們旨在放寬問題正確性的概念。正確性的標準概念可以概括為“算法在所有輸入上都是正確的”。這有兩種自然的放鬆

1. 隨機類（如 BPP、ZPP、（co）RP）。在任何特定情況下，算法現在只需要“平均”正確，您可以對隨機硬幣的內部選擇進行平均。
2. Promise 問題，您可以接受算法在“硬實例”上犯錯，但它始終必須在“簡單實例”上正確。

特別是，在困難的情況下，算法可能完全不正確，我們不在乎。只要它在簡單的情況下是正確的，我們就說它總體上是正確的。

把事情帶回到 GapSVP，困難的例子是當 $ d\leq \lambda\leq \gamma d $ . 所以我們說一個算法解決了 GapSVP 如果

1. 給定一個實例 $ (L, d) $ （格子和距離界限）很容易，意思是 $ \lambda_1(L)\leq d $ 或者 $ \lambda_1(L)\geq \gamma d $ ，算法返回正確答案
2. 給定一個硬實例，算法返回它想要的任何東西。我們不在乎。

特別是，給定相同的硬實例兩次，算法可以返回兩個答案（它不必內部一致）。我們不在乎 — 我們只關心算法在“簡單”實例上的表現如何，通過以下方式衡量 $ \gamma $ .

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