Unanswered Questions
4,172 questions with no upvoted or accepted answers
36
votes
0
answers
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 ...
- 126k
34
votes
2
answers
2k
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 ...
CommunityBot
- 1
18
votes
0
answers
401
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 ...
- 4,274
16
votes
0
answers
347
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 ...
- 1,346
16
votes
0
answers
359
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 ...
- 13.8k
16
votes
0
answers
370
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 ...
- 126k
15
votes
0
answers
325
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 ...
- 2,298
14
votes
0
answers
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
0
answers
929
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 ...
- 4,556
13
votes
0
answers
211
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 ...
- 13.8k
12
votes
0
answers
531
views
The backdoor of Telegram on Diffie-Hellman Key Exchange and possibly 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 ...
- 44.2k
12
votes
0
answers
265
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 ...
- 126k
12
votes
0
answers
466
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.
...
- 11
12
votes
0
answers
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 ...
12
votes
1
answer
611
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 ...
CommunityBot
- 1