Stack Exchange Network

Stack Exchange network consists of 175 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).

11
votes
0answers
250 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 ...
6
votes
0answers
60 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
69 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}{...
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 ...
3
votes
0answers
54 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 ...
3
votes
0answers
94 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 ...
2
votes
0answers
59 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 ...
2
votes
0answers
133 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 ...
1
vote
0answers
97 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
0answers
85 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
vote
0answers
231 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
0answers
42 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 $...
1
vote
0answers
151 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 ...
1
vote
0answers
351 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 ...
0
votes
0answers
25 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
0answers
26 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 ...
0
votes
0answers
38 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 ...
0
votes
0answers
125 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
35 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 ...
0
votes
0answers
38 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 ...
0
votes
0answers
151 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 ...