Score:1

On an Elliptic Curve is that possible that from $P$ we can tell if $a$ is quadratic residue modulo $N$?

sr flag

Imagine that, On an Elliptic Curve cryptography scheme where $P=a\times G$, Bob shares his public key $P$ with Eve (the devil who wants to know secrets he is not supposed to). Bob has also revealed a clue about $a$ accidentally. The clue can be one or a combination of items from the following list:

  1. The number $a$ is ODD/EVEN integer.
  2. The number $a$ is GREATER/SMALLER than half of the group order $N/2$.
  3. The number $a$ has $x$ meaningful bits when written as binary. (there $x$ is the count of bits of $a$, for example if $a=152=10011000$ then $x=8$
  4. The number $a$ is quadratic RESIDUE/NON-RESIDUE modulo $N$.

Question 1:

Will knowledge of such a clue be considered a significant weakness for the public key of Bob so that we should say it is not safe anymore to use it?

Question 2:

Clues mentioned above are very little information about $a$ I suppose. Am I right? What if we can reveal them for all points on the curve by using a magic algorithm?

I know that, for items 1-3, knowledge of a general algorithm that for any given $P=a\times G$ it can tell us for sure that $a$ is ODD/EVEN or $a$ is GREATER/SMALLER than $N/2$ or $a$ has $x$ bits will completely break the security of Elliptic Curves and by which it will be possible to retrieve $a$ from $P$.

But what about item 4? I mean if one can discover an algorithm by which they can determine that for any given $P$, $a$ is or is not a quadratic residue modulo $N$, will they be able to completely retrieve $a$ and break the cryptographic scheme?

What if the algorithm can also tell the square root of $a$ modulo $N$?

Update 1:

These questions arose when I was studying risks of private key database being partially compromised. That is what happens if an attacker knows clues of our private keys.

kelalaka avatar
in flag
What is the origin of this question? What is meaningful in (3)? How do you quantify this? 1 and 2 reduce the space to 1/4. The effect of 4 cannot be perfectly be told if $N$ is not given.
Titanlord avatar
tl flag
Can you explain (3)? If it's the number of ones and zeros in a key, this is a serious risk.
PouJa avatar
sr flag
@kelalaka I updated the question and tried to address your questions, please look.
PouJa avatar
sr flag
@Titanlord If I give you my public key $P$ and also tell you that my private key has $124$ ones and $130$ zeros will you be able to calculate my private key? What if I don't tell the number of zeros and ones and I just tell the total sum in this example $254$.
kelalaka avatar
in flag
Why should a private key with a good random source have a problem of leaking 3 bit, expect (3), still not clear how these are leaked.
Score:1
tl flag

The impact on security from 1 and 2 can be considered as not significant. Say you have 256 Bit security, that implies $2^{256}$ different keys to chose from. If you know the key is odd, this is reduced to $2^{255}$ different keys. For 2 it is similar.

Knowing how many ones and zeros there are can be considered as a significant risk. Let's assume you have a 256 Bit key containing one 1. Only 256 possible keys remain. This results in the question of how many permutations there are. For binary numbers with a given length X and a given number if ones N this leads to the numbers of key, that can be calculated using:

$$ number\ of\ keys=\frac{(X!)}{ (N! * (X-N)!)} $$

In the best case this results in $\approx 2^{252}$ possible keys, for 128 ones. But for a different numbers of ones this only gets worse. Timing Attacks often try to find out how many different ones and zeros there are (or even try to locate some). These attacks are often a serious problem. Some of these attacks tried to guess the starting 1 of elliptic curve keys, because some old algorithms had different computing time depending on the position of the leading 1. This must not be a risk, e.g. the 1 is the first or second bit. But if the leading one was at position $i$ the security would drop to $2^{256-i}$. Depending on $i$ this can be a significant risk, especially if keys are completely chosen at random. You definitely don't want these risks.

For 4 I'm unsure. I will edit this, if I find a good answer.

PouJa avatar
sr flag
Thank you for responding. Did you find out about 4?
PouJa avatar
sr flag
Any update about 4?!
Titanlord avatar
tl flag
Sorry, I am not able to prove my assumption, but I think it would not make a significant difference. Depending on the setting, there may already be efficient algorithms to obtain that knowledge.
PouJa avatar
sr flag
Thanks, do you know of any efficient algorithm that for a given $P$ it can tell if $a$ is quadratic residue for a curve of your own choice?
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.