Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

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

Filter by
Sorted by
Tagged with
0
votes
1answer
66 views

Order of subgroups formed by Elliptic Curves with a Cofactor

In this question: Why are the lower 3 bits of curve25519/ed25519 secret keys cleared during creation? The answer indicates that the order of all points on the curve over the finite field ...
1
vote
1answer
53 views

Why do we use prime numbers apart from hard factorization?

Why are prime numbers important in cryptographic constructs? I am not interested in RSA examples where factorization is the hard problem itself, that makes sense. However wherever I go I encounter ...
0
votes
0answers
21 views

What is the current state of the Conjugacy Search Problem in Matrix and Permutation Groups?

It results that I have come with a mathematical approach to solve the CSP (Conjugacy Search Problem) where the platform group $G$ is either a permutation group or a Matrix Group. From my part I ...
0
votes
1answer
34 views

Multiplying between generators degree

I have to elements of multiplicative group of finite field with generator g - $$g^x,g^y $$ Can I get? $$g^{xy} $$
3
votes
1answer
87 views

Is there another group structure that is suitable for RSA other than $U_{pq}$?

I know that calculating the cardinality of $U_{pq}$ is infeasible and therefore it is extremely hard to break a code using Lagrange's theorem. But later on my studies i realized main principle of RSA ...
0
votes
1answer
36 views

Orthogonal generators of a group in Lelantus protocol

In the Lelantus Paper, the authors mentionned this: In our case, the commitment key ck specifies a prime-order group G and three orthogonal group generators $g, h_1$ and $h_2$. G is mentioned in ...
2
votes
1answer
53 views

Variants of Bilinear Diffie-Hellman Assumption

Could someone point me to the paper/reference where the following variant of q-strong Bilinear Diffie-Hellman assumption was used? Given $s \in \mathbb{Z}_p^*$ and $g, g^{\frac{1}{s}}, g^{s}, g^{s^2},...
0
votes
1answer
40 views

How can we evaluate a polynomials in a group instead of a field? (verifiable secret sharing on elliptic curves)

I am trying to understand how we can have cryptographic schemes that builds on both secret sharing, which is build on top of a finite field, and bilinear maps, which are built on top of elliptic curve ...
0
votes
1answer
50 views

How to represent the point-at-infinity(Elliptic Curves) in code? [duplicate]

I am writing code for Elliptic Curve Cryptography. I have a class class EllipticCurvePoint. ...
2
votes
2answers
158 views

Would SHA-256(SHA-256(x)) produce collisions?

Was reviewing some Bitcoin public-key hash literature and the use of RIPEMD-160 and the SHA-256 as below: RIPEMD160(SHA256(ECDSA_publicKey)) The Proof-of-work ...
0
votes
0answers
46 views

Difference in elliptic curve order and finite field size [duplicate]

Must the prime finite field, Fp, an elliptic curve is defined over always have a greater number of elements than the cardinality of an elliptic curve. For example, If I have ...
0
votes
1answer
83 views

Is modulus a prime number important for non-symmetric cryptology?

From this link Generation of a cyclic group of prime order we know how to generate a prime order group. This illustrates why a prime order group is important. But why is modulus a prime number ...
1
vote
1answer
88 views

Calculation of the order of the cosets used in defining the Tate Pairing

I'm working through Pairings for Beginners by Craig Costello, and am trying to understand the preamble to the Tate pairing. (See p. 70 ff., section 5.2 of of the PDF.). I'm having trouble following a ...
0
votes
2answers
85 views

Why are some group representations much easier to compute discrete logarithm for? [duplicate]

The multiplicative group mod $p$ is isometric to the additive group mod $p-1$, yet computing discrete logarithms in the additive group is easy and completing discrete logarithms in the multiplicative ...
3
votes
2answers
232 views

How can we effectively compute the sqrt of some element in the group?

I only know one way, if this group is a cyclic group, and we know the element can be expressed in $g^m$, then $g^{(m/2)}$ is the answer. Another question, if $m$ is an odd number, can we be sure ...
3
votes
0answers
117 views

Are there any cryptographic methods which use multiple cyclic groups?

For some cryptographic methods you can construct them. e.g. elliptic curves (product of two cyclic groups) or Diffie–Hellman (can be product of n-cyclic groups). But they have no usage because at a ...
2
votes
1answer
65 views

Calculating G for a give cyclic group mod P

For DH key agreement, one must begin with a generator of a cyclic group g. However, intuitively to me at least, it seems that g ...
0
votes
1answer
97 views

Is that possible to calculate modular inverse of a point on elliptic curves?

Imagine that you are given a point $P$ so that $P=a\times G$. If you have no knowledge of $a$ is that possible to calculate point $I$ so that $I$ is the modular inverse of $P$? We know that over ...
-2
votes
1answer
70 views

Is permutation conjugate search problem many answer? Are there many answer equal? [closed]

If conjugate search problem of permutation is difficult , then there are next cryptosystem will appear. A=XYX−1,B=XZX−1,Y and Z are public key.And X is secret permutation. then encryption is C=...
0
votes
0answers
35 views

How to encrypt a small number of identities (which are related to each other)? / Which algorithm has the smallest bit-length?

I'm looking for an encryption with as small numbers as possible. Given a small group of identities ($G$) (e.g. numbers from $1$ to $N$). Given one entry (or a small number) $e_i$ allows to compute ...
5
votes
0answers
90 views

Variant of Pollard rho using small factors of p - 1

Given an integer $N$ to factor which is divisible by some prime $p$, suppose you know (or guess) that $p - 1$ has a few small factors, e.g. $3, 2^2, 5$. Define $B$ as a product of small prime powers ...
0
votes
1answer
86 views

Why are the session keys in DHKE for different values of 'a' the same?

In a DHKE scheme with the a prime p = 467. an element g = 4. The element 4 has order 233 and generates thus a subgroup with 233 elements. after Computing the common key for A. a=400, b=134 B. a=167, b=...
2
votes
1answer
64 views

Why does Ed25519 scalar multiplication allow values larger than the subgroup order?

The GeScalarMultBase function is documented like so. From the way it is documented we see that it expects a little-endian value and has a precondition that constrains the range it accepts. ...
3
votes
0answers
91 views

Group Rings on Cryptography

Let $R[G]$ or $RG$ be the group ring where $R=F_q$ and $G$ is any group. Let $Dim(V)=\vert G \vert$. It's clear that $V$ has $\vert R \vert^{\vert G \vert}$ distinct $\vert G \vert$-tuples. This ...
0
votes
1answer
288 views

What's the number of unique possible Cayley tables in a 16*16 grid for XOR'ing single hex characters?

A few days ago, I designed and s-box then derived the following Cayley table of all possible XOR outputs of hex digits in the range of ${2^4}$ and was curious how many such "valid" possible ...
3
votes
1answer
130 views

What can be said about the self-power map on groups based on DLP?

Introduction I've been playing with group representation theory some time, concretely representing groups as permutation groups (Cayley's theorem), where the group $G$ has an embedding into the ...
1
vote
1answer
48 views

How to prove element equality in G1 using Groth-Sahai proofs

In the BeleniosRF e-voting scheme, Groth-Sahai proofs with the "Instantiation based on the SXDH assumption" are used (see https://eprint.iacr.org/2007/155, version 20160411:065033, page 24). In the ...
2
votes
1answer
153 views

What does the number 256 in pairing curve BN256 indicate?

There are many pairing based elliptic curves like MNT curves, BN curves, SS curves etc., When we say BN256 curve, what does the number 256 indicate? Is it some group order or number of bits required ...
0
votes
0answers
29 views

Is there any property of the product you can predict before using $n$-times generator $g$ $\mod P$? Can any $n$'th element have a certain property?

Given a value $v$ which is in same group as the generator $g$ modulo prime $P$. The group size is a prime $s$. $v = g^a \mod P$ Only known values are $v,g,P,s$. Some (possible) computation of other ...
0
votes
1answer
34 views

Which is the fastest way to find a member of a subgroup with known size modulo prime $P$, with know factorization of $P-1$?->$x$ with $x^s \mod P = 1$

Assuming you know the factorization of used prime $P-1$ $P-1 = s \cdot f_2\cdot f_3...f_i$ Now you want to find a member of a subgroup $\mathbb{Z}_s$. This means any $x$ with $x^s \equiv 1 \mod P $ ...
6
votes
1answer
103 views

why a group used in cipher based on DLP must be Abelian group?

I can't understand it because $(g^x)^y=(g^y)^x$ in nonabelian group too. thank you very much for read my question
3
votes
0answers
76 views

Doubt in computing $g^\frac{1}{\delta+x}$ where $x \in \mathbb{Z}$

I was going through Zero Knowledge Set Membership and came across the following: Given $x \in \mathbb{Z}$ and $g$ is the generator of a multiplicative group $\mathbb{G}$ how do we compute $g^\frac{1}{...
1
vote
0answers
112 views

How do pairings behave on G2/twist points off the prime order subgroup?

$\newcommand{\F}{\mathbb{F}}$ Consider the ate pairing defined on a curve $G_1 = E(\F_q)$ and $G_2 = E'(\F_{q^r})$ where $E'$ is a twist of $E$ with the twisting isomorphism defined over $\F_{q^r}$. ...
1
vote
1answer
83 views

Understanding Baby-Step Giant-Step Algorithm and discrete logarithm

Studying the Baby-Step/Giant-Step Algorithm, I have some questions: 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}\...
0
votes
0answers
34 views

How does the order of a group, it's torsion subgroup and the co-factor link?

Given an elliptic curve that defines some group of non-prime order, with co-factor h. Would it then have a h-torsion subgroup? What are the implications for ECC ...
2
votes
0answers
86 views

Is this an error in the Pinocchio Protocol paper

I am going through the Pinocchio protocol paper and I need 2 clarifications in the section Protocol 1 (Verifiable Computation from strong QAP). The part that explains the Verify process, which ...
0
votes
2answers
47 views

Elliptic curves - operations in larger groups - performance

According to my measurements and to this work, it seems that operations, for example scalar multiplication, are more expensive in larger groups. If I have, for example, an 80-bit elliptic curve and an ...
3
votes
0answers
32 views

EC non-shared cryptosystems - different group for every party

Efficient Identity Based Parameter Selection for Elliptic Curve Cryptosystems by Arjen K. Lenstra contains a proposal for a non-shared elliptic curve cryptosystem. Every party chooses its own field ...
0
votes
0answers
44 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
66 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
142 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
37 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
614 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
51 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
101 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
82 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
157 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
90 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
70 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
46 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 ...