4,288 questions with no upvoted or accepted 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 ...
413 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 ...
398 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 ...
387 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 ...
377 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 ...
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, ...
984 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 ...
215 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 ...
605 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 ...
277 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 ...
481 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. ...
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 ...
498 views

Requirements for security against multi-target attacks, for McEliece and other code-based cryptosystems?

This question is potentially relevant to NIST post-quantum cryptography standards, involving code-based cryptosystems such as McEliece, BIKE and HQC. For these cryptosystems, it seems that an attacker ...
797 views

RSA factorization with special primes

Suppose that primes for RSA modulus are generated using formula: $P_i(x,y) = \operatorname{next\_prime}(x^{z_i}+y^{z_i}) = x^{z_i}+y^{z_i}+d_i$ where $x,y$ are unknown random numbers with size 128 ...