隐私保护整数点和区间关系判定问题

Privacy-preserving determination of integer point-interval relationship

隐私保护地判断整数点和整数区间的属于关系是一类重要的安全多方计算问题,但该问题的现有解决方案存在效率不高、隐私泄露、甚至可能判断错误等缺陷,针对此类不足,构建解决该判定问题的一个安全双方计算协议。首先,分析已有的解决方案并指出不足之处;其次,定义了整数点和整数区间的一种新的0-1编码规则,在此基础上证明了整数点属于整数区间的一个充分必要条件;最后,以此充分必要条件为判定准则,基于Goldwasser-Micali加密体制构建了判断整数点是否属于整数区间的一个安全双方计算协议,并证明了协议的正确性和半诚实模型下的安全性。分析表明,与已有的解决方案相比,所提协议具有更好的隐私保护特性且不会输出错误结果,且在轮复杂度不变的情况下,其计算复杂度和通信复杂度降低了约一半。

The determination of the relationship between integer point and integer interval in the sense of privacy preserving is an important secure multi-party computation problem,but there are some defects in the existing solutions,such as low efficiency,privacy disclosure,and even possible wrong determination. Aiming at these defects,an improved secure two-party computation protocol for solving this determination problem was constructed. Firstly,analysis of the existing protocols was given and some shortcomings of the protocols were pointed out. Secondly,a new 0-1 coding rule for integer point and integer interval was defined,based on this,a necessary and sufficient condition for an integer point belonging to an integer interval was proved. Finally,by using the necessary and sufficient condition as the determination standard,a secure two-party computation protocol for determining wether the integer point belonging to the integer interval was proposed based on the Goldwasser-Micali encryption system,and its correctness and the security under the semi-honest model were proved.Analysis shows that compared with the existing solutions,the proposed protocol has better privacy preserving feature and will not output wrong results,in addition,both the computation complexity and the communication complexity of the protocol are reduced by about half while the round complexity remains the same.