Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

Unanswered Questions

26
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 ...
19
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 ...
17
votes
0answers
333 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
3answers
490 views

Does a partial preimage attack imply a preimage attack?

Let's assume we have an $n$-bit hash function and a $b$-bit partial preimage attack that is faster than brute force. Does this imply a faster than brute force preimage attack on the whole hash? It ...
12
votes
0answers
285 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 ...
11
votes
0answers
166 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 ...
10
votes
0answers
360 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). ...
9
votes
0answers
112 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 ...
8
votes
1answer
140 views

AES cache-timing attacks and nonce-based operation modes

As I understand it, AES cache-timing attacks exploit the execution time variations due to cache hits/misses, especially the ones depending on the SBox look-up tables which are key-related. To mount ...
8
votes
0answers
194 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 ...
8
votes
1answer
329 views

Homomorphic decryption circuit in integer-based scheme

I'm reading this excellent paper by Gentry as a smooth introduction to Fully Homomorphic Encryption. Most things are clear to me except from the way the homomorphic evaluation of the decryption ...
8
votes
0answers
492 views

Are there attacks against broken RSA signature pad checking with $e = 65537$?

Let's say that an RSA implementation of PKCS #1 signatures fails to validate that the 00 01 FF FF FF ... FF 00 portion of the decrypted signature is exactly as long ...
8
votes
0answers
296 views

Why SIVP Is Worst Case Problem?

I just started to study lattice cryptography. I'm now studying worst-case to average-case reduction for SIS. In previous question, "worst means any and average means random". And I wonder why ...
8
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 ...
8
votes
0answers
418 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 ...

15 30 50 per page