考慮到至少有一對（原像，圖像），知道一個圖像可能有多少原像有多容易？
我一直在考慮一種方法來激勵加密貨幣礦工來驗證量子計算霸權的主張。簡而言之，礦工發現碰撞 $ f(x_1)=f(x_2)=y $ 一些已知的 $ f:m+1\mapsto m $ 位散列函式 $ f $ . 我設想量子電腦廣播並承諾 $ y $ 和另一個刺痛 $ d $ 與原像有關 $ (x_1\oplus x_2) $ ，然後礦工尋找兩個原像。量子計算公司可以起草一份智能合約，在發現和廣播原像後向礦工付款。一台誠實的量子電腦可能不會分別找到兩個原像，而是可以將兩個原像疊加在一起。
但是，雜湊函式並非設計為 2 對 1，而是可以用類似
SHA256. 我認為，一般來說，隨機雜湊函式的衝突次數是根據Poisson分佈分佈的，而且通常會有很多 $ y $ 只有一個原像。快速回答問題：
> 對於一些通用的雜湊函式 $ f $ 例如
SHA，決定給定圖像有多少原像有多難 $ y $ 有，當我們可以隨便選擇一個隨機的 $ x $ 並且知道 $ y=f(x) $ 至少有一個原像？我很高興知道是否有一個作弊證明者可以找到 $ (x,f(x)) $ 隨意配對沒有簡單的方法來確定是否有另一個原像 $ x’ $ 和 $ f(x)=f(x’) $ .
理想散列函式的常見經典模型是隨機預言機。這是一個接受輸入的假設設備 $ x $ （這裡一個 $ m+1 $ -bit 位串），然後產生一個輸出 $ y $ （這裡一個 $ m $ -bit 位串）。該設備維護一個表 $ (x_i,y_i) $ 對在哪裡 $ x_i $ 是先前的輸入並且 $ y_i $ 然後給出輸出；和一個櫃檯 $ n $ 表中的條目，最初 $ 0 $ . 當一個 $ x $ 送出後， $ n $ 掃描表中的條目以查找匹配項 $ x_i $ . 如果找到一個，設備輸出 $ y:=y_i $ . 否則，設備繪製一個均勻隨機的 $ y $ 它輸出，添加一個新條目 $ (x_n,y_n):=(x,y) $ 到表中，並遞增 $ n $ . 因此，在任何時候都沒有重複 $ x_i $ ， 和 $ 0\le n\le2^{m+1} $ .
為了確定地知道給定的原像有多少 $ m $ -bit 位串具有每個隨機預言機，有必要使 $ 2^{m+1} $ 涵蓋所有值的查詢 $ x $ ，因為到目前為止已經找到了多少原像可以在這些查詢的最後一個增加。
如果我們將“一些通用散列函式”建模為經典隨機預言機，對於
決定給定圖像有多少原像有多難 $ y $ 有
因此，經典計算模型和理想雜湊下的答案是
- 如果我們最初知道一個 $ x $ 和 $ f(x)=y, $ ： $ \ 2^{m+1}-1 $ 雜湊（ $ -1 $ 術語是因為我們不需要測試已知的 $ x $ ）。
- 否則， $ 2^{m+1} $ 雜湊，或 $ 2^{m+1}-1 $ 在極少數情況下，第一個都沒有 $ 2^{m+1}-1 $ 返回的雜湊值 $ y $ ，這使我們可以得出結論，原像的數量是 $ 1 $ 沒有測試最後一個 $ x $ .
對於實際的雜湊（例如 SHA-256 截斷為 $ m $ 位和輸入由一些固定的常量位串組成，後跟 $ m+1 $ 位），我們不知道更好的方法。但是，有可能解決許多不同的問題，不同之處僅在於 $ y $ 投入，成本略高於一個問題。
我不敢猜測這對假設的量子電腦有何影響。但是無所謂 $ m $ 考慮到（經典）散列的複雜性，我們擁有的量子電腦對此類問題沒有實際幫助†。我不確定人類是否會達到那個階段。
† 暫定定義：標準筆記型電腦無法在 1 秒內以高機率解決問題，並且作為支持所需的 QC 和經典計算/電路的組合比為任務優化的經典計算/電路快 10%，在經典計算/電路的同等資源（門，功率）。