安全计算欧氏距离平方的 Paillier 密码系统和协议

Question

我正在尝试实施 this paper（第 3.2 节）中提出的协议。我最近开始研究同态加密和 Paillier。因此，我的问题可能太简单了，但我无法以任何方式解决问题。

论文说：

"那么Paillier密码系统满足所有要求计算欧氏距离的加密平方。因此，等式（3）可以分解为..."

...这个等式：

但是，我不知道如何计算第三部分。我在 Java 中使用了 Kun Lui's Paillier implementation 并且还遵循了幂方法：

    public static BigInteger power(BigInteger m, BigInteger i) {
            BigInteger result = m;
            while(i.compareTo(BigInteger.ONE) != 0){
                    result = result.multiply(m);
                    i = i.subtract(BigInteger.ONE);
            }
            return result;
    }

很遗憾，第三部分无法计算成功：

// Part I
BigInteger esumsqr_p = paillier.Encryption(p1.multiply(p1).add(p2.multiply(p2)));

// Part II
BigInteger esumsqr_q = paillier.Encryption(q1.multiply(q1).add(q2.multiply(q2)));

// Part III
BigInteger esum_pq = power(eq1, new BigInteger("-2").multiply(p1)).multiply(power(eq2, new BigInteger("-2").multiply(p2)));

如果你能帮我解决这个问题，我将不胜感激。提前谢谢你。

Answer 1

您的 power 函数不适用于负指数。你一直减去一个负数，所以你永远不会达到零。使用以下公式计算它。

因此，对于负数，您应该 return BigInteger.ONE.divide(power(m,i));

Answer 2

我测试了算法。如您所见，每一方都安全地计算结果。我认为一些 sub-methods 会以更成功的方式展示协议。方法如下：

public BigInteger secureEuDistanceMD(int[] p, int[] q){

    // Server (Owner of q) - PART 1
    BigInteger[] enc_Q = new BigInteger[q.length];
    BigInteger sumsqrQ = BigInteger.ZERO;
    BigInteger enc_sumsqrQ; 
    for (int i = 0; i < q.length; i++) {
        BigInteger bigQ = new BigInteger("" + q[i]);
        enc_Q[i] = paillier.Encryption(bigQ);
        sumsqrQ = sumsqrQ.add(bigQ.multiply(bigQ));
    }

    enc_sumsqrQ = paillier.Encryption(sumsqrQ);

    // Client (Owner of p) - PART 2
    BigInteger sumsqrP = BigInteger.ZERO;
    BigInteger enc_sumsqrP; 
    BigInteger enc_sumPQ = BigInteger.ONE;
    for (int i = 0; i < p.length; i++) {
        BigInteger bigP = new BigInteger("" + p[i]);
        sumsqrP = sumsqrP.add(bigP.multiply(bigP));

        enc_sumPQ = enc_sumPQ.multiply(enc_Q[i].modPow(new BigInteger("-2").multiply(bigP), paillier.nsquare));
    }

    enc_sumsqrP = paillier.Encryption(sumsqrP);
    BigInteger enc_euDist = enc_sumsqrP.multiply(enc_sumsqrQ).multiply(enc_sumPQ);

    // Server - PART 3 (Decryption)
    return paillier.Decryption(enc_euDist);
}

安全计算欧氏距离平方的 Paillier 密码系统和协议

Paillier Cryptosystem and Protocol for Computing the Square of the Euclidean Distance Securely

java

security

encryption

cryptography

privacy