Join Log in
Score:1
Mahsa Bastankhah avatar Crypto

A finite group with a threshold functionality

de flag
Mahsa Bastankhah

I am trying to find a generator of a finite group that its powers devides the group into two parts. For example look at the last row of this table that shows the powers of 10 in the group Z_19. enter image description here

You can devide the group to two part. the elements before "10^7 mod 19" that all of them are less than "13" and the elements containing and after "10^7 mod 19" that with probablity 1/2 are more than "13". I am trying to find a group with modulo of a large prime(as large as be secure for cryptographic purpose) and a generator that can devide the group to two part as I explained before. It would be more desired if a group can be found that the probablity 1/2 that we talked about before be closer to 1. I don't care if the partition be based on something different and not greater than or less than "13". Any partition that can be easily checked would be useful.

28
0 + 5
fgrieu avatar
ng flag
fgrieu
Sorry, but many things are unclear. First and foremost, is a large multiplicative group required, and if not how is the question relevant to cryptography? Is there some size requirement on the two partitions ? Can we change the test criteria $(g^x\bmod p)<13$ to something different, like "$g^x\bmod p$ is odd"? Can we change the partition criteria $x<7$ to something different, like $(x\bmod5)<2$?
1
Reply
Mahsa Bastankhah avatar
de flag
Mahsa Bastankhah
yes, I need a large multiplicative group because I need the discrete log to be computationally hard. I need both the partitions to have the size o(n). test criteria can be anything that is computationally feasible. partition criteria should be in the form x<a for some a.
1
Reply
fgrieu avatar
ng flag
fgrieu
Remark, possibly a hint: it seems that any such method would give an advantage to guess if $x<a$ for random $x$, given $g^x\bmod p$.
1
Reply
Mahsa Bastankhah avatar
de flag
Mahsa Bastankhah
Yes but anyway it is a guess. Always given g^x mod p you can have a probability distribution on the x but doesn't matter because it is just a probability distribution.
0
Reply
fgrieu avatar
ng flag
fgrieu
Given $g^x\bmod p$ for $(p,g)$ as used in cryptography, and random $x$, we typically can't guess something interesting about $x$ (that is, something with probability and it's complement both non-vanishing). A rare exception is that if the order of $g$ is even, we can tell the parity of $x$. And that can't happen when the order of $g$ is a large prime, which is customary.
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.