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.

Filter by
Sorted by
Tagged with
0
votes
1answer
77 views

Group in the context of elliptic curve crypto [duplicate]

I understand that the discrete log problem is defined as $G^y \bmod p = x$ Speaking generally, $G$ here is a generator for the group zp*, where $G$ is able to ...
0
votes
0answers
32 views

Pollard's Kangaroo: How random does $f$ have to be?

I'm implementing Pollard's kangaroo algorithm as described here. Wikipedia's description of the protocol says that you should have "a pseudorandom map $f:G\rightarrow S$." Does anyone know what ...
0
votes
0answers
53 views

DLP instances for given number of congruences

Let $S$ be the set of $k$ congruences of the type $g_{i}^{x_i} \equiv h_i \pmod{n_i}, \quad \forall i,1\leq i \leq k$ What would be the best way to describe such set $S$ with a term in literature. ...
0
votes
1answer
60 views

structure in modular arithmetic

I was playing around with modular arithmetic when I noticed something. \begin{align} g^k &= a \bmod n\\ g^{k+0.5(n-1)} &= b \bmod n \end{align} Then $a + b = n$, so you can also write $$g^{...
1
vote
1answer
32 views

Questions regarding random values in Schnorr authentication

In Chapter 21.3 of Schneier, Applied Cryptography I read the following about the Schnorr Authentication Protocol: To generate a key pair, first choose two primes, $p$ and $q$, such that $q$ is a ...
7
votes
1answer
132 views
+100

Simultaneous Discrete Logarithm with Small Exponent

Given two distinct safe primes $p_1 = 2 \cdot q_1 + 1$, $p_2 = 2 \cdot q_2 +1$, consider the following two instances of the discrete logarithm problem with the same unknown exponent $x$. $$ g_1^x \...
0
votes
1answer
61 views

Proof Dlog is hard in generic group model

I want to know a proof for why the dlog problem is hard in the generic group model. But i can't find any resources online. Can someone please provide me a link or an explanation?
1
vote
1answer
77 views

Discrete logarithm problem particularly hard for Schnorr groups?

The Wikipedia article on Discrete Logarithm just states without source: In some cases (e.g. large prime order subgroups of groups ($\mathbb{Z}_p)^×$) there is not only no efficient algorithm known ...
1
vote
1answer
113 views

Finding tetration in a multiplicative group modulo p

I have a variant on the discrete logarithm problem, involving finding tetration in a multiplicative cyclic group of integers modulo a large prime $p$: $$a = x^x \mod p$$ Where $a$ and $p$ are known, ...
0
votes
2answers
72 views

Why are some group representations much easier to compute discrete logarithm for? [duplicate]

The multiplicative group mod $p$ is isometric to the additive group mod $p-1$, yet computing discrete logarithms in the additive group is easy and completing discrete logarithms in the multiplicative ...
3
votes
1answer
126 views

Does knowing that the exponent is in a certain range help solving discrete log?

given: $c=g^i \bmod P$ $g$ generator for group with group size $\varphi(P)$ $g,P,\varphi(P)$,c is known by the attacker He wants to know $i$. Now the attacker also knows $j,k$ with $j<i<k$ $k-j$...
-1
votes
1answer
68 views

How do discrete logarithm with modulo a prime and a non-prime compare?

Let $c_N = g^i \mod N$ and $N=p \cdot q$ and $c_P = f^j \mod P$ and $P$ a prime We assume $N,P$ has the same bit-length. $P$ is the best type of prime you can choose (e.g. safe prime). $N$ is a ...
2
votes
1answer
69 views

Elliptic Curve Discrete Log in a Composite Ring

Elliptic curves are usually defined over prime rings (fields), but what if we chose a ring of composite order? Let $n = pq$ for $p,q$ large primes. Say I have elliptic curve $y^2 = x^3 + ax + b$ over ...
0
votes
1answer
65 views

Elliptic curve with prime subgroup equal to field size

I am aware that when the equation $\#E(\mathbb{Z}_p) = p$ holds for prime $p$, the elliptic curve is called "anomalous" and is insecure do to "Smart's attack". Consider the similar case that $E(\...
2
votes
1answer
81 views

Understanding the Definition of Most Significant Bits in the Hidden Number Problem

Boneh's and Venkatesan's "Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes" defines the Hidden Number Problem (HNP). The HNP shows that computing ...
0
votes
2answers
56 views

Bulletproof - Is it possible to do range proof only from public key?

is it possible to proof x in range (2^1,2^64) from xG=Q with bulletproof or something else only from Q? I’m new in this subject, so thanks before.
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
1answer
141 views

Why is the NIST recommendation for the private key exponent so much smaller than the modulus?

NIST recommends a 256-bit private key exponent for DLP with a 3072-bit modulus. This question answered how the modulus was chosen/calculated, however, why isn't the private key size closer to the ...
0
votes
2answers
71 views

Verify the discrete log of ECDSA is in range

Is it possible to verify the discrete log in elliptic curve is within range without uncovering it? I need to verify that $x$ is within $1$, $2^{64}$ for $xG=P$.
1
vote
0answers
65 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)$....
10
votes
0answers
250 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. ...
1
vote
1answer
85 views

How is the recommended NIST modulus for DLP chosen/calculated?

NIST recommends a 256-bit private key exponent for DLP with a 3072-bit modulus. From this answer it appears that the range of private key numbers is derived by calculating a prime modulus via $2⋅p$ ...
2
votes
1answer
77 views

Pollard's Kangaroo— What is the failure probability (assuming random functions)?

I'm reading Pollard's paper on solving the discrete log problem, i.e. to find $x$ given $y = g^x$, where $g$ is a generator of the group. He has a Kangaroo Algorithm (page 4) which allows you, if you ...
3
votes
1answer
125 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 ...
2
votes
1answer
82 views

Bit-strength of discrete logarithm for a group of integers modulo a safe prime

Preliminaries Let $p$ be a safe prime number. Let $\mathbb{Z}_p^*$ be the multiplicative group of integers modulo $p$. We have $\mathbb{Z}_p = \{\,a \in \mathbb{Z} \mid 1 \le a \lt p\,\}$ . Let $g \...
3
votes
1answer
178 views

What information does $g^x$ reveal about $x$?

Let $p$ be a large prime number. Let $G$ be a subgroup of $\mathbb{Z}_p^*$ with order $q$ - again a large prime. Let $g$ be a generator of $G$. Consider the following standard protocol for ...
2
votes
2answers
403 views

Why Smart's attack doesn't work on this ECDLP?

The Problem is as follows: ...
0
votes
0answers
38 views

Why do they use elliptic curve instead of circle or other simpler curves? [duplicate]

I am curious why people use elliptic curve in cryptography. I know the main requirement is DLP, but elliptic curve is not the only curve with such property. Some of curves seem to be even simpler. As ...
0
votes
1answer
87 views

What makes the Discrete Logarithm Problem hard?

I am missing a crucial piece of the maths behind the DLP, and I'm hoping someone can give me a really dumbed down answer.. If $h=g^x \bmod p$ and we're working in the group $Z^*_p$, why can I not ...
2
votes
1answer
57 views

How to determine if $\{n \cdot g^a \mod P\}$ and $\{m \cdot g^a \mod P\}$ generate the same sets? (set size < $P-1$)

given some examples $k_{n_i},k_{m_i}$ out of each value set: $k_{n_i} \in \{n \cdot g^a \mod P\, \forall a \in \mathbb{N}<P\}=G_m$ $k_{m_i} \in \{m \cdot g^a \mod P, \forall a \in \mathbb{N}<P\}...
-1
votes
1answer
76 views

Is there a fast way to solve $k = n \cdot g^a \mod P$? (get $a$ for unknown $n$)

Would a factor besides the normal discrete logarithm problem increase or decrease the solving time? $k = n \cdot g^a \mod P$ with given $k,g,P$ and the knowledge $P= 2 \cdot N \cdot f+1$, while $...
0
votes
0answers
29 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
1answer
33 views

Which is the fastest way to find a member of a subgroup with known size modulo prime $P$, with know factorization of $P-1$?->$x$ with $x^s \mod P = 1$

Assuming you know the factorization of used prime $P-1$ $P-1 = s \cdot f_2\cdot f_3...f_i$ Now you want to find a member of a subgroup $\mathbb{Z}_s$. This means any $x$ with $x^s \equiv 1 \mod P $ ...
7
votes
1answer
281 views

How safe is a prime with $P=2 \cdot Q \cdot R \cdot S \cdot t+1$ for discrete logarithm? How to enhance/compare?

To get some certain properties for my use case I need a prime $P$ which has the form: $P=2\cdot Q \cdot R \cdot S \cdot t+1$ with $Q,R,S,t$ primes as well. Why that form - Use case Together with ...
6
votes
1answer
90 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
-1
votes
1answer
45 views

Is there a way to determine the number of subgroups (with size $s$) while computing $A^b \bmod P$? Constructing a $P$ with $n$ times size $s$?

If you compute $A^b \bmod P$ for all $b$ the set of results $R$ depend at $A$ (and $P$). $R = \{A^b \bmod P, \forall \space b \in \mathbb{N}\}$ In case $R$ contain all numbers from 1 to $P-1$, it ...
4
votes
1answer
148 views

Could Diffie-Hellman protocol serve as a zero-knowledge proof of knowledge of discrete logarithm?

The Schnorr identification protocol is widely recognized as the simplest ZKPoK of the discrete logarithm (more clearly, Honest-Verifier ZKPoK). However, I can't figure out why this simple protocol, ...
1
vote
1answer
55 views

Does a different exponent and base but same key help to resolve discrete logarithm?

E.g.: $k = N^a \mod P$ The attacker knows the prime $P$ and $N$, which is also a prime and (1.) prime root of $P$ or (2.) has a cycle size of $s$, so $1 = N^s \mod P$, (and for $\forall s'<s$, $...
1
vote
1answer
89 views

How to compute a discrete logarithm modulo a power of 2?

This question is related to this one. Specifically, assume that we have $p$ = 2048, $m$ = 13 and $c$ = 357. In this case, $c\ =m^e\ \bmod \ p$. I know that many algorithms rely on the difficulty of ...
2
votes
1answer
78 views

Discrete logarithm with exponentiation oracle

Suppose $(n, d)$ is an RSA private keypair. We know the public key only (wlog suppose it's $(n, 2^{16}+1)$ and we are given oracle $E$, decryption oracle for $(n, d)$. Is there any efficient algorithm ...
2
votes
2answers
285 views

Does classifying an integer as a discrete log require it be part of a multiplicative group?

This question is not a question about the discrete log problem, the generalized discrete log problem, or an additive group. The confusion is whether any integer can be considered a discrete log or ...
11
votes
3answers
3k views

Why was the term “discrete” used in discrete logarithm?

Is there anything especially "discrete" about a discrete logarithm? This is not a question of what is a discrete logarithm or why the discrete logarithm problem is an "intractable problem" given ...
2
votes
2answers
112 views

Compute discrete logarithm mod $n=p \times q$ knowing factorisation

I read in a document that for a given $n = p\times q$ ($p$, $q$ primes), if you know $p$ and $q$ then you can easily solve the discrete logarithm problem, i.e. for fixed $a,b$, you can find $x$ such ...
2
votes
0answers
41 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 ...
1
vote
1answer
75 views

Understanding Baby-Step Giant-Step Algorithm and discrete logarithm

Studying the Baby-Step/Giant-Step Algorithm, I have some questions: In the algorithm, $p$ is the order of group, $x$ is solution. We rewrite $x = i * m + k $, but why do we make $m =\lfloor\sqrt{p}\...
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
2answers
66 views

Difference between when select x from $\mathbb{Z}_{p-1}$ and $\mathbb{Z}_p$ in discrete logarithm Problem?

Reading "Security Arguments for Digital Signatures and Blind Signatures" paper, I confused by some questions. Q1. when it refers to "El Gamal signature scheme", The key generation algorithm: it ...
2
votes
1answer
155 views

find $a$ and $k$ for a given el gamal cryptosystem

I am given this question: Suppose Alice is using the ElGamal Signature scheme with parameters $p = 31847$, $\alpha = 5$, and $\beta = 25703$ Assuming that we have received signed messages $(x_1,(\...
1
vote
0answers
76 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 \...
0
votes
1answer
70 views

How should one refer to the smallest remainders generated by a modulus within DH or DLP?

It's my understanding that the integer base and exponents chosen to create the initial public keys in DH are from the remainders of a modulus. For example, if the value of the modulus is $N=11$, a ...