2,125 questions with no upvoted or accepted answers
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 ...
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 ...
520 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). ...
178 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 ...
218 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 ...
323 views

### Is Pohlig-Hellman Cipher the only option?

I am looking for a cipher which would allow something like this: E(E(M, a), b) = E(M, ab), where a and b are encryption keys, and ab is a combination of the keys that is impractical to separate into a ...
257 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 ...
455 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 ...
162 views

### Proving multiple products “in the exponent”

I'm trying to come up with a small-sized (non-interactive) proof for a Diffie-Hellman-like statement. I'll start by giving an example. The prover has $g^a, g^b, g^c, g^{ac}, g^{ab}, g^{bc}, g^{abc}$. ...
349 views

### Potential Flaws With Lattice Based Cryptography?

From researching post-quantum cryptographic schemes it seems hash-based and lattice-based algorithms are the most promising (MQ-based seem to be covered by patents and have more potential unknowns ...
139 views

### How exactly does ASKE (Alpha Secure Key Establishment) in Zigbee work?

I am working on Zigbee security. For key establishment, some approaches are given in Zigbee. Some of them are: ASKE (Alpha Secure Key Establishment), ASAC (Alpha Secure Access Control), and SKKE (...
551 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 ...
128 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 ...
286 views

### What might be assumed about a PRF if the key has been chosen?

The defining feature of a PRF $f:\{0,1\}^k\times\{0,1\}^s\mapsto\{0,1\}^*$ is that, if the first parameter is selected at random, it should be indistinguishable from a function \$g:\{0,1\}^s\mapsto\{0,...
187 views

### Do trinomials weaken the Alternating Step Generator?

The Alternating Step Generator was proposed by Christoph G. Günther: Alternating step generators controlled by de Bruijn sequences, in proceedings of Eurocrypt 1987. It's perhaps the conceptually ...

15 30 50 per page