# Tagged Questions

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.

87 views

### What does Shor's algorithm tell us about the complexity class of RSA and the DLP?

If quantum computers operate in BQP and (using Shor's algorithm) they are able to factor large integers and break the discrete log problem, what does that tell us about the complexity class of these ...
60 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 ...
59 views

### Using Shor's algorithm to solve the discrete logarithm problem

I have read about Shor's algorithm and my understanding is that it can be used to factor large numbers efficiently. Can Shor's algorithm, though, be used to solve this problem: Find the number $e$ ...
29 views

### Why $p-1$ needs large factors in discrete logarithm?

In discrete logarithm over cyclic group $\Bbb Z_p$ where $p$ is a prime or $p=q^n$ a prime power it is desired that $p-1$ needs to have large factors except for $2$. What is the consequence even if ...
57 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 ...
62 views

### How to calculate the exponent in modular exponentiation?

I have a problem when calculating power in modular, $a^b \bmod c = d$. where we can know values of $a$, $c$ and d, but we don't know values of $b$. example : $29^b \bmod 1024 = 365$. So, how can I ...
86 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$ ...
77 views

### How secure is this logarithmic encryption algorithm?

How secure would the following logarithmic encryption algorithm be when tested under the same conditions as high end encryption algorithms (AES, RSA etc...). Note: For smaller text the text will be ...
67 views

65 views

### Suppose $A$ knows $a$ and $B$ knows $b$, is it possible to efficiently compute $g^{ab}$ without leaking $g^a$ and $g^b$ to each other?

I know the garbled circuit solution, but is there any more efficient method?
78 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 ...
103 views

### Is $(a,g^{ab})$ computationally indistinguishable from $(a, g^c)$?

From wikipedia, the DDH assumption says，given a cyclic group $G$ of order $q$ with generator $g$, $(g^a, g^b, g^{ab})$ looks like $(g^a, g^b, g^c)$ where $a,b,c$ are randomly and independently chosen ...
I was reading 'Pinocchio Coin' paper by Danezis et al. where they have said, "If we use the efficient pairing groups of Pinocchio, computing discrete logarithms in the exponent field $\mathbb{F}_p$ ...