Unanswered Questions
3,568 questions with no upvoted or accepted answers
34
votes
0answers
2k 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 ...
33
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 ...
22
votes
0answers
800 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). ...
18
votes
0answers
837 views
Crypto AG (Switzerland) - Which algorithms were used and how did the backdoors work?
Backstory
Crypto AG was a company located in Switzerland that specialized in communication security. They produced a number of encryption machines (some similar to the infamous Enigma) used for ...
16
votes
0answers
326 views
Adding bit constants to the key schedule to reduce rounds?
Bit constants are often added to the key schedule to reduce slide attacks. I have reviewed David Wagner's work, where he showed that the increased rounds in a Feistel network do not help if you have ...
16
votes
0answers
338 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 ...
15
votes
0answers
286 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 ...
15
votes
0answers
289 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 ...
14
votes
0answers
225 views
The aftermath and considerations of the new record of 30750-Bit Binary Field Discrete Logarithm - 2020
Granger et al. recently published a paper about breaking a record for discrete logarithm on the Binary field
Computation of a 30 750-Bit Binary Field Discrete Logarithm, Robert Granger and Thorsten ...
13
votes
0answers
2k views
Has Telegram security been significantly improved with MTProto 2.0?
Telegram messenger's original encryption scheme, MTProto 1.0, has been shunned by most cryptographers for a number of reasons, like being vulnerable to IND-CCA attack; being unorthodox in general, ...
13
votes
0answers
795 views
Given a 'good' basis for a lattice, how can we solve the CVP?
I'm doing a little bit of reading about lattices. I read that if we can find a 'short' basis for our given lattice, we can solve CVP and SVP very efficiently. However, the paper didn't describe an ...
13
votes
0answers
192 views
Space complexity of quantum collision search?
Is there a known way to reduce the space complexity of quantum collision search (PDF) beyond what is offered by the built-in time-space tradeoff, while keeping the time complexity significantly below ...
12
votes
0answers
219 views
RSA key such that pi deciphers to your name per RSA-OAEP
Can you efficiently construct an RSA public/private key pair with $8k$-bit public modulus such that $C=\left\lfloor\pi\,2^{8k-2}\right\rfloor$ deciphers per RSA-OAEP to your name as a bytestring in ...
12
votes
0answers
426 views
How Significant is the New Quasi-Polynomial-Time Attack on Fixed Characteristic Discrete Logarithms?
There is a new paper by Kleinjung and Wesolowski on eprint that claims and proves a new attack on the discrete logarithm problem in finite fixed characteristic fields in quasi-polynomial time.
...
12
votes
0answers
1k views
Yaos Millionaire Problem: Why distance >= 2?
I'm currently reading about Yao' Millionaire Problem: http://research.cs.wisc.edu/areas/sec/yao1982-ocr.pdf
Alice and Bob want to know which of them is richer.
Let $j \in \{1, \cdots 10\}$ be Bobs ...
