This sentence worries me: "any secure computation algorithm that can compare our choice of user behavioral signature without exposing it" because it makes it seem as though there are lots of these just lying around. It seems like this would be very tricky to construct, especially given the inherent fuzziness of a signature/fingerprint based on user behavior. Do zero-knowledge 'proofs of behavior' exist?
I knew someone will catch that. I was a bit sloppy on that sentence :) I will have to improve it.
1- We only need secure multi-party computation algorithm if we cannot trust the server. In cases that server can be trusted with behavioral fingerprints then we can use server to to do the comparison.
2- One can assume that in some cases the server should not know about the behavioral fingerprint. For example in case that this procedure is implemented as a service, it might not be proper to send client side mouse movement and key presses to the server. Still server can be trusted as a mediator but should not know anything more than fingerprints being almost equal. You are right that behavioral finger prints like mouse movement are fuzzy. Specially since agent and browser are running on two different threads they get different time stamps for each mouse location. In this case you have to introduce some acceptance for fuzziness as you mentioned. Some statistical comparison. This is not as easy as checking equality securely (like Socialist millionaires problem) but you can in theory turn any circuit and make it secure so that the circuit will only expose fuzzy equality and nothing more about the data. See secure multi party computation: https://en.wikipedia.org/wiki/Secure_multi-party_computation
But your concern is valid since in practice the computation involved to do secure multi party computation in this case might be demanding for a browser. I have yet to verify that in practice. Keep in mind that our case is a bit more relaxed than general secure multi party computation problem since we have a server that can be trusted a little bit. Maybe that can help us a bit in devising a secure computation scheme. Any volunteers to work on that? :)
Actually the secure comparison protocol is the easy part - even generic SMC techniques are getting really fast these days. Also, they only involve about as much heavyweight crypto as a few TLS handshakes. Extracting a per-user fuzzy fingerprint from mouse and keyboard movements with enough entropy to make brute-force infeasible might be harder.
EDIT: That said, I do think this is a cute idea.