Importance of non-degeneracy property of bilinear map for cryptography

empty_stack

2/15/24, 11:04 AM

I'm currently looking into pairing-based cryptography and I stumbled upon the definition of the properties bilinearity, computability and non-degeneracy.

Now I have a problem with understanding the non-degeneracy and how it is important to the security of elliptic curve cryptography. I have not found a paper that goes into detail about it, only from a mathematical standpoint which is a little to abstract for me.

Let $ e: G_1 \times G_2 \rightarrow G_T$ where $G_1, G_2$ and $G_T$ are of prime order $p$.

Non-degeneracy is defined as: $$\forall P \in G_1,P \neq 0, \exists Q \in G_2: \quad e(P,Q) \neq 1$$ $$\forall Q \in G_2,Q \neq 0, \exists P \in G_1: \quad e(Q,P) \neq 1$$

tl;dr Why is the non-degeneracy an important property for pairings in cryptographic applications?

1 + 0

elliptic-curves

group-theory

pairings

Score:1

Crypto

Daniel S

2/15/24, 12:13 PM

In cryptography the groups in question are typically cyclic and of prime order and non-degeneracy is equivalent to saying that $e(P_1,P_2)\neq 1$ where $P_1$ and $P_2$ are generators for the groups. If this is not the case, then all of our pairing computations will produce the answer 1.

In pairing-based encryption we regularly compute shared secret values that are of the form $e(P_1,P_2)^{abc}$ or other pairing outputs that are supposed to be confidential. In pairing-based verification we regularly produce pairing outputs that are only supposed to be constructible by someone in possession of secret knowledge. In both cases an adversary with a degenerate pairing, the adversary can easily construct any pairing output because they would know that it is always 1.

In the non-prime order case, there is still the danger of weak keys/secrets for which the adversary can effectively construct pairing outputs.

+ 1

empty_stack

2/15/24, 1:02 PM

Does this relate to the complexity of reversing the output of the pairing? E.g. if i know the result of the pairing is 1, I can construct a pairing that solves the equation $e(P_1, P_2) = 1$? I'm trying to make sense of how an attacker could actually exploit a degenerate pairing.

Elon Musk

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

EN: Importance of non-degeneracy property of bilinear map for cryptography

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.