Tagged Questions

Cryptography that will remain secure should large-scale quantum computing become feasible. Based on hard problems with no known polynomial-time quantum algorithm (e.g., Shor's algorithm).

learn more… | top users | synonyms

2
votes
1answer
66 views

Are post-quantum cryptographic ciphers *also* secure if the P=NP conjecture holds true?

First of all, I only understand the P versus NP debate on a rather shallow level as I am not a computer scientist. So perhaps the answer to the question is straightforward but if not, I would be ...
0
votes
3answers
205 views

Alternative to NSA encryption algorithm

I am looking for a strong alternative to elliptic curve cryptography. It should be something that could face quantum computing attacks, but nothing created by the NSA. I heard about isogeny key ...
0
votes
2answers
78 views

Does NTRU provide Perfect Forward Secrecy?

Does NTRU provide Perfect Forward Secrecy if the world would use it in an HTTPS connection?
-2
votes
1answer
105 views

Why are we advising PKI if we know that quantum computers will break them? [closed]

DNSSEC, ECDHE, RSA, even SSH and all other important specifications, protocols that we rely on and advise people to use them, they use Public key infrastructure. Question: Why do we still use, ...
0
votes
1answer
34 views

FSB Hash Functions and Convetional hash Functions

I'm reading FSB cryptographic hash function and the authors say that security of this function depends on NP-Complete Problem: "Decoding Linear Code Unlike most other cryptographic hash functions in ...
3
votes
3answers
151 views

Asymmetric algorithm for one time signing of small cleartext

I want to generate a key pair such that the private key can be used once to sign a small message (1024 bytes) at some indeterminate point in the future and the public key can be used to verify that ...
7
votes
1answer
147 views

How dead is braid based cryptography

Braid groups has drawn the attention of cryptographers for a few years, as a promising platform for post-quantum cryptographic protocols. The security of the proposed schemes mostly relied on ...
3
votes
1answer
107 views

Is SRP post-quantum secure?

Is SRP-6a post-quantum secure? If it is not post-quantum secure, do any post-quantum secure alternatives similar to SRP-6a exist?
2
votes
1answer
104 views

Generalized Merkle Signatures, SHA-3 and Sakura

Sakura specifies a tree hash mode for e.g. Keccak (SHA-3). Are there any reasons to use the Sakura tree hash mode in a Generalized Merkle Signature Scheme? It seems to me Sakura primarily solves a ...
4
votes
1answer
96 views

McEliece and cryptanalysis

What is the computational time to break McEliece on a quantum computer? I've seen that polynomial time algorithms exist, but for special conditions. What about the general case?
4
votes
1answer
104 views

Deterministic Rand function for Winternitz One Time Signatures

Suppose you are implementing a Generalized Merkle Signature Scheme, using the Winternitz One-Time Signature Scheme for the node signatures. Furthermore, suppose the implementation is to be stateless ...
3
votes
1answer
114 views

What is the quantum-resistant signature scheme with the smallest signature + pubkey?

After playing cat and mouse with an number of quantum-resistant signature schemes and coming up with nothing with small enough signatures, I'm turning to Crypto.SE. I need a quantum-resistant ...
3
votes
2answers
113 views

Basic attacks on McEliece; finding S and P

Take a McEliece cryptosystem with public generator matrix $G' = S G P$ where $G$ is a generator of a secret code with known fast decoding (not necessarily a Goppa code over $\mathbb{F}_2$), $S$ is ...
2
votes
0answers
42 views

space complexity of quantum collision search

Is there a known way to reduce the space complexity of quantum collision search beyond what is offered by the built-in time-space tradeoff, while keeping the time complexity significantly below what ...
3
votes
0answers
89 views

FHE over the integers - Is that paper's scheme known to be insecure against quantum adversaries?

I was reading the paper Fully Homomorphic Encryption over the Integers, and started wondering if there is a known quantum attack on their main scheme, because There is an efficient quantum attack ...
3
votes
2answers
188 views

Stateless hash based public key cryptography?

Merkle-Winternitz signatures based on fractal hash trees are an attractive alternative to other post-quantum cryptographic schemes, in particular since they are conceptually simple, the security ...
4
votes
1answer
209 views

For a one-time pad, which MAC method is information-theoretically secure?

In the the main post about MAC methods it mentions a few methods: Authenticate And Encrypt: The sender computes a MAC of the plaintext, encrypts the plaintext, and then appends the MAC to the ...
2
votes
0answers
41 views

McEliece information set decoding attack vulnerability

Wikipedia states that McEliece is open to "information set decoding attack". What is an "information set decoding attack" and how serious is the vulnerability? (is it just a matter of choosing proper ...
1
vote
2answers
82 views

McEliece key size

There's a lot of references about McEliece key size being the barrier for proper usage of the algorithm, exactly (or roughly) how large are the keys?
4
votes
1answer
195 views

Long-term data protection, storage of old encrypted traffic and quantum cryptocalipse

Tony Arcieri makes an interesting point in his Imperfect Forward Secrecy article which basically boils down to: large entities such as NSA are storing encrypted internet traffic, also what's to stop ...
1
vote
2answers
247 views

How can I simulate and measure brute force hacking using RSA?

I want to implement brute force hacking using RSA. How can I simulate and measure time duration? What software (or software-based simulator) would be needed?
8
votes
1answer
133 views

Is the Couvreur et al. polynomial time attack on McEliece practical?

There's a new e-print out on arXiv titled "A Polynomial Time Attack against Algebraic Geometry Code Based Public Key Cryptosystems" by Alain Couvreur, Irene Márquez-Corbella and Ruud Pellikaan: ...
0
votes
0answers
78 views

Question Error Correcting Codes

Let $C$ be a code over the finite field $GF(2)$ with generator matrix $G$ and parity matrix $H$. Let $e+C=C'$ be a coset of code $C$. Let $S$ be a non-singular matrix and $H'=H\times S$. Finally, let ...
3
votes
3answers
167 views

Can one use a Cryptographic Accumulator to efficiently store Lamport public keys without the need of a Merkle Tree?

One of the problems of one-time Lamport signatures is that public keys are disposed after use, so you must generate many keys and store them in a Merkle tree. The root is the "real" public key and ...
1
vote
0answers
67 views

Can you provide an example in relation to Hidden Field Equations Multivariate?

I'm reading about Hidden Field Equations Multivariate scheme. My lecture states that the central map is a univariate polynomial $$P(X)=\sum_{i=0}^{r-1}\sum_{j=0}^{r-1}p_{ij}x^{q^i+q^j} \in K[X]$$ ...
8
votes
1answer
292 views

Did NIST verify “post-quantum” claims in the SHA3 proposal papers?

I have been reading Bernstein’s “Quantum attacks against Blue Midnight Wish, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Shabal, SHAvite-3, SIMD, and Skein” paper from 2010… This document disproves ...
0
votes
2answers
116 views

Why use two affine transformations in Multivariate Cryptography?

I'm reading Multivariate Cryptography and would like to know why we use two affine transformations to scramble the central map? Why not use only one?
3
votes
1answer
117 views

Why is Lamport-Diffie secure?

Why is Lamport-Diffie secure? I note that there is a demonstration based on onewayness (in the book postquantum cryptography). But a one way function is not sufficient to ensure that it can not infer ...
1
vote
1answer
167 views

What is a Trapdoor in Merkle Signature?

Merkle signature (pag. 40) use than public key (verification key) the root of the Merkle Tree and than private key (to sign) the set of pre-images of the $g(Y_i)$ where $Y_i$ is the verification key ...
3
votes
2answers
136 views

Merkle Tree High Tree

I'm reading Merkle tree signatures and I like know if the security of the that scheme depends, also, of the high of the tree or only depends that hash function is resistant to collision?
3
votes
1answer
215 views

Public-key cryptosystems without poly-time quantum attacks

It's well-known that Shor's algorithm can solve integer factorization, discrete logarithm and discrete log over elliptic curves in cubic time. This implies that cryptosystems like RSA, ElGamal, and ...
6
votes
1answer
2k views

How long does it take a quantum computer to brute force AES?

I understand that using Grover's algorithm it only requires $2^{64}$ lookups for a 128 bit AES encryption, leading people to say we need to increase to 256 bit keys. But how long would it actually ...
1
vote
1answer
107 views

Is there any restriction in using lossless compression algorithms for huge key sizes?

I'm studying McEliece and Multivariate Public Key cryptographic systems. The main problem here is the huge key size. Is there any restriction in using lossless compression algorithms to fix this ...
4
votes
2answers
94 views

post-quantum threshold secret sharing

I am looking for a references for post-quantum threshold secret sharing schemes. I am especially interested in knowing whether any one based on one-way compressor functions or cryptographic hashes ...
1
vote
5answers
975 views

Using one-way hash functions as the encryption method

Suppose two parties want to communicate securely with each other (Bob and Alice) using a simple messaging system in English. There are approximately 180,000 currently used words in the English ...
1
vote
0answers
71 views

LogSpace Merkle Traversal

I am studying LogSpace Merkle Tree Traversal algorithm in "Post Quantum Cryptography". I don't understand the Table 1 on page 58. My question is: Why within of the $2^h$ rounds for $NEED_h$ exist ...
4
votes
2answers
278 views

Is there any research about cryptography on nondeterministic Turing machines?

I know it's a highly theoretical topic, but I was wondering if there was any research out there about what cryptography would be like assuming that we had access to nondeterministic Turing machines. ...
4
votes
2answers
194 views

Fractal Merkle Traversal

I am studying Fractal Merkle Tree Traversal algorithm in this book. In the [pag. 54] I don't understand this paragraph: We may determine the number of pebbles returned at these times by ...
15
votes
1answer
500 views

What exactly is the base for the KECCAK (SHA3) claim that a security strength of 256 bits is “post-quantum sufficient”?

On page 14 of "Keccak and the SHA-3 Standardization" (February 6, 2013) it says: Instantiation of a sponge function the permutation KECCAK-f 7 permutations: b → ...
7
votes
1answer
2k views

Assuming a 1024qb quantum computer, how long to brute force 1024bit RSA, 256bit AES and 512bit SHA512

Assuming in the future there was a functioning 1024 qubit quantum supercomputer and it could run Shor's algorithm or Grover's algorithm to crack encryption very quickly. I'm interested in how the ...
1
vote
0answers
98 views

Merkle path authentication

In point 4 of the Algorithm 4.2 (Classic Merkle Tree Traversal) of *"Post_Quantum_Cryptography.pdf"* shows *"Stack_h.update(2)"* each stack receives two updates. I am trying understand to understand ...
1
vote
1answer
152 views

Merkle Signature Generation

In the section 2 (page 42) of the book "Post Quantum Cryptography", it says: Then he generates the one-time signature $\sigma_{\text{OTS}}$ of the digest using the $s$-th one-time signature key ...
1
vote
1answer
100 views

Merkle signature + PRNG?

In the section 3 (page 44) of the book "Post Quantum Cryptography", it says: Then each one-time signature key must be generated twice, once for the MSS public key generation and once during the ...
2
votes
1answer
348 views

Winternitz One-Time Signature

I am reading the page 38 in this "Post Quantum Cryptography" book (Equations 8 and 9). My question is, why to compute the verification key $Y$, $f$ is applied $2^w-1$ times? Are there any security ...
3
votes
1answer
224 views

Quantum resistance of Lamport signatures

The Lamport-Diffie signature scheme is said to be quantum-resistant. Why is that? What would a quantum attempt to attack this signature scheme look like, and how does it fail?
-2
votes
1answer
869 views

University for Crypto grad study [closed]

(I thought twice before asking this question and quite reluctant to type as well, but I think this would be helpful). I am an undergrad student and choose theoretical computer science as my major. ...
0
votes
1answer
85 views

Sematically Secure McEliece

I am read the Lemma 2 (pp13) in the paper "Kazukuni Kobara and Hideki Imai: Semantically Secure McEliece Public-Key Cryptosystems –Conversions for McEliece PKC– (PKC 2001)". Related to the question ...
2
votes
0answers
79 views

PKC McEliece + $S$ + $P$ [closed]

I am trying implement the McEliece crytosystem in SAGE. My question is How I will be able to choose the appropriate matrix $S$ and $P$?. I ask this because when I trying obtain the vector $\hat{m}=mS$ ...
5
votes
1answer
133 views

Using encryption schemes for identification

I've been researching how to implement a post-quantum SSL-like connection authentication, especially correct identification&authentization of the server/client. Because good post-quantum digital ...