Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.
12

The main difference is that Pohlig-Hellman is a symmetric cypher, while RSA is a public key system. This is because, with Pohlig-Hellman, anyone who knows the encryption key $e$ can compute the inverse operation (because the 'decryption' key $e^{-1} \bmod p-1$ is easy to compute), while the RSA, someone who knows the encryption key $e$ (but not the ...


9

Does the factorization of N somehow help me? It sure does. I think I could compute the logarithm modulo each prime and then combine it, but do not know how exactly. Seems similar like problems for Chinese remainder theorem but I cannot find the way how to do it. You're real close; you do recombine them using the Chinese Remainder Theorem; however the ...


9

You need a large random prime modulus where the discrete log is hard. Read about how to choose a prime so the discrete log is hard. Also, you want $p-1$ to have as few small factors as possible. Therefore, the short version is, I suggest you choose a large random 2048-bit prime $p$ such that $(p-1)/2$ is prime. However, Pohlig-Hellman has some serious ...


8

Yes. Such proofs are possible for El Gamal. It involves a zero knowledge proof of equality of a discrete log, together with the homomorphic property of El Gamal encryption. Recall that given $E(a)$ and $E(b)$, anyone can form $E(a/b)$ using the homomorphic property of El Gamal. Suppose $E(a/b)=(r,s)=(g^k,h^k a/b)$ (where $g$ is the generator and $h$ is ...


7

To clarify a little, you need "encryption" that is commutative, deterministic (otherwise the commutative ciphertexts won't necessarily match even if the plaintexts do), and has a private encryption function (otherwise given that it is deterministic and the plaintext space is small, an exhaustive search would be possible). For example, Elgamal is commutative ...


6

Is there any better algorithm ? Actually, your second algorithm (select a small set of primes $\{ 2, q_1, q_2, ..., q_n \}$ and check if $\ 2q_1 q_2 ... q_n + 1$ is prime) is quite efficient. You say that it's trial and error (and it is), however it's about as efficient as the traditional algorithms we use to search for primes; if you're looking for an $q$ ...


6

I was wondering if this could be trivially adapted to be done over elliptic curves If you don't mind the plaintexts being confined to points on the curve (as opposed to elements of $\mathbb{Z}^*_p$), then it's easy; pick a key $k$ that's relatively prime to the curve order $q$ (easy to do if you pick a curve with prime order), and then: $$\begin{align} ...


5

I don't know the general answer, however, it appears that Baby-step Giant-step is able to give you the solution in $O(\sqrt{in})$ time (where $n$ is the size of $G$); this is $O(\sqrt{i})$ times longer than it takes the same algorithm to solve a single discrete-log problem. The first observation is that if you know the group order $n$ and a group generator $...


4

Generally speaking, this algorithm uses the Chinese Remainder Theorem to split up the group order, and then uses a Babystep-Giantstep algorithm for each prime factor potency of the group order. If the group order is smooth (all prime factors are small, s.t. all BS-GS algorithms can be done efficiently), this can be done very efficiently. However, the ...


3

Choice of public modulus $p$ Using for $p$ a large safe prime (that is, a prime $p=2q+1$ with $q$ also prime) is the way to go for the Pohlig-Hellman cipher, because that simplifies the choice of encryption key $k$: a random odd $k$ in range $[1,q-2]$ will do, because that ensures that $\gcd(k,p-1)=1$ (the condition for validity of an exponent in the ...


3

Note that $\alpha$ is a primitive element in $GF(p)$ and $\gamma_i$ is a generator of a subgroup $G_i\subseteq GF(p)$ with order $p_i$, i.e., $G_i=\{\alpha^{(p-1)/p_i},\alpha^{2(p-1)/p_i},\ldots,\alpha^{p_i(p-1)/p_i}(=1)\}$. Since $y^{(p-1)/p_i}\in G_i$, there exists a unique value $b_0\in \mathbb{Z}_{p_i}$ such that $y^{(p-1)/p_i}=\gamma_i^{b_{0}}$. To ...


3

Although I was not able to run the scripts (perhaps my fault, my Python skills are mediocre at best), let me try to elaborate (slightly) on fkraiem's comment. You are indeed right that the complexity of Pohlig-Hellman is lower than the complexity of BSGS (for a curve of smooth order). However, your parameters are relatively small. Looking at the definition ...


3

I'm not sure if I understand the question correctly, but let's try anyway. By assumption we have some integer $m$ such that $\varphi(m)=2pq^5r^2$ for primes $p,q,r$. The goal is to solve a discrete logarithm problem in $\mathbb{Z}_m^*$, say we have $g,h\in\mathbb{Z}_m^*$ such that $h=g^\ell$ for some integer $\ell$. We note that $\mathbb{Z}_m^*$ is a ...


3

You forgot step 4: $m$ and $s$ should each be primitive roots mod $p$ and mod $q$ $m$ is not a primitive root mod $p$. We can easily deduce that (without the bother of actually performing any nontrivial math) from the relation you gave: $$s^{e_p} = m \bmod p$$ for $e_p$ even; hence $m$ must be a quadratic residue, and hence cannot be primitive. ...


3

The right solution is to use a private set intersection protocol. Using Pohlig-Hellman is not the best approach. This problem has been studied in the literature, and there are sophisticated and effective solutions available; they go by the name "private set intersection". In other words, you are asking the wrong question. You have a particular ...


2

The answer to the final part of the question about index calculus depends on the finite field you are choosing to construct your group $G$. If the characteristic is large enough, the algorithm to use is the number field sieve. In this case, computation of individual logarithms is much faster than the initial computation that leads to logarithm of the ...


2

You are in a twist here: semantic security (equal to IND-CPA) can only be fulfilled by probabilistic encryption schemes. You need a deterministic encryption scheme for your drop-out tolerance. As it was pointed out previously, any homomorphic encryption allows you to proof in zero knowledge the equality of two ciphertexts: known: $c_0 = E(x,r_0)\;,\;c_1 = ...


2

Pohlig–Hellman algorithm can't be used as is, but it can be modified to make use of known partial factorization of $n$. Suppose that you need to find such $x$ that $g^x=h$. This can be done as follows: Choose small $k'$ such that $k'\ge k$. If the upper bound on $n$ is $n'$, then $k'=\lfloor\log_pn'\rfloor$ can be used. Set $g'=g^{p^{k'}}$ and $h'=h^{p^{k'}}...


2

I believe this protocol should be satisfying the requirements of an Oblivious PRF. This protocol is (nearly) identical to what is proven secure as an OPRF in the OPAQUE paper (Appendix A). There the OPRF is described (up to some formal notation) as follows, I'll annotate your notation in parenthesis: Parameters: A multiplicatively-written Group $\mathbb ...


1

A field like $GF(2^n)$ is represented by the residue classes of polynomials modulo $f(x)$ where $f \in GF(2)[x]$ is an irreducible polynomial of degree $n$ with binary coefficients. There are $2^n$ such polynomials $$a(x)=a_0+a_1 x+ \cdots+ a_{n-1} x^{n-1}.$$ Addition is by mod 2 addition of coefficients. When you multiply two polynomials, you take the ...


1

So if modulus, n is composite (i.e. non-prime) and the base is NOT a generator of Zn. Actually, if $n$ is has two distinct odd primes as factors, there will never be a generator; that is, there will never be a value $g$ where $g^x \bmod n$ takes on all values in $\mathbb{Z}_n^*$ Will PH algo still work and if so, why? If you know the factorization of $n$...


1

When solving for $x$ in the equation $g^x \equiv h \text{ mod } p$ the idea behind Pohlig Hellman is to solve discrete logs on group elements with smaller orders and then recombine those results to obtain $x$. For each prime factor $q^e$ of $p-1$ you do the following: Find an element with order $q^e$. You can do this via $g' = g^{\frac{n}{q^e}} \text{ mod }...


1

Because $x$ is defined modulo $28$ ($2^{28} = 2^0$ in $(\mathbf{Z}/29\mathbf{Z})^*$), you can view $x$ as an element of $\mathbf{Z}/28\mathbf{Z}$, while $2$ and $3$ are elements of $(\mathbf{Z}/29\mathbf{Z})^*$.


1

[Isn't this] just as hard as the RSA problem? Oddly enough, no. If we were given a random $p$, and were asked to see if there's a large prime factor $q$ of $p-1$, yes, that would be, on average, a hard problem. However, that's not what we actually do. Instead, we get to pick $p$, and so that gives us a lot of flexibility. One way is to pick $q$ first (...


1

You are correct in the procedure. You need to express $x$ as $x = 2^0x_0+2^1x_1+2^2x_2+...+2^{15}x_{15}$ Where the $x_i$ are in $GF(2)$ First compute: $3^{(0*(p-1)/2)} \pmod p \equiv 1$ $3^{(1*(p-1)/2)} \pmod p \equiv 65536$ So that when you'll compute $2^{65536/2^{i+1}} \pmod p$ you'll get either 1 (corresponding to $x_{i} = 0$) or 65536 (corresponding ...


1

With any convergent encryption algorithm E, it's easy for Alice to prove -- without revealing(*) a, b or the private key -- that a == b. In order for the data deduplication feature to work, convergent algorithms are specifically designed such that when Alice encrypts two messages a and b, such that x=E(a), y=E(b), then x == y whenever a == b. There's some ...


Only top voted, non community-wiki answers of a minimum length are eligible