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
1
vote
1answer
28 views

Generation of the order $\lambda$ (which is lcm((p-1),(q-1))) element g in modified paillier, why $-a^{2n}$?

As the question states, in variants of paillier cryptosystem, such as CS01 and DT-PKC, when they want an element $g$ of order $\lambda$, they choose a random number $a$ from group $Z^*_{n^2}$ and ...
1
vote
1answer
90 views

How to find integer point of a ec curve in a given range?

I was looking inside the basics of ecc and found the examples from Internet either uses continuous domain curve or use a very small prime number p like 17 in a ...
0
votes
1answer
52 views

Setting up the discrete logarithm framework

The discrete logarithm problem over prime cyclic groups consist of finding $x$ satisfying $g^x\equiv h\bmod p$ where $g$ is generator of multiplicative group $\mathbb Z/p\mathbb Z$ at a large prime $p$...
6
votes
2answers
117 views

Does Poly1305 have weak keys like GCM/GHASH?

Some block cipher keys are weak when used with GCM; see this question. This happens when the multiplier $H$ decided by the key ends up in a small-order subgroup of $\mathbb{F}_{2^{128}}$. Poly1305 ...
4
votes
1answer
90 views

Why does Index Calculus work?

I understand how the Index Calculus algorithm works - I know & understand the steps. I understand how the steps are derived. However, I am not able to figure out why it works. I can understand why ...
0
votes
1answer
46 views

what does "product of two cyclic groups" mean

I am reading "Elliptic curve cryptosystems" and the link is here(https://www.ams.org/journals/mcom/1987-48-177/S0025-5718-1987-0866109-5/S0025-5718-1987-0866109-5.pdf). I don't understand ...
1
vote
0answers
28 views

A finite group with a threshold functionality

I am trying to find a generator of a finite group that its powers devides the group into two parts. For example look at the last row of this table that shows the powers of 10 in the group Z_19. You ...
0
votes
0answers
112 views

Using random invertible matrices over finite fields to define the hash of a list

This is a follow-up to a prior question Does matrix multiplication of hash digests admit manipulation of the result?; this formulation failed because it admitted singular matrices and therefore ...
0
votes
0answers
26 views

Checking whether a particular group has an efficient, faithful representation as a matrix group

There are cryptographic protocols being developed for non-abelian groups. For some protocols it is necessary to know whether the group has an efficient representation as a matrix group (say, a matrix ...
2
votes
1answer
87 views

Representation theory in cryptography/coding theory

How can representation theory be used in cryptography and/or coding theory? I am studying a MSc in pure mathematics and I am currently working on things related to biset functors, but cryptography and ...
1
vote
1answer
48 views

Do groups generated by round functions generate the alternating group?

Let $K,X$ be sets and let $F:K\times X\rightarrow X$ be a function. For each $k\in K$, let $f_{k}:X\rightarrow X$ be the function where $f_{k}(x)=F(k,x)$ whenever $k\in K,x\in X$. Assume that each $f_{...
1
vote
2answers
89 views

Different modulus in the exponent

Given two values $g^{a_1}, g^{a_2}$ where $a_1, a_2 \in \mathbb{Z}_q$ and $g$ is a generator of group $\mathbb{G}$ of order $q$. Discrete logarithm is assumed to be hard in $\mathbb{G}$. Is there a ...
1
vote
1answer
43 views

Verifiable Delay Function: Trusted Setup

Efficient Verifiable Delay Function paper suggested that there is two way to construct the group. One of them requires trusted setup in the sense whoever constructs the RSA unknown group order needs ...
1
vote
0answers
39 views

Verifiable Delay Function - Fake Proofs

For unknown group order such as RSA groups $ G %$, it takes $T$ sequential steps to compute the below function (time-lock puzzle). $$ y = g^{2^T} mod N$$ This paper states that if $ /Phi(N) $ (Group ...
2
votes
2answers
230 views

VDF / RSA groups

I believe I am overthinking it; however, I need to clear out my doubts. What is exactly RSA groups and how their order is unknown? I know in RSA N is computed by multiplying two prime numbers (p and ...
2
votes
0answers
27 views

Does having CDH oracle breaks El-Gamal signature scheme?

Having a oracle that solves Computational Diffie-Hellman problem which for given values $(g, g^a, g^b)$ outputs $g^{ab}$, is it possible to forge a signature in El-Gamal (wiki) signature scheme?
1
vote
1answer
82 views

Diffie Helman obtaining $g^y \bmod p$ from $g^{xy} \bmod p$ and $g^x \bmod p$

This may seem like a strange question. Lets say I have $g^x \bmod p$ and $g^{xy} \bmod p$. How can I efficiently obtain $g^y \bmod p$? I assume I must use modular inverse but I don't know where.
1
vote
2answers
86 views

What are the typical instance parameters of non-commutative cryptographic schemes?

Recently, I grew a tremendous interest for public-key cryptography based on "groupoids", and collaborated with someone on this topic. What I notice afterwards, is that there had been a huge ...
2
votes
2answers
256 views

Prime order elliptic curve groups: Generators and the reason choice

As far as I understand, the elliptic curve group based on BLS12-381 is prime order and cyclic. Thus, any group element could be used to generate all the elements of ...
2
votes
2answers
108 views

ElGamal encryption security

Assume we have 2 prime numbers in form p = 2q + 1. Is it safe to use the cyclic group of order p-1 instead of one with order <...
3
votes
0answers
53 views

Succint, interactive proof that $y^2 = x$ in $\mathbb{Z}^*_p$

Let $p$ be a large prime, such that $(p = 3) \mod{4}$. Let $x$ be an element of $\mathbb{Z}^*_p$ such that, for some $y \in \mathbb{Z}^*_p$, we have $y^2 = x$. It is a well-known result that $y = x^{\...
2
votes
1answer
191 views

How is a generator found for a group, both in case of DH & ECDH?

First step in DH & ECDH is to choose a random prime $p$. Then you choose a generator $g$ for the group $\mathbb Z_p^*$. How do you find a generator? Likewise in ECDH, you would need to find a ...
0
votes
1answer
31 views

Practical use of semi direct product of group in Cryptography

Is there any example of semi-direct product used in any of cryptographic application? Does it help in choosing integers p, q in RSA?
1
vote
2answers
150 views

How to get the order of a group generator in DH?

For a DH parameter prime, if the generator $g$ is 2, how do I get the order $q$?
1
vote
0answers
26 views

Equality with Bilinear Maps

Let e be a bilinear pairing function and $g_1$ and $g_2$ be the generators of $G_1$ and $G_2$ Given $e(a,g_2^x), e(b,g_2^y), g_2^x,g_2^y$ is there a way to find out if $a = b$?
0
votes
0answers
21 views

Is it hard to determine an automorphism when the mapped value by several compositions of the automorphism is given

Generalization of the Discrete logarithm problem to non-abelian groups is discussed by many authors. One of the generalizations is shown in MOR cryptosystem as in the below link, by considering the ...
4
votes
1answer
417 views

Why Abstract Algebra in Cryptography?

I come from an engineering background, but not from computer science or anything to do with pure math. I studied applied math in college--never abstract algebra, number theory, or discrete math, ...
1
vote
1answer
136 views

Solving Diffie-Hellman vs DLP

I'm wondering what is the current knowledge regarding the difficulty of solving the Diffie-Hellman problem (DHP). Obvisously solving the DLP (discrete log) is at least as hard as solving the DH ...
5
votes
2answers
235 views

Why use prime number $q$ such $q$| $(p-1)$ in discrete logarithm based schemes?

In discrete logarithm based schemes on finite field we have a prime number $q$ that divides $p-1$ and $q$ is to specify a subgroup with the order $q$. But why do we do that? Why do not we work on the ...
2
votes
1answer
126 views

Why is the point at infinity on Edwards Curve different to Weierstrass curves?

If I understand correctly, the identity point on all elliptic curves is the point at infinity. But on the Edwards curve, this can be written in Affine form? Does this have something to do with the ...
1
vote
0answers
52 views

Schoofs Algorithm

I studied Schoofs Algorithm described by Washington. On page 125 he says that we could write $y'/y$ as a function of $x$, which makes sense since earlier on the page he denotes $y'= r_{2,j}(x)y$. But ...
0
votes
1answer
81 views

Message mapping to elliptic curve in BLS signature

In the BLS signature the subgroup $G$ of elliptic curve constructed with point $P$ with prime order $q$ by $G=\langle P\rangle $. The $h(x)$ is a hash function. The point $S$ is map (image) of $h(m)$ ...
1
vote
1answer
128 views

Safe primes and subgroups

I've been reading about safe primes and their use in: Cryptography Engineering by Niels Ferguson, Bruce Schneier, and Tadayoshi Kohno. Having a safe prime $q$ with $q=2p+1$ where $p$ is a Sophie ...
2
votes
3answers
144 views

Some questions on building permutations from boolean functions

I've seen multiple examples of boolean functions being used as a permutation. For example the Keccak Chi : 2.3.1 function: from https://keccak.team/figures.html Or as a formula: for $i=\{0..4\}$ $A_i=...
3
votes
0answers
84 views

How to efficiently find Schnorr groups that have a generator $g=2$?

A Schnorr group is a multiplicative group of integers modulo an odd prime $p$ of prime order $q$, normally such that $p$ is much greater than $q$. As far as I know, the normal way to find a Schnorr ...
0
votes
0answers
62 views

Elliptic curve group inverse addition in OpenSSL

I am using group P-256 on OpenSSL with C++. My understanding was that, if you have a point $xP$ and then calculate (xP)^(-1) with EC_POINT_invert(group, xP_inv, ctx), then when I calculate: xP + (xP)^(...
1
vote
1answer
71 views

What is the order of the Identity point on prime order elliptic curve groups?

I'm trying to understand how the identity point is represented in a group of prime order. What I think is correct: If the group has even order, then the identity point is in the group, because the ...
0
votes
0answers
34 views

Finding the relationship given by the generating elements of a non-abelian group (for a maximum case) where they correspond to finding cycles

Let $G=(\mathbb{Z}_p \times \mathbb{Z}_p) \rtimes_{\phi} \mathbb{Z}_q$, where $p$ and $q$ are odd distinct primes. Let $G$ be generated by the elements $s=(g_1,e_q)$ and $t=(e_p,g_3)$, $g_1,e_p \in \...
0
votes
0answers
24 views

How do I generate a number from a Z* order q set

I would like to generate a random number based on this set, firstly how do I generate the numbers that belong to the Z* order q set. I have the q value and the prime p value. Also if there's a ...
1
vote
1answer
56 views

RSA assumption and relationship given by generating elemts of a Cayley graph

I have read a very interesting description of computation related to the RSA group as follows. "By the Chinese remainder theorem, we have that: $$(\mathbb{Z}/pq\mathbb{Z})^* \cong (\mathbb{Z}/p\...
0
votes
2answers
67 views

Collusion resistance in proxy re-encryption scheme depending on bilinear map rules

A proxy re-encryption scheme is collusion resistant, if the proxy and a delegatee are not able to recover the secret key of the delegator. For example, when we have a message that was originally ...
0
votes
0answers
48 views

Computing discrete logarithms in the subgroup generated by 1 + N

When I read about DLP, I found that there are groups where the computation is easy. I found that it is known that computing discrete logarithms in the subgroup generated by 1 + N is easy. For example :...
3
votes
1answer
57 views

Mapping a value $g^x \bmod p$ to a small interval $[1...H]$

My question is in $\mathbb{Z}_p^{*}$ context, where $p=q\cdot k+1$ for two primes $p,q$ and $k \in \mathbb{Z}$; $g$ is the generator of the subgroup $G_q$ of $\mathbb{Z}_p^{*}$, of order $q$. Let's ...
0
votes
1answer
56 views

Are there any zero knowledge protocols which do not rely on a Group?

To me (new), it seems that a lot of cryptography relies on group theory. Are there any zero knowledge protocols which do not rely on a group?
2
votes
1answer
308 views

RSA and the strong RSA assumptions

The RSA assumption: Given a randomly generated RSA modulus $n$, exponent $r$ and a random $z \in \mathbb{Z}_n^{*}$, find $y$ such that $y^r=z$. The strong RSA assumption: Given a randomly chosen ...
5
votes
2answers
155 views

Prime numbers of the form $(2^k)p+1$, for a given prime $p$

Let $p$ be a prime. (say 256 bit) Does there a exist a prime $q$ such that $q = (2^k)p + 1$, for a large $k$ (something like 256), if it does exist, is there a way to find out for which all $k$ such ...
4
votes
1answer
86 views

Relationship between generating elements given by cycles in Cayley graph

The strong RSA assumption is that the following problem is hard to solve. "Given a randomly chosen RSA modulus $n$ and a random $z \in \mathbb{Z}_n^*$, find $r>1$ and $y \in \mathbb{Z}_n^*$ such ...
4
votes
1answer
123 views

Understanding the groups used in bilinear Ate-pairing

The bilinear ate pairing $e:G_1\times G_2 \rightarrow G_T$ is defined over the following groups: \begin{equation} \begin{aligned} & G_1 = E(\mathbb{F}_p)[r] \cap Ker(\pi_p-[1]), \\ & G_2 = E(...
6
votes
1answer
447 views

When using Ristretto or Decaf with Ed25519 and Ed448, do scalars still need pruning/trimming/clamping?

Decaf is a point compression method that builds a prime-order group for (twisted) Edwards curves and Montgomery curves with cofactor $h = 4$ based on the Jacobi quartic [H2015]. The promise is to ...
1
vote
2answers
187 views

All generators for modulo p

so I have to find all generators for modulo p. And I thought: isn't there are rule for it? As far as I remember, every number from {1,...,p-1} is a generator because p is a prime. Is that true? Or am ...

1
2 3 4 5 6