Unanswered Questions
3,351 questions with no upvoted or accepted answers
33
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 ...
32
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
752 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
736 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
312 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 ...
15
votes
0answers
272 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
317 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
266 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
191 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
744 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
179 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
204 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
413 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
984 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 ...
11
votes
0answers
201 views
The backdoor of Telegram on Diffie-Hellman Key Exchange and possible other examples?
Diffie-Hellman Key-Exchange (DHKE) should be used carefully during the end-to-end encryption. A man-in-the-middle (MITM) attack is possible.
Standard DHKE
The simple protocol on the multiplicative ...
