Unanswered Questions
2,051 questions with no upvoted or accepted answers
29
votes
2answers
1k 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 ...
25
votes
0answers
1k views
Who first published the interest of more than two prime factors in RSA?
Multi-prime RSA is now a well known technique (described here): it uses $k>2$ distinct secret prime factors in the public RSA modulus, with the advantage that, using the CRT, we can gain a speed ...
14
votes
0answers
493 views
Memory-hard password hash in practice?
Dan Boneh, Henry Corrigan-Gibbs, and Stuart Schechter have proposed Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks (in proceedings of AsiaCrypt 2016). ...
13
votes
0answers
208 views
Name of an archaic type of RSA padding (0BBBBBBB…)
In some legacy code, I encountered RSA signature padding in the following format (hexadecimal):
0B BB BB BB BB BB BB ... BB BB <hash>
Is there a name for ...
12
votes
0answers
165 views
Fewest qubits required for the discrete logarithm problem and integer factorization
According to a paper from 2002, the most efficient circuit to factor an $n$-bit integer requires $2n+3$ qubits and $O(n^{3}\lg(n))$ elementary quantum gates, assuming ideal qubits. Later on, according ...
11
votes
0answers
240 views
Finding $x$ such that $g^x\bmod p<p/k$?
In a Schnorr group as used for DSA, of prime modulus $p$, prime order $q$, generator $g$ (with $p/g$ small), how can we efficiently exhibit an $x$ with $0<x<q$ such that $g^x\bmod p<p/k$, for ...
11
votes
1answer
2k views
Consequences of AES without any one of its operations
Suppose AES-$128$. There are $4$ operations in AES's encryption, they are SubByte, Shift Row, MixColumns and AddRoundKey.
Question: If I remove one of the following opearations, what will happen to ...
11
votes
0answers
448 views
Efficient decoding of irreducible binary Goppa codes and the role of matrix P in McEliece cryptosystem
If we assume that the support for an irreducible binary Goppa code $\gamma_1, ..., \gamma_n$ is publicly known, when is it possible to efficiently decode the code? I know it's possible if one knows ...
10
votes
0answers
148 views
Proving multiple products “in the exponent”
I'm trying to come up with a small-sized (non-interactive) proof for a Diffie-Hellman-like statement.
I'll start by giving an example.
The prover has $g^a, g^b, g^c, g^{ac}, g^{ab}, g^{bc}, g^{abc}$.
...
10
votes
1answer
292 views
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 ...
10
votes
0answers
328 views
Potential Flaws With Lattice Based Cryptography?
From researching post-quantum cryptographic schemes it seems hash-based and lattice-based algorithms are the most promising (MQ-based seem to be covered by patents and have more potential unknowns ...
10
votes
0answers
126 views
How exactly does ASKE (Alpha Secure Key Establishment) in Zigbee work?
I am working on Zigbee security. For key establishment, some approaches are given in Zigbee. Some of them are:
ASKE (Alpha Secure Key Establishment),
ASAC (Alpha Secure Access Control), and
SKKE (...
10
votes
0answers
573 views
Are there attacks against broken RSA signature pad checking with $e = 65537$?
Let's say that an RSA implementation of PKCS #1 signatures fails to validate that the 00 01 FF FF FF ... FF 00 portion of the decrypted signature is exactly as long ...
10
votes
0answers
1k views
Cracking a PRNG by observing ranks within groups of its output
Suppose that I am generating random numbers with Python's random module, so that there is a known random number generator (Mersenne Twister in this case). I've ...
10
votes
0answers
386 views
Why SIVP Is Worst Case Problem?
I just started to study lattice cryptography.
I'm now studying worst-case to average-case reduction for SIS.
In previous question, "worst means any and average means random".
And I wonder why ...
