匿名位置散列

Question

是否有可能知道两个地理位置是否在一定的距离内而不透露位置？

我在考虑新冠肺炎爆发期间的联系追踪。假设用户有一个记录他们的位置历史的应用程序，更具体的说是停在哪里，花几分钟。当一个用户被诊断出患有新冠肺炎时，想象一下他们可以分享他们去过的地方和时间，但没有透露他们的实际位置和时间。其他用户可以比较他们自己的位置历史，并知道是否有匹配。

到目前为止，我的想法是这样的，但我不确定它是否安全：

假设在7.5米和7.5分钟之间的位置被认为是匹配的。

• 把你的坐标精确到5米。
• 以你周围5米的方格为例，这样你就有了一个3x3网格。
• 取当前时间四舍五入到最近的5分钟。
• 在5分钟之前和5分钟之后
• 散列坐标平方和5分钟间隔的每个组合

现在你有一组27个哈希。其他用户可以散列他们自己的位置和时间(以相同的精度)，并查看它是否与您的散列匹配，但否则无法知道该哈希集对应于何处或何时。

当然，这是不精确的，有一个误差范围(是2.5吗？)但这是可以接受的。

这个能行吗？

Answer 1

你的解决方案对彩虹桌攻击没有抵抗力。此外，如果对手假设你的位置:询问你的“私人”位置信息，伪造他/她的位置信息，并试图检索你的位置信息，那该怎么办？

当您说“匿名位置”和“不透露位置”时，您要求的是一个非常困难的多方计算问题:参见MPC百万富翁问题。

B.T.W，我们可以找到更健壮的解决方案，混合哈希和位置隐私:你听说过“空间花过滤器”吗？

Answer 2

戴着我的前普拉丁帽子，关于距离的“不远处”声明的施诺尔式协议取得了一些进展。它还没有完全完成，仍然缺少一些部分，如产生4平方(拉格朗日定理)和调整整数协议参数(不是素数场)。

https://github.com/platinprotocol/location-zkp