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.
