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.


5

There is numerical evidence that for the vast majority of primes $p$, there exists $k$ making $q=2^k\,p+1$ prime. See first exceptions in A137715. The only practical way I see to find which $(p,k)$ make $q=2^k\,p+1$ prime in the question's context is testing $q$ for primality using a fast test. As noted in the other answer, sieving for small primes can be ...


5

What is meant by "$r$ may be chosen in a way dependent on $z$"? An hypothetical algorithm $\mathcal A_2$ breaking the strong RSA assumption has input¹ $(n,z)$ with $n$ generated by the RSA key generation procedure, and outputs² $(r,y)$ such that $y^r\equiv z\pmod n$, with the only other constraint on $r$ that $r>1$. Contrast with an hypothetical ...


4

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


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


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

Are there any zero knowledge protocols which do not rely on a group? It depends on your definition of "relying on a group". If you mean "doesn't rely on a group-based assumption like DDH, CDH or DLog or variants thereof", then yes. If you mean "doesn't use a group at some point" then no, because such a protocol would be unimplementable because the most ...


3

The claim is completely false. The security of DDH over appropriate composite-order elliptic curves is not only believed to hold, the assumption that it holds has been widely used in cryptography. To give a single famous example, the BGN cryptosystem was initially defined over composite-order elliptic curves (with a pairing), before being generalized a few ...


3

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


3

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


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

The immediately obvious solution would be this simple cut-and-choose protocol: Prover: selects a random value $v$ and sends the value $y = v^\ell$ Verifier: selects and sends a random bit $b$ Prover: if $b=0$, sends the value $t_0=v$. If $b=1$, sends the value $t_1=vu$ Verifier: if $b=0$, then verify that $t_0^\ell = y$. If $b=1$, then verify that $t_1^\...


3

This problem has been studied already; see this Wikipedia article. Does there a exist a prime $q$ such that $p = 2^kq + 1$ is also prime? A number $q$ such that $p$ is never prime is called a Sierpiński number; such numbers do exist, and some of them are prime. The smallest known such prime is $q = 271129$; the next known ones are $322523, 327739, ...


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

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


2

can we build the following algorithm: $$\mathcal{A}(g,g^x,g^{x^k},p,q) = g^{y^k} \text{ where } y = \bigg \lfloor x \cdot \frac{p}{q}\bigg\rfloor \in \mathbb{Z}_p$$ It would appear that such an algorithm that works for any input would allow us to compute discrete logs (hence we hope the answer is "no" in general, however it might be possible for ...


2

What does the order of $U(N)$ has to do with RSA key generation? The usual notation is $\Bbb Z_N^*$ for the multiplicative group modulo $N$, that the question names $U(N)$, and $\Phi(N)$ or equivalently $\varphi(N)$ for its order (number of elements), as given by Euler's totient function. $\forall x\in\Bbb Z_N^*$, it holds $x^{\Phi(N)}\equiv1\pmod N$. This ...


2

Why we don't use additive groups? Is it a security thing? Yes, it's a security consideration. If we used the additive group $(\Bbb Z_N,+)$ rather than $(\Bbb Z_N^*,*)$ for RSA, public encryption would go $M\mapsto C=e\,M\bmod N$ rather than $M\mapsto C=M^e\bmod N$. Problem is, decryption would be trivial since anyone with the public key $(N,e)$ could ...


2

This is not true. In particular, consider $4\in (\mathbb{Z}/5\mathbb{Z})^\times$. We have that $4^2 = 16\equiv 1\bmod 5$, so $\langle 4\rangle = \{1, 4\}$ is not the full group. The theorem you mention is known as Fermat's little theorem, and it states: $\forall x\in (\mathbb{Z}/p\mathbb{Z})^\times$, $x^{p-1}\equiv 1\bmod p$ As you mention, all elements ...


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

By the Chinese remainder theorem, we have that: $$(\mathbb{Z}/pq\mathbb{Z})^* \cong (\mathbb{Z}/p\mathbb{Z})^*\times (\mathbb{Z}/q\mathbb{Z})^* \cong (\mathbb{Z}/(p-1)\mathbb{Z})\times (\mathbb{Z}/(q-1)\mathbb{Z})$$ From this, we should be able to write: $$(\mathbb{Z}/pq\mathbb{Z})^* \cong \langle g_q, g_p\mid [g_q, g_p] = e, g_q^{q-1} = e, g_p^{p-1} = e\...


2

Just sample a random $x$, and $[(g^x \bmod p) \bmod H]$ will equal your target value $h$ with probability $1/H$. After trying $O(H)$ candidates you will find a preimage. Fine print: Technically speaking, the probability isn't exactly $1/H$. Each $h \in \mathbb{Z}_H$ has either $\lfloor \frac{p-1}{H} \rfloor$ or $\lceil \frac{p-1}{H} \rceil$ preimages under ...


2

A proxy re-encryption scheme is collusion resistant, if the proxy and a delegatee are not able to recover the secret key of the delegating party. Are you sure that definition makes sense? After all, if proxy has the Alice->Bob reencryption key, and Bob has his private key, then the two of them can jointly decrypt any message encrypted by Alice's public key....


1

wouldn't that just be quadratic time? No. TLDR: modular arithmetic. You may have an impression that it should be easy and takes a small number of steps. But the complexity comes from the fact that we use modular. In a normal arithmetic you know for instance that if $a < b$, then $g^a < g^b$ (for N). But in the modular arithmetic there are no such ...


1

Define the function $$\begin{align} f: G&\to G\\ x&\mapsto x^{\prod_i e_i} \end{align}$$ $f$ is injective. Proof: if $f(x)=f(y)$ then $x^{\prod_i e_i}=y^{\prod_i e_i}$, thus $(x\cdot y^{-1})^{\prod_i e_i}=1$, thus the order $k$ of $(x\cdot y^{-1})$ is a divisor of $\prod_i e_i$. Since the order of any group element divides the group order, $k$ is ...


1

Since this is a field, you know that the polynomial $x^2-2=0$ may have up to 2 roots, no more. You could use the quadratic formula (since the polynomial ring over a field is an integral domain) but this would require the extraction of a square root. But it is certainly more efficient than checking all elements. Also if if $a$ in $x^2-a$ is a square then you ...


1

Q3.) Would a small $g, g^{-1}$ have any impact to security? It would not appear so. It is easy to show that, if we had a generator $g$ that makes the Discrete Log (or the Computational Diffie-Hellman) problem easy, then the Discrete Log/CDH problem is easy with respect to any base $h$ that's within the same subgroup. Suppose we had a way that, given $g, g^...


1

However, in the case of elliptic curves, $h^x$ is interpreted as the point $h$ added to itself $x$ times, resulting in curve point, $[x]h$ That is incorrect; as you had stated previously: $h \in \mathbb{Z}_p^*$ is an element of order $q$. That is, $h$ is not a point on the elliptic curve; instead, it is a member of a finite field, and so $h^x$ is ...


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