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.
2
votes
1answer
68 views
Why is the discrete log problem easy when the exponent comes from a binomial distribution?
I read in http://epubs.surrey.ac.uk/7219/2/esorics06.pdf that in exponential El Gamal the discrete log problem for recovering $m$ from $g^m$ can be made tractable when $m$ is drawn from a binomial ...
3
votes
1answer
94 views
Trying to better understand the failure of the Index Calculus for ECDLP
So I'm going to give you guys my understanding and then if you would be so kind as to tell me where I'm off the mark (hopefully I'm not completely wrong).
So basically the index calculus for the ...
2
votes
1answer
42 views
How is ElGamal not secure under chosen ciphertext attack, but semantically secure in some cases?
I know that you can create a ciphertext c' using c and then find the corresponding m' for c' which you can use to find m for c. So, doesn't this mean that it is not semantically secure? But I also ...
3
votes
1answer
50 views
Chosen ciphertext insecurity in an ElGamal variant
I'm trying to prove something and if I can show that there is a simple way to calculate $(g^a \bmod p)^k$ if I know both $g^k \bmod p$ and $g^a \bmod p$, then (I think) it will help me prove it, but ...
6
votes
1answer
129 views
Solving hard problems in $\mathbb Z_{p}^{*}$ when $\mathbb p$ is close to $\mathbb 2^{n}$
Suppose, for some security parameter $n$ you choose a prime $p$ such that $p = 2^n+c$ for some relatively small $|c| < 2^m << 2^n$. I have seen such primes being called Pseudo-Mersenne Primes ...
2
votes
1answer
106 views
DLP based crypto systems with multiple independent generators
One example of a DLP based crypto system (or rather DDH based crypto system) where the public key parameters include two independent generators of the subgroup, is Cramer Shoup. Since the security ...
3
votes
1answer
69 views
How hard are discrete logarithms problems in $\mathbb Z^{*}_{n}$ and $\mathbb Z^{*}_{n^2}$, where $n$ is the RSA $n=pq$
Use the notations form the Wikipedia article Paillier Cryptosystem
, assume that the chipertext $c$ and $c^{\lambda} \mod n^2$ are both given, is it possible to compute $\lambda$ easily?
4
votes
0answers
162 views
Security of pairing-based cryptography over binary fields regarding new attacks
In the last week, the discrete logarithm problem was broken for the binary fields $\mathbb{F}_{2^{(14 \times 127)}}$ and $\mathbb{F}_{2^{(27 \times 73)}}$.
Pairing-based cryptography using binary ...
5
votes
2answers
175 views
Why would this method of discrete logarithm finding not work?
Say we do know $b$ but not $k$, and are given $g$ such that $g\equiv b^k\pmod p$. And say there exist factors $E = e + m'p$ ($e \equiv b^i \bmod p$) and $F = f + m''p$ ($f \equiv b^j \bmod p$) of $g$. ...
2
votes
1answer
69 views
Discrete log analog of ECM factoring algorithm?
Anecdotally, most factoring algorithms have a corresponding variant algorithm that can be used to attack the discrete log problem using similar ideas.
Is there an analog of the elliptic curve (ECM) ...
2
votes
1answer
74 views
How much do we trust KEA1 Assumption?
Let $$(g,h=g^s,q)$$ be a tuple such that $g$ is a generator for a group $\mathbb{G}$ of ord $q$ and $s$ is uniformly random in $\mathbb{Z}_q$.
The KEA1 Assumption saies that for any adversary ...
2
votes
1answer
52 views
Discrete logs on elliptic curve with embedding degree 3 with the 'MOV' attack
The curve $E(\mathbb{F}_{47}):y^2=x^3+x+38$ has order $61$ and $61|47^3-1$ so the embedding degree of $E$ is $3$ and therefore the MOV attack, presumably using some sort of distortion map and a ...
0
votes
0answers
47 views
How compared encryption algorithm in terms of efficiency
I doing to compare two algorithm cryptography. first algorithm is RSA cryptography and second algorithm is El Gamal elliptic curve cryptography. now I want a way to compare between two algorithm by ...
2
votes
1answer
271 views
Why can't I break ElGamal encryption by brute-forcing the secret exponent?
I am doing a course on cryptography on coursera and one of the topics covered was the ElGamal Encryption system.
I am using the terms as defined in Wikipedia.
Alice publishes $g$ and $g^x$. ...
2
votes
2answers
112 views
Probability that an attacker wins the discrete logarithm game when exponents are drawn from a subset
Suppose $g$ is a generator of an order $p$ cyclic group in which discrete logarithm is hard and $p$ is a prime (i.e., given $g^x$ for a random $x \in \{0,1,\ldots, p-1\}$, it is hard to recover $x$ ...
3
votes
1answer
69 views
iterated discrete log problem
Consider the following problem: given $g_1 \ldots g_i,h_1 \ldots h_i \in G$, $\forall i$ find $x_i$ such that $g_i^{x_i}=h_i$
For $i=1$ this is the discrete log problem and is assumed to to have ...
2
votes
0answers
163 views
Is there a practical zero-knowledge proof for this special discrete log equation?
We have a multiplicative cyclic group $G$ with generators $g$ and $h$, as in El Gamal. Assume $G$ is a subgroup of $(\mathbb{Z}/n\mathbb{Z})^*$. There are two parties, Alice and Bob:
Alice knows: ...
2
votes
1answer
216 views
Why are elliptic curve variants of RSA “chiefly of academic interest”?
Yesterday I was thinking about elliptic curve variants of popular protocols/algorithms (ECDH, ECES[1], etc) and the thought occured that I had never seen an elliptic curve variant of RSA. My ...
3
votes
1answer
179 views
A discrete-log-like problem, with matrices: given $A^k x$, find $k$
Let $p$ be a large prime; we will work in $GF(p)$. Let $A$ be a $n\times n$ matrix. Also, let $x$ be a $n$-vector and $k$ a positive integer.
Suppose we are given $p$, $A$, $x$, and $y$. The goal ...
3
votes
0answers
125 views
Finding where I am in a linear recurrence relation
Suppose I have a linear recurrence relation
$$a(n) = c_1 a(n-1) + \dots + c_k a(n-k) + d,$$
where the constants $c_1,\dots,c_k,d$ are given and the initial values $a(0),\dots,a(k-1)$ are given as ...
2
votes
3answers
193 views
Discrete log problem, when we have many examples
Suppose I have many instances of the discrete log problem, all using the same unknown exponent. Is this problem easier than the standard discrete log problem?
Oh, heck, I should be more precise. ...
2
votes
1answer
144 views
Stream ciphers based on discrete logs
Blum Blum Shub is a stream cipher that is provably reducible to the difficulty of factoring integers.
I'm wondering whether there is a similar construction for discrete logs?
For example, I could ...
2
votes
2answers
136 views
Is there a way to compare the 923 bit pairing based key with RSA or AES, etc
I've see many articles, most of them basically the same, praising Fujitsu for cracking what is referred to as a 923 bit pairing based encryption. I understand that in comparing RSA to AES you've got ...
3
votes
2answers
202 views
How can I solve the discrete logarithm modulo 2q+1 if I can solve it in the subgroup of order q?
As part of my cryptography course I came across an exercise that neither me or my friends could figure out.
The problem statement is as follows:
Let $p$ be a large prime of the form $p = 2q + 1$ ...
2
votes
0answers
129 views
Safe generator for ElGamal signature
What are the properties a generator $g$ should have to be secure for ElGamal signatures (original scheme)?
I am aware that it is poorly chosen and not secure when $g|p-1$ or $g^{-1}|p-1$, where $p$ ...
2
votes
1answer
169 views
Finding a solution to a (sort of) discrete logarithm by asking questions
Let $p = kq + 1$ and $q$ be primes such that $log$ $q = n$, $log$ $k = n$ and such that the bit size of every prime factor of $k$ is bounded
by $log$ $n$. Let $g$ be a generator of the unique ...
2
votes
2answers
329 views
ECC algorithm pollard's $\rho$ complexity
One of the methods to break a ECDLP is Pollard's rho algorithm. When ECDLP is defined over a finite field $F_p$, and given a relation $S=w.T$, where S and T are a member of $F_p$. Then ECDLP is to ...
4
votes
0answers
78 views
RSA security assumptions - does breaking the DLP also break RSA? [duplicate]
Possible Duplicate:
Would the ability to efficiently find Discrete Logs have any impact on the security of RSA?
I'm wondering if breaking the DLP, that is the basis for ElGamal and DSA, ...
3
votes
3answers
911 views
What should be the size of a Diffie-Hellman private key?
I'm implementing the SRP-6 protocol, which relies on discrete logarithms for it's security (essentially Diffie-Hellman).
The RFC documents state:
The private values $a$ and $b$ SHOULD be at least ...
3
votes
3answers
405 views
What is the relation between Discrete Log, Computational Diffie-Hellman and Decisional Diffie-Hellman?
How are the three problems Discrete Logarithm, Computational Diffie-Hellman and Decisional Diffie-Hellman related?
From my understanding, since the Discrete Log (DL) Problem is considered hard, then ...
10
votes
2answers
267 views
Are safe primes $p=2^k \pm s$ with $s$ small less recommandable than others as a discrete log modulus?
I take the definition of safe prime as: a prime $p$ is safe when $(p-1)/2$ is prime.
Safe primes of appropriate size are the standard choice for the modulus of cryptosystems related to the discrete ...
4
votes
2answers
230 views
An Elliptic curve cryptography implementation which can be terminated
I'd like to have an implementation of elliptic curve cryptography along the lines of secp256k1 which is secure until some information is published after which it is broken.
One idea would be to use ...
6
votes
3answers
434 views
Would the ability to efficiently find Discrete Logs have any impact on the security of RSA?
This answer makes the claim that the Discrete Log problem and RSA are independent from a security perspective.
RSA labs makes a similar statement:
The discrete logarithm problem bears the same ...
6
votes
3answers
266 views
Mapping between subgroups and the integers
This question is a companion to the equivalent question on elliptic curves.
Preliminaries
Diffie-Hellman, Elgamal, DSA, etc. are examples of protocols that work in the integers modulus a large prime ...
1
vote
2answers
155 views
Is there a cumulative commitment scheme?
For a certain application I need a commitment scheme where each user could make a commitment, and a single verification operation could verify all the commitments simultaneously, faster than single ...
3
votes
1answer
857 views
How to practically find solutions to a discrete logarithm?
Are there any ongoing or current practical attempts to solve instances of the discrete logarithm problem of the order of magnitude used in cryptographic applications, for example with a 256 bit ...
5
votes
1answer
119 views
Are there security issues with discrete logarithm keys not being uniformly distributed?
Generally, algorithms based on discrete logarithm specify that private keys are chosen as scalars between 1 and the order of the group (denoted q here). For instance IEEE P1363 and FIPS 186-3 both ...
11
votes
3answers
750 views
How robust is discrete logarithm in GF(2^n) ?
"Normal" discrete logarithm based cryptosystems (DSA, Diffie-Hellman, ElGamal) work in the finite field of integers modulo a big prime p. However, there exist other finite fields out there, in ...
