Unanswered Questions
2,337 questions with no upvoted or accepted answers
28
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 ...
22
votes
1answer
431 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
426 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). ...
14
votes
0answers
295 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 ...
13
votes
0answers
179 views
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$ ...
13
votes
0answers
183 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
140 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
218 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
657 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 ...
11
votes
0answers
1k 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
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 ...
11
votes
0answers
432 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
1answer
243 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
252 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 ...
