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
4
votes
1answer
402 views

Do Gap-CDH groups exist?

A Gap-CDH group is such that, given group elements $g, a = g^x, b = g^y$, it is hard to compute $g^{xy}$, but, given a group element $c$, easy to verify if $c = g^{xy}$. While such groups have been ...
4
votes
1answer
164 views

Does Linear Cramer-Shoup have pseudo-random ciphertexts?

"Linear Cramer-Shoup" is defined on pages 4 and 5 of $\:$ eprint.iacr.org/2007/074.pdf . Are the ciphertexts in Linear Cramer-Shoup computationally indistinguishable from uniform under a chosen-...
4
votes
1answer
165 views

$L^3$ Grover search of NTRU variants

I was reading a text on cryptology by Wayne Patterson and came across the $L^3$ algorithm which reduces integer lattices with respect to their base. I've also read on the NIST CFP A8 that attacks ...
3
votes
3answers
479 views

How is it decided if $G_1$ and $G_2$ are two “additive” or “multiplicative” cyclic groups?

According to wiki's definition of Bilinear pairing… Let $G_1$ and $G_2$ be two additive cyclic groups of prime order $q$, and $G_T$ another cyclic group of order $q$ written multiplicatively. A ...
3
votes
2answers
462 views

Subgroups generators with respect to group generators of composite order

If I have a group $\mathcal{G}$ of order $N=npq$ and subgroups $\mathcal{G_n,G_p,G_q}$ of order $n$, $p$, $g$ respectively and if $g$ is a generator of $\mathcal{G}$ why then $g^{nq}$ is a generator ...
3
votes
2answers
80 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
2answers
287 views

Why do elliptic curves require fewer bits for the same security level?

I'm studying the basics of cryptography and I didn't understand why elliptic curves use fewer bits. For example, finite-field Diffie-Hellman needs at least 1024 bit and it's a DLP, but elliptic ...
3
votes
2answers
938 views

What does the linear assumption over bilinear groups mean?

In the abstract of "Cryptography with Tamperable and Leaky Memory", at the end of the 3rd paragraph, the authors say: In both schemes we rely on the linear assumption over bilinear groups. What ...
3
votes
1answer
87 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)?
3
votes
1answer
514 views

Discrete logarithm weak group

I'm looking for weak groups in discrete logarithm, that $x$ can be extracted from $Y$ in polynomial time where $Y \equiv g^x \pmod{p}$ . I thought one way is to produce a prime $p$ that $p-1$ is an ...
3
votes
1answer
538 views

How to construct a hash function into a cyclic group such that its discrete log is intractable?

From the Linkable Ring Signatures paper: Let $G = \langle g\rangle$ be a cyclic group of prime order $q$ such that the underlying discrete logarithm problem (DLP) is hard. Let $H_1 : {0, 1}^∗ \to \...
3
votes
1answer
1k views

What is a cyclic group of prime order q such that the DLP is hard?

On the original paper on Linked Ring Signatures, in order to construct its scheme, the author relies on this: Let $G = \langle g\rangle$ be a cyclic group of prime order $q$ such that the ...
3
votes
2answers
246 views

Finite fields in elliptic curve

I have an elliptic curve defined over finite field where $S_1=aP$ . Is it valid to say that $S_1P$ can also be computed. $P$ is the generator of the group. What my real question is that. Should '$a$' ...
3
votes
1answer
398 views

On getting beyond LSB in discrete log

In discrete log we employ sophie germain primes $p=2q+1$ where $q$ is a prime. Then we know least significant bit $x_0$ in $$g^{2x+x_0}=h\bmod p$$ where $2x+x_0$ is discrete logarithm of known $h\...
3
votes
1answer
345 views

Can we reduce Diffie-Hellman problem to “Discrete-log inversion” problem?

Let $G$ be a cyclic multiplicative group of order $n$. Let $g$ be a (public) generator of $G$. The Diffie-Hellman (DH) problem asks: Given $g^x, g^y\in G$ for $x, y\in \mathbb{Z}^*_n$, to compute $g^{...
3
votes
2answers
267 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
1answer
473 views

What's dh-composite test on badssl.com?

The site badssl.com provides examples of bad (red icon) and good (green icon) uses of TLS for the purpose of testing TLS implementations. I'm a bit confused by the test called dh-composite. This ...
3
votes
1answer
595 views

Diffie-Hellman key exchange using addition instead of multiplication?

I know that the additive finite group $(Zp,+)$ of prime order $p$ when I perform the Diffie-Hellman key exchange (DHKE) protocol is insecure. I didn't however find many sources online explain why it ...
3
votes
1answer
316 views

Number generation for Fujisaki-Okamoto commitment scheme parameters

I need to implement the Fujisaki-Okamoto commitment scheme for a project such that I can demonstrate performance of various zero-knowledge proofs in relation to one another, for example Boudot's "...
3
votes
2answers
1k views

Why does Diffie-Hellman need be a cyclic group?

Why is Diffie-Hellman defined on a cyclic group? Doesn't it work for any commutative operation which the inverse is hard to find? Say Alice and Bob agree in a public prime $c$ and both choose a ...
3
votes
1answer
489 views

Modular Arithmetic in RSA

Consider the following the following RSA public key $pk = (N, e) = (1457, 1307)$. (a) Knowing that $187^2 \equiv 1 \pmod {1457}$ find the factorization of $N$. (b) Given the factorization of $N$ ...
3
votes
1answer
633 views

Generator for Group $QR_{N}$

Let $N=PQ$, where $P=2p+1$ and $Q=2q+1$. $P,Q,p,q$ are prime numbers. $QR_{N}$ is the set of quadratic residues modulo $N$. Please help me to prove $QR_{N}$ is a cyclic group. Note: $QR_{P}$ and $...
3
votes
1answer
90 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 ...
3
votes
1answer
132 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 ...
3
votes
1answer
86 views

Question about the location of the r-torsion in the quotient group used in the Tate pairing

I'm working through Pairings for Beginners by Craig Costello, and am trying to understand the Tate pairing. He defines $rE = \{r*P | P \in E(\mathbb{F}_{q^k})\}$ and then forms the quotient group $E(\...
3
votes
1answer
159 views

Why work in a subgroup for Naor and Pinkas oblivious transfer?

In section 4 (protocol 4.1) of the paper by Naor and Pinkas [1], why did the authors decide to operate in a subgroup? When they say "the messages are in the subgroup" does that mean $x, y, z_0, z_1$, $...
3
votes
1answer
90 views

Does pairings based cryptography inherently require a CRS/trusted setup?

In all algorithms I've seen that rely on pairings-based cryptography (some examples: snarks without PCPs, more snarks, sublinear ring signatures), a common reference string is required. Is this always ...
3
votes
1answer
129 views

How is a group element converted into a key?

I've only just started research on cryptography so I apologize if this is a basic question or I'm getting terms confused. I'm researching braid group cryptography and currently looking at the Anshel-...
3
votes
0answers
123 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 ...
3
votes
0answers
131 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 ...
3
votes
0answers
78 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
68 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
1answer
1k views

why are non singular curves used in elliptic curve cryptography?

It is not possible to draw tangent at all the points of a singular curve. What is the specialty of this and how it is related to cryptography and elliptic discriminant?
2
votes
2answers
260 views

Given $g$, $b$, $g^{ab}$, is finding $g^a$ a hard problem?

As in the title, given $g$, $g^{ab}$ are big elements in a prime group $Z_p$ and $b$ in prime group $Z_r$ ($p > r$, $g$ is one generator of $Z_p$). $a$ is unknown and also in $Z_r$, is finding $g^a$...
2
votes
2answers
2k views

Factoring large $N$ given oracle to find square roots modulo $N$

When $p$ and $q$ are distinct odd primes and $N = pq$, the points in $\mathbb Z_N^\ast$ have either zero or four square roots. A quarter of the points have four square roots; the rest have no square ...
2
votes
2answers
2k views

Simple example to describe Bilinear mapping

Notation : $\mathbb{G}$ is an additive group and $\mathbb{G}_T$ is multiplicative group of prime order $q$. Bilinear mapping $e: \mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}_T$ has to satisfy ...
2
votes
1answer
899 views

Diffie-Hellman on additive group

Given the finite cyclic, additive group (G, +), with |G| = n and generator = g, what are the computations and exchanged messages for Diffie-Hellman? What I tried myself: Alice chooses a private $a$ ...
2
votes
2answers
274 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 ...
2
votes
1answer
70 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 ...
2
votes
2answers
77 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^...
2
votes
1answer
5k views

How to find the generator of an elliptic curve? [duplicate]

If the elliptic curve has prime order of points, then all of its points are generator. Is this true? If so, how can I find the optimized generator(which generates more number of points) among them?
2
votes
1answer
533 views

Why is only one generator stated in literature for elliptic curve group P-256?

I refer to elliptic curve groups over prime fields and their application in cryptography. If the order of a group is prime, it follows (am I wrong?) that: the group is cyclic and every element ...
2
votes
1answer
191 views

Hash “Preimage by product” resistance

Let H() be a hash function that achieves collision resistance as well as first and second preimage resistance. Let's equip the output set of H of a multiplicative group structure, more precisely a ...
2
votes
3answers
2k views

RSA finding the inverse of the public exponent

I have a very basic doubt in RSA key generation and its usage. In RSA key generation you choose two large prime numbers of a very large order. Then you multiply them.(eq $p \cdot q = N$) Now, $\phi(N)...
2
votes
1answer
228 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 ...
2
votes
2answers
354 views

How to determine proportion of quadratic residues in elliptic curve group?

I'm using a 'try and increment' method to hash to an Elliptic Curve point, explained below. With security parameter $k$, EC equation $y^2 = x^3 + ax + b \mbox{ mod } q$, we have: $ u = sha256(\mbox{...
2
votes
1answer
381 views

Is Triple-DES a group?

I know for a fact that DES is not a group, but are any of the Triple-Des versions a group? Why, or why not?
2
votes
1answer
97 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 ...