Score:1

Anonymous PAKE using two party computation

us flag

Let's say client side has a secret password $\pi$. The server has a series of indices $0..n-1$ and a salt associated value $s_i$ for all $i \in \{0,n-1\}$ call it set $S=\{s_i | i \in \{0,n-1\}\}$ for each client. Client wishes to compute an OPRF function $f(\pi,s)$ such that he does not learn $s$ and the server does not learn anything. This is basically what OPAQUE does for $f(\pi,s)=H(\pi,H'(\pi)^s)$ where $H'$ hashes to a sub group element. Because the server only ever sees the blinded $H'(\pi)$ which is a random group element, it can simulate its view and no matter how many query client does, it never learns $s$.

But I need to take it one step further and require that it allows logging in anonymously. That is I need a function $g(i,\pi,S)=f(\pi,s_i)$ such that server does not learn anything about either $i$ or $\pi$ and client does not learn anything else about $S$ or about any other elements in $S$. Least not $f(\pi,s_j)$ for another $j$ that allows one to target multiple accounts at the same time with brute force/dictionary attacks.

One way of doing this for the same function as in OPAQUE is using OPAQUE along with oblivious transfer. Client does not need to send many values at a time but simply using OT here means that the server has to do perform it's end of calculation of $f(\pi,s_i)$ for each $i$ i.e $n$ exponentiations/scalar multiplications and needs to send $n$ cipher texts each time a client tries to login. And this is outside the computations involved with OT itself. After all, OT can be used to transfer arbitrary messages not just compute some functions so $n$ cipher texts in general case is justified. But this would be impractical here.

So, does anyone knows of any work about this or is doing anything which can achieve this more efficiently in constant or at least sublinear time of number of clients to be practical.It may be something that uses some accumulator in $S$ which can be precomputed or something. It does not have to be same function as in OPAQUE, anything with above properties works.

EDIT: I am not suggesting performing full OPAQUE anonymously, which since it holds encrypted client ID private DH key and server public DH key requires OT to perform anonymously. But doing only the calculation of OPRF part anonymously and perform rest of key exchange separately.

Score:1
my flag

So, does anyone knows of any work about this or is doing anything which can achieve this more efficiently in constant or at least sublinear time of number of clients to be practical.

Well, with your OPAQUE-based suggestion, you don't need all the security guarantees of OT; you don't care if the client learns about encrypted payloads for other clients. Hence, Private Information Retrieval (PIR) is sufficient, as it gives you the one security guarantee that you do care about (the server doesn't know which client encrypted payload the client is retrieving). Now, we don't know how to do PIR in sublinear time (without prior communication with the client - that's not possible in this case, and without assuming multiple servers where at least one is trusted); however I believe that the constant of proportionality on existing PIR mechanisms is small enough to make this practical.

On the other hand, if you don't mind leaking an upper bound on the number of clients, one practical workaround may to place the list of all the encrypted client payloads on a public server (signed by the server's public key, naturally); anyone can download that at any time at no cost to the server.

Manish Adhikari avatar
us flag
Yes, I get about client encrypted payload retrieval, anonymity can be preserved by separating it from calculation of $f$. But my main question was about the calculation of OPRF which requires OT like security guarantees, I don't want an attacker being able to probe multiple accounts for one password at the same time. Like PIR, if it is practical even with linear time and communication I don't mind using OT here. If we don't know how to do it in sublinear time, maybe sacrificing some anonymity (OT for a subset of clients) for practicality might be a workaround.
poncho avatar
my flag
@ManishAdhikari: the easiest way to prevent someone from probing multiple accounts simultaneously is to make the password that you give to Opaque include the user name, as in "poncho@my_password". Because Opaque gives you the property that it allows you to test only one password per exchange, including the username means that we cannot test multiple users with a single exchange.
Manish Adhikari avatar
us flag
That is a good way. Thanks
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.