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

219 views

### Is it possible to determine or estimate the period for Blum-Micali PRG?

The Blum-Micali is a cryptographically secure pseudorandom number generator. The construction (from wikipedia): Let $p$ be an odd prime, and let $g$ be a primitive root modulo $p$. Let $x_0$ be a ...
710 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 ...
247 views

### Parallel Pollard's Rho: Number of distinguished points

When using the parallel version of Pollard's Rho algorithm for discrete logs, each processor performs its own random walk to find distinguished points, and reports the starting point and the ...
60 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 ...
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 ...
51 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 ...
35 views

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 $\... 0answers 68 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, ... 0answers 150 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 ... 0answers 47 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 ... 0answers 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 ... 0answers 43 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 ... 0answers 42 views ### Is it possible to generate backdoored DH parameters? I know it has been already asked and answered whether it's possible to generate weak DH parameters. But "recentely" we experienced the Logjam attack, which makes use of the pre-computation ... 0answers 45 views ### Testing PRNG quality from ECC public keys? Having a large set of ECC public keys$P_i = n_iB$on a fixed curve$E$over a prime field, is there a way to determine if coefficients$n_i$were generated using a bad PRNG? In other words, can a ... 0answers 95 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: ... 0answers 67 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 \... 0answers 18 views ### Sigma protocol: witness hiding I am working on an assignment and I am stuck with the last part of proving witness hiding for the protocol. I have previously proved it is witness indistinguishable, and it has q (primer number ... 0answers 39 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 ... 0answers 30 views ### Looking for an adjustable compute bound decryption function I'm looking for a way to decrypt data, but make it require varying amounts of CPU power to do so. Maybe this could be illustrated as e(m) = m' and ... 0answers 184 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 ... 0answers 89 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 ... 0answers 63 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 ... 0answers 99 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 ... 0answers 97 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 ... 0answers 700 views ### How compared encryption algorithm in terms of efficiency I want to compare two cryptographic algorithms. The first algorithm is RSA, and second algorithm is ElGamal elliptic curve cryptography. Now, I’m looking for a way to compare the speed of the two ... 0answers 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 ... 0answers 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 ... 0answers 31 views ### Is original DSA a TEGTSS-I scheme? Brickell et al. define TEGTSS-I scheme in paper "Design validations for discrete logarithm based signature schemes" In this paper original DSA is generalized as DSA-I variant where$r = g^k \bmod p \...
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 ...
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$ ...