通過限制對手執行時間來無條件證明 PRP
我是博士。學習CS理論的學生，我為這個問題做了這個說明。
最近，我似乎已經獲得了 PRP 存在的證明（這是無條件的，因為它不依賴於未經證實的假設），但為了使其工作，它確實需要限制對手的執行時間. 也就是說，在通常的設置中，對於安全參數 $ n $ ，假設通常認為對手可以及時執行 $ an^c $ 對於任意（正）常數 $ a, c $ . 因此，在將 PRP 與隨機排列區分開來的情況下，他們可以使 $ an^c $ 向預言機查詢。
我已經建構了一個 PRP，我可以證明沒有對手可以從隨機排列中區分出來，只要 $ c<1 $ . 也就是說，如果對手的執行時間不超過 $ an^c $ oracle 查詢，在哪裡 $ a $ 是任意的並且 $ c $ 小於 1，那麼我可以證明對手無法將 PRP 與隨機排列區分開來。但只要 $ c\geq 1 $ 所有的賭注都關閉了，證明不起作用。
我意識到這個結果很弱，所以我想在這裡問一下這是否值得與我的顧問分享。我不想通過與我的顧問分享這樣的結果來讓自己難堪，因為它可能無用且不有趣。但是以防萬一（理論）社區覺得它有趣，我想在這裡檢查一下。
許多計算模型在受限於執行時間時會崩潰 $ o(n) $ ，因為對手沒有時間檢查他們的整個輸入（或寫下相同長度的輸出）。對我來說，你可以在這個受限的環境中表現出安全性並不奇怪。這就是說，我不會立即懷疑您顯示了一些錯誤的結果（這是將結果保密的原因之一，至少在您對結果的正確性有信心之前）
話雖如此，正如您所說，這可能並不是特別有趣（我們通常假設對手比誠實的一方擁有更多的計算能力，而不是更少）。你會遇到很多這樣的結果（與家庭作業相比，研究的很大一部分是有趣的事情現在至關重要——對於家庭作業來說，重要的是它是否真實）。
綜上所述，如果你能清楚地呈現
- 結果本身的技術說明，以及
- 結果的局限性
與任何人討論它沒有壞處。如果您不想與您的顧問特別討論結果，其他自然的事情是
- 與您計劃中的高級博士生交談，或
- 寫一些部落格文章什麼的。
每當您有這樣的“無用”想法時，與其他人分享也不錯（如果您錯過了案例怎麼辦？）。唯一需要注意的是，您應該花更多時間確保精確的結果/結構比正常情況更清晰，因為人們通常不太願意花大量精力來理解結果不太明確的含義
值得一提的是，您的想法可能沒有您最初想像的那麼無用。在密碼學中提出了一些設置，其中假設對手具有亞線性界限（例如大密鑰加密，它假設密鑰本身的亞線性量可以洩漏）。我沒有看到你的建築有明顯的應用，但它對這個領域的合理研究可能會有所幫助。此外，了解這樣的領域可能是談論“無用”結果的好處。