Hot answers tagged

8

Grover's algorithm treats the function it is evaluating as a black box and finds, with high probability, an input to the black box such that it outputs a specified value in $O(N^{1/2})$ evaluations of the function. Since Grover's algorithm works on the function as a black box, your modification does not hinder Grover's algorithm at all in finding the ...


7

I see two problems with this idea. The first problem is Shor's algorithm; that's a quantum algorithm that is able to find the cycle length of a group (and if you can solve that problem, it is easy to factor and compute discrete logs). In this case, if we define the group of elements defined by the initial start state in the signature, where $H^n$ is the ...


7

I work for Security Innovation, which owns the NTRU patents. All NTRU-related patents are freely usable under GPL 2.0 and 3.0 -- in other words, they should fit in with your license requirement as given above. If you have specific license requirements beyond GPL please let me know and we'll accommodate them if we can. There's an open-source C and Java ...


6

The statement a 15360-bit RSA key is the equivalent to a 256-bit symmetric key does not take into account quantum algorithms. In fact, it is based on a specific computation model. It is just based on the fact that there exist sub-exponential algorithms for factoring and therefore you need longer keys than when using symmetric-key crypto where it is ...


6

Why is 128-bit encryption considered good enough for medium term security only? Because in the long term it is expected that mankind will be able to carry out $2^{128}$ operations because it's not physically as impossible as $2^{256}$ operations. Quantum computing or brute force attack? Assuming quantum computers work at a speed comparable to ...


5

We recently discussed this question with some colleagues and this is what we came up with (no guarantees): Grovers algorithm only outputs a correct answer if it is feed with a input set such that the target function evaluates as 1 for a single input and as 0 otherwise. The algorithm then iterates a subroutine $\sqrt{N}$ times (where $N$ is the size of the ...


5

Actually, most of the primitives that are currently believed to be secure FHE methods would appear to be quantum resistant; a partial list would include Craig Gentry's original scheme based on ideal lattices, BGV (based on ring-LWE), and this NTRU-based approach. All three are based on hard problems that are not susceptible to Shor's algorithm.


5

This is in principle similar as how "normal" cryptosystems are proven. With some algorithms we can reduce them to some "hard problem", but we do not know that those problems are actually hard to solve. Only that we cannot solve them efficiently. For example, the Diffie-Hellman problem is not even known to be NP-hard, never mind the whole issue of P vs. NP. ...


4

That means a plaintext of length 524 will be encrypted to a ciphertext of length 1024 and then will be sent. Isn't is also an inefficiency? Not really; or at least, that's not an inefficiency we care about. A length of 1024 means, in this context, 1024 bits (or 128 bytes). This compares favorably to RSA (for which a key with a 1024 bit ciphertext has ...


4

Yes, a stateless hashbased signature method called Sphincs was recently proposed. It works by having a moderately large Merkle tree (similar to what D.W. suggested), but instead of using Lamport or Winternitz one time signatures at the bottom, it uses a hash based few-time signature method; this allows an occasional collision at the very bottom of the tree. ...


4

You could be able to reduce the space required for a meet-in-the-middle attack, if you follow a similar idea as the application of Grover's algorithm on collisions. Suppose you have two layers of $n$-bit encryption: Partition the inner keyspace into $2^{n/4}$ parts of size $2^{3n/4}$. For each partition generate the inner encryption table. Run Grover's on ...


4

The Supersingular Elliptic Curve Isogeny Key Exchange that you refer to was first published in 2011 by DeFeo, Jao, and Plut. It builds on but is quite distinct from earlier work by Rostovetsev and Stolbunov in 2006. As a Post Quantum/Quantum Safe replacement for Elliptic Curve Diffie-Hellman (ECDH) it has several good properties: The number of bits that ...


4

The expression $c' = \lfloor w^{-i} c \rfloor$ is a slight abuse of notation. What it technically means is to interpret each coefficient of $c$ as real number, divide by $w^i$, round the result to the nearest integer, and then interpret it as an element of $\mathbb{Z}_q$ again. This is equivalent to expressing each $\mathbb{Z}_q$ coefficient of the ...


4

In order to answer this question, we need to understand the basis behind all of modern cryptography, which is computational hardness. Today, we believe that we know how to construct block ciphers that are secure, except for brute force search (or almost that secure). However, we don't really know this. We also think that factoring is hard, and so on. All of ...


4

If he gets the signature for the message 00000..00000, then the checksum will be $t_1 2^w$. For any other message, the checksum will be smaller, and hence the there will be at least one digit $i$ within the checksum for which the $c_i$ digit with value $v$ for the signed message will be larger than the corresponding digit for the new message. The attacker ...


4

The best generic attack against a PRG (i.e. an attack that does not use any internal structure of a construction and hence works for any PRG) is exhaustive search for a seed. I think this was not done yet but it is very likely that the optimality of Grover's algorithm carries over to this setting. This would mean that for $n$ bit seeds, the best attack ...


3

Essentially any IND-CPA-secure lattice-based cryptosystem offers additive homomorphism, up to a predetermined number of operations. I don't know of any IND-CCA1-secure post-quantum candidate that offers any homomorphic property, except Loftus-May-Smart-Vercauteren SAC'11, which is based on a nonstandard "knowledge of error" lattice assumption.


3

In this notation, $f^k(x)$ means "apply $f$ $k$ times in succession". For example, $f^3(x)$ is defined to be $f(f(f(x)))$. Because of this definition $f^a(f^b(x)) = f^{a+b}(x)$ holds trivially (even though we known nothing else about $f$), as the the left side means "do $f$ $b$ times, and then do it $a$ times", while the right means "do $f$ $a+b$ times". ...


3

Douglas Stebila published: We demonstrate the practicality of post-quantum key exchange by constructing ciphersuites for the Transport Layer Security (TLS) protocol that provide key exchange based on the ring learning with errors (R-LWE) problem There is also a patch implementing it for OpenSSL 1.0.1f.


3

This [Carter-Wegman] MAC is not, in general, secure in the quantum setting This is true; however we need to ask "what is this setting, and is it a realistic one?" This setting is one where the adversary can ask queries that are composed of a superposition of quantum states, and the oracle returns the superposition of the answers. In other words, the ...


2

The combination of Grover algorithm and man in the middle attack is the main subject of a paper (arXiv:1410.1434) published last year by Marc Kaplan (Full disclosure: Marc is a friend of mine.) In this paper beyond applying Grover to MITM to reduce the time needed to analyse double-encryption, he also looks at the time-space gain, which is different, and ...


2

There is some software available for the isogeny key exchange. It was developed by one of the designers of the key exchange (DeFeo). It is available on GitHub her: https://github.com/defeo/ss-isogeny-software/ The key exchange was first published in late 2011 and its security has held up under analysis since then. A 2014 paper from Indocrypt supports ...


2

Since the time you asked your question some new algorithms have shown great promise. The first set of algorithms are based on the Learning with Errors Problem in over polynomial rings. See http://www.cc.gatech.edu/~cpeikert/pubs/suite.pdf There is also an elliptic curve scheme based around supersingular elliptic curve isogenies. There's a Wikipedia ...


2

I am a little confused about why it is believed to be secure against quantum attacks, couldn't the hash function be attacked? Yes, the attacker could attack the hash function, for example, by trying to find a second preimage (and there are known Merkle Signature Schemes where we can show that forging a signature can be reduced to the second preimage ...


2

Sorry I will have to answer my own question. I received a mail from Luca De Feo a moment ago. "Nope, I discussed this at length with Jean-François Biasse, and we couldn't find a way to apply this kind of attack to SSIKE." I'll leave this question around for reference for the next person who wonders.


2

It is easy to find preimages for the hash function you designed. Remember, to break the scheme it is enough to find any preimage. It is not necessary to find the one used to compute the image. Now, you got public integers $a,b,c,d,$ and $f,g$ as well as a modulo $M$. An $n$-th image is $$P(n) = a*x(n) + c*y(n) \mod M$$ $$Q(n) = b*x(n) + d*y(n) \mod M$$ ...


2

Random oracles are used in cryptographic proofs as a way to abstract away a complex function, making the analysis easier (ie "ignore the actual function, and model it as a random oracle instead"). In the paragraphs before the sentence you highlighted, they propose to measure the "complexity" of an equation / function by the degree of its multivariate ...


2

Does this attack work? Yes, it works. However, "textbook" McEliece was never claimed to be IND-CPA. In fact, it was already published in 2008 by Nojima et. al. in "Semantic Security for the McEliece Cryptosystem without Random Oracles" (PDF). They also propose a mitigation in the paper, which is to simply front-pad the message with sufficiently many ...


2

Your best bet at the moment are probably the lattice-based key exchange described in the "Post-quantum key exchange – a new hope" paper. You can also find different implementations. C code can be found on Peter Schwabe's homepage. For signatures, if you want to use lattices, you will end-up with BLISS or BLISS-B both of which are implemented by various ...


2

Let $\mathbb{Z}, +$ be the group integers, $\mathbb{Z}/n\mathbb{Z}, \times$ the multiplicative group of integers modulo $n$, and $\varphi(n)$ its order. Then $\varphi(n)\mathbb{Z}, +$, the additive group of multiples of $\varphi(n)$ is a subgroup of $\mathbb{Z}$. The function $f : \mathbb{Z} \rightarrow \mathbb{Z}/n\mathbb{Z} : x \mapsto a^x \mod n$ for ...



Only top voted, non community-wiki answers of a minimum length are eligible