Skip to main content

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

50 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
19 votes
0 answers
498 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 ...
fgrieu's user avatar
  • 142k
5 votes
0 answers
233 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 ...
Seawaves32's user avatar
3 votes
0 answers
111 views

Effective key length in Enigma encryption

Each Enigma machine setting induces a certain encryption in the sense of a function from the space of plain texts to the set of cipher texts. The number of different Enigma machine settings can be ...
maya's user avatar
  • 139
3 votes
0 answers
54 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^{\...
Matteo Monti's user avatar
  • 1,417
3 votes
0 answers
293 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 ...
xorhash's user avatar
  • 233
3 votes
0 answers
225 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 ...
J. Doe's user avatar
  • 453
3 votes
0 answers
321 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 ...
kub0x's user avatar
  • 898
3 votes
0 answers
94 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}{...
Abhijit's user avatar
  • 83
3 votes
0 answers
36 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 ...
Daniel Herbrych's user avatar
3 votes
0 answers
102 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 ...
swain's user avatar
  • 31
3 votes
0 answers
95 views

Why does the new encryption scheme proposed by authors stop an adversary from guessing the subspace of the secret key?

In this paper, the authors construct an encryption scheme that is supposed to be resilient to tampering and leaking (as opposed to just leaking). Specifically this scheme: If you look at the ...
user1068636's user avatar
2 votes
1 answer
181 views

Parameters needed for Chaum-Pedersen Protocol

I've came across a Stackexchange question about the Chaum-Pedersen Protocol which is based on the generalised schnorr protocol. As I understand it, it uses discrete logs and cyclic groups of prime ...
Jason L. B.'s user avatar
2 votes
0 answers
88 views

Create random element from group G in BLS Scheme

I hope this question is not too basic. I'm currently trying to implement compact proofs of retrievability that are publicly verifiable by BLS scheme as described in this paper Compact Proofs of ...
unsigned_int2's user avatar
2 votes
0 answers
119 views

If $e(aP, bP) = e(P, P)^{ab}$ then how can we solve $e(P^a, P^b)$?

I'm a bit confused regarding the bilinear pairing operation. Let's say I have a Public key of a receiver $P_r = P^x$ and I want to create a symmetric key using KEM with a pairing operation. If I chose ...
Alia's user avatar
  • 51
2 votes
0 answers
97 views

Secure multiparty scheme in key (splitting) distribution among the players

Suppose that we have a game with $I$ players and each of them has a private secret say $e_i$. Every player wants to share her secret with the rest of the players but in such a way that she will not be ...
Hunger Learn's user avatar
2 votes
0 answers
65 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?
Adam Stanisław Jagielski's user avatar
2 votes
0 answers
129 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}$. ...
Izaak Meckler's user avatar
2 votes
0 answers
164 views

BLS signatures in the G-valued Random Oracle Model

This paper on semi-generic algorithms considers "non-standard properties of the employed hash function". For BLS signatures whose main group is $G$, I'm curious what can be shown when the hash ...
user avatar
1 vote
0 answers
39 views

Grow-only set homomorphic hash function from semigroup?

I have been exploring Bellare and Micciancio's "randomize-then-combine" paradigm for deriving set homomorphic hashing functions. I am particularly interested in grow-only sets, such that ...
Carson Farmer's user avatar
1 vote
0 answers
98 views

Understanding Gentry's initial FHE construction based on ideal lattices

I am trying to understand the encryption procedure in Craig Gentry's initial construction for FHE described in Fully Homomorphic Encryption Using Ideal Lattices. Unfortunately after repeated attempts ...
Parham's user avatar
  • 111
1 vote
2 answers
313 views

Can I move elements from cyclic subgroup to its cyclic parent group?

The following context is based on elliptic curves in short-weierstrass form y^2 = x^3 + b. I know that elements of a non-prime order cyclic group G can be moved to its subgroup H by a process called &...
Homer's user avatar
  • 7
1 vote
0 answers
63 views

ddh and statistical distance

Let $\mathbb{G}$ be a cyclic group of prime order q and generated by g. Let $D$ be the uniform distribution over $\mathbb{G}^3$. Let $D_{dh}$ be the uniform distribution over the set of all DH-triples ...
Cristie's user avatar
  • 93
1 vote
0 answers
50 views

Compact Proofs of Retrievability publicly verifiable with RSA

I'm currently trying to implement compact proofs of retrievability that are publicly verifiable by RSA as described in this paper Compact Proofs of Retrievability in GO. I'm currently struggling on ...
unsigned_int2's user avatar
1 vote
0 answers
56 views

Could anybody help by applying a secure multiparty secret sharing scheme?

Suppose that we have a multi-secret sharing scheme as it is described in the literature Let there be $I$ agents and say that $S$ is the space of the (uniform) random variables $s=(s_1,s_2,\cdots,s_I)\...
Hunger Learn's user avatar
1 vote
0 answers
30 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 ...
Mahsa Bastankhah's user avatar
1 vote
0 answers
59 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 ...
blockByblock's user avatar
1 vote
0 answers
41 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$?
sandeep kiran p's user avatar
1 vote
0 answers
94 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 ...
WonderHow20's user avatar
1 vote
0 answers
249 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 ...
jawad's user avatar
  • 11
1 vote
0 answers
135 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. "...
John Miller's user avatar
1 vote
0 answers
326 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, ...
Mark S's user avatar
  • 289
1 vote
0 answers
81 views

Hash function notations and their corresponding existing cryptographic hash algorithm

I am implementing Role-based access control by referencing the paper Enforcing Role-Based Access Control for Secure Data Storage in the Cloud. In page 6, they have mentioned to choose hash functions $...
Mariam's user avatar
  • 69
1 vote
0 answers
225 views

What is the hardness in Decisional Linear Assumption (DLIN)?

I had understood what does the DLIN assumption means and here is a related question. But I fail to understand the 'real hardness' in this problem. I would be grateful if someone can help me to ...
user0x0's user avatar
  • 111
1 vote
0 answers
457 views

Best group if one wants the discrete log problem to be hard?

Suppose one is implementing a cryptographic scheme over a group where one needs the discrete logarithm to be hard - what is the recommended group to use? I'm looking for a group where calculations are ...
Morty's user avatar
  • 599
0 votes
0 answers
32 views

Safe use of bilinear pairing, using one way function in the exponent

Given a generator $g$ of a cyclic group, I am trying to look for a case where I use pairing over an element that has an exponent which is a one-way function, e.g., $g^{x^2\mod n}$ (here $x$ in the ...
Doron's user avatar
  • 99
0 votes
0 answers
63 views

How could this scheme work?

When we use a secret sharing scheme we usually want to reconstruct the polynomial function $p(x)\in\mathbb{Z}_q[X]$ with the Lagrange interpolation method and then compute $s=p(0)=a_0$. However, the ...
Hunger Learn's user avatar
0 votes
0 answers
31 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 ...
Buddhini Angelika's user avatar
0 votes
0 answers
170 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)^(...
Joe's user avatar
  • 41
0 votes
0 answers
36 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 \...
Buddhini Angelika's user avatar
0 votes
0 answers
25 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 ...
Wild Tarzan's user avatar
0 votes
0 answers
53 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 :...
sof's user avatar
  • 61
0 votes
0 answers
58 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 ...
C0DEV3IL's user avatar
0 votes
0 answers
54 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 ...
Sam Smith's user avatar
  • 105
0 votes
0 answers
142 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$ ...
user178592's user avatar
0 votes
0 answers
70 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 ...
Erwan Ounn's user avatar
0 votes
0 answers
360 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=...
Jonathan Kiersch's user avatar
0 votes
0 answers
67 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 ...
omnomnom's user avatar
  • 491
0 votes
0 answers
174 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 ...
satya's user avatar
  • 1,414
0 votes
0 answers
596 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 ...
satya's user avatar
  • 1,414
-1 votes
1 answer
49 views

How to define a cryptosystem when the encryption-decyrption scheme is based on Shamir's secret sharing scheme?

I would like to make a parallelism between Shamir's secret sharing scheme and how to define a cryptosystem where the encryption scheme is based on secret sharing. To begin with I do not know if there ...
Hunger Learn's user avatar