Proof of number of logins in last N days without saving login times

Question

Let's say we have an user Bob. User Bob logs in into our web application every so often. We are a website that tries to save as little information about our users, however we'd like to know which users are inactive so we can suspend their account.

Is there any way we could save information about Bobs logins in a way that doesn't tell us anything about when he logged in, but tells us how many times Bob logged in in last n days?

Assume everything is being done on server side, and only thing we're trying to prevent is data leak in case of a database breach or similar.

Answer 1

I'm not sure cryptography is the way to go. A day level counter could suffice, possibly aggregated later to coarser resolution and deleting any old information you no longer need.

If you want accurate counting for last N days with a certain resolution of last N days the information on what you did N days ago must be kept. It can be inferred by querying count and querying it again after a short while. But you could perhaps do things more fuzzy, maybe store some users data together and inactivate a user group if together they didn't meet the threshold and replace which users are grouped together periodically.

Answer 2

Is there any way we could save information about Bobs logins in a way that doesn't tell us anything about when he logged in, but tells us how many times Bob logged in in last n days?

Actually (theoretically) yes, even without invoking fully-homomorphic encryption. "Mere" circuit-based randomizable-functional encryption (I'll call it CRFE) is enough.

Namely the beauty of this is that the functionalities you need are actually all unary functions:

• Remark that a user visited the website today into the log.
• Shift the log to a new day, deleting old entries.
• Extract whether the number of days visited in the log exceeds a fixed threshold.

Now suppose you have a CRFE scheme. The setup phase for your logging would then be:

1. Execute the setup algorithm of the CRFE scheme, yielding the master public key (MPK) and the master secret key (MSK).
2. Use the MSK to generate a secret key $sk_\ell$ for the function $\ell(x;r)=\operatorname{Enc}_{MPK}(x\lor 1;r)$, i.e. the function that takes the decrypted value, OR's a 1 into its lowest bit position and uses the provided randomness to re-encrypt it under the public key.
3. Use the MSK to generate a secret key $sk_u$ for the function $u(x;r)=\operatorname{Enc}_{MPK}((x\ll 1)\land 1^n;r)$ which shifts the plaintext to the left, adds in a 0 bit at the lowest position and performs an AND operation with an all-one string of length $n$ - the number of days you want to track and then re-encrypts the result.
4. Use the MSK to generate a secret key $sk_a$ for the function $a(x;r)=\operatorname{HW}(x)\geq T$ which computes the hamming-weight (the number of non-zero bits) of the decrypted value and compares that to your fixed threshold, outputting only the binary result of that comparison.
5. Securely delete the MSK.
6. Distribute $sk_\ell$ to your login-service, $sk_u$ to your daily database-update service and $sk_a$ to your "check if users have logged-in service" which preferably is somewhat harder to hack than the other two as access to this secret and at least one of the others allows revealing some information on your user's login behavior.

Now with all these secrets equipped, we can finally describe what each service should do:

• The daily database update service should lock a user's row, fetch the current encrypted log value, decrypt it with $sk_u$ and write the result back into the encrypted log field and unlock the row.
• The login service should lock a logged-in user's row, fetch the current encrypted log value, decrypt it with $sk_\ell$ and write the result back into the encrypted log field and unlock the row.
• The user registration service should use MPK to encrypt an all-0 string and write that into the new user's encrypted log field.
• The "detect absent users service" should lock a user's row, fetch the current encrypted log value, decrypt it with $sk_a$ and if it gets a "1" back, declare the user active, otherwise declare it inactive and finally unlock the row again.

_{The "lock" and "unlock" operations here are meant to enforce atomic updates and ensure that e.g. the login and the update services don't interfere unintentionally.}

---

Of course the above does not prevent an observant attacker from simply placing a cleartext logger into your user-login service and extract the login behavior this way. It also doesn't prevent an attacker who has learnt all three secrets from learning the login behavior (as they can OR and shift as needed to recover the bits from the ciphertext knowing how many they added), but it should limit leakage to about 0 if $sk_a$ is not leaked and limit leakage to about 1 bit if $sk_\ell$ and $sk_a$ are leaked and to a about $n-T$ (?) bits if $sk_u$ and $sk_a$ are leaked.

Also, of course, I make no guarantees about the practical performance of the above scheme. It might be too slow to be practically useful, especially since you need to do a re-encryption in the functionality for each update.

Answer 3

This is an XY problem.

You say "we're trying to prevent is data leak in case of a database breach or similar".

1. If smb. has got access to your dabase (to a live database or to a backup copy of it), then based on active/inactive status of accounts an attacker will know that particular users were very active in the last n days. If disclosing timestamps can harm users, then I'd suppose that disclosing that some user intensively used your web site in the last n days can also harm users.

2. If you accept encryption with server password and consider the risk of password compromising as much lower compared to compromising database, then you can store a login counter for each user for every day and encrypt it e.g. with AES-256 or ThreeFish. The encryption by widely used algorithms will also ensure that the same plain values will produce different encrypted values. Thus there will be no way to get any assumption about the plain values. Thus you will have an encrypted counter for every day and you can easily compute a sum for any n days you wish.

3. Your criteria to deactivate users seems strange. In many systems user is considered inactive based on the date of the most recent login. But you want to know the number of logins. This can lead to deactivation of users who use your web site regularly, but not as intensive as you want. For instance, if you want to deactivate users that have less then 10 logins in the last 30 days, you will also deactivate users who use your web site regularly once a week (because this will give 4 to 5 logins in the last 30 days). Thus, if you consider the risk of compromising server password as low, you can simply store the date of the last login and encrypt it with a server password.

Answer 4

I can provide a solution with additive homomorphic schemes like the Paillier encryption scheme or with FHE, however, this will be slow.

Represent the last $n$ days a bit vector of size $n$ where $1$ represent used was logged in and $0$ is the otherwise ( and for simplicity, we represent only for 5 days).

$$[0,1,1,0,0]$$ Each bit is Paillier encryption ( represent as $E_{pai}$ ) of either one or zero.

$$[E_{pai}(0),E_{pai}(1),E_{pai}(1),E_{pai}(0),E_{pai}(0)]$$ and store this information.

You can sum the bits with the additive homomorphism property of the Paillier and decrypt the summation result ($D_{pai}$) to see how many days the user entered.

$$days = D_{pai}(E_{pai}(0)+E_{pai}(1)+E_{pai}(1)+E_{pai}(0)+E_{pai}(0)) $$

You can decrypt each day to reveal the daily activities.

When a day is passed, shift the vector left by 1 and the new space will be the user's new activity;

$$[E_{pai}(1),E_{pai}(1),E_{pai}(0),E_{pai}(0),E_{pai}(0)].$$ That new value initially can be set encryption of zero, and updated to encryption of $1$ when necessary.

The sum and decryption are only necessary when requested. The new day data can be prepared during less active times of the server and stored.

Paillier is Ind-CPA secure that will not reveal information about the user data. Like any key-based solution, however, the server must protect the key at all costs. MYSQL has user-defined functions that may help to facilitate the use of Paillier and HSMs.