Security of modular exponentiation for non-uniform inputs

pintor

4/6/24, 2:26 PM

Suppose we have a function $F = f_{s}(x)$ with a key $s \gets \mathbb{Z}_q$ that on input $x$ outputs modular exponentiation $x^s$, where $\mathbb{G}$ is a cyclic group of order $q$ where DDH is hard. If $x$ is selected uniformly at random from $\mathbb{G}$, then modular exponentiation $F$ behaves like a weak PRF (Naor et. al "Distributed Pseudo-Random Functions and KDCs").

However, what happens when inputs are not chosen at random? Say, one can query $F$ for any $x \in \mathbb{G}$. Are there any security estimations?

1 + 2

modular-arithmetic

fgrieu

4/6/24, 2:57 PM

Hint: $(xy)^s=(x^s)(y^s)$. Or the lesser $1^s=1$.

pintor

4/6/24, 3:25 PM

@fgrieu Homomorphic properties? Not sure what you mean. Sure, $F$ wouldn't be weak PRF as we can't do a reduction to DDH with adaptive $x$ selection. But I'm not sure what would $F$ be. It is not a one-way function as $x$ is not a random generator (as per this def https://people.seas.harvard.edu/~salil/cs127/fall13/lec9.pdf). Don't know. I can't find a way to show $F$ leaks $x$ eventually, nor can I prove it doesn't.

Score:1

Crypto

fgrieu

4/6/24, 3:50 PM

What happens when inputs are not chosen at random?

We can distinguish an oracle implementing some $f_s$ from one implementing a true PRF with near certainty, as follows:

Take two arbitrary group elements $x$ and $y$.
Compute $z=xy$ by multiplying in the group.
Query the oracle with $x$, $y$, and $z$ so that we get $X=f_s(x)$, $Y=f_s(y)$, $Z=f_s(z)$.
Test if $XY=Z$ and if so output "the oracle probably is implementing some $f_s$", else output "the oracle must be implementing a PRF".

This works because $(x^s)(y^s)=(xy)^s$.

We can simplify this by querying with $x$ and $z=x^2$ and checking $Z=X^2$. Or just by querying with $x=1$ and checking $X=1$, where $1$ is the group identity.

This contrasts with when we are limited to random queries: no such distinguisher is possible.

+ 3

pintor

4/6/24, 4:08 PM

Yes, $F$ wouldn't be PRF, not even weak PRF (it's not a question). The question is: what security does it have? Can we prove something about $F$ when $x$ is not random?

fgrieu

4/6/24, 4:49 PM

@pintor: I see. You want some _positive_ result on some aspect of the security of $F$; like, it can't be inverted even with access to an oracle implementing $F$ (or perhaps, no past access to an oracle for $F$ will allow to compute $F$ for a random $x$). I'm clueless.

pintor

4/28/24, 2:34 PM

@ fgrieu Yeah, I'm clueless too. Thank you anyway. Anyway, I realized I didn't phrase my question well (it's unclear if I'm asking for positive results or just wondering why). I'll accept the answer (it's a good one) and create another question with hopefully better wording.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Security of modular exponentiation for non-uniform inputs

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.