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
0answers
42 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
46 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
66 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
2answers
66 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=...
2
votes
0answers
37 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
40 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
46 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
31 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
22 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
41 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
53 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
42 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
51 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
49 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
188 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
149 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 ...
0
votes
0answers
20 views

Finding the relationship between generating elements represented by a Hamiltonian cycle of a Cayley graph (like in strong RSA condition)

Consider an undirected Cayley graph of a finite group $\mathbb{Z}_p \times \mathbb{Z}_q$, where $p$ and $q$ are distinct primes. Let the generating set for the Cayley graph be $S=\{g_p, g_q\}$, where $...
0
votes
0answers
16 views

A related question to “relationship between generating elements given by cycles in Cayley graphs”

I am writing this question with reference to the post at Relationship between generating elements given by cycles in Cayley graph When considering the generating elements $g_qg_p$, does it have the ...
4
votes
1answer
75 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 ...
3
votes
1answer
58 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(...
5
votes
1answer
167 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
71 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 ...
0
votes
2answers
100 views

Why is Multiplicative group used in RSA or Euler's theorem but not additive?

I am on the verge to understanding RSA, but suddenly a question popped into mind. When we are calculating $U(N)$ i.e $U(PQ)$, we are taking invertible elements that are co-prime to $N$. For example, $...
0
votes
1answer
52 views

Research topics related to cryptography and Hamiltonian cycles

I am very interested in pursuing a research where I can show an application of Hamiltonian cycles in Cayley graphs of some group such as reflection groups to the field of cryptography. But currently ...
1
vote
0answers
169 views

Steps to determine the single element generators for a multiplicative group

As student I've been asked the following question: Consider the specific prime $p=17$. Determine the single element generators (by hand or by Java program) of $F^*_{17}$. Recall $F^*_{17}$ is the ...
0
votes
0answers
41 views

FLT is partly applying to RSA equation, and also relation between ED mod phi and Phi + 1 mod N

After numerous attempts from myself and all of you guys, I finally came to understand RSA. I can now prove it and understand how I got there. But I still have some very few polishing questions. 1) We ...
4
votes
2answers
80 views

Protocol for proof of knowledge of $l$-th root

Assume we have Group G in which the adaptive root assumption holds. This assumption states that if we choose an element $w$ and after that, if we receive a prime value $l$ it is hard to find the $u$ ...
2
votes
1answer
91 views

Relation between $N = P \times Q$, and $\Phi(N)$

When studying RSA, and proving simple concepts to myself, I went and understood groups and rings, but I failed to understand Lagrange's theorem. I did understand how from invertible finite groups I ...
0
votes
0answers
34 views

Proof of two pairs with same exponent

Lets assume we have a group $G$ with unknown order. And we have a pair $(A_1,K_1), (A_2,K_2)$ in which all $A_1,K_1,A_2,K_2$ are group elements. The claim is $A_1= K_1 ^ x$ and $A_2 = K_2 ^ x$. or ...
1
vote
1answer
107 views

(How) Is DDH generally broken in groups of composite order?

In a somewhat recent lecture a claim was made that I couldn't back up myself but it got me curious whether it actually holds: If the order of the group is not prime, then the DDH assumption does ...
0
votes
0answers
38 views

Secret sharing in different groups; Rounding down of elements

I have the following problem: A secret $x \in \mathbb{Z}_q$ is secret shared (additive secret sharing) between $n$ parties, now is it possible to compute the secret shares of $y = \lfloor x \rfloor ...
0
votes
1answer
25 views

Rounding down in the exponent of group element

I have been struggling to find the algorithm $\mathcal{A}$ in the following. Let $(G,g,q)$ be the group parameter, $p << q$, $x\in \mathbb{Z}_q$, can we build the following algorithm: $$\...
0
votes
1answer
51 views

Discrete log problem exponential runtime

I am trying to understand the runtime complexity of the discrete log problem (in the most basic sense). So, if we have $\langle g \rangle = G$ and are trying to find $g^x = a, a \in G, 0 < x < ...
1
vote
1answer
56 views

number theory question in a group with unknown order

I was reading a paper and I am struggling understanding one part of it. Lets say we have a group $G$ of an unknown order $n$. we know that $B<n<B+C$. both B and C are large values). we choose a ...
1
vote
1answer
32 views

Is there a quick method of listing certain elements of a cyclic group?

I'm studying applied cryptography and stumbled upon the following question to practice the knowledge about Congruence, Groups etc. "List all Elements $x$, where $x^2 = 2$ in $\mathbb{Z}_{31}$ Okay, ...
1
vote
1answer
55 views

How to find a small generator with small inverse? Does it have negative impact to security? (for Schnorr subgroup of $\mathbb{Z}/P\mathbb{Z}$)

Given a prime $P$ with $$P= r \cdot q+1$$ with $q$ prime as well. I'm looking for a generator $g$ of the Schnorr subgroup with order $q$ which is small by value and has a inverse (to $\bmod P$) which ...
1
vote
1answer
81 views

Double discrete logarithm on elliptic curve

Background: I am attempting to implement the paper Publicly Verifiable Secret Sharing. I managed to get it working using modular groups, but when I want to make it more efficient by transferring to ...
0
votes
0answers
109 views

Define a Decryption algorithm on a given group-based Cramer Shoup lite scheme

I am currently working on public key encryption schemes and I want some help to figure out how decryption algorithms work. Suppose we have a public key $pk = (G,p,g,e)$ with $e \in Z^*_p$ . (where $G$ ...
3
votes
2answers
82 views

Size of $E$ over $\mathbb{F}_p$ contains $p+1$ points

I am struggling to prove this claim: I proved that the map $x\mapsto x^3+1$ is a bijection from $\mathbb{F}_p$ to itself if we have that $p\equiv 2\bmod{3}$. We have to use this fact to prove that ...
3
votes
1answer
88 views

Is it possible to construct a multiplicative group from $\mathbb{Z}_n$ if $n$ is not a prime number?

With $n$ being a prime number I know we can generate groups over multiplication. Is it possible the other way around ($n$ not being a prime)?
0
votes
1answer
148 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
70 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
28 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
35 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
100 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
41 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
86 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
48 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
141 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. ...
3
votes
2answers
493 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 ...

1
2 3 4 5