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 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

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 ...


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 ...


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

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

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 ...


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

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 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

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 ...


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

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. ...


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

The elliptic curve discrete logarithm—like integer factorization and the classic finite field discrete logarithm—is an instance of the abelian hidden subgroup problem. Any abelian (commutative) instance of the hidden subgroup problem can be efficiently solved in quantum computers with (variants of) the Shor algorithm; therefore all of the above problems ...


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

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

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

Though this question is fairly old, there is still no accepted answer. Hence, let me try to clarify this. The W-OTS scheme that your talking about was proposed by Ralph Merkle in his 1979 paper as an improved version of the Lamport-Diffie OTS to reduce the size of signatures. Instead of a "per-bit-signature", Merkle proposed to sign multiple Bits at once. ...


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$$ ...


1

Also, the algorithm given in the mentioned paper has a complexity os $\tilde{O}(p^{\frac{1}{4}})$. The best known attack (As mentioned by de Feo, Jao and Plut) on the SSIKE is based on the claw finding problem (see below) and has a complexity of $\theta(p^{\frac{1}{6}})$. Very interesting paper btw ;): Claw finding algorithm using quantum walk


1

There should be plenty of them. Off the top of my head, I'm thinking of the provable secure version of NTRU by Stehlé and Steinfeld [1], which is IND-CPA secure. In this scheme, ciphertexts are of the form: \begin{equation} c = pk \cdot s + p\cdot e + \operatorname{encode}(m) \end{equation} where $s$ and $e$ are random polynomials, $p$ is a small prime, ...


1

In order to convert a 3-move id-scheme to a digital signature you have to replace the request (or the challenge) by the value of a secure hash function applied to the message (this method is called Fiat-Shamir method). In Sterns's id-scheme you have to choose a random element from the set $\{0,1,2\}$ for your message. That is $H(m)\in \{0,1,2\}.$ For ...


1

Found the answer: The $l$-torsion subgroup is isomorphic to a direct sum of two quotient groups: $E[l] \simeq \mathbb{Z}_n \oplus \mathbb{Z}_n$, hence the basis requires two points and the elements of $E[l]$ are represented by linear combinations of such a basis. [Reference: Elliptic Curves, Washington, section 3.1]



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