Unanswered Questions
26
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 ...
19
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 ...
17
votes
0answers
333 views
Uniform vs discrete Gaussian sampling in Ring learning with errors
The Wikipedia article on RWE mentions two methods of sampling "small" polynomials namely uniform sampling and discrete Gaussian sampling. Uniform sampling is clearly the simplest, involving simply ...
14
votes
3answers
490 views
Does a partial preimage attack imply a preimage attack?
Let's assume we have an $n$-bit hash function and a $b$-bit partial preimage attack that is faster than brute force. Does this imply a faster than brute force preimage attack on the whole hash?
It ...
12
votes
0answers
285 views
Has the distributed project “Number Fields @ Home” project benefited cryptography in any meaningful way?
Is there any new understanding, property, or knowledge that has come from the Number Fields @Home distributed computing project? Has any outcome advanced the study of cryptography, or altered ...
11
votes
0answers
166 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 ...
10
votes
0answers
360 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). ...
9
votes
0answers
112 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 ...
8
votes
1answer
140 views
AES cache-timing attacks and nonce-based operation modes
As I understand it, AES cache-timing attacks exploit the execution time variations due to cache hits/misses, especially the ones depending on the SBox look-up tables which are key-related.
To mount ...
8
votes
0answers
194 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 ...
8
votes
1answer
329 views
Homomorphic decryption circuit in integer-based scheme
I'm reading this excellent paper by Gentry as a smooth introduction to Fully Homomorphic Encryption. Most things are clear to me except from the way the homomorphic evaluation of the decryption ...
8
votes
0answers
492 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 ...
8
votes
0answers
296 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 ...
8
votes
0answers
3k views
Reasons for Chinese SM2 Digital Signature Algorithm
In the IETF RFC draft named "SM2 Digital Signature Algorithm" a signature algorithm is specified. The RFC does however not mention why this signature algorithm has been defined. Nor does it specify ...
8
votes
0answers
418 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 ...
