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.