Questions tagged [pairings]
Pairing-based cryptography uses bilinear maps to create a gap group that allows efficient constructions of certain primitives.
275
questions
1
vote
2
answers
45
views
Has the ideal "pairing" $\langle aG, bG\rangle \mapsto abG$ been ruled out conditionally?
Let $G$ be a prime order $Q$ elliptic curve over a prime field of size $P$ which admits the following mapping $f$
$f(aG, bG) = abG$
which can be computed in polynomial time in $\log(PQ)$.
Is the ...
- 195
0
votes
0
answers
32
views
In groth16, how restricting public Inputs to the prime field instead of the snark scalar field can be used?
Recently such an overflow was fixed in snarkjs but given the small difference between the 2 and that it was restricted to the prime field anyway, how could this be exploited ?
- 240
0
votes
2
answers
79
views
Not able to find any references for opening of BBS+ signature
I've reviewed the BBS signature scheme and the constant size k-TAA, known as BBS+. However, I couldn't find any specific mechanism for opening in BBS+. In the constant size k-TAA, if a user attempts ...
1
vote
0
answers
45
views
Unable to find any references for opening of BBS+ signature [duplicate]
I've reviewed the BBS signature scheme and the constant size k-TAA, known as BBS+. However, I couldn't find any specific mechanism for opening in BBS+. In the constant size k-TAA, if a user attempts ...
- 11
0
votes
0
answers
66
views
Bilinear pairing question
Can I calculate below equation?
$e(g_1^{a}, g_2^{b}) / e(g_1^{a}, g_2^{b+c}) / e(g_1^{a}, g_2^{c}) = 1$
'/' means divide.
I think it works, but there is no evidence to prove it.
- 1
0
votes
0
answers
37
views
Can I compute the following bilinear pairing equation?
Given $G_1 \times G_2 \mapsto G_t$,
How can I compute the following equations?
Firstly, $e(g_1^a, g_2^b) = g_t^{ab}$
After that, $(e(g_1^a, g_2^b))^{c} = g_t^{abc}$
3
votes
2
answers
529
views
Why is the bilinearity of an elliptic curve pairing shown as multiplicative rather than additive?
In vitalik's post here the below is mentioned,
This is the pairing. Mathematicians also sometimes call it a bilinear map; the word “bilinear” here basically means that it satisfies the constraints:
$...
- 121
0
votes
0
answers
73
views
Recommendations for tools and libraries to aid implementation for a Private Key Generator
I'm currently tasked to implement this cryptographic scheme. But currently struggle to understand these hash functions of the scheme. Can anyone explain and suggest a way or some kind of tool to build ...
1
vote
0
answers
124
views
One-more co-CDH assumption in pairing group
I am asking it again because no one answered my previous question with more clarity. I have deleted that question
One more co-CDH in Type three pairing groups $G_1 \times G_2 \to G_T$: means given a ...
- 631
2
votes
1
answer
124
views
Cryptographic assumptions with bilinear pairings
I have two statements which I think are correct:
$\beta, s$ are unknown.
Only $g^\beta$ is known to the prover but not any of $g^{\beta s^i}$ for $i \ge 1$.
If the prover is able to find group ...
- 121
3
votes
1
answer
146
views
BLS curve with a smaller modulus?
To achieve approximately 128 bits of security, curve BLS12-381 uses 381 bits to encode the X coordinate. This means the size of a group element needs at least 48B to store/transmit.
I am in a ...
- 95
3
votes
1
answer
235
views
Problem with efficiency of projective coordinates in Elliptic Curve arithmetic
Ok sort of long post incoming. Will go slow to make it as clear as possible
I'm trying to build a C library for Elliptic Curve Arithmetic. Since the idea is to learn from the process, I decided to ...
- 95
1
vote
1
answer
93
views
Hashing to the target group of bilinear pairing
Assuming we have fixed pairing friendly elliptic curve groups $G_1$, $G_2$ and $G_T$ where for $a \in G_1$ and $b \in G_T$ it holds $e(a,b) \in G_T$.
Let's put some more context and we are working in ...
- 6,230
1
vote
1
answer
71
views
Similar to Diffie Hellman for BLS in asymmetric pairing?
I had asked one question before One-More Computational Diffie-Hellman in asymmetric pairing groups and have not received answer. I am posing a supplementary question now that I just realized I don't ...
- 631
0
votes
0
answers
37
views
Safe use of bilinear pairing, using one way function in the exponent
Given a generator $g$ of a cyclic group, I am trying to look for a case where I use pairing over an element that has an exponent which is a one-way function, e.g., $g^{x^2\mod n}$ (here $x$ in the ...
- 99
1
vote
1
answer
60
views
Why the full $r$-torsion group contains $r^2$ many elements and consists of $r+1$ subgroups
let $F$ be a finite field, $E(F)$ an elliptic curve of order $n$, $r$ a factor of $n$, $k(r)$ for the embedding degree of $E(F)$ with respect to $r$.
Then why the full $r$-torsion group contains $r^2$...
- 111
0
votes
0
answers
18
views
Are there two curves that can be mapped between with a 2-isogeny that support pairing checks and Montgomery ladders?
Are there two curves that can be mapped between using a 2-isogeny that support pairing checks on on curve and Montgomery ladders on another?
Is there a paper?
- 11
1
vote
0
answers
29
views
Is there a curve that supports both pairing checks and Montgomery ladders?
Is there a curve that supports both?
Or are there two curves that can be mapped between using a 2-isogeny that support pairing checks on one and Montgomery ladders on the other?
Is there a paper on it?...
- 11
3
votes
0
answers
77
views
Real-world protocols based on pairings such that the number of additions in $\mathbb{G}_1$ is equal to the number of additions in $\mathbb{G}_2$
Consider a pairing-friendly elliptic curve $E$ over a finite field $\mathbb{F}_q$ with embedding degree $k$. Do you know examples of real-world cryptographic protocols based on pairings $\mathbb{G}_1 \...
- 425
1
vote
1
answer
99
views
Where & how is the 2nd group used in the KZG Commitment Scheme in case the 2 groups are not the same?
This is about the KZG Polynomial Commitment Scheme
In Section 2, it's written
We use the notation $e : \mathbb G \times \mathbb G \mapsto \mathbb G_T$ to denote a symmetric (type 1) bilinear pairing....
- 2,262
0
votes
1
answer
36
views
What is a efficient algorithm to compute e(u, v) in bilinear map
My problem is about this paper Efficient k-out-of-n oblivious transfer scheme with the ideal communication cost https://www.sciencedirect.com/science/article/pii/S0304397517309143
I don't know what is ...
1
vote
0
answers
88
views
How many pairings are needed to verify beta term in GGPR13 zk-snark? Pinocchio paper says 3 but I count 4
The Pinocchio paper contains a description of the GGPR protocol (Protocol 1), and states that verification requires "8 pairings for the $\alpha$ terms, and 3 for the $\beta$ term". However I ...
- 121
2
votes
0
answers
54
views
1
vote
1
answer
54
views
Any SuperSingular curve or similar with Fp = Fq which is not badly broken unless big field orders are used?
AFAIK, SuperSingular curves appear to be broken by MOV:
A. J. Menezes, T. Okamoto and S. A. Vanstone, "Reducing elliptic curve logarithms to logarithms in a finite field," in IEEE ...
- 325
2
votes
1
answer
144
views
How to find second subgroup for ECC Pairing?
Pretty new to ECC Pairings. I am trying to understand KZG Commitments from multiple sources. I found this blog beginner friendly and easier to understand. However, I'm stuck at ECC Pairings and having ...
- 31
3
votes
1
answer
164
views
Division of two Elliptic curve points in KZG polynomial commitment scheme!
I have some issue to understand the verify round of the KZG polynomial commitment scheme. The following diagram is associated to the scheme. I appreciate any help.
To verify, the verifier should ...
- 181
1
vote
1
answer
121
views
Proving scalar multiplication given elliptic curve points
From this blog post: https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627
if P = G * p, Q = G * q and R = G * r, you can check whether or not p * q = r, having just P, Q ...
- 33
2
votes
1
answer
104
views
Why not compose bilinear maps for higher arity maps?
I understand the only multilinear maps used in cryptography are bilinear maps, and higher arity multilinear maps are not "known."
Why does the composition of bilinear maps not yield usable ...
- 357
2
votes
1
answer
586
views
Is pairing-based crypto post-quantum secure?
Bilinear Pairings are widely used in many new schemes like Group Signature and Aggregate Signature. The problem is whether it is post-quantum secure. In other words, does Bilinear Diffie-Hellman ...
- 95
2
votes
1
answer
77
views
How do exactly twists interact with pairing and non-pairing computations?
Say that $\mathbb{G}_1,\mathbb{G}_2,\mathbb{G}_T$ are cyclic groups of prime order $r$ over which the pairing $e : \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ is defined. It is well known that $...
- 762
2
votes
1
answer
92
views
Replacing the Hash function with messages in the BLS signature scheme, the security degenerates from EUF to SUF?
I have been thinking about this question: if I directly replace the hash function with the message in the BLS signature, does the security of the BLS degenerate from existential unforgeability(EUF) ...
- 434
2
votes
1
answer
54
views
How to determine if a bilinear map satisfies XDLIN?
Let $\{(q, G_1, G_2, G_T, e: G_1 \times G_2\to G_T)_s\}$ be a family of bilinear groups parameterized by the security parameter $s$. We use $g_1$ (resp. $g_2$) to denote the generator of $G_1$ (resp. $...
- 121
4
votes
1
answer
119
views
Why pairing domains are subgroups of the r-torsion group?
In pairing based cryptography (PBC) we restrict the pairing domains to be subgroups of the $r$-torsion group $E[r]$. This arises two questions to me:
Why do we restrict them to subgroups of $E[r]$? ...
- 762
3
votes
1
answer
144
views
Bilinear pairing for compact BLS signature
What family of bilinear pairing is recommendable for BLS signature when the overriding criteria is compactness of the signature, as desirable for something to be keyed-in from printout, or embedded in ...
- 144k
2
votes
1
answer
119
views
Importance of non-degeneracy property of bilinear map for cryptography
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 ...
1
vote
1
answer
242
views
What is a practical application of evaluating at a point in the Kate Polynomial Commitment Scheme?
I understand how the Kate Polynomial Commitment Scheme Evaluation Proof works however, I don't understand what is the purpose of it?
In general, in a commitment scheme, Peggy commits to message & ...
- 2,262
3
votes
1
answer
113
views
Question about the soundness of using a pairing map in the Kate Polynomial Commitment Scheme
I am looking at the paper on Kate Polynomial Commitments.
On Page 7, VerifyEval, the verifier checks the following to verify commitment.
$e(\mathcal C, g) \stackrel {?}{=} e(w_i, \frac {g(\alpha)}{g(i)...
- 2,262
2
votes
1
answer
239
views
Trying to understand the 2nd subgroup in the Weil Pairing used for the MOV attack
EDIT: The bounty is actually to draw more attention. I accidentally chose the wrong reason.
$E$ – Elliptic Curve over finite field $\mathbb F_p$.
Let $k$ be the embedding degree of the Curve with ...
- 2,262
5
votes
1
answer
2k
views
What are the structural differences between BLS12-381 and BLS12-377?
What's the difference between BLS12-381 and BLS12-377?
Previously I thought their basic cryptographic algorithms were same, so it's easy to construct BLS12-381 from BLS12-377, or construct BLS12-377 ...
- 53
1
vote
2
answers
98
views
Is it possible to show and hide certain values of a message and still able to very a BLS aggregated signature?
When using BLS, let's say Alice signs each of the 5 messages ($m_1, m_2, m_3, m_4, m_5$), aggregates the signatures and sends the aggregated signature to Bob. Bob can verify it.
Here's the goal:
...
- 225
6
votes
1
answer
211
views
Will a semi-hyperelliptic pairing be used in real-world cryptography if it is faster than state-of-the-art elliptic pairings?
Let $\mathbb{G}_1$, $\mathbb{G}_2$, $\mathbb{G}_T$ stand for three groups of the same large prime order $r$. I invented a pairing $e\!: \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ (with ...
- 425
1
vote
1
answer
407
views
Why the definition of bilinearity property is different in cryptography compared to mathematics?
Background:
In Wikipedia (bilinear map definition), a condition listed as the following:
For any $\lambda \in F, {\displaystyle B(\lambda v,w)=B(v,\lambda w)=\lambda B(v,w)}$
In a ...
- 13
2
votes
1
answer
82
views
Follow-up II: Number of points on an elliptic curve
Context: paper on pairing based cryptography, question 1, question 2.
Let $E: y^2 = x^3+x$ be an elliptic curve over $\mathbb{F}_{q}$ where $q=3^m$ for some $m\geq 1$.
Then I know that
$$
\# E(\mathbb{...
- 177
2
votes
1
answer
105
views
Follow-up: Number of points on an elliptic curve
Consider this question.
Say I would want to do something similar for $E_2:y^2=x^3−x+1$ over $\mathbb{F}_{3^m}$. How would I proceed?
- 177
3
votes
1
answer
155
views
Number of points on an elliptic curve
In his paper on pairing based cryptography, Menezes claims that for
$$
E_1: y^2+y = x^3+x+1
$$
the number of $\mathbb{F}_{2^m}$-points is $2^m +1 - (1+i)^m - (1-i)^m$. Whereas this is clear, it is not ...
- 177
1
vote
1
answer
118
views
Why use pairing to construct identity based encryption?
Identity Based Encryption is an asymmetric encryption scheme such that encryption uses the receiver's identity as the public key. Such a identity can be receiver's email address or some other string ...
- 75
0
votes
0
answers
74
views
A doubt in pairing based cryptography
I have seen authors taking $G_1=G_2=G_T=G$ to be the same group of prime order $q$.
What I know is that for pairing of type $$e:G_1\times G_2\rightarrow G_T,$$ size of the element in the target group ...
- 309
2
votes
1
answer
144
views
Why is the set of r-torsion points isomorphic to $\mathbb{Z}_r \times \mathbb{Z}_r$
I'm reading "On the implementation of pairing-based cryptosystems".
It states that $E(\mathbb{F}_{k^q})[r]$ is isomorphic to the product of $\mathbb{Z}_r$ with itself.
$E(\mathbb{F}_{k^q})[r]...
- 247
1
vote
0
answers
46
views
Norm() of bilinear pairing
Consider two points P, Q over a pairing friendly elliptic curve $E[F_q]$, e.g., BN254. Let Z = e(P, Q). It is known that $Z \in F_{q^k}$ where $k$ is the embedding degree. The norm map N(Z) is defined ...
- 109
2
votes
1
answer
667
views
How to have a hash function that maps any binary string of size n to binary string of size n?
I am implementing certificateless cryptography from this research paper in python language. Essentially, I want to have the following hash function mapping. This hash function is mentioned in the ...
- 43