# Tag Info

8

The group you're working with does not have order $p$. In discrete log schemes, you're not working in a finite field, $F_p$, but rather a multiplicative group $1,...,p-1$, which has order $p-1$. Since $p$ is a prime, $p-1$ is composite (as long as $p > 3$). Group theory tells us that there is a subgroup of size $d$ for every $d$ that divides $p-1$.$^{1}$ ...

5

Abstract algebra basically comprises Groups, Rings, Fields, Vector Spaces, Modules, and many other algebraic structures. It is not only useful in Cryptography but in Channel Coding, in the branch of Chemistry and Physics too. It is a tool like Groups where you can do arithmetic and algebraic operation under a closed set. One can compare two algebraic ...

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

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

For something to be a group, it must have an identity. This is a definition. The order of an element, $g$, in a group is defined to be the smallest positive number $n$ such that $g^n = 1$, where $1$ is the identity of the group. By this definition, the order of the identity in any group is $1$.

4

One relevant point is that if $p-1$ is not of a form like $2q$ for $q$ prime, then it could be difficult to find the multiplicative order of an element. You can't use Lagrange's theorem to determine the order if you can't factor $(p-1)/2$, but the mere fact that you haven't yet found a small factor wouldn't show that one doesn't exist. Using a $p$ where $p-1$...

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

4

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

4

Yes, by Lagrange's Theorem in the group theory, the order of any element must divide the order of the group. Therefore, except for the identity element, which has order 1, all other points can be a generator. If you define a protocol, you need a common agreement and the generator is a part of this. If you don't include it in the specifications you need to ...

3

The most common proposals around non-commutative cryptography have been around braid groups. Its proponents have struggled to find parameter sets that are agreed to resist security analysis. Recent proposals have included the algebraic eraser key establishment system and WalnutDSA, a signature scheme that was entered in the NIST post-quantum crytpography ...

3

Lets say I have $g^x \bmod p$ and $g^{xy} \bmod p$. How can I efficiently obtain $g^y \bmod p$? We hope that there is no efficient method (without using knowledge of $x$ or $y$) Here's why: if you can solve that problem, you can solve the (computational) Diffie-Hellman problem; here's how: Suppose that you did have an Oracle that, given $g, g^x, g^{xy}$, ...

3

To extend kelalaka's answer, if $p$ is a safe prime (that is, if $p = 2q+1$ with $q$ prime), then: If $p \equiv 7 \pmod 8$, then the order of $g=2$ will be $q$ If $p \equiv 3 \pmod 8$, then the order of $g=2$ will be $2q$ If $p = 5$ (the only other possibility), then the order of $g=2$ is 4 (that is, $2q$)

3

The answer to your question can be found in the paper Why Textbook ElGamal and RSA Encryption Are Insecure by Boneh et al. It is an easy paper to read and worthwhile going through the details there.

3

In the case of Diffie-Hellman Key Exchange (DHKE or DH) in the multiplicative group $\mathbb Z_p^*$, the recommendable practice is to pick a prime $p$ and generator $g$ from RFC 3526, which gives these parameters for bit size $k$ of $p$ in $\{1536,2048,3072,4096,6144,8192\}$. These $(p,g)$ obey the criterion below: $p$ is a prime such that $q=(p-1)/2$ is ...

3

Why is a point explicitly hard-coded as the generator of the group Because, while any non-neutral element would serve as a generator, there has to be an agreement about which generator would be used (at least for most cryptographical operations). To take the simplest case, consider DH (not that you'd want to use BLS12-381 to do DH); one side picks a random ...

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 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.... 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 Is it safe to use the cyclic group of order$p-1$instead of one with order$q$in ElGamal encryption? No, for small values of$p$. This is the only security issue in the question's example. For modern security,$p$should be at least in the order of$2048$‑bit (rather than$4$‑bit for$p=11$in the question), and not close to a prime power. Anything below ... 1 In case you would read Rusian: a Diffie-Hellman -like common key from non-commutative group operation. http://mi.mathnet.ru/dan5041 http://www.mathnet.ru/rus/person17348 1 Public key exchange using semidirect productof (semi)groups by Habeeb et al https://eprint.iacr.org/2013/226.pdf 1 A generator$g$means that$g$generates the group$\langle g \rangle =G$. Therefore the order of the group$ord(G)$is equal to the order of the generator$ord(g)$. If$2$( or any other element) is not a generator that is$\langle 2 \rangle \neq G$then the element$2$forms a subgroup under the group operation. Then the order of$2$must divide the order ... 1 According to Wikipedia (with two articles sourced): Computing the discrete logarithm is the only known method for solving the CDH problem. But there is no proof that it is, in fact, the only method. It is an open problem to determine whether the discrete log assumption is equivalent to the CDH assumption, though in certain special cases this can be shown to ... 1 For finding the maximum length cycle, it is taken as finding the maximum solution to the two congruence relations. But since these are congruent relations how can we justify that the maximum will give the answer relevant to the longest cycle? It looks like it shouldn't. I'm pretty sure I was visualizing cycles in the Cayley Graph as being paths in the ... 1 In mathematics, every group need and identity element. The points on the elliptic curves forms a group. Therefore they need an identity element, too. The identity element is determined by the addition law of the curve. Some curves need a point at infinity$\mathcal{O}$as the identity element (neutral element). In the Edwards curve, the neutral element is ... 1 It depends on whether the pairing is a type 1 pairing or some other type of pairing. In a type 1 pairing,$S$is a multiple of$P$. In any other type of pairing,$S$is not a multiple of$P$. 1 The Decisional Diffie-Hellman assumption, on which the key-exchange would be based on does not hold in$\mathbb{Z}_q^*$. The reason is that the Jacobi symbol "leaks" information about the shared key. Therefore one, instead, works with the subgroup of$\mathbb{Z}_q^*$of order$p$, which is intuitively obtained by "quotienting out" this ... 1 The$\chi$function is defined and analyzed in Joan Daemen Ph.D. Thesis Cipher and Hash Function Design Strategies based on linear and differential cryptanalysis, 1995 Chapter 6: Shift-Invariant Transformations (SIT) is where the theory is mentioned. I'll provide a glimpse of it (lots of definitions and results). The properties of SIT that make them useful;... 1 The general algebraic question is multifaceted and can be quite complicated. Some depend on vector space, some on extension field properties. As mentioned in the comments checking the property can be simpler. I answered a related question Examples of multi output bit balanced Boolean functions Nyberg’s articles mentioned there are K. Nyberg, Differentially ... 1 fgrieu's answer in algorithmic shape: Given is prime$p$and multiplicative group$(\Bbb Z_p^*, \cdot)$. 1.) Find all prime factors$\{p_1,p_2,...,p_k\}$of$p-1$. 2.) Iterate through$g = 2,3,... $until a generator is found, where$g$is a generator of$(\Bbb Z_p^*, \cdot)\$, iff \forall i\in\{1,...,k\}: g^\frac{p-1}{p_i}\neq 1 \mod p \end{...

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