Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [group-theory]

Groups are an abstract algebraic concept based on a set and a group law (a binary function which closes the set).

-1
votes
0answers
26 views

What are some potential applications of trilinear mappings?

In "Applications of Multilinear Forms to Cryptography" Boneh and Silverberg give "one-round n-way Diffie-Hellman key exchange protocol" as a potential application of n-multilinear mappings. If we ...
3
votes
0answers
41 views

Is there a bilinear map on a non abelian group or non cyclic group?

I've recently been studying a pairing map on cryptography. In usual definition, a pairing map is always defined on the cyclic group G. Is it possible to construct a bilinear map on a non-abelian group ...
0
votes
0answers
105 views

Proof in RSA encryption over multiplicative group

I everyone, I am considering an RSA encryption over the multiplicative group $G = (Z/nZ)$ of the ring $Z/nZ$, where $n = pq$, and $p$ and $q$ are distinct odd primes. First, I want to prove that $H=...
0
votes
0answers
34 views

Attack against factorization of $p-1$ of $\mathbb{Z}_p^*$ group

It is said that for the group $\mathbb{Z}_p^*$, the factorization of $p-1$, is critical. If $p-1$ has some small factors $q_1, q_2, q_3, q_4$, then when we transmit $g^x \bmod p$ where $g$ is a ...
7
votes
1answer
561 views

Which properties of a group are used in the steps of Diffie Hellman?

I’m trying to understand which properties of a group are used in DHKE at each step. For example, Alice and Bob’s public keys appear to only use the closure property of a group and maybe identity (e....
1
vote
1answer
25 views

How is the generator used in Feldman's Verifiable Secret Sharing scheme determined? [duplicate]

According to the Wikipedia description of Feldman's VSS scheme First, a cyclic group G of prime order p, along with a generator g of G, is chosen publicly as a system parameter. (Typically, one ...
0
votes
1answer
93 views

If I know an element and it's inverse, can I learn the modulus?

If I know an element $x$ in a group, and it's inverse $x^{-1}$, can I guess the modulo, or with a probability?
5
votes
1answer
75 views

Cyclic Groups Other than $\mathbb{Z}^*_n$ or Elliptic Curves

I see two types of cyclic groups are most commonly used in cryptography: modulo multiplicative group of integers with prime order elliptic curves Are there any other cyclic groups used in ...
-1
votes
1answer
51 views

find additive inverse of modular arithmetic [closed]

For a set to be called as a ring, it should have the following properties closed commutative associative Identity existence Inverse existence but how is Z7 a ring, as there aren't any inverse ...
2
votes
1answer
62 views

How to compare the order of elements in cyclic groups?

In a cyclic group with randomly looking behavior like the one used in secp256k1, is there any known efficient algorithm to compare the order of two randomly given elements $P_1$ and $P_2$ and find out ...
2
votes
2answers
61 views

Rational exponents on group generators

In elementary concepts, mostly scalar exponents shows up in group operations: $g^x$ As one may encounter in more advanced papers, there are rational exponents over generators. Simply seems like: $g^...
0
votes
0answers
35 views

Algorithm to compute DLOG for elliptic curve $E(F_p)$ with order p

I was reading about elliptic curves in this pdf. Page 55 of the pdf states that if number of points on elliptic curve #$E(F_p) = p$, then there exists a p-adic logarithmic map that homomorphically ...
2
votes
1answer
104 views

Generators and Multiplicative group $\mathbb{Z_7}$

In the multiplication table for $\mathbb{Z^*_7}$, each row has all the elements of the set My questions are: is each element a generator here? if not why? is an element considered as ...
0
votes
0answers
80 views

Size of group for Elliptic curves vs RSA for equal security

For my research, I would like to compare the efficiency of a scheme when instantiated with Elliptic curves and RSA. So, I would like to know a "latest" comparison (as of 2018) on what group sizes of ...
1
vote
1answer
65 views

Proof one-time pad is perfectly secret with eavesdropping game definition

I have the following definition of perfect secrecy (please assume that the probabilistic version is not available): If we consider the eavesdropping game given by: $$\begin{array}{|r | r|} \...
2
votes
1answer
151 views

What role does Representation Theory play in Cryptography?

Shannon said that every cryptosystem can be expressed as a system of linear equations with a large number of unknowns of complex type. In cryptography groups are used since they are a natural ...
0
votes
1answer
55 views

Key exchange protocols non-reducible to groups

Some questions I have ended up wondering about while reading through many of key-exchange protocols are: Is there an intrinsic reason, why most key exchange protocols use group-based approaches apart ...
-1
votes
1answer
34 views

Operation Table for Permutation Group

I cannot seem to figure out how the operation table for this permutation is formed. Is it multiplying each index and doing modulus? I can't seem to figure out. This is a Table 4.2 found in "...
1
vote
0answers
58 views

Drawbacks of Schnorr Authentication that require Fiat-Shamir and Random Oracles?

I've been going through G. Maxwell's paper on the Borromean Ring Signature, and I don't fully understand this part on Schnorr Signature. If some could explain it more intuitively thank you. "...
-1
votes
1answer
56 views

What is the difference between these cyclic groups

$\mathbb{Z}^*_p$ vs $\mathbb{Z}^*_{p-1}$ vs $\mathbb{Z}^*_{p^2}$ vs $\mathbb{Z}^+_{p^2}$ I know $p$ is the value. The value create must be coprime to $p$. Does that mean that the value create must be ...
1
vote
1answer
62 views

Is this problem same as discrete logarithm?

Given $g,h\in\mathbb Z_p$ where $g$ generates $\mathbb Z_p^\star$ Discrete logarithm problem is to find $z$ such that $g^z\equiv h\bmod p$ holds. Take the problem given $g,g',h$ where $g^z\equiv h\...
5
votes
2answers
880 views

Why do algebraic proofs apply to cryptography?

How do we know that the number theoretic and algebraic results used in cryptography provide a perfect model for the behavior of integers as implemented in computers? Does there exist a bijection ...
4
votes
1answer
315 views

Solving the discrete logarithm problem for a weak group

I was reading an answer about an attack on a weak group for the discrete logarithm problem and wanted to formalize and verify that the attack was correct. That is, that it was guaranteed to always ...
1
vote
1answer
92 views

bilinear maps rules

A bilinear map has to satisfy this property: $e(aP,bQ) = e(P,Q)^{ab}$ for all $P,Q \in \mathbb{G} , a,b \in \mathbb{Z}_q$ so far so good. My question now is related to this paper: https://eprint....
0
votes
0answers
50 views

Bilinear groups

I am reading my first cryptography paper and actually I am having problem understanding it. Maybe you can help me and push me into the right direction. This is the paper: http://ink.library.smu.edu....
5
votes
1answer
89 views

Checking if discrete logarithm is $\geq\frac{\varphi(p)}2$ in polynomial time?

Given $p$ a prime, $g$ generator of $\Bbb Z_p^*$, and $h\in\Bbb Z_p^*$, that uniquely defines some $z\in[0,\varphi(p)[$ such that $g^z\equiv h\pmod p$. Is it possible to determine in polynomial time ...
4
votes
1answer
112 views

Using multiple permutations to strengthen the security of a cipher

In one book it says a set of permutations with the composition operation is a group. This implies that using two permutations one after another cannot strengthen the security of a cipher, ...
0
votes
0answers
46 views

Shor's algorithm: Similarities between exponent r and Carmichael's function

I'm trying to learn Shor's algorithm. In the explanation section on the Wikipedia article, there is a paragraph - The integers less than $n$ and coprime with N form the multiplicative group of ...
0
votes
1answer
214 views

Elliptic Curve - Divide by 2

Can anyone tell me the specific equations and steps for dividing a point on an elliptic curve by 2? For instance, I have the point $(P_x, P_y)$, and I would like to find the point $(R_x, R_y)$ which ...
1
vote
1answer
193 views

How to select elements randomly from a multiplicative group Zn*

I am working on a problem in which I have two large safe primes say p and q randomly selected each of 512 bits. I have generated ...
14
votes
2answers
2k views

Why are finite groups used in cryptography?

Most of the cryptographic schemes I know are all based on group theory, e.g. they use finite groups. Can someone explain why is that the case? And why not base the schemes on elements and operations ...
1
vote
0answers
104 views

discrete logarithm vs normal logarithm [duplicate]

Crypto schemes normally use discrete logarithm instead of normal logarithm. I think this has to do with the fact that discrete logarithm is hard to solve while normal logarithm isn't. Can someone ...
3
votes
1answer
380 views

Discrete logarithm weak group

I'm looking for weak groups in discrete logarithm, that $x$ can be extracted from $Y$ in polynomial time where $Y \equiv g^x \pmod{p}$ . I thought one way is to produce a prime $p$ that $p-1$ is an ...
0
votes
1answer
110 views

Can we prove $(a,b,c,d)$ is of form $(g,g^x,g^y,g^{xy})$ without knowing $\phi (N)$?

assume $N=pq$ where $p$ and $q$ are two large prime numbers and all computations are modulo $N$. given $\phi(N)$, one can prove that the tuple $(a,b,c,d)$ is of the form $(g, g^x,g^y, g^{xy})$, i.e....
2
votes
1answer
135 views

What is the correct elliptic curve representation?

I'm studing the basics of elliptic curve from various resource some more mathematical someone more practical. I know that the equation where the elliptic curves come from is the Weistraß equation $$...
1
vote
0answers
88 views

Why do elliptic curves require fewer bits for the same security level?

I'm studying the basics of cryptography and I didn't understand why elliptic curves use fewer bits. For example, finite-field Diffie-Hellman needs at least 1024 bit and it's a DLP, but elliptic ...
3
votes
1answer
69 views

Question about the location of the r-torsion in the quotient group used in the Tate pairing

I'm working through Pairings for Beginners by Craig Costello, and am trying to understand the Tate pairing. He defines $rE = \{r*P | P \in E(\mathbb{F}_{q^k})\}$ and then forms the quotient group $E(\...
3
votes
1answer
132 views

Why work in a subgroup for Naor and Pinkas oblivious transfer?

In section 4 (protocol 4.1) of the paper by Naor and Pinkas [1], why did the authors decide to operate in a subgroup? When they say "the messages are in the subgroup" does that mean $x, y, z_0, z_1$, $...
7
votes
1answer
589 views

When to use safe prime or Schnorr group

Protocols that use $\mathbb{Z}_{p}^*$ arithmetic often choose $p$ to be a safe prime ($p = 2q + 1$, for prime $q$) or to have the Schnorr group form ($p = rq + 1$, for prime $q$). I understand that ...
1
vote
0answers
214 views

Can Bitcoin mining solve Graph Isomorphism-related problems?

Given a cryptographic hash $H:\{0,1\}^*\mapsto\{0,1\}^N$ and data $D\in\{0,1\}^*$, the Hashcash/Bitcoin Proof-of-Work entails finding a nonce $x$ such that $H(x\Vert D)$ begins with $d$ leading zeros, ...
1
vote
1answer
126 views

Sum probability

if $a,b,c$ are selected at random from a large cyclic group, then what could be the probability that $g^{a+b}$=$g^c$? it simply corresponds to the probability that multiplication of two random ...
11
votes
0answers
230 views

Finding $x$ such that $g^x\bmod p<p/k$?

In a Schnorr group as used for DSA, of prime modulus $p$, prime order $q$, generator $g$ (with $p/g$ small), how can we efficiently exhibit an $x$ with $0<x<q$ such that $g^x\bmod p<p/k$, for ...
1
vote
0answers
136 views

Is there a flaw in this ring signature scheme? [closed]

Having read some papers about RSA accumulators applied to ring signatures schemes, I ended up thinking why would we need to accumulate all the members public keys for our specific use case. So I came ...
0
votes
1answer
66 views

What does the “description of group $G$” includes?

I was reading here:second discrete log meaning in the solution and also here:key generation, first point where the say given $G$ (or its description). My question is what does this description ...
4
votes
1answer
75 views

Does pairings based cryptography inherently require a CRS/trusted setup?

In all algorithms I've seen that rely on pairings-based cryptography (some examples: snarks without PCPs, more snarks, sublinear ring signatures), a common reference string is required. Is this always ...
1
vote
2answers
205 views

Elliptic Curve Point at Inifnity in Projective Coordinates

I'm implementing an elliptic curve system primarily for ECDSA verification. I've evaluated different point representations and decided that using Jacobian projective coordinates suits best for my ...
0
votes
1answer
228 views

Number of generators of an elliptic curve

Consider the elliptic curve E:$y^2 = x^3 + 3x + 11\,\, mod\,\, 19$. Two questions: Let the cardinality of the set of points on the elliptic curve( including $O$ ) be $|E| = 25$. How many points are ...
3
votes
1answer
296 views

On getting beyond LSB in discrete log

In discrete log we employ sophie germain primes $p=2q+1$ where $q$ is a prime. Then we know least significant bit $x_0$ in $$g^{2x+x_0}=h\bmod p$$ where $2x+x_0$ is discrete logarithm of known $h\...
0
votes
2answers
52 views

A Question about Notations and Groups

Please consider the following question: Determine the order of all the elements of the following multiplicative groups. You can write a C or Java program to do this. a. $Z_{21}^*$ b. $Z_{23}^*$ Now ...
1
vote
2answers
409 views

RSA keys are multiplicative inverse in mod phi(n), but also in mod n?

I understand that the RSA keys $pk$ and $sk$ are choosen such that one is the multiplicative inverse of the other, in $\mod \phi(n)$ But for the encryption and decryption to work, in other words, ...