Questions tagged [pohlig-hellman-cipher]

In group theory, the Pohlig–Hellman algorithm, sometimes credited as the Silver–Pohlig–Hellman algorithm, is a special-purpose algorithm for computing discrete logarithms in a finite abelian group whose order is a smooth integer.

Filter by
Sorted by
Tagged with
0 votes
1 answer

Cryptographic Systems Involving Modular Exponentiation

I am going through an "Introduction to Cryptography" chapter in my Elementary Number Theory course, wherein I'm studying cryptographic systems involving modular exponentiation. The textbook (...
Key76's user avatar
  • 3
1 vote
1 answer

How to decrypt Pohlig-Hellman cipher if e and (n-1) aren't relatively prime

I couldn't find any articles that addressed to how to decrypt c after it was encrypted using the Pohlig-Hellman cipher if $e$ and $n-1$ aren't relatively. Can someone please tell me how to do it? I ...
Yolo's user avatar
  • 21
3 votes
2 answers

Is the encryption more secure if we apply Pohlig-Hellman cipher twice with different keys but with the same modulus?

To encrypt a message $M$, we compute $C=M^k \bmod p$ and to decrypt a Cipher-text we compute $M=C^{k^{−1} \bmod (p−1)} \bmod p$ But if we use Pohlig Hellman twice like $C_1=M^k \bmod p$, and then $...
Ayush Gupta's user avatar
3 votes
1 answer

Weakness in Pohlig-Hellman algorithm

Let's try to solve a discrete logarithm: $\beta \equiv \alpha ^{x} \bmod \,\, p$ using the Pohlig-Hellman algorithm. Let's suppose that $p-1=tq$, where $q$ is a large prime number. This means that ...
AleWolf's user avatar
  • 461
0 votes
1 answer

Can we use Pohlig-Hellman Exponentiation Cipher with a PRG to achieve an oblivious PRF

The Commutative Cipher Setup Alice and Bob agree on a 2048-bit safe-prime $p$, where $(p-1)/2$ is also a prime. Both parties have an encryption exponent $e$ in the range $(1, p-1)$ with $gcd(e, p-1) =...
zetaprime's user avatar
  • 591
6 votes
1 answer

Can Pohlig-Hellman encryption be done over elliptic curves?

Following a bunch of questions on the topic of Pohlig-Hellman encryption. I was wondering if this could be trivially adapted to be done over elliptic curves just like we create EC-DH instead of DH. ...
Meir Maor's user avatar
  • 11.7k
13 votes
1 answer

Is Pohlig-Hellman Cipher the only option?

I am looking for a cipher which would allow something like this: E(E(M, a), b) = E(M, ab), where a and b are encryption keys, and ab is a combination of the keys that is impractical to separate into a ...
irakliy's user avatar
  • 969
2 votes
0 answers

Security aspects of a splitted Pohlig-Hellman system

Given a Polig-Hellman (is that really the name for that?) system with $$C = M^k \bmod p$$ where $M$ is the message, $C$ is the ciphertext, $k$ is a (secret) key (any integer relatively prime to $p-1$...
ChaosCoder's user avatar
1 vote
0 answers

Pohlig-Hellman exponentiation block cipher

Let $G$ be a group of order $n$ and let $e,d$ be integers such that $ed\equiv 1 \pmod{n}$. Then the exponentiation maps $x \mapsto x^e$ and $y \mapsto y^d$ are inverse maps on $G$. These maps give us ...
K.G.'s user avatar
  • 4,607
6 votes
1 answer

Security of Pohlig-Hellman exponentation cipher?

I am looking into implementing Pohlig-Hellman exponentiation cipher and I would like to know how secure that algorithm is? I am guessing it's security relates greatly to the prime number used in it. ...
ThePiachu's user avatar
  • 1,669
7 votes
3 answers

Is there a public key semantically secure cryptosystem for which one can prove in zero knowledge the equivalence of two plaintexts?

If Alice encrypts two messages $a$ and $b$, such that $x=E(a)$, $y=E(b)$. Can Alice prove (without revealing $a$, $b$ or the private key) that $a = b$? Obviously the proof must not be too long and it ...
SDL's user avatar
  • 1,867
5 votes
1 answer

What's the main difference between Pohlig-Hellman and RSA?

Both Pohlig-Hellman and RSA perform encryption and decryption by exponentiation modulo some integer ($p$ prime for PH, $n$ composite for RSA). They both use a key $e$ as the exponent to encrypt a ...
curious's user avatar
  • 6,140
9 votes
5 answers

Software implementation of a commutative cipher?

I've got an application (detailed below) that calls for the use of a cipher that is commutative. I've been doing some googling & reading, and there are two algorithms that seem to get mentioned ...
Roy Pardee's user avatar
8 votes
5 answers

Applications of Group Ciphers

I've been reading a paper [1], and I've ran across something called a "Group Cipher", which is similar to homomorphic encryption, with an important difference. In homomorphic encryption we have an ...
Mohammad Alaggan's user avatar