2024年3月6日
以下答案中，尤其是攻擊的那部份存在錯誤。我有空會來更新，請謹慎使用。感謝 @一般透過路人 的提醒。
跟隨 @劉巍然-學酥 來到這個問題，做個對立面的補充，提供一個看似高安全，實則 不安全 的思路。有興趣的同學可以考慮在我提示攻擊之前發現攻擊。
以下答案僅用來說明 金鑰協商協定+加密 可能 無法解決這個問題 。
很直接的想法是基於密碼（password）的隱式金鑰協商協定(Password-based authentication key exchange)。比如使用SPAKE [1] 作為具體例項化。圖片也來自文章截圖 [1]
對於不關心具體內部流程的同學，PAKE可以理解為一個黑盒子。其最重要的一條性質是， 只有當雙方都輸入相同的password時，雙方才能得到相同的會話金鑰 。隱式這個額外限制是用來保證， 除非協商好的金鑰被使用，雙方在PAKE執行完之後，也無法判定對方是否持有和自己相同的金鑰。
用來判斷是否相鄰的大體流程如下。
初始化：
Alice持有房間號u，Bob持有房間號w。雙方合議好一套SPAKE參數，如上圖中的 \mathbb{G}, g, p, M, N, H()
開始計算：
- 根據酒店形態，Alice計算u-1,u+1。 具體來說，如果是環形酒店，總房間數是N，則計算u-1 mod N, u+1 mod N，再對映到PAKE所需要的群中。其他情況只需要把u-1, u+1對映到PAKE所需要的群中即可。
- Alice以u-1, u+1作為password, Bob以w為password，跑兩輪PAKE(即每輪使用的輔助隨機量不同)。協定執行過程中，Alice會 隨機置換使用u-1,u+1的次序 ，即Alice有可能在第一輪使用u-1, 第二輪用u+1，或者在第一輪使用u-1, 第二輪使用u+1。Alice得到兩把會話金鑰 sk_{A,1},\ sk_{A,2} ，Bob得到兩把會話金鑰 sk_{B,1}, sk_{B,2} .
- Alice將兩把會話金鑰 sk_{A,1},\ sk_{A,2} 分別用來加密0字串，得到兩個密文 C_{A,1}, C_{A,2} ，都發送給Bob，此時可以再次 隨機置換密文次序 。Bob用自己的兩把會話金鑰嘗試解密 C_{A,1},\ C_{A,2} ，如果能解出0字串，則Bob知道Alice住在和自己相鄰的
正確性：
顯然，只有當Bob的房號w=u-1或者w=u+1的時候，密文才能被正確解密。
如果Bob的房號不與Alice相鄰，兩把金鑰都不對，直接解密無法解出正確結果。
(偽)安全性定理：由於PAKE是安全的，加密方案也是安全的，且進行了隨機置換，所以Bob無法得到Alice的房號。
============分割線，請停下來思考一下安全性=========================
目前看來一切似乎沒問題， 如果Bob單看密文和解密結果，由於次序置換，Bob是無法判斷Alice到底是住在w+1還是w-1號房的。
可惜的是，Bob在此可以離線窮舉出u-1,u+1。
還是以SPAKE為例， 假設Alice第一輪PAKE中傳過來的是 X^* = g^{x_1}\cdot M^{u*} 。 由於Bob知道 y^1 ,它可以分別計算 \begin{align} K_{B-} &= (X^*/M^{w-1})^{y_1}\\ K_{B} &= (X^*/M^{w})^{y_1}\\ K_{B+} &= (X^*/M^{w+1})^{y_1} \end{align} ,然後計算對應的 sk_{B-,1}, sk_{B,1}, sk_{B+,1} 。用它們來解密Alice後續傳過來的密文，只要能解密成功，比如用 sk_{B-,1} 解出了0字串, 則可以的得到u*= w-1. 類似可以得到另一個關系，比如u** = w+1。如果偏序關系是嚴格的，且N<群的大小，則可以由這兩個方程式唯一確定u的值。比如得到一個房號u*是3，一個u**是5，房號最大是9，群大小是11，那麽肯定可以得到u是4。
更嚴重的是，即使與Alice不相鄰，在猜測空間足夠小(比如題目中的0-9)，類似的方法也可以讓Bob離線窮舉出u+1, u-1，從而找出u。
不安全的深層原因
由於Bob 比針對PAKE的攻擊者強大（ 即超出安全性定義範圍 ） ，PAKE的正確性和基於密文的「相等判斷相鄰」讓Bob有了攻擊的可能。Bob同時持有了 參與計算的輔助隨機量 ，且會話金鑰被 使用 了，已然超出了PAKE所能保證的安全範圍（考慮文章開始對PAKE安全性的歸納中的「除非會話金鑰被使用...」，也請見參考文獻 [1] 中對攻擊者的限制）。所以，當password空間有限，且有使用會話金鑰做操作的參照物時，無法保證協定參與對方的password仍然安全。
另外，和 @劉巍然-學酥 討論過，安全的hash也是一個保證DH-based PSI可以用的必要條件，此處的hash必須是一個至少打破了同態性質的hash。
對安全性的思考
- 即使是半誠實(semi-honest)的理想協定，協定成果產生後， 任何一方也僅有不超過1/2的機率隱藏自己的房間號。 具體來說，一旦知道相鄰，即使是亂猜，也有1/2機率猜中對方的房間號。
- 離線窮舉的威脅。在秘密空間如此有限的情況下(只有0-9)，如果組合成最終協定的各個部件中但凡有一個不防離線攻擊，攻擊者都有可能可以窮舉出對方的秘密。反過來說，由於DH-PSI是防離線的，則使用它有了解決這個問題的可能。
參考
- ^ a b c Abdalla, M. and Pointcheval, D., 2005, February. Simple password-based encrypted key exchange protocols. In Cryptographers’ track at the RSA conference (pp. 191-208). Springer, Berlin, Heidelberg.
