secure_comparison.secure_comparison module

Implementation of secure comparison protocol as given in https://eprint.iacr.org/2018/1100.pdf Protocol 3 (with fixes).

We implement all (sub)steps separately, and do not handle communication or which player performs what action.

We implement the protocol using Paillier only, i.e., in our implementation \([[m]]\) and \([m]\) are both the same Paillier scheme.

secure_comparison.secure_comparison.from_bits(bits)

Convert a set of bits, least significant bit first to an integer.

Parameters:

bits (List[int]) – List of bits, least significant bit first.

Return type:

int

Returns:

Integer representation of the bits.

secure_comparison.secure_comparison.shuffle(values)

Shuffle the list in random order.

Parameters:

values (List[Any]) – List of objets that is to be shuffled.

Return type:

List[Any]

Returns:

Shuffled version of the input list.

secure_comparison.secure_comparison.step_1(x_enc, y_enc, l, scheme)

\(A\) chooses a random number \(r, 0 \leq r < N\), and computes

\[[[z]] \leftarrow [[y - x + 2^l + r]] = [[x]] \cdot [[y]]^{-1} \cdot [[2^l + r]] \mod N^2.\]

Parameters:

• x_enc (PaillierCiphertext) – Encrypted value of \(x\): \([[x]]\).

• y_enc (PaillierCiphertext) – Encrypted value of \(y\): \([[y]]\).

• l (int) – Fixed value, such that \(0 \leq x,y < 2^l\), for any \(x\), \(y\) that will be given as input to this method.

• scheme (Paillier) – Paillier encryption scheme.

Return type:

Tuple[PaillierCiphertext, int]

Returns:

Tuple containing as first entry the encrypted value of \(z\): \([[z]] \leftarrow [[y - x + 2^l + r]] = [[y]] \cdot [[x]]^{-1} \cdot [[2^l + r]] \mod N^2\). The second entry is the randomness value \(r\).

secure_comparison.secure_comparison.step_2(z_enc, l, scheme)

\(B\) decrypts \([[z]]\), and computes \(\beta = z \mod 2^l\).

Parameters:

• z_enc (PaillierCiphertext) – Encrypted value of \(z\): \([[z]]\).

• l (int) – Fixed value, such that \(0 \leq x,y < 2^l\), for any \(x, y\) that will be given as input to this method.

• scheme (Paillier) – Paillier encryption scheme.

Return type:

Tuple[int, int]

Returns:

Tuple containing as first entry the plaintext value of \(z\). The second entry is the value \(\beta = z \mod 2^l\).

secure_comparison.secure_comparison.step_3(r, l)

\(A\) computes \(\alpha = r \mod 2^l\).

Parameters:

• r (int) – The randomness value \(r\) from step 1.

• l (int) – Fixed value, such that \(0 \leq x,y < 2^l\), for any \(x, y\) that will be given as input to this method.

Return type:

List[int]

Returns:

Value \(\alpha = r \mod 2^l\) as bits.

secure_comparison.secure_comparison.step_4a(z, scheme)

\(B\) computes the encrypted bit \([d]\) where \(d = (z < (N - 1)/2)\) is the bit informing \(A\) whether a carryover has occurred.

Parameters:

• z (int) – Plaintext value of \(z\).

• scheme (Paillier) – Paillier encryption scheme.

Return type:

PaillierCiphertext

Returns:

Encrypted value of the bit \(d = (z < (N - 1)/2)\): \([d]\).

secure_comparison.secure_comparison.step_4b(beta, l, scheme)

\(B\) computes the encrypted bits \([\beta_i], 0 \leq i < l\) to \(A\).

Parameters:

• beta (int) – The value \(\beta\) from step 2.

• l (int) – Fixed value, such that \(0 \leq x,y < 2^l\), for any \(x, y\) that will be given as input to this method.

• scheme (Paillier) – Paillier encryption scheme.

Return type:

List[PaillierCiphertext]

Returns:

List containing the encrypted values of the bits \(\beta_i\): \([\beta_i], 0 \leq i < l\) to \(A\).

secure_comparison.secure_comparison.step_4c(d_enc, r, scheme)

\(A\) corrects \([d]\) by setting \([d] \leftarrow [0]\) whenever \(0 \leq r < (N - 1)/2\).

Parameters:

• d_enc (PaillierCiphertext) – Encrypted value of \(d\): \([d]\).

• r (int) – The randomness value \(r\) from step 1.

• scheme (Paillier) – Paillier encryption scheme.

Return type:

PaillierCiphertext

Returns:

Corrected encrypted value of \(d\): \([d]\). If \(0 \leq r < (N - 1)/2\), then \([d] \leftarrow [0]\), else \([d]\) remains unaltered.

secure_comparison.secure_comparison.step_4d(alpha, beta_is_enc)

For each \(i, 0 \leq i < l\), \(A\) computes \([\alpha_i \oplus \beta_i]\) as follows: if \(\alpha_i = 0\) then \([\alpha_i \oplus \beta_i] \leftarrow [\beta_i]\) else \([\alpha_i \oplus \beta_i] \leftarrow [1] \cdot [\beta_i]^{-1} \mod n\).

Parameters:

• alpha (List[int]) – The value \(\alpha\) from step 3.

• beta_is_enc (List[PaillierCiphertext]) – List containing the encrypted values of \(\beta_i\): \([\beta_i], 0 \leq i < l\).

Return type:

List[PaillierCiphertext]

Returns:

List containing the encrypted values of the bits \(\alpha_i \oplus \beta_i\): \([\alpha_i \oplus \beta_i], 0 \leq i < l\).

secure_comparison.secure_comparison.step_4e(r, alpha, alpha_is_xor_beta_is_enc, d_enc, scheme)

A computes \(\tilde{\alpha} = (r - N) \mod 2^l\), the corrected value of \(\alpha\) in case a carry-over actually did occur and adjusts \([\alpha_i \oplus \beta_i]\) for each \(i\): If \(\alpha_i = \tilde{\alpha}_i\) then \([w_i] \leftarrow [\alpha_i \oplus \beta_i]\) else \([w_i] \leftarrow [\alpha_i \oplus \beta_i] \cdot [d]^{-1} \mod n\)

Parameters:

• r (int) – The randomness value \(r\) from step 1.

• alpha (List[int]) – The value \(\alpha\) from step 3.

• alpha_is_xor_beta_is_enc (List[PaillierCiphertext]) – List containing the encrypted values of the bits \(\alpha_i \oplus \beta_i\): \([\alpha_i \oplus \beta_i], 0 \leq i < l\).

• d_enc (PaillierCiphertext) – Encrypted value of \(d\): \([d]\).

• scheme (Paillier) – Paillier encryption scheme.

Return type:

Tuple[List[PaillierCiphertext], List[int]]

Returns:

Tuple containing as first entry a list containing the encrypted values of the bits \(w_i\): \([w_i], 0 \leq i < l\). The second entry is the value \(\tilde{\alpha} = (r - N) \mod 2^l\) as bits.

secure_comparison.secure_comparison.step_4f(w_is_enc)

For each \(i, 0 \leq i < l\), \(A\) computes \([w_i] \leftarrow [w_i]^{2^i} \mod n\) such that these values will not interfere each other when added.

Parameters:

w_is_enc (List[PaillierCiphertext]) – List containing the encrypted values of the bits \(w_i\): \([w_i], 0 \leq i < l\).

Return type:

List[PaillierCiphertext]

Returns:

List containing the encrypted values of the bits \(w_i\): \([w_i], 0 \leq i < l\).

secure_comparison.secure_comparison.step_4g()

\(A\) chooses a uniformly random bit \(\delta_A\) and computes \(s = 1 - 2 \cdot \delta_A\).

Return type:

Tuple[int, int]

Returns:

Tuple containing as first entry the value \(s = 1 - 2 \cdot \delta_A\). The second entry is the value \(\delta_A\).

secure_comparison.secure_comparison.step_4h(s, alpha, alpha_tilde, d_enc, beta_is_enc, w_is_enc, delta_a, scheme)

For each \(i, 0 \leq i < l\), \(A\) computes \([c_i] = [s] \cdot [\alpha_i] \cdot [d]^{\tilde{\alpha}_i-\alpha_i} \cdot [\beta_i]^{-1} \cdot (\Pi^{l-1}_{j=i+1}[w_j])^3 \mod n\). We add an additional value \([c_{-1}]\), with \(c_{-1}=\delta_A + \Sigma^{l-1}_{i=0}(x_i \oplus y_i)\) to also make the scheme work in case of equality of \(x\) and \(y\).

Parameters:

• s (int) – The value \(s\) from step 4g.

• alpha (List[int]) – The value \(\alpha\) from step 3.

• alpha_tilde (List[int]) – The value \(\tilde{\alpha}\) from step 4e.

• d_enc (PaillierCiphertext) – Encrypted value of \(d\): \([d]\).

• beta_is_enc (List[PaillierCiphertext]) – List containing the encrypted values of the bits \(\beta_i\): \([\beta_i], 0 \leq i < l\).

• w_is_enc (List[PaillierCiphertext]) – List containing the encrypted values of the bits \(w_i\): \([w_i], 0 \leq i < l\).

• delta_a (int) – The value \(\delta_A\) from step 4g.

• scheme (Paillier) – Paillier encryption scheme.

Return type:

List[PaillierCiphertext]

Returns:

List containing the encrypted values of the bits \(c_i\): \([c_i] = [s] \cdot [\alpha_i] \cdot [d]^{\tilde{\alpha}_i-\alpha_i} \cdot [\beta_i]^{-1} \cdot (\Pi^{l-1}_{j=i+1}[w_j])^3 \mod n, 0 \leq i < l\).

secure_comparison.secure_comparison.step_4i(c_is_enc, scheme, do_shuffle=True)

\(A\) blinds the numbers \(c_i\) by raising them to a random non-zero exponent \(r_i \in \{1,\ldots,u-1\}\), and refreshing the randomness with a second exponent \(r'_i\) of \(2t\) bits: \([c_i] \leftarrow [c_i]^{r_i} \cdot h^{r'_i} \mod n\).

Parameters:

• c_is_enc (List[PaillierCiphertext]) – List containing the encrypted values of the bits \(c_i\): \([c_i], 0 \leq i < l\).

• scheme (Paillier) – Paillier encryption scheme.

• do_shuffle (bool) – Boolean parameter stating whether or not the bits should be shuffled randomly. (Default: True).

Return type:

List[PaillierCiphertext]

Returns:

List containing the encrypted values of the masked bits \(c_i\): \([c_i], 0 \leq i < l\).

secure_comparison.secure_comparison.step_4j(c_is_enc, scheme)

\(B\) checks whether one of the numbers \(c_i\) is decrypted to zero. If he finds one, \(\delta_B \leftarrow 1\), else \(\delta_B \leftarrow 0\).

Parameters:

• c_is_enc (List[PaillierCiphertext]) – List containing the encrypted values of the bits \(c_i\): \([c_i], 0 \leq i < l\).

• scheme (Paillier) – Paillier encryption scheme.

Return type:

int

Returns:

Value \(\delta_B\).

secure_comparison.secure_comparison.step_5(z, l, delta_b, scheme)

\(B\) computes \(\zeta_1 = z \div 2^l\) and encrypts it to \([[\zeta_1]]\) and computes \(\zeta_2 = (z + N) \div 2^l\) and encrypts it to \([[\zeta_2]]\). \(B\) also encrypts \(\delta_B\) to \([[\delta_B]]\).

Parameters:

• z (int) – Plaintext value of \(z\).

• l (int) – Fixed value, such that \(0 \leq x,y < 2^l\), for any \(x, y\) that will be given as input to this method.

• delta_b (int) – The value \(\delta_B\) from step 4j.

• scheme (Paillier) – Paillier encryption scheme.

Return type:

Tuple[PaillierCiphertext, PaillierCiphertext, PaillierCiphertext]

Returns:

A tuple with the first entry being the encrypted value of \(\zeta_1\): \([[\zeta_1]]\). The second entry is the encrypted value of \(\zeta_2\): \([[\zeta_2]]\). The third entry is the encrypted value of \(\delta_B\): \([[\delta_B]]\).

secure_comparison.secure_comparison.step_6(delta_a, delta_b_enc)

\(A\) computes \([[(\beta < \alpha)]]\) as follows: if \(\delta_A = 1\) then \([[(\beta < \alpha)]] \leftarrow [[\delta_B]]\) else \([[(\beta < \alpha)]] \leftarrow [[1]] \cdot [[\delta_B]]^{-1} \mod N^2\).

Parameters:

• delta_a (int) – The value \(\delta_A\) from step 4g.

• delta_b_enc (PaillierCiphertext) – Encrypted value of \(\delta_B\): \([[\delta_B]]\).

Return type:

PaillierCiphertext

Returns:

Encrypted value of \((\beta < \alpha)\): \([[(\beta < \alpha)]]\).

secure_comparison.secure_comparison.step_7(zeta_1_enc, zeta_2_enc, r, l, beta_lt_alpha_enc, scheme)

\(A\) computes \([[(x \leq y)]] \leftarrow [[\zeta]] \cdot ([[ r \div 2^l]] \cdot [[(\beta < \alpha)]])^{-1} \mod N^2\), where \(\zeta = \zeta_1\), if \(r < (N - 1) / 2\), else \(\zeta = \zeta_2\).

Parameters:

• zeta_1_enc (PaillierCiphertext) – Encrypted value of \(\zeta_1\): \([[\zeta_1]]\).

• zeta_2_enc (PaillierCiphertext) – Encrypted value of \(\zeta_2\): \([[\zeta_2]]\).

• r (int) – The randomness value \(r\) from step 1.

• l (int) – Fixed value, such that \(0 \leq x,y < 2^l\), for any \(x, y\) that will be given as input to this method.

• beta_lt_alpha_enc (PaillierCiphertext) – Encrypted value of \((\beta < \alpha)\): \([[(\beta < \alpha)]]\).

• scheme (Paillier) – Paillier encryption scheme.

Return type:

PaillierCiphertext

Returns:

Encrypted value of \((x \leq y)\): \([[(x \leq y)]]\). This is the final result of the computation.

secure_comparison.secure_comparison.to_bits(integer, bit_length)

Convert a given integer to a list of bits, with the least significant bit first, and the most significant bit last.

Parameters:

• integer (int) – Integer to be converted to bits.

• bit_length (int) – Amount of bits to which the integer should be converted.

Return type:

List[int]

Returns:

Bit representation of the integer in bit_length bits. Least significant bit first, most significant last.