Join Log in
Score:0
J. Doe avatar Crypto

Given a series $g^n \mod P$. Can consecutive members be assigned to a unique value which if given the next and previous unique value can be computed

at flag
J. Doe

Given a safe prime $P$ and a generator $g$ which generates all values from $1$ to $P-1$ with $$g^n \mod P$$

1.) Is there now a function $f$ which assigns a unique value to a range of members

$$f(g^{i-a_i},...,g^{i+b_i}) = f(g^i) = v_{ia_ib_i}$$

2.) Given such a unique value $v_{ia_ib_i}$ the offset to the next $g^{q_i}$ and previous $g^{-q'_i}$ can be computed/approximated in a quite fast time (hours)

Example:
Let those unique values be group members with $g^k \equiv 0 \mod 10000$.
The assignment (1.) would just be the closest such value.
Is there now a way to compute the smallest offset $t$ to find the next unique value $g^r \equiv 0 \mod 1000 $ with $$g^k\cdot g^t = g^r$$ Same for previous unique value (both with $|t| \min$)

More details:

  • the number of unique values will be much smaller than $P$
  • one random unique number will always be given. Computing the assignment 1.) don't need to be fast. (I guess if there is some solution it can't be fast else solving dlog would be easy)
  • 2.) dont need to be an exact calculation. Some kind of search in between a small set of possible values is fine too. But it always need to lead to the very next/previous unique value
  • not all group members need to be assigned to such a unique value -the interval length ($a+b+1$) should different (in most cases) for ever unique value

So every value which can be generated with $g^{i-a_i}$ to $g^{i+b_i}$ is assigned to $f(g^i)$.

Unless the assignment changes the interval ($a,b$) also changes just by one. So for $g^{i+1}$: $$a_{i+1} = a_i +1$$ $$b_{i+1} = b_i -1$$ ($b = 0$ would be the border of the assignment)

59
0 + 0
kelalaka avatar
in flag
kelalaka
The unique values cannot be smaller than $p$. The argument is clear; what is the number of intervals? consider $a\times b$ as a grid with $a$ and $b$ from 1 to $p$, then we can see a triangle fulfills the unique values which are around $p^2/2$. If you also let $i$ be a free position on the range, then we need much higher unique values. Note that, I did not precisely calculate none of them.
1
Reply
J. Doe avatar
at flag
J. Doe
The number of intervals is equal to the number of those unique values. With this the range $a_i,b_i$ is defined with $i$. They just have an indices because they can be different for every $i$. In most cases if $i$ is changed by 1 also $a,b$ are just changed by one. They only change to bigger amount if the assignment changes as well. I added some text to make it more clear.
0
Reply
kodlu avatar
sa flag
kodlu
Firstly you cannot generate $0$ by $g^n$ since $g$ is nonzero, and no $g$ divides $P$ which is prime. Secondly, any ability to do what you are suggesting would imply a massively fast attack on Discrete Log, and thus is quite unlikely to exist, based on all current evidence for DL problem on large prime groups. There is no simple function that preserves intervals, that's the whole point of the exponentiation leading to discrete log.
1
Reply
J. Doe avatar
at flag
J. Doe
@kodlu thanks for the hint, fixed the typo (0->1). Those interval length don't need to be preserved (they also should not) in between those unique values. You are absolutely true about predicting a large number of steps ahead. But I'm not quite sure if thats also the case for just the very next/previous instance. E.g. Given that example above $g^k \equiv 0 \mod 10000$ and $g^k$ and $g < \sqrt(P)$ than the prediction of the next 'unique value' can be done very easily (just the next element). If part 1.) would take longer than $\sqrt{P}$ it would still be safe.
0
Reply
J. Doe avatar
at flag
J. Doe
Another locally easy example would be if we define those 'unique values' as every value where the mod operator had to be applied (in forward direction). E.g for $P=11, g=2$ the member list would be $[1,2,4,8,5,10,9,7,3,6]$ the 'unique value' list would be $[5,9,7,3]$. This would be locally easy to compute but the member size of those 'unique list' won't be much smaller than the total list. A $g \lll P$ is needed to work out well which is almost impossible to find for large $P$.
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.