Unanswered Questions
24
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 ...
14
votes
0answers
198 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 ...
13
votes
0answers
878 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 ...
12
votes
1answer
392 views
Is it better to maximize memory usage or number of passes with Argon2i 1.3?
I wrote a small application that uses Argon2i for deriving symmetric keys for encryption of local files and secret Curve25519 keys. Argon2i v1.3 is susceptible to TMTO attacks if the number of passes ...
12
votes
1answer
287 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 ...
11
votes
1answer
269 views
Turing's (still?) classified inference engine algorithm?
Does anyone know the algorithm used by Turing's Colossus inference engine, so highly classified that the Brits kept it secret for decades after WW II?
Indeed, it may still be classified. Several ...
9
votes
0answers
108 views
How many unique elements are generated by the equation in DSA for r?
How many unique elements are generated from the following equation?
$$i = (g^x \bmod p) \bmod n $$
where:
$g$ has order $q$
$q$ and $p$ are prime numbers
$q\mathop{|}p-1$
$n$ is integer number more ...
9
votes
0answers
135 views
Are there any signatures based on matrix multiplication with noise?
Are there any signatures based on matrix multiplication with noise? Representing the message as a matrix and multiplying with some randomness coming from another matrix such that the signature itself ...
9
votes
0answers
110 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 ...
9
votes
0answers
386 views
Parallel Pollard's Rho: Number of distinguished points
When using the parallel version of Pollard's Rho algorithm for discrete logs, each processor performs its own random walk to find distinguished points, and reports the starting point and the ...
9
votes
0answers
234 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 ...
9
votes
1answer
190 views
Quantum complexity of LWE
As per my understanding LWE is quantum secure because there is no known quantum algorithm to solve LWE in polynomial time. Due to the reductions given by Regev et al. If there is any algorithm that ...
8
votes
0answers
142 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). ...
8
votes
0answers
140 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
0answers
93 views
Which compression functions are PRFs?
In a 2006 paper Bellare showed that HMAC remains secure even if collision resistance for MD5/SHA-1 is broken as long they are still PRFs.
The Wikipedia article on cryptographic hash functions ...
