We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [discrete-logarithm]

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.

60 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
30
votes
2answers
1k views

Hardness of finding mutual discrete logarithms of small generators in $\mathbb{Z}_p$

Suppose you want to select a prime $p$ such that finding e.g. $\log_2(3)$ in $\mathbb{Z}_p$ is expected to be either at least as hard as the general Discrete Logarithm Problem in $\mathbb{Z}_p$, or at ...
14
votes
0answers
205 views

Fewest qubits required for the discrete logarithm problem and integer factorization

According to a paper from 2002, the most efficient circuit to factor an $n$-bit integer requires $2n+3$ qubits and $O(n^{3}\lg(n))$ elementary quantum gates, assuming ideal qubits. Later on, according ...
13
votes
1answer
366 views

Is Pohlig-Hellman Cipher the only option?

I am looking for a cipher which would allow something like this: E(E(M, a), b) = E(M, ab), where a and b are encryption keys, and ab is a combination of the keys that is impractical to separate into a ...
13
votes
0answers
271 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 ...
10
votes
0answers
264 views

How Significant is the New Quasi-Polynomial-Time Attack on Fixed Characteristic Discrete Logarithms?

There is a new paper by Kleinjung and Wesolowski on eprint that claims and proves a new attack on the discrete logarithm problem in finite fixed characteristic fields in quasi-polynomial time. ...
8
votes
0answers
118 views

Software timing attack using Kocher method

What's the minimum number of random sample points needed in Kocher's timing attack, so that we can determine enough valid measurements of $A_{i,r}$ and $D_{i,r}$? I'm working from this paper: Volker ...
6
votes
0answers
240 views

Index calculus over elliptic curve over function field

According to my understanding there are some pretty solid seeming roadblocks to carrying out an index calculus on an elliptic curve over a finite field. The general strategy is to take points over $E(\...
4
votes
0answers
92 views

Use of randomness in an Elgamal like encryption

Suppose I have the following encryption scheme: for a message $m\in\mathbb{F}_p^*$, I generate the ciphertext = $(g^r,f^mh^r)$ where $g$ is the generator of a cyclic group $G$ of unknown order $n$ and ...
4
votes
0answers
85 views

Implications of TLS-SRP client with improper N validation?

During development of a client side application of TLS-SRP, i noticed a bug that allows an attacker spoofing as the server to send custom, but non-arbitrary $N$ values, with the client accepting them. ...
4
votes
0answers
818 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

Subexponential algorithms that apply only one of factoring and discrete logarithm?

Shor (quantum polynomial), Number Field Sieve (subexponential), Pollard rho (square root) all have both factoring and discrete logarithm over $\mathbb F_p^*$ variants. What are the subexponential ...
3
votes
0answers
88 views

How many qbits are required to break Diffie-Hellman over a multiplicative group

There have been comparisons between RSA and ECDH with regards to the number of qbits (qubits) required to break the algorithm with a specific key size. But how many qbits are required to break "...
3
votes
0answers
142 views

Cryptographically Secure Elliptic Curve

What are the properties a cryptographically secure Elliptic Curve must have? I have started to create a list and wanted to know if I forgot some important points, and if it is correct so far: A curve ...
3
votes
0answers
135 views

Are analog quantum computers a threat to RSA and DLP?

We already know that D-WAVE's "quantum computers" can't really run the Shor's algorithm, because the way they're built doesn't qualify them as universal quantum computers. Now researchers actually ...
3
votes
0answers
50 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
102 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
465 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
70 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 ...
2
votes
1answer
37 views

Identity Based Encryption: Known Random Value

Let's consider a situation whereby: Alice generates a ciphertext c from a message m using Bob’s ID. An attacker Carol can get c from the open channel. She knows that c is generated by using ...
2
votes
0answers
48 views

Selection of parameters for Massey-Omura Cryptosystem

I have 4 questions about Massey-Omura Cryptosystem. Are there standards that define these parameters? How to choose a group order? What is better to take the function f? What is the recommended key ...
2
votes
0answers
70 views

Distributed key generation (for discrete-log based cryptosystems) with fake shares

Under the definition of Gennaro et al (link), a DKG protocol needs to satisfy “correctness” and “secrecy”. Correctness is divided into three sub-properties: C1. All subsets of $t+1$ shares provided ...
2
votes
0answers
57 views

Proving key equivalence across different elliptic curves

We can use the technique described in this answer to prove key equivalence across two elliptic curves of different order. I'm wondering if modifying the technique as described below would compromise ...
2
votes
0answers
83 views

Explanation of a proof of one of Shoup's lemmas

In Lower Bounds for Discrete Logarithms and Related Problems, Victor Shoup states the following lemma: Lemma 1 Let $p$ be prime and let $t \ge 1$. Let $F(X_1, \dots, X_k) \in \mathbb{Z} / p^t[X_1, \...
2
votes
0answers
57 views

Does secure LWE implementation leak bit information?

We know RSA leaks one bit about the factors and improper yet secure implementations of Discrete Logarithm leak one bit about the discrete logarithm. Does LWE leak any information?
2
votes
0answers
81 views

Is the representation problem as hard as the discrete logarithm problem?

I found the assumtion that finding a representation in a cyclic Group G for a randomly chosen value y is as difficult as solving the DL problem. That assumption was without proof so I am not sure if ...
2
votes
0answers
183 views

Frey-Rück Attack (FR-Reduction) - Tate Pairing

I am trying to understand the Frey-Rück attack and found different ways of a possible implementation. Since I am not yet very familiar with the Tate-Lichtenbaum pairing and the theory of divisors I ...
2
votes
0answers
126 views

Hash function onto a Schnorr group

Let $q$ be a given random prime of $2b$-bit for some security parameter $b$ (say $b=128$); let $p$ be a given much larger random prime with $p=q\cdot r+1$. Let $(G,*)$ be the (Schnorr) subgroup of $\...
2
votes
0answers
72 views

Recover secret $x$ when $c\equiv m^x \pmod p$ with public $p$ (modified)

Given an encryption system where $c\equiv m^x \pmod p$, $p$ is a known prime, 1. Is it possible to recover $x$ with a known plaintext attack? Given $(p,\text{factorization of }\varphi(p),m,c)$ 2. Is ...
2
votes
0answers
177 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 ...
2
votes
0answers
105 views

Reliability of a single-pass deniable authentication protocol?

I look for one-pass deniable authentication protocol with a short message payload for my project and find a solution: ...
1
vote
0answers
53 views

Elliptic curve discrete logarithm problem

I'd like to know what is the maximum bits of the finite field that we can solve the ECDLP in a "regular" computer in trivial time. Is there any recent data about this?
1
vote
0answers
69 views

How can I prove that the plaintext of an elgamal ciphertext is the discrete log of an element?

Is there any (efficient) method to prove that the plaintext of an ElGamal ciphertext is the discrete log of an element? In the scenario I concerned, I have an El Gamal key pair $(pk, sk) = (g^y, y)$....
1
vote
0answers
63 views

Breaking the discrete logarithm problem in subgroups of $G$

I need to find the discrete logarithm of 20 modulo 71 where the generator of the group is 7. I need to break the group $|G|=2 \times 5 \times 7$ in subgroups $|G_1|=2, |G_2|=5, |G_3|=7$. I am new to ...
1
vote
0answers
84 views

Prove that two commitments are commitments to the same value

Let $x$ be the secret value, $(n,a,b,c)$ a public key, $(n_C, g, h)$ the commitment public key. Furthermore let $r, r_C$ be two random numbers. Define $C = g^x h^{r_C} \bmod n_C$, $C_x = a^x b^r \...
1
vote
0answers
104 views

Security of BLS under additional information on the secret key

Question A Is the BLS signature scheme still secure if an adversary in addition to the public key $ pk = g_2 \, sk \in \mathbb{G}_2 $ also obtains additional information on the private key $ sk $, ...
1
vote
0answers
104 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
191 views

breaking DLOG with special prime

This question is not directly about cryptography, but I feel that it is most suitable for this site. DLOG problem: Given a prime $p$, $g$ a multiplicative generator of $\mathbb{Z}_p^\star$ and an ...
1
vote
0answers
202 views

For the discrete log zero-knowledge proof, can all challenges be done at once?

Section 2 of this paper (page 5 in the PDF) gives a protocol for a zero-knowledge proof to prove Alice has $x$ for $y = a^x \mod p$ to Bob without revealing the value of $x$. The protocol is as ...
1
vote
0answers
51 views

Converting discrete log problem to a multivariate system of equations

Is there any method of converting a discrete logarithm problem to an equation system, such that the solution of the system corresponds to the solution of that instance of DLP?
1
vote
0answers
107 views

Is there any concrete working example for Function Field Sieve method?

I'm new to Function Field Sieve(FFS) (Number Field Sieve(NFS) as well) method and I'm finding it is quite difficult to understand it (especially concepts of valuation at infinity, Ca,b curves etc.) ...
1
vote
0answers
159 views

Isomorphic curve vs isomorphic curve group

It is said that if two elliptic curves $E_1, E_2$ defined over a finite field $K$ are isomorphic, then $E_1(K), E_2(K)$ groups are also isomorphic. But the converse is not true. Now, By definition, ...
1
vote
0answers
80 views

Is discrete log as hard when given same challenge in both pairing groups, in the case of BN curve and its sextic twist

This is a special case of the question Generalization of the DL-assumption in bilinear group pair, that wasn't answered. Suppose $G_1$ is a BN curve over $F_q$. That is the set of elements $(x,y)\in ...
1
vote
0answers
355 views

Calculating the discrete logarithm

I'm given a prime number $p = 1217$ I'm also given the following equations: $$ 40 \equiv \log2 \pmod{64} \\ 63 \equiv \log3 \pmod{64} \\ 13 \equiv \log5 \pmod{64} \\ 13 \equiv \log2 \pmod{19} \\ 10 \...
1
vote
0answers
51 views

How to find the integer multiplicand from given two points?

I have two points on an elliptic curve $P(x_1,y_1)$ and $Q(x_2,y_2)$ and a scalar value $x$, where $P=x \cdot Q$. What is the best way that I could figure out the value of $x$? Given that I know all ...
1
vote
0answers
277 views

Solving discrete logarithm when p is not a safe prime

If you have the cyclic group of integers modulo $p$, where $p$ is not a safe prime, as well as a generator $g$ with which for all factors $q$ of $(p-1)$, $g^{(p-1)/q} \ne 1$, This answer says that ...
1
vote
0answers
643 views

Zero Knowledge Non Interactive Proof with random oracle

I am trying to write an assay about Non Interactive Zero-Knowledge proofs and would like to take the simple discrete logarithm problem example fallowing the Feige-Fiat-Shamir heuristics. I understand ...
1
vote
0answers
172 views

Exploration of Blum Micali Security By Seed Size

I'm new to cryptography and am most intrigued by mathematically based pseudo random number generators. With reference to the Blum Micali algorithm: $X_{i+1} = G^{X_i} \bmod P$ can security be ...
1
vote
0answers
108 views

DLOG in $\mathbb{F}_{p^n}^*$?

Assume that we are given an element $g\in \mathbb{F}_{p^n}^*$ and $g$ does not belong to any of the smaller subfields contained in $\mathbb{F}_{p^n}$. If the degree of $g$ is some number $q$, how much ...
1
vote
0answers
106 views

Modulo settings for successful encryption?

I saw this awesome video which shows how encryption works using "discrete logarithm". The example says: $3^x\mod17$. I understood that $3$ is called “generator”, because it has no "straight" root and ...
1
vote
0answers
129 views

Factorization or discrete logarithm is difficult for an attacker?

I have read that difficulty in breaking many algorithms are based either on Factorization or discrete logarithm. I am reading about schemes that are similar to RSA which make use of integer ...