Join Log in
Score:1
avatar Crypto

Modifying discrete logarithm problem in Zp by selecting a subset of group elements

do flag
Panos

Let $g$ generator of cyclic group $Z_p$ of order $p-1$, where $g$ can generate all group elements $\alpha \in Z_p$ as $\alpha = g^x$mod$p$, $x \in (0..p-1)$, where the discrete logarithm problem is hard, i.e. computing $x= $log$_ga$.

Suppose we instantiate a cryptographic system with the above parameters (e.g. an encryption scheme or a digital signature scheme), but with the modification of only considering values $x$ valid such that $\alpha < t$, where $t \in (0..p-1)$ a "target" value. Intuitively, the security of this system is equivalent to the one without that modification (i.e. introducing the requirement that it can only use those $x$ such that the resulting $a$ are below the target), because an attacker would still need to brute-force all $x$ that do not satisfy this.

My question however is, does this open any potential number-theoretic attack? For example, could an attacker's work be sped up using some mathematical formula to exclude the "invalid" $x$ and thus directly reduce the security of the crypto system?

88
0 + 0
kelalaka avatar
in flag
kelalaka
First, make sure that $p-1$ doesn't cause an attack by Pohlig-Hellman. Second, Look for Pollard's Kangaroos, which works very well in ranges.
0
Reply
do flag
Panos
So for Pohlig-Hellman to work, $p-1$ needs to be a power of a prime, which also applies to the original parameters (i.e. it seems that my modification is not affected by this). The kangaroo algorithm looks applicable to my modification, but I'm still not sure on how it could reduce the security of the original problem. Considering the algorithm in https://en.wikipedia.org/wiki/Pollard%27s_kangaroo_algorithm , even if my valid range (0,...t) is very small (e.g. if t=1 as the extreme case), then the kangaroo would still need to compute the series of integers $d_0,... ,d_p$ which is expensive,no?
0
Reply
fgrieu avatar
ng flag
fgrieu
It's computationally hard to instantiate a cryptographic system limiting to $x$ with $g^x\bmod p=\alpha<t$. That's hard even when we can choose $x$ (e.g. for public/private keys): by the simplest strategy, if $t\approx p/2^v$, effort grows as $2^v$; and I can't think of a strategy bringing that below $2^{v/2}$. And when we use such $(x,\alpha)$ in a standard protocol the group elements will grow full size, e.g. the shared secret in basic DH key exchange. Thus I do not see that we can reach $t$ low enough that it can save a significant fraction of the space.
1
Reply
do flag
Panos
I agree that reaching $t$ requires computational effort. Let's assume that $t$ is sufficiently large such that this effort is within reasonable limits. So intuitively, the security of the modified system (i.e. the attacker's brute force work needed) would be $p-t$, because the attacker knows $t$. I'm just trying to understand if there's any number-theoretic attack that reduces the security below $p-t$. Kangaroo mentioned above seems not a problem to me.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

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.