3

Is it possible to build a bilinear map where the underlying group is an RSA group? I.e. $e: \mathbb{Z}_N \times \mathbb{Z}_N \rightarrow \mathbb{Z}_N$ where N is an RSA modulo? If we can build a nontrivial bilinear map over arbitrary RSA groups, then we can solve the DDH problem over a prime field. Here's how: The DDH problem is: given $g, p, g^a \bmod p,...


3

The first part of the question is answered in the comments. Regarding the second part, yes, indeed, you are right! It's a typo in the Pinocchio paper, Section 2.3. Protocol 1., you also linked. The problem is that the left hand side of the verification equation enumaretes the I/O related coefficients twice in the left wire polynomial, V, therefore $g^{v_0}.g^...


3

No. For example, these pairing-based protocols don't require trusted setup: BLS signatures; tripartite Diffie-Hellman, as mentioned in Elias' answer; some identity-based encryption schemes (when users are their own PKGs, e.g. when using IBE for forward-secure encryption); the Bünz–Maller–Mishra–Vesely polynomial commitment scheme. (This could in principle ...


3

The most general form of a bilinear map is $e : G_1 \times G_2 \to G_T$. We can categorize a scheme's usage of the bilinear map into 3 standard categories: Type 1: in addition to the bilinear pairing, the scheme requires efficiently computable homomorphisms $\phi_{12} : G_1 \to G_2$ and $\phi_{21} : G_2 \to G_1$. In other words, the scheme sometimes needs ...


3

That paper is misleading in several ways: The DSA vs BB comparison: it is unfair because it compares DSA with the "full" BB scheme, which does not produce shorter signatures. The same BB paper describes a "basic" scheme that has a signature that is half the size of DSA. That's the whole point of short signature schemes (being shorter than ECDSA/DSA). This ...


2

$E(\mathbb{F}_{p^k})[r]$: all elements $P$ of $E(\mathbb{F}_{p^k})$ such that $rP = 0$. In other words, all points whose order divide $r$. In protocols $r$ is usually prime, so that means all points with order $r$ and the point at infinity. $\pi_p$: the Frobenius endomorphism. This is a function that takes an elliptic curve point such that $\pi_p((x, y)) = (...


2

BLS12-381 is a Type 3 curve, yes. I'm not aware of any difficulty of assuming SXDH for BLS12 curves, and there's no reason BLS12-381 in particular would be special in this respect. (Almost all pairing-based protocols defined recently are designed for Type 3 curves, and almost all curves defined recently for pairing-based crypto are Type 3. If you come across ...


2

The linked paper is not about Elliptic Curves which relies on additive groups. It is about the multiplicative groups. For both of them the discrete logarithm is defined. There are common notations that confuse people about them. In the multiplicative version, the division is actually not a division like in the reals. It is the inverse in the group and ...


2

The paper writes $z^r \cdot G$; however $z^r$ is a member of the extension group $\mathbb{F}_{q^{12}}$, while point multiplication is formally defined over the integers; you ask "what are we supposed to do here?" Well, going through the paper, it appears that if we rewrite that equation to $h(z^r) \cdot G$, where $h$ is a function from $\mathbb{F}_{...


1

I've always used it as #1. Hyperledger Ursa has an implementation in Rust (see https://github.com/hyperledger/ursa/tree/master/libzmix/bbs). However, it is a type of group signature which allows the type of signing of multiple messages. When someone says to me group signature I immediately think your #2. If we look at a paper written by David Chaum (https://...


1

You cannot create a verifiable $Z$ but you can create a verifiable $W$ but you have to add public keys multiple times as well. So $W$ can be verified using a key $PK_a + 2*PK_b + 2*PK_c + PK_d$ if you had the same message or doing having multiple pairings for each repeated key in case of distinct messages


1

To the best of my knowledge, this hard assumption is introduced by Boneh and Boyen in this paper. But I don't think so the assumption that you mention being hard, because $c=0$ is a simple solution for it. Then the element $g^{\frac{1}{s}}$ should not publish. Also, this assumption is not bilinear because the challenge is an element in the cyclic group of $...


1

I do not have access to the paper you have linked, but I certanly can answer the first question and maybe answer the third question: $(\hat{u}, \hat{v}) \in G_2^2$ is a short version of $(\hat{u}, \hat{v}) \in (G_2 \times G_2)$ which is a short version of "$\hat{u} \in G_2$ and $\hat{v} \in G_2$". Since I don't have access to the paper I'm gonna make some ...


Only top voted, non community-wiki answers of a minimum length are eligible