Questions tagged [pairings]
Pairing-based cryptography uses bilinear maps to create a gap group that allows efficient constructions of certain primitives.
254
questions
2
votes
1
answer
69
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
0
votes
0
answers
19
views
How can we construct a ZKPoK which hides both $x$ and the witness $W_x$ in dynamic accumulators?
Consider a verification equation $ e(\Delta,\tilde{G}) = e(W_x,x\tilde{G}+pk_{acc})$ from a pairing based accumulator which uses the value $x$ and the corresponding witness $W_x$ to verify that a ...
3
votes
1
answer
97
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 ...
- 171
1
vote
1
answer
50
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
82
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
304
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 ...
- 23
2
votes
1
answer
31
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 $...
- 712
2
votes
1
answer
44
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) ...
- 336
2
votes
1
answer
44
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
82
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]$? ...
- 712
0
votes
0
answers
35
views
Why it is important the notion of equivalent divisors in pairing definitions?
Following the book Pairing for Beginners, the Tate pairing computation requirements are:
Let $P$ be an point on the $r$-torsion subgroup in $E(\mathbb{F}_q)$.
Let $f$ be a function whose divisor is $(...
- 712
3
votes
1
answer
102
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 ...
- 134k
2
votes
1
answer
47
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 ...
- 75
1
vote
1
answer
60
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,310
3
votes
1
answer
92
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,310
6
votes
0
answers
460
views
How the mimc bug from circomlib was safely exploited in practice?
Several years ago, there was an unenforced constraint on verification in the cirmcomlib library : a tool for building projects using ZsNarks. The error allowed to forge cryptographic nullifiers/proofs ...
- 185
2
votes
1
answer
140
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,310
5
votes
1
answer
438
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
81
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
5
votes
1
answer
170
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 ...
- 355
1
vote
1
answer
379
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
79
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
101
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
134
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
81
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 ...
- 73
0
votes
0
answers
67
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
85
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
40
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 ...
- 57
2
votes
1
answer
344
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
2
votes
1
answer
277
views
What is a function on a Line or a Curve?
I am reading up on Pairings using Elliptic curves & all the texts talk about functions on a Curve.
I am finding it difficult to even figure out what they mean by "function on a curve" or ...
- 2,310
2
votes
1
answer
224
views
Size of group elements in a bilinear context
In a asymetric pairing context, which size (in bits) should have the elements of $\mathbb{G}_1,\mathbb{G}_2$ and $\mathbb{G}_T$ if we consider the most efficient elliptic curves?
- 2,543
2
votes
1
answer
267
views
How to have a hash function that maps from a group element to a binary string of a certain size in charm-crypto?
I am facing a problem in programming with the charm-crypto library. The hash functions for pairing group elements in charm-crypto can only map from a string to a specific field: $\mathbb Z_r$, $G_1$ ...
- 43
1
vote
1
answer
68
views
Developments in ABE using Pairings
What are the recent developments in Attribute-Based Encryption (ABE) using Pairings assumptions?
Is pairings the most viable assumption while designing ABE. What other assumptions are used for ABE ...
1
vote
0
answers
80
views
Multiplication of pairings vs. exponentiation of the group elements
Assume that we have a pairing as $e:G_1\times G_2\rightarrow G_T$. such that $g_1$ and $g_2$ are the generator of $G_1$ and $G_2$ respectively.
In a protocol I have $A=\prod_{i=1}^n e(H(i),pk_i)$ ...
- 335
1
vote
0
answers
184
views
What's the difference between Optimal ate pairing and R-ate pairing?
I compare the algorithm description of Optimal ate pairing and R-ate pairing, it turns out to me that the formulas are the same. So I'm a little confused, what's the difference between them? or is it ...
- 11
5
votes
1
answer
164
views
Pairing-friendly curve whose group order is a safe prime
Are there any pairing-friendly curves whose group order is a safe prime?
That is: the order of the group is $2q + 1$ for some prime number $q$.
Or, is it impossible to have such groups?
- 57
1
vote
0
answers
23
views
Chaining a smaller group inside the pairing friendly group
Let's say there is a bilinear pairing $G \times G \rightarrow G_t$ (e.g., for bn128), and let prime $q$ be the order of $G$. Is it possible to find a prime order group over integers such that its ...
- 57
1
vote
0
answers
55
views
Can we instantiate VRF without using pairing?
As my survey, most of(I am not sure if it is "all") the constructions of VRF are instantiated with the use of pairing. Can we construct a VRF without using pairing?
- 777
1
vote
0
answers
47
views
Range proofs and Groth-Sahai PPEs
I'm looking for a set of pairing product equations (ala Groth-Sahai) which allow a prover to prove that the output of a VRF is in a specific range.
In the E-cash system in [BCKL] there is a ...
- 11
3
votes
1
answer
284
views
Is this pairing-based signature scheme secure?
There are a number of signature schemes on small domains based on bilinear pairings which do not use random oracles. Examples are the Boneh-Boyen schemes and an interesting one from Okamoto which ...
- 366
3
votes
2
answers
130
views
Independent parameters basis for torsion-groups in SIDH: Is the Weil-pairing necessary?
In the original SIDH paper by De Feo, Jao and Plût, the basis points $P_A$ and $Q_A$ are supposed to be independent points in $E(\mathbb{F}_{p^2})$ of order $\ell_A^{e_A}$ for some small prime $\ell_A$...
- 33
2
votes
1
answer
59
views
Hard Problems in Pairings
I want to know whether the following problem is considered as a hard problem in complexity theory or not?
Given $g,g^a,g^b \in G_1$ (for unknown $a,b\in \mathbb{Z}_p^{\ast}$), compute $e(g,g)^{ab^2}\...
4
votes
5
answers
5k
views
Why do we use groups, rings and fields in cryptography?
I'm a student of Masters in Cyber Security. I have a habit to understand things from their first principles (at the very beginning). Kindly use any simple mathematical example to answer because I have ...
- 57
2
votes
1
answer
118
views
Software implementation of symmetric and asymmetric bilinear pairings
I have recently read a paper about pairings, which only implemented asymmetric bilinear pairings and it mentiond that $\eta_{T}$ pairing is the most efficient algorithm for symmetric pairings. I ...
- 75
0
votes
0
answers
129
views
How to prove possession of a CL signature in zero-knowledge?
Assume that we have the following signature scheme CL Signature:
Choose two cyclic groups $G = \langle g \rangle$ and $G_T = \langle g_T \rangle$ of order $q$, that have a pairing $e$.
Uniformly and ...
- 712
2
votes
1
answer
111
views
How to prove in zero-knowledge that the attributes of Pointcheval Sanders signature is the opening of a commitment?
In anonymous credentials schemes, it is possible to anonymously prove knowledge of a signature. Proposals for anonymous credentials with attributes also include a method for proving statements about ...
- 243
1
vote
1
answer
362
views
Can you use ECDSA on pairing-friendly curves?
I'm learning about Elliptic curve cryptography. If I understand right, ECDSA and other algorithms used in ECC are dependent on the curve chosen. So, before you want to use ECDSA, you first have to ...
- 13
2
votes
1
answer
392
views
Is BBS+ 1. a multi-messages signing protocol or 2. a group signature signed by a member of a group anonymously?
There's no doubt that the BBS Signature was born from this classic Short Group Signature paper in 2004. It's capable of Zero-knowledge.
In the paper, section 5, it describes how a member of a group, ...
- 123
1
vote
1
answer
92
views
Importance of supersingularity of elliptic curves
I'm struggling to understand the high-level idea of "Verifiable Delay Functions from Supersingular Isogenies and Pairings" (https://eprint.iacr.org/2019/166.pdf) by De Feo et al.
I will ...
- 143
2
votes
1
answer
97
views
In q-SDH problem, where are those points $\frac{1}{\beta+x}g_1$ or $g_1^\frac{1}{x+c}$ on elliptic curve?
For the q-SDH problem, given the generator $g_1$ as a point on the elliptic curve, I can picture the $\beta g_1, \beta^2g_1, ..., \beta^qg_1$ since we can simply do the point adding $g_1$ multiple of $...
- 123