# In Microsoft Password Monitor implementation using HME how do they perform ComputeMatch Function?

In this they mention

The server then evaluates a matching function on the encrypted credential, obtaining a result (True or False) encrypted under the same client key. The matching function operation looks like this: computeMatch(Enc(k), D).

How exactly do they perform it? As far as I can understand client data would be encrypted by their own private key and database will be encrypted using server's private key. So since keys mismatch they wouldn't be able to perform HME computations right? What am I missing here?

• The equality circuit Representing a function as FHE circuit – kelalaka Mar 11 at 13:20
• @kelalaka thanks I somewhat understand that answer but not sure how to implement that using SEAL or HELib to compare to integers. Can you provide me with basic idea on how to achieve it? – NaveenStuns Mar 11 at 13:39
• Most probably, there is no "key mismatch" because the database is not encrypted. – Hilder Vitor Lima Pereira Apr 11 at 5:55

Let the client have public and private keys $$k_{pub}, k_{prv}$$ of a secure FHE (Fully Homomorphic Encryption). Now clients want to check that their password $$pwd$$ is on the breach list or not.

As stated on the MS site, to prevent the user from querying dictionary attacks on the server, they use hash $$H$$ of the form Oblivious Pseudo-Random Function (OPRF). The client calculates $$h(pwd)$$ then uses their public key and encrypts as $$= E(k_{pub},h(pwd))$$. Now the client sends the $$(c,k_{pub})$$ to the server.

Now, the server, for each breached password $$p_i$$ calculates $$c_i = E(h(p_i), k_{pub})$$. Using the FHE equality circuit $$C$$ they compare each breached password's hash and the user's to get the result. Note that this result is encrypted and only the client can decrypt it. Now instead of sending each value to the user, they execute OR operation on the result to get only one value $$v$$.

The value $$v$$ sent back to the user and the user decrypt the single bit $$b \stackrel{?}{=} D(k_{prv},v)$$. If the $$b=0$$ mean not in the breach list, if $$b=1$$ mean it is on the breach list.

###Client
c = FHE_encrypt(k_pub, h(pwd)
send c to the server

###server
### Encrypt each password on the list
for each p in breachedList

c[i] = FHE_Encrypt(k_pub, p)

###Calcualte the equality of the ciphertext
for i in sizeof breachedList

eq[i] = FHE_Equality_Circuit(k_pub, c[i], c)

v = E(k_prv, 0)

###Combine the results to reduce the bandwidth
###Not to reduce the dep a binary tree calculation must be preferred.
for i in sizeof breachedList

v = FHE_OR_Circuit(k_pub, v, eq[i])

return v

###
Client
b = FHE_Decrypt(k_prv,v)
if b = 1
print ( "Change your password immediaately, it is on the breach list")
else