Questions tagged [pairings]

Pairing-based cryptography uses bilinear maps to create a gap group that allows efficient constructions of certain primitives.

Filter by
Sorted by
Tagged with
3 votes
1 answer
101 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 ...
Chunchi Liu's user avatar
3 votes
1 answer
119 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 ...
popeye's user avatar
  • 95
1 vote
1 answer
70 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 ...
curious's user avatar
  • 6,150
1 vote
1 answer
52 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 ...
Manish Adhikari's user avatar
1 vote
0 answers
69 views
+50

One-More Computational co-Diffie-Hellman in asymmetric pairing groups

I am writing a paper and having one issue. In a part of protocol, I need to perform one step similar to OPAQUE to calculate, $s_{mi} = H_m(i)^{x_m}$, where ${x_m}$ is a server specific secret and ...
Manish Adhikari's user avatar
0 votes
0 answers
30 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 ...
Doron's user avatar
  • 99
1 vote
1 answer
57 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$...
l4rmbr's user avatar
  • 111
0 votes
0 answers
17 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?
Alex's user avatar
  • 11
1 vote
0 answers
24 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?...
Alex's user avatar
  • 11
3 votes
0 answers
75 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 \...
Dimitri Koshelev's user avatar
1 vote
1 answer
80 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....
user93353's user avatar
  • 2,199
0 votes
1 answer
32 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 ...
Rongkuan He's user avatar
1 vote
0 answers
83 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 ...
Ethan's user avatar
  • 121
1 vote
0 answers
50 views

Is bilinear pairing reversible?

Given $e(a,b)$ as known, can I get the value of $a$ or $b$?
mioz's user avatar
  • 11
1 vote
1 answer
42 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 ...
CPereez19's user avatar
  • 325
2 votes
1 answer
109 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 ...
Razor Sharp's user avatar
0 votes
0 answers
24 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 ...
Kanchan Bisht's user avatar
3 votes
1 answer
135 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 ...
tesoke's user avatar
  • 181
1 vote
1 answer
97 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 ...
Jeffrey's user avatar
  • 33
2 votes
1 answer
92 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 ...
Joseph Johnston's user avatar
2 votes
1 answer
461 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 ...
Chunchi Liu's user avatar
2 votes
1 answer
61 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 $...
Bean Guy's user avatar
  • 732
2 votes
1 answer
64 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) ...
ming alex's user avatar
  • 368
2 votes
1 answer
51 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. $...
heller's user avatar
  • 121
4 votes
1 answer
98 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]$? ...
Bean Guy's user avatar
  • 732
0 votes
0 answers
45 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 $(...
Bean Guy's user avatar
  • 732
3 votes
1 answer
127 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 ...
fgrieu's user avatar
  • 140k
2 votes
1 answer
80 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 ...
unsigned_int2's user avatar
1 vote
1 answer
171 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 & ...
user93353's user avatar
  • 2,199
3 votes
1 answer
108 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)...
user93353's user avatar
  • 2,199
2 votes
1 answer
200 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 ...
user93353's user avatar
  • 2,199
5 votes
1 answer
1k 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 ...
Xing Chang's user avatar
1 vote
2 answers
86 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: ...
xenon's user avatar
  • 225
6 votes
1 answer
206 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 ...
Dimitri Koshelev's user avatar
1 vote
1 answer
396 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 ...
Özgün ÖZERK's user avatar
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{...
fish_monster's user avatar
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?
fish_monster's user avatar
3 votes
1 answer
147 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 ...
fish_monster's user avatar
1 vote
1 answer
96 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 ...
zbo's user avatar
  • 75
0 votes
0 answers
72 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 ...
Shweta Aggrawal's user avatar
2 votes
1 answer
121 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]...
Foobar's user avatar
  • 247
1 vote
0 answers
43 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 ...
Sean's user avatar
  • 99
2 votes
1 answer
505 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 ...
ashizz's user avatar
  • 43
2 votes
1 answer
390 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 ...
user93353's user avatar
  • 2,199
2 votes
1 answer
344 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?
Ievgeni's user avatar
  • 2,575
2 votes
1 answer
397 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$ ...
ashizz's user avatar
  • 43
1 vote
1 answer
78 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 ...
Novice_researcher's user avatar
1 vote
0 answers
114 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)$ ...
A.Solei's user avatar
  • 405
1 vote
0 answers
237 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 ...
jessica Hu's user avatar
5 votes
1 answer
200 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?
Sean's user avatar
  • 99

1
2 3 4 5 6