7

The best algorithm for computing discrete logs in a well-chosen finite field $\mathbb Z/p\mathbb Z$, where the safe prime $p$ has no structure that can be exploited by the special number field sieve, is the general number field sieve, or GNFS for short. The GNFS costs $L^{\sqrt[3]{64/9} + o(1)} \approx L^{1.92999 + o(1)}$ bit operations, where $L = e^{n^{1/...


6

Yes. The subset of $\Bbb Z_n$ of integers that are relatively prime to $n$ (otherwise said: the set of $x$ in $\Bbb Z_n$ with $\gcd(n,x)=1$ ) form a group under the multiplicative law of $\Bbb Z_n$ (multiplication modulo $n$ ). That finite group is noted $(\Bbb Z_n^*,*)$ or just $\Bbb Z_n^*$, or $(\Bbb Z/n\Bbb Z)^\times$. It has $\varphi(n)$ elements, where ...


5

For every $y \in \mathbf F_p$, there is a unique $x \in \mathbf F_p$ such that $(x,y)$ is on the curve, namely $x = \phi^{-1}(y^2)$, where $\phi : x \mapsto x^3+1$. Adding the point at infinity, that gives $p+1$ points.


4

How is this done efficiently on the fly for Diffie Hellman? For Finite-Field Diffie-Hellman, you usually pick $p$ such that $q=(p-1)/2$ is also prime. Now Lagrange's theorem tells us that every element's order must divide the group order which is $p-1=2q$. This leaves us with four divisors: $1,2,q,2q$. Once you know that, you can simply test that your ...


4

Well, the group being isomorphic doesn't imply that the isomorphism is efficiently computable. If $G \simeq H$ via $\phi : G \rightarrow H$ and $\phi$ is computable, then indeed, DLOG is no harder in $G$ than in $H$ because you can transform the instance. In the case you mentioned, we have $G = \mathbb Z/(p-1) \mathbb Z$ and $H = (\mathbb Z/p\mathbb Z)^\...


3

TL;DR: Efficient algorithm only exist in specific cases. The problem, in its full generality (finite abelian groups) is equivalent to the integer factorization problem. How can we effectively compute the square root of an element in a group? One case where we can compute a square root is when the group order is known and it is odd. Any element $g$ in a ...


3

It's the size of the prime number of the underlying field in G1, G2 and GT. In BN256, G1 is $E(\mathrm{GF}(p))$, G2 is a subgroup of $E(\mathrm{GF}(p^{12}))$ (or $E'(\mathrm{GF}(p^{2}))$ when using a twist) and GT is a subgroup of $\mathrm{GF}(p^{12})$. Elements of G1 requires the same number of bits as $p$ for each elliptic curve point coordinate. Note ...


3

How many such Caley XOR tables are theoretically possible that hold such qualities for a 16*16 table? It is essential to define what we want to count. I read the constraints as A table of $r$ line and columns for an internal law $\boxplus$ on $\Bbb Z_r$ (the non-negative integers less than $r$), with line and columns in the same arbitrary order. More ...


3

In the algorithm, $p$ is the order of group, $x$ is solution. We rewrite $x = i * m + k $, but why do we make $m =\lfloor\sqrt{p}\rfloor$, rather than something else like $\lfloor {p/2}\rfloor$? The time taken by Big Step-Little Step is $O( m + p/m )$ (the $O(m)$ term comes from the time taken iterating through the various $k$ values, the $O(p/m)$ term ...


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^...


2

What you are asking is in some sense a tautology. In any group $G$, Abelian or not, the subgroup generated by an element $g \in G$ is Abelian. (Recall: the subgroup generated by $g$ is: $ \langle g\rangle := \{g^0, g^1, g^2....\} $ ). Hence, you can probably take your favourite DLP-based encryption scheme and implement it in $G$, without dealing with the ...


2

No, this is a known variation of the computational Diffie-Hellman problem, called Inverse computational Diffie-Hellman (InvCDH), according to which on input $g$, $g^{x}$, it is difficult to find $g^{x^{-1}}$. See section 2.2 at Variations of Diffie-Hellman Problem by Bao et al. for more info and problem reduction proofs.


2

With the bijection, you proved that for every $x$ there is a unique $x^3+1$. Now, for modulo an odd prime number $p$ the number of QR (quadratic residue) is $(p + 1)/2$ by Euler's criterion. Therefore these are the solutions for $y^2$s for your EC. For every $y$, $-y$ is going to satisfies the equation i.e. if $(x,y)$ is a point on the curve than $(x,-y)$ ...


2

SHA256(SHA256(x)) Would this be a bijective mapping? or Surjective mapping? SHA-256 is almost certainly not injective on 256-bit inputs, so it is almost certainly not a bijection or a surjection onto 256-bit outputs either. And if SHA-256 is not injective, then applying it twice can't be injective—if $x \ne x'$ are distinct preimages of $h$ under SHA-...


2

First of all, note that, SHA-256 operates on a minimum of 512-bit messages. The message is always padded to be a multiple of 512-bit ( see padding below). For double SHA256(SHA256(m)), after the first hash, the result is padded to 512-bit. padding: The SHA-256 message format |L|1|0..0|message size in 64 bits|. L is the original message bits to be hashed, it ...


2

Yes, such a group is useful. In particular, when $N= p\cdot q$ where $p,q$ are both strong primes (i.e. $p=2p'+1,q=2q'+1$ where $p',q'$ are also prime numbers). Discrete logarithm in the prime order cyclic groups (order-$p'$ and order-$q'$) is believed to be hard. Such a group is called a group with hidden order. A few examples of application: Fujisaki ...


1

Try doing some examples. Sage (free and open source software) is very helpful here. I think the simplest example is $E : y^2 = x^3 + 1$ over $\mathbf{F}_5$. This curve has embedding degree $k=2$. sage: q = 5 sage: k = 2 sage: F.<z> = GF(5^2, modulus = x^2 + 2) sage: E0 = EllipticCurve(GF(5), [0,1]) sage: E = EllipticCurve(F, [0,1]) sage: E0 Elliptic ...


1

Any finite setting with addition that distributes over multiplication where neither operation loses information—except multiplying by zero—necessarily has a prime characteristic, which is the number of times you can add 1 to itself before you get back 0. Further, the size of any finite field is some power of its characteristic, so the size of any finite ...


1

The problem 'given a group and the elements $g, g^x, g^y$, find $g^{xy}$' is known as the Diffie-Hellman problem (or, more precisely, the computational Diffie-Hellman problem). As for how difficult it is, well, we typically work with groups where this is difficult (by design; we often need to assume that the DH problem is hard). As for how it might be ...


1

The key point in RSA is the fact that inversion in modulo $|G|$ is hard, of course other groups are a priori okay to build a secure encryption scheme. For example $U_{pqr}$, with $p, q, r$ large primes seems to be okay. But it will be probably less efficient (keys and ciphertexts will be probably larger for the same level of security). Of course, it is not ...


1

A GUESS: the author meant that three numbers $a,b,c \in \mathbb{Z}$ such that $$g^a\cdot h_1^n \cdot h_2^c =1$$ are infeasible to compute. While the term "orthogonal" seems inappropriate, This is a fairly standard assumption.


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

It is correct to me. Polynomial is not evaluated in the elliptic curve group $G$, but in $F_q$ (where $q$ is the order of $G$), which is a field because $q$ is a prime number. To be clearer, I add brackets to the equation you gave: $$X_i = \prod_{j=0}^{t-1} (C_j)^{{i}^j} = \prod_{j=0}^{t-1} (g^{\alpha_j})^{ i^j}= (g)^{ \sum^{t-1}_{j=0} \alpha_j i^j}$$ You ...


1

I suppose it is a short Weierstrass curve. There are several possibilities: Projective coordinates: a point $P = (x,y)$ is stored with three coordinates, $X$, $Y$ and $Z$ that satisfy $x=X/Z$ and $y=Y/Z$. We note $P=(X:Y:Z)$. That means a point can have more than one representation (it is the same as fractions, $\frac 3 4$ is the same as $\frac{15}{20}$). ...


1

The prototypical example of a group in cryptography is a cyclic group. You can write this in a variety of ways, so I'll go through a few quickly. Additively: Consider the group $\mathbb{Z}/n\mathbb{Z}$ under $+$. This forms a group, and it's a cyclic group generated by $\langle 1\rangle$ (subject to the relation that $n\cdot 1 = 0$). Note that the "...


1

In a generic group, I don't know if it exists really a generic algorithm to solve your problem, but if you group is also a field ($\mathbb{Z}_p$ with $p$ a prime number for example), then you can use the Berlekamp algorithm to factorize $X^2 -x$ where $x$ is your element. I made an error, I've deleted the wrong part.


1

Since $\gcd(2,467)=1$, one can observe using Fermat's little theorem that $4^{233}\pmod{467}=2^{466}\pmod{467}=1$. Thus, $$g^{a_1}=4^{400}=4^{233+167}\equiv\underbrace{1\cdot4^{167}}_{=g^{a_2}}\pmod{467}=89.$$ This results into identical session keys (shared secrets) $S=(g^a)^b=89^{134}\equiv161\pmod{467}$.


1

My understanding of elliptic curves has me thinking that the range of accepted values for scalar point multiplication should be in [0, group_order]. Actually, that's not the case - the point multiplication $xG$ is well-defined for all integer values of $x$. While it could accept larger values since $(n+x)G=xG$, it would be wasteful computationally so I'...


1

Well this answer is a bit of a fishing game, but I have a few leads after some thought and maybe they will help. The binary operation $$ a*b = \underbrace{a^{a^{a^{\dots}}}} $$ where the chain is repeated b times, has been studied before. If this is what you mean by "Self-Power Map," then Tetration (and the associated hyperoperations) have been studied for ...


1

First of all, the idea of proving element equality does not make much sense, since that would reveal the secret element. $prove(X == T)$ with secret $X \in G_1$ and public constant $T \in G_1$ reveals the value of $X$. What I was looking for instead is $prove(g_1^x == T)$ with public constants $g_1, T \in G_1$ and secret scalar $x$. It tuned out that type 2....


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