基于加法同态加密的有理数百万富翁问题高效协议

"安全多方计算（SMC）是密码学领域的重要研究方向，主要关注如何在多个参与者之间进行计算，同时保持数据的隐私性。百万富翁问题是一个经典的SMC问题，其目标是让两个不想公开自己财富的百万富翁得知谁更富有，而无需透露各自的财富具体数额。当前大多数解决方案依赖于整数操作，限制了其应用范围。本文提出了一种新的协议，该协议基于加法同态加密和有理数，旨在解决一般化的百万富翁问题，即适用于有理数的情况。通过计算三角形面积的方法，该协议能高效地比较两个私有输入的大小关系，计算复杂度显著降低。协议的安全性通过模拟样本得到证明，并且可以广泛应用于涉及有理数和整数的SMC场景，以及解决有理数领域的计算几何问题。" 本文详细探讨了安全多方计算中的一个关键问题——百万富翁问题，并提出了一种创新的解决方案。传统的百万富翁问题协议通常基于整数操作，这使得它们在处理非整数数据时效率低下或无法适用。作者提出的新协议利用了加法同态加密技术，这是一种允许在加密数据上直接执行加法运算的技术，从而在保持数据隐私的同时进行计算。 其中一个关键创新点是将计算几何的原理引入协议设计。通过计算由三个私人点构成的三角形的面积，协议能够确定两个私有输入（代表百万富翁的财富）的相对大小，即哪个百万富翁更富有。这种方法简化了比较过程，降低了计算复杂度，对于涉及有理数的比较尤其具有优势。 协议的安全性通过模拟范例进行了证明，这是评估SMC协议安全性的一种常见方法，它模拟了攻击者可能的行为并验证协议在攻击下的安全性。此外，这些新协议不仅限于解决百万富翁问题，还可以应用于更广泛的SMC场景，包括那些涉及有理数和整数的协议。更重要的是，它们直接解决了有理数域中的计算几何问题，为安全多方计算提供了新的工具和思路。 这项研究为SMC领域带来了新的突破，扩展了百万富翁问题的解决方案，提升了在有理数环境下的计算效率，并为计算几何中的安全多方计算提供了可行途径。这对于推动SMC技术的发展和应用具有重要意义。