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
-1
votes
0answers
32 views

Is any of this new? or is it already well established knowledge? [closed]

I have done some research into the functions a^floor(x) mod p floor(x)^e mod n and wanted to share my results and see if this is new to anyone? Here is a pdf of it in a nice format (can be viewed ...
0
votes
0answers
32 views

Zero Knowledge Proof: Prove correct ElGamal encryption without leaking message

I know it is possible to prove zero knowledge that a given ElGamal ciphertext $(c,d)$ encrypts a plaintext belonging to some set ($\{0,1\}$ is frequently used for electronic voting applications). Next ...
1
vote
1answer
38 views

ElGamal Encryption over a Subgroup

Say for instance we are encrypting over a subgroup of ($Z_{67}^*, \bmod 67$). To perform a round of El Gamal's encryption scheme we should: Choose a subgroup of ($Z_{67}^*, \bmod 67$), of prime order....
0
votes
1answer
58 views

Problem about complexity of Chinese remainder theorem

I have a question about CRT. Assuming, that we have this system (S): x=a0 mod n0 x=a1 mod n1 with N=n0*n1 and n0,n1 are two distinct prime numbers. Then the complexity in terms of binary operation is ...
1
vote
0answers
42 views

Security of an ECDSA Adaptor Signature Implementation

I'm currently working on an implementation of ECDSA Adaptor Signatures, and part of the signature scheme calls for a NIZK proof to verify knowledge of exponent over two public keys that share a ...
0
votes
1answer
40 views

Is this an instance of a Diffie-Hellman problem?

Let $\mathbb{G}$ be a cyclic group of order $p$ with generator $g$, and let $m\in\mathbb{G}$. Problem: Given $c=m.g^{k.a}$ and $v=g^a$, where $k,a \in \mathbb{Z}^*_p$, output $k$. Is this an instance ...
2
votes
0answers
55 views

Is there any way to encrypt the path in between a small number of 3D positions?

Or more general: given two valid random cipher $c_0, c_1$ a function $D$ with $$D(c_0,c_1) = (a,b,c)$$ should exist but hard to compute (for most cases). The result $(a,b,c)$ represents the path from $...
0
votes
0answers
49 views

Proof of knowledge of discrete log

Suppose that $P = pG = H(rK)G$, where $P$ is a point on an elliptic curve, $H$ is a hash function, $rK = kR$ is a shared secret between the party that knows $r$ and the party that knows $k$, and $G$ ...
2
votes
2answers
94 views

In which case number field sieve/index calculus is faster for solving discrete logarithm?

Given the normal discrete logarithm problem: $$a = b^c \mod{P}$$ with prime $P$ and numbers $a,b,c$ For which kind of $P,b$ the NFS/IC algorithm is faster than Baby-Step/Giant-Step+ Pollard's Rho ($\...
1
vote
1answer
101 views

How does the security of Elliptic curve compare to normal discrete logarithm?

Intro: EC are often compared with RSA but how about a more safe version of the discrete logarithm? All 3 can be reduced to the problem: $$b = g^a \mod{P}$$ In RSA $P$ is a product of two primes. To ...
1
vote
1answer
40 views

Clarification of Advantage vs Probability/Success of an Adversary

In cryptography, for a polynomial time-bounded adversary $\mathcal{A}$, given a scheme $\Pi$, the success or probability of succeeding $\mathcal{A}$ is the likelihood for $\mathcal{A}$ to break $\Pi$, ...
3
votes
0answers
82 views

How can the Number Field Sieve attack the discrete log in $\mathbb Z_p^*$ of DSA?

The Digital Signature Algorithm (DSA) uses $L$-bit prime $p$ and $N$-bit prime $q$ with $q| p-1$, i.e., $p = r\cdot q +1$ ( Schnorr group if $r>2$ and safe prime if $r=2$). In a way, the security ...
1
vote
0answers
24 views

what is the probability for an adversary to find the new key after adding new entropy in a group where computational diffie hellman is hard?

Let's say I have an Elliptic curve group $E(\mathbb{F}_q)$ with base Point $G$ and large prime order $n$. Computational Diffie-Hellman is assumed to be hard in that group. $H: \{0,1\}^*\rightarrow \{...
1
vote
0answers
32 views

How hard will it be to solve an equation in elliptic curve group/ cyclic group where Discrete Logarithm is hard?

Given an Elliptic curve group $E(\mathbb{F}_q)$ where the Discrete Logarithm Problem (DLP) is hard and a base point $G \in E(\mathbb{F}_q)$ with large prime order $n$, what will be the advantage of a ...
1
vote
0answers
77 views

Find solution to discrete logarithm equation

Task: Find $x$ with $3^{x}\equiv5\pmod p$, where (a): $p-1=2\cdot 3\cdot 101$; (b): $p-1=2\cdot 3\cdot 101\cdot 103\cdot 107^2$. I found a solution using online calc., but is there anyway except (...
1
vote
0answers
36 views

How to reconstruct the static private key of a Diffie Hellman client, when I can freely choose A, g and p?

I am struggling with a Diffie Hellman crypto challenge based on a client that uses a static private key. My goal is to trick the client into revealing enough information to reconstruct the private key ...
1
vote
1answer
66 views

Does this describe an invalid key share attack?

I recently came across a mention of invalid key share attacks on this site. It is done with DH groups over $\mathbb{ℤ}_p$ :prime $p$, where $p = qh + 1$, where $q$ is the prime order of DH subgroup ...
1
vote
1answer
120 views

Modular equation system

I have $N=p\cdot q$ and the following system where I know $A,B,C,D, k$: $$A = B \cdot q^k \pmod N$$ and $$C = D \cdot p^k \pmod N$$ Is there an easy way to recover $p$ and $q$?
0
votes
1answer
80 views

Discrete logarithm with 2 solutions? A clarification request

I need some clarification on the discrete logarithm problem... When a friend and I were solving for the discrete logarithm problem of 9 = 2 ^ x mod 11, we got two ...
0
votes
0answers
24 views

Does resuing pederson commitment preserve the hiding property?

Assume you have a pedersen commitment scheme where the commitment is: $$\mathcal C_1 =C(m,r)=g^m\cdot h^r$$ with $g,h$ being public generators in a public group $(G,\cdot)$ in which the discrete ...
1
vote
0answers
35 views

Question about hiding commitment scheme for integers

Given a generic group $\mathbb{G}$ of an unknown order (such as a $3000$-bit RSA group) and a randomly generated element $g \in \mathbb{G}$, is the commitment scheme $\mathrm{Com}(x)= g^x$ not ...
1
vote
1answer
72 views

Computing $g^y\bmod p$ from $g^{y^2}\bmod p$ if Diffie-Hellman is compromised?

Given generator $g$ of a multiplicative group mod a prime $p$ the Diffie Hellman problem is to find $$g^{xy}\bmod p$$ from $g^x\bmod p$ and $g^y\bmod p$. The best way to solve this is through discrete ...
0
votes
0answers
76 views

A card game (for mental poker or any other card game)

I thought of a way to produce trustless card game in a flexible way. One feature that I want is it should be flexible (It should work for any type of card game, though I indeed started it as a ...
1
vote
2answers
111 views

Question about the proof of the change of base formula for the discrete logarithm

I was looking at the proof of a change of base formula for the discrete logarithm in this paper (page 6, 4th bullet indent). In the intruduction, the paper states: Let $F_q$ be a finite field of order ...
1
vote
1answer
58 views

By what modulo calculations with discrete logarithms are performed?

For odd prime $p$, I have been given a group $\mathbb{Z}_p^*$ of all invertible elements from $\mathbb{Z}_p$. Basically, $\mathbb{Z}_p^* = \{1,2,\ldots , p-1 \}$. I also have $a$ and $b$, which are ...
0
votes
2answers
72 views

Show how an efficient algorithm for computing discrete logarithms with base a can be used to efficiently compute discrete logarithms with base b

I have an exercise that says the following: Let $p$ be an odd prime, and let $a$ and $b$ be generators $\mathbb{Z}​_p^*$. Suppose that we have an efficient algorithm $A$ for computing discrete ...
0
votes
1answer
77 views

Breaking Elgamal private key

I have been given a task to explain if - given a public key and a portion of a private key (over 300bits) with a remain unknown of 80 bits - the private key can be broken with an algorithm faster than ...
0
votes
0answers
35 views

Is there a concept of Pedersen commitment “in the base”?

This question Can Elgamal be made additively homomorphic and how could it be used for E-voting? says ElGamal can be made homomorphic over multiplication. So you can have $(g^r, h^r g^m)$ (i.e., ...
1
vote
0answers
86 views

Where is factoring if discrete logarithm is broken?

Assume given $g^X\equiv h\bmod p$ where $g$ is of order $\frac{\lambda(p)}2$ where $\lambda(p)$ is Carmichael Lambda function applied to prime $p$ (so $2$ is invertible in exponent) we can compute $X$ ...
5
votes
1answer
294 views

Why do the discriminant and primality of the group order of an elliptic curve affect security?

In a book about cryptography and elliptic curves, there was a mention that not all curves are secure, and a statement than in order to pick a secure curve the curve must satisfy 3 requirements. The ...
0
votes
0answers
15 views

Is it hard to determine an automorphism when the mapped value by several compositions of the automorphism is given

Generalization of the Discrete logarithm problem to non-abelian groups is discussed by many authors. One of the generalizations is shown in MOR cryptosystem as in the below link, by considering the ...
10
votes
2answers
803 views

What is a “constant time” work around when dealing with the point at infinity for prime curves?

I've been working for some time, on designing a constant time solution for dealing with the "point at infinity" for prime curves. So, far I'm using the Standard Projective Coordinates for ...
3
votes
1answer
79 views

Why is this signature independent of the message?

Assume that we have the following signature scheme CL Signature: Choose a cyclic group $G = \langle g \rangle$ of order $q$. Uniformly and randomly choose two elements $x,y \in \mathbb{Z}_q$, and ...
0
votes
2answers
95 views

The Generator point and Mod P in ECDSA

I've been reading about The discrete logarithm problem as of recent and i decided to try it out on a small portion of numbers myself and i actually came to a mental gridlock after watching this Video....
2
votes
1answer
84 views

How does $g^{x^2} \bmod p$ help you find $x$?

I was thinking about the Diffie-Hellman key exchange. One fact that we seem to know is that given a group generator $g$, a prime $p$ and the expression $g^x \bmod p$ its believed to be hard to find $x$...
1
vote
1answer
123 views

Solving Diffie-Hellman vs DLP

I'm wondering what is the current knowledge regarding the difficulty of solving the Diffie-Hellman problem (DHP). Obvisously solving the DLP (discrete log) is at least as hard as solving the DH ...
0
votes
0answers
33 views

Strong Diffie-Hellman Problem

While reading the following paper about the Strong Diffie-Hellman Problem, i got curious about ways to compute $ g^{x^{l}} $ for unknown $x$ in an elliptic curve, without first solving the discrete ...
4
votes
1answer
91 views

Are there any public-key encryption schemes based on DLog?

There are public-key encryption schemes based on many different mathematical hardness assumptions, like the hardness of Decisional Diffie-Hellman problem, the hardness of the Factoring problem, the ...
2
votes
1answer
187 views

Discrete Logarithm problem with selected order

If the order of group ($p$)selected by attacker then discrete logarithm is still hard?
0
votes
0answers
38 views

Zero knowledge proof of Paillier cryptosystem

I have read the paper recently and I am curious about part 3. According to part 3, Bob sends a zero-knowledge proof such that $c_B=b\times_{E}c_A+_E E_A(\beta')$. Then Alice should first decrypt the ...
0
votes
1answer
21 views

On the hardness of addition when the elements of a field is represented by the powers of generator and possible any existant scheme

We can represent elements of a finite field $F$ in various ways polynomial basis and normal basis. There is one other; generator-based representation and this is based on the fact that the ...
0
votes
1answer
81 views

Problem related to the discrete logarithm problem

Let $G$ be a generator of a cyclic group in which the discrete logarithm problem is hard and $x$ and $u$ be scalars of the group such that $X = xG$ and $U = uG$, respectively. We want to compute $J = ...
0
votes
0answers
28 views

What are the consequences of Diffie Hellman problem in P?

Computational Diffie Hellman problem wants to know $g^{ab}$ given $g^a$, $g^b$ and $g$ while the discrete logarithm problem wants to know $x$ from $g^x$ and $g$. The latter resolvable in polynomial-...
1
vote
1answer
61 views

DH: Is it possible to solve for A private if all other variables are known with 90-bit modulus

$g^{ab} \pmod{p} = B^a \pmod{p}$ where all variables are known except $a$. In this case, I have an equivalent value for $a'*b'$, but this is not the same as the real values of $a*b$ due to the modulus....
6
votes
0answers
194 views

RSA like trapdoor permutations in Discrete logarithm

In RSA, given only $(n,e)$, where $n =pq$ and $e$ is the public exponent, it is hard to find $p$ and $q$. It also seems hard to find $d$. So we came up the RSA conjecture that is RSA defines a ...
5
votes
2answers
197 views

Why use prime number $q$ such $q$| $(p-1)$ in discrete logarithm based schemes?

In discrete logarithm based schemes on finite field we have a prime number $q$ that divides $p-1$ and $q$ is to specify a subgroup with the order $q$. But why do we do that? Why do not we work on the ...
2
votes
1answer
51 views

Is matrix elliptic curve discrete logarithm problem quantum-safe?

I can't be the first one to think of this and there must be a reason nobody design cryptosystem off this problem. Let's define MECC as matrix of elliptic curve points, and MI as matrix of non-negative ...
0
votes
1answer
110 views

Proof of (in)distinguishability based on DDH/CDH/DL

I am wondering whether or not it is known that the following problem is computationally infeasible while working in a group for which the DDH (or CDH or DL) assumption holds (as usual, g is a group ...
0
votes
0answers
43 views

Is that proved that breaking ECDSA as hard as solving ECDLP? [duplicate]

Is that proved that breaking ECDSA (Elliptic Curve Digital Signature Algorithm) as hard as solving ECDLP(Elliptic Curve Discrete Logarithm Problem)?
0
votes
1answer
70 views

May an adversary be fooled by a random-looking input that in reality is fixed?

I want to prove the EUF-CMA-security of a signature scheme. It is a variation on an established scheme, therefore I would ideally like to reduce the new-scheme-security to the old-scheme-security. the ...

1
2 3 4 5
10