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

https://www.microsoft.com/en-us/research/blog/password-monitor-safeguarding-passwords-in-microsoft-edge/

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

## 1 Answer

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
print ( "Your password is not on the breach list")


• Regarding the FHE_Equality_Circuit I am not that familiar with circuit related things how can I replicate it in code using SEAL or HELib for integers/floating point numbers. – NaveenStuns Mar 11 at 14:38
• Are you familiar with SEAL or HELib? If so then, the circuit linked on the comment must be enough for you, also, in the linked answer there are articles that you can find in more detail. I wrote this answer since the last part is not included in that answer, combining the result to return encryption of a single bit. – kelalaka Mar 11 at 15:13
• That answer is too complicated for me as I am purely computer based cryptography background and no knowledge in circuits. I am stuck in converting the bit based circuit to code could you maybe provide a simple example. The step where you mention multiply the bits how exactly would I do that Homomorphically? – NaveenStuns Mar 11 at 17:22
• The circuit is used to define the function in your sense ( adder function, sort function, etc.), nothing is magical there. I think I've already provided enough circuits in the linked answer. Yes, this requires a circuit design in the special sense that you have mainly two operations ( but you can generate the rest), and not able to direct equality makes the problem. Did you implemented any function? – kelalaka Mar 11 at 18:01
• "Now, the server, for each breached password 𝑝𝑖 calculates 𝑐𝑖=𝐸(ℎ(𝑝𝑖),𝑘𝑝𝑢𝑏)." does that mean server will encrypt the database with client's public key for every request? that sounds like computationally expensive. – NaveenStuns Mar 12 at 7:33