# 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.

503 questions
Filter by
Sorted by
Tagged with
0answers
4 views

### if they exist a relation between Decisional Composite Residuosity Assumption and Square roots in elliptic curve groups assumption

We have DCRA and ECSQRT assumptions. It is know that the Decisional Composite Residuosity Assumption and Square roots in elliptic curve groups assumption are related to factoring problem. I need to ...
1answer
81 views

0answers
58 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 ...
1answer
61 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....
1answer
72 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 ...
0answers
61 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 ...
1answer
49 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 ...
0answers
57 views

1answer
113 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 ...
1answer
46 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$, ...
0answers
92 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 ...
0answers
28 views