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 ...
23
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 ...
19
votes
0answers
363 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
0answers
291 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 ...
14
votes
3answers
562 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 ...
13
votes
0answers
402 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). ...
12
votes
0answers
123 views
+50
Selection of rotation constants in ARX design
My question is about choosing the rotation values in ARX design such as SIMON-like or SPECK-like ciphers to provide optimal differential and linear immunity. According to this, the selection of $a$ ...
12
votes
0answers
130 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 ...
12
votes
0answers
177 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
204 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 ...
9
votes
0answers
523 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 ...
9
votes
0answers
309 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 ...
9
votes
1answer
581 views
Evaluating Algebraic Complexity of a S-box
While studying the design and the desirable properties of an AES S-box , I came to know that Algebraic Complexity is also an important property of an S-box which is usually considered while evaluating ...
9
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 ...
9
votes
0answers
423 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 ...
