In cryptography, a discrete logarithm is the number of times a generator of a group must be multiplied by itself to produce a known number. By choosing certain groups, the task of finding a discrete logarithm can be made intractable.

learn more… | top users | synonyms

4
votes
1answer
232 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
2answers
116 views

Discrete logarithm over prime modulo: small input, large exponent, larger prime

I am considering using modular exponentiation as a one-way hash function. More specifically, here is the scenario. 1) Input ($m$): the input messages are small (16-bit) 2) Exponent ($e$): the ...
4
votes
0answers
76 views

Is the reverse of the “discrete logarithm problem” equally dificult? [duplicate]

It is not easy to understand why this becomes a hard problem. The discrete logarithm problem as defined here: “any integer k that solves $b^k = \{g\mod{n}\}$ is termed a discrete logarithm” i.e.: ...
3
votes
2answers
346 views

Why is “multiplying” $g^x$ and $g^y$ not possible?

The computational Diffie-Hellman problem states that for a cyclic group $G$ of order $p$ and a generator $g$, it is hard to find the value $g^{xy}$ given only $g^x$ and $g^y$ (but easy if either $x$ ...
3
votes
3answers
256 views

SRP-6 vulnerabilities when N is small

I'm one of the developers of an application which uses SRP-6 as the authentication mechanism. The authentication part of the code is very old and uses N with only 256 bits (all arithmetic is done in ...
3
votes
1answer
331 views

Discrete logarithm modulo a smooth number

I am solving the discrete logarithm problem modulo $N$. $N$ is a composite number, I found its factors — lots of small primes and two big primes ($> 2^{50}$). Does the factorization of $N$ somehow ...
3
votes
2answers
2k views

How to test if a number is a primitive root?

How to test if a number is a primitive root, assuming the modulus is a prime? And if not? Is it not enough if the number is relatively prime to the modulus or prime?
3
votes
1answer
585 views

Why is the discrete log problem easy when the exponent comes from a binomial distribution?

I read in http://epubs.surrey.ac.uk/7219/2/esorics06.pdf that in exponential El Gamal the discrete log problem for recovering $m$ from $g^m$ can be made tractable when $m$ is drawn from a binomial ...
3
votes
2answers
190 views

iterated discrete log problem

Consider the following problem: given $g_1 \ldots g_i,h_1 \ldots h_i \in G$, $\forall i$ find $x_i$ such that $g_i^{x_i}=h_i$ For $i=1$ this is the discrete log problem and is assumed to to have ...
3
votes
1answer
91 views

Why do the subexponential algoriths for the DLP not work for the ECDLP?

Elliptic curve cryptography is much more secure for the same parameters because attacks that work on the DLP do not work on the ECDLP. Why do the attacks fail in the latter case?
3
votes
1answer
147 views

What does signed fixed window method mean in ECC?

I am studying (sliding) window method in Elliptic Curve Cryptography (ECC) but I am confused by the term, signed fixed window method. By the way term is used in a research paper and not in the book ...
3
votes
1answer
244 views

Security equivalent to Diffie–Hellman problem?

I've been doing the security proof for one of my Theorem. Basically, given $g^a$, $g^b$, $g^{cb}$, $g$ and $c$ as known values. Is the problem of computing $g^{acb^{-1}}$ equivalent to the Diffie ...
3
votes
1answer
1k views

Difference between Pedersen commitment and commitment based on ElGamal

Does any of you know what is the difference between the Pedersen commitment and the commitment that uses the ElGamal encryption scheme? For the sake of completeness, I recall what both of them look ...
3
votes
2answers
166 views

Could this be a valid variation of the Schnorr protocol?

The Schnorr protocol is a 3-steps proof of knowledge of a discrete logarithm, whose interactive version works as follows. Let $p$ and $q$ be two public primes, such that $q \mid (p-1)$, and let $G$ ...
3
votes
2answers
239 views

Efficiency of finding sub group order vs factorization

Suppose you got a prime $p = 2\mathbb\Pi_{i=0}^{n-1}q_i+1$, where $2^{k-1} \lt q_i \lt 2^k$ for some $k$ and all $0 \le i \lt n$, and that you also got a generator $g$ of one of the prime order sub ...
3
votes
1answer
132 views

How hard are discrete logarithms problems in $\mathbb Z^{*}_{n}$ and $\mathbb Z^{*}_{n^2}$, where $n$ is the RSA $n=pq$

Use the notations form the Wikipedia article Paillier Cryptosystem , assume that the chipertext $c$ and $c^{\lambda} \mod n^2$ are both given, is it possible to compute $\lambda$ easily?
3
votes
1answer
966 views

Why can't I break ElGamal encryption by brute-forcing the secret exponent?

I am doing a course on cryptography on coursera and one of the topics covered was the ElGamal Encryption system. I am using the terms as defined in Wikipedia. Alice publishes $g$ and $g^x$. ...
3
votes
2answers
171 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
2answers
263 views

Probability that an attacker wins the discrete logarithm game when exponents are drawn from a subset

Suppose $g$ is a generator of an order $p$ cyclic group in which discrete logarithm is hard and $p$ is a prime (i.e., given $g^x$ for a random $x \in \{0,1,\ldots, p-1\}$, it is hard to recover $x$ ...
3
votes
1answer
267 views

Stream ciphers based on discrete logs

Blum Blum Shub is a stream cipher that is provably reducible to the difficulty of factoring integers. I'm wondering whether there is a similar construction for discrete logs? For example, I could ...
3
votes
1answer
43 views

How many bits of an exponent are leaked when doing a powmod?

How many bits of the exponent $x$ are leaked when you calculate and reveal $g^x \pmod p$ for some generator $g$ of $\mathbb Z^∗_p$? The low bit of $x$ is obviously leaked: the low bit equals $1-\frac{...
3
votes
1answer
241 views

Chosen ciphertext insecurity in an ElGamal variant

I'm trying to prove something and if I can show that there is a simple way to calculate $(g^a \bmod p)^k$ if I know both $g^k \bmod p$ and $g^a \bmod p$, then (I think) it will help me prove it, but I'...
3
votes
1answer
294 views

Finding a solution to a (sort of) discrete logarithm by asking questions

Let $p = kq + 1$ and $q$ be primes such that $log$ $q = n$, $log$ $k = n$ and such that the bit size of every prime factor of $k$ is bounded by $log$ $n$. Let $g$ be a generator of the unique ...
3
votes
1answer
128 views

Given $g,g^t$ in a cyclic group of order $pq$, is it hard to compute $g^{t^{-1}}$?

Suppose we have a group $G$ cyclic of order $pq$ , where $p,q$ are primes. Let $g$ be a generator of $G$ and $t\in \mathbb{Z}_{pq}$. Having $g$ and $g^t$, it seems to be very hard to find $g^{t^{-1}}$,...
3
votes
1answer
357 views

Generating a valid signature on El-Gamal without knowing the private key

Suppose we are given $p$, the large prime, $g$ which is the primitive root for $p$, $b$ which is calculated as $b=g^x$ mod $p$ where $x$ is the private key and $0<x<p-1$. Also suppose we know $...
3
votes
0answers
54 views

How does the Number Field Sieve find the target number for Diffie-Hellman?

I have read some papers relating to the Number Field Sieve, but I could not figure out how this algorithm helps in Logjam, or even what is meant by the number field. What is this? What is meant by ...
3
votes
0answers
51 views

Cost of attack on DSA with attack on DLP

Are there any (recent) estimates of cost of attack on DSA by solving the discrete logarithm? I'm especially interested in attacks that use Pollard's rho algorithm. Are there any optimized ...
3
votes
2answers
73 views

Discrete Logarithm problem with inverse

Let $\mathbb G$ be a cyclic group of order $q$. The Discrete Logarithm Problem (DLP) is, given $g, g^x \in \mathbb G$, to compute $x \in \mathbb Z_q $. I'm interested to know if there is a known ...
3
votes
0answers
35 views

El-Gamal and Lines on Planes

I've been thinking about a geometric picture for El-Gamal. The idea is to understand the set $\{(my^{x},g^x) \mid x \in Z_p\}$ (the set of encryption of $m$ for fixed $g$ and $y$) by taking the $\...
3
votes
0answers
67 views

Pollard's Rho - Restricting the random function to the exponents

Pollard's Rho is usually constructed using a function $f:G \rightarrow G$ which behaves 'random enough' in order to detect a collision with Floyd's cycle detection trick. It is easy enough to observe, ...
3
votes
0answers
148 views

Relations between RSA and DLOG, factoring and DLOG

Definition: (The generalized Diffie-Hellman problem) Let $n=pq$ for two large primes $p,q$. Given $x, x^a, x^b,n$, find $x^{ab}\pmod{n}$. (1) Is there a known reduction from the GDH problem to ...
3
votes
0answers
47 views

Can anyone explain how the modified r-adding walk works?

I was going through a paper titled “Accelerating Pollard's Rho Algorithm on Finite Fields” by Jung Hee Cheon et al. I understand the table(Ml) creation part of it, but after that I somehow fail to ...
3
votes
0answers
123 views

RSA security assumptions - does breaking the DLP also break RSA? [duplicate]

Possible Duplicate: Would the ability to efficiently find Discrete Logs have any impact on the security of RSA? I'm wondering if breaking the DLP, that is the basis for ElGamal and DSA, would ...
2
votes
1answer
279 views

Adding points on Elliptic Curves

How do we add the integer points $P=(-1, 4)$ and $Q=(2, 5)$ on the elliptic curve of the form $y^2=x^3+17$ ?
2
votes
2answers
217 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
243 views

Is there a cumulative commitment scheme?

For a certain application I need a commitment scheme where each user could make a commitment, and a single verification operation could verify all the commitments simultaneously, faster than single ...
2
votes
2answers
269 views

Zero knowledge-proof for discrete log that is not honest-verifier

Take a cyclic group of prime order. The Schnorr-protocol for proving knowledge of the discrete logarithm of some group element is honest-verifier zero-knowledge, meaning that if the verifier chooses ...
2
votes
1answer
57 views

Discrete log accumulator without pairings

Here $g$ is some fixed generator of a discrete log group. I don't want the group to be bilinear for efficiency and BDH-skepticism reasons. Is anyone aware of a discrete log accumulator? What I mean ...
2
votes
2answers
150 views

What does variable-base point/scalar multiplication mean in ECC?

I am a bit confuse about the term, variable-base point/scalar multiplication, in Elliptic Curve Cryptography. What I have understood so far. It means that the base or point on EC is variable/unknown. ...
2
votes
1answer
361 views

Proof of correctness of a homomorphic ElGamal sum

Let's suppose we are using the exponential ElGamal as a public-key encryption scheme, so that we encrypt $g^m$ instead of $m$, for some generator $g$. Let $x$ be the private key, and $h=g^x$ be the ...
2
votes
1answer
61 views

In a additive group is it hard to calculate $bg$ given $ag, g, abg$

The ECDH problem defined that given $g,ag,bg$ it is difficult to calculate $abg$. But it is also difficult to calculate $bg$ given $ag,g,abg$. where $g$ is generator and a,b are elements of group.
2
votes
1answer
242 views

Is there a simple zero knowledge proof of $x$ for $b=x^x\pmod p$?

We have a multiplicative cyclic group $G$ which is a subgroup of $(\mathbb{Z}/n\mathbb{Z})∗$. There are two parties, Alice and Bob: If: Alice knows: $b$ and $x$ such that $x^x = b$; Bob knows: $b$. ...
2
votes
1answer
673 views

How is ElGamal not secure under chosen ciphertext attack, but semantically secure in some cases?

I know that you can create a ciphertext c' using c and then find the corresponding m' for c' which you can use to find m for c. So, doesn't this mean that it is not semantically secure? But I also ...
2
votes
2answers
228 views

Is there a way to compare the 923 bit pairing based key with RSA or AES, etc

I've see many articles, most of them basically the same, praising Fujitsu for cracking what is referred to as a 923 bit pairing based encryption. I understand that in comparing RSA to AES you've got ...
2
votes
2answers
85 views

Fixed primes in discrete logarithm

The discrete logarithm problem is to find $z$ when the inputs are $g,h,p$ where $g^z\bmod p$. Supposing if you fix $p$ then does the problem become any easier to attacks and is there a $(\log p)^c$ ...
2
votes
1answer
51 views

Generalization of the DL-assumption in bilinear group pair

When thinking about a pairing-based cryptographic scheme, I encountered the following problem. Let $e \colon G_1, G_2 \to G_T$ be a Type 3 pairing. Then: Given $P, zP \in G_1$ and $Q, zQ \in G_2$, ...
2
votes
1answer
72 views

Elliptic Curve ElGamal and DSA - smooth group order and element of large prime order

In regular ElGamal and DSA, we choose large primes $p$ and $q$ such that $p\equiv 1\pmod{q}$, and a group element $g$ of order $q$ by computing $a^{(p-1)/q}$ for some random $a$. This is to prevent ...
2
votes
1answer
63 views

Bilinear map assumpion

Is there an assumption that says from a tag $k\cdot e(g,g_1)^{rx}$ ($k,r$ are secret) it is difficult to forge it with some x': $k\cdot e(g,g_1)^{rx'}$, as long as you cannot solve DL in $\mathbb{G}_1$...
2
votes
1answer
301 views

DLP based crypto systems with multiple independent generators

One example of a DLP based crypto system (or rather DDH based crypto system) where the public key parameters include two independent generators of the subgroup, is Cramer Shoup. Since the security ...
2
votes
1answer
181 views

Discrete log analog of ECM factoring algorithm?

Anecdotally, most factoring algorithms have a corresponding variant algorithm that can be used to attack the discrete log problem using similar ideas. Is there an analog of the elliptic curve (ECM) ...