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

Questions tagged [post-quantum-cryptography]

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

0
votes
1answer
19 views

CSDIH: Why do we need ideals in the form of $\langle \ell, \pi \pm 1 \rangle$ in order to apply Vélu's formulas when computing the action?

I am trying to understand the action of the CSIDH protocol. Let $E_0:y^2=x^3+ax^2+bx$ be a Montgomery elliptic curve over $\mathbb{F}_p$ for some prime $p$. If we take $\mathcal{O}$ as $End_{\mathbb{...
0
votes
1answer
23 views

Associative Multivariate Permutation

Popular multivariate schemes are constructed by having a several easy-to-invert functions/maps as parivate key, and their composition as the public key. When signing, the hash, or a padded form of ...
3
votes
1answer
46 views

Question about degree of regularity

I have been reading some papers on cryptography based on multivariate systems and I have a question. How does one relate the difficulty of calculating Gröbner basis (GB) of a multivariate system with ...
4
votes
1answer
58 views

Differences between NewHope-CPA-KEM and NewHope-CCA-KEM

According to the web page for NewHope, an R-LWE post-quantum key encapsulation mechanism (KEM) candidate for standardization, it comes in types that are or IND-CPA or IND-CCA secure. I know what CPA ...
0
votes
0answers
78 views

How reassuring is 64-qubit security?

After we've concluded that 64-bit is an insecurity for classical computers, I think many would like to know, how secure in a perspective view, is 64 quantum bits security. As we know, the Grover's ...
1
vote
1answer
124 views

Can AES be broken by factorization (using Quantum Period Finding)?

I am trying to understand the paper "Breaking Symmetric Cryptosystems using Quantum Period Finding", and I reckoned the paper is roughly implying to break secret-key cryptographic system by finding ...
10
votes
1answer
108 views

WOTS+: Why does it XOR before running data through the hash function?

I'm implementing WOTS+ in a new language and I can't seem to wrap my head around the fact that WOTS+ XOR's their input with its mask right before hashing it. I tried to look for any reasoning but so ...
0
votes
2answers
194 views

Are zero-knowledge proofs quantum-resistant?

Are zero-knowledge proofs quantum-resistant?
3
votes
1answer
80 views

Adapting LWE Trapdoors for Ring-LWE

In the paper Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller by Micciancio and Peikert, they present the following theorem about the existence of trapdoor for LWE. Theorem 5.1: There is an ...
2
votes
1answer
55 views

Why are computations (isogeny) in SIDH done in an extended prime field?

While reading the SIDH key exchange protocol, I noticed that all the isogeny computations and curves are defined over the extended prime field $\mathbb{F}_{p^2}$. Does it make the problem ...
2
votes
1answer
131 views

Practical quantum attacks on SHA256 MAC and HMAC

Is SHA256 MAC (or HMAC) vulnerable to any quantum attacks? Game setup: The attacker's goal is to produce a valid MAC to be accepted by other devices in the ecosystem. The ecosystem consists of ...
3
votes
1answer
93 views

Practical quantum attacks on AES - Is AES-128 used in a block mode vulnerable to attack using quantum algorithms

Can Grover's (or similar) algorithm be used to attack AES-128 when used in cipher modes like CTR? It seems like the answer is no... Also I have a similar question for SHA256 when used for a MAC. It ...
2
votes
2answers
190 views

Attacking AES128 with Grover's algorithm

How many plain text / cipher text pairs are required by Grover's algorithm when it is used to try and discover a secret AES key? I am trying to determine if having a device which limits the speed at ...
2
votes
1answer
76 views

Encrypt your ECDSA signature with NTRU to make them quantum secure, does that work?

I have a general question about quantum security. ECDSA is suppose to be broken by quantum computers. Whilst something like NTRU is suppose to be secure. My question is: if we sign with ECDSA and ...
4
votes
0answers
58 views

IND-CCA2 post-quantum key exchange

QUIC requires that servers reuse keys so that session resumption works. That breaks many post-quantum key exchange systems. I am looking for a post-quantum key exchange algorithm with the following ...
2
votes
1answer
62 views

Original NTRU : How to calculate the size of private key?

In the original NTRU paper:NTRU: A Ring-Based Public Key Cryptosystem,1996, the author proposes 3 choices of implementation parameters: moderate, high and highest. Let's take moderate security level ...
3
votes
1answer
103 views

Post-quantum X3DH

I was trying to look into weather or not it would be possible to build a post-quantum version of the signal protocol. The double ratchet algorithm is trivial to modify, replacing the ECDH key ...
0
votes
1answer
45 views

How many messages before Sphincs(+) becomes insecure?

How many messages would it take until the success probability of a forger becomes $1/2$? $1/4$?
2
votes
1answer
82 views

Is post-quantum Oblivious Transfer possible

If I’m not mistaken classical OT is not regarded quanum-safe. However I’ve been reading (not really understanding) some papers [1,2] and some reviews[3] on quantum OT and/or post-quantum OT, it seems ...
-5
votes
1answer
60 views

What happens when quantum-resistant cryptography is implemented using a quantum computer?

What happens when quantum-resistant cryptography is implemented using a quantum computer? Give the whole deal with the qubits, is this even a worthy action?
3
votes
1answer
143 views

How are isogeny graphs made and how are they helpful to crypto?

I don't understand how the shapes of isogeny graphs are determined. While Alice and Bob do walk on it and don't backtrack, are they actually relevant to crypto? Also, I was told that supersingular ...
1
vote
1answer
149 views

What is post Quantum Cryptography?

Post-quantum cryptography is cryptography under the assumption that the attacker has a large quantum computer; post-quantum cryptosystems strive to remain secure even in this scenario. Post-quantum ...
4
votes
2answers
540 views

Can post-quantum algorithms be run on commercial devices?

Noob alert! Can we run quantum safe algorithms on commercial devices (like phones, laptops, etc)? I've seen some messaging apps and vpn providers marketing themselves as quantum-proof. How likely is ...
1
vote
1answer
99 views

Exactly what part of SIDH is proven to be NP-hard?

SIDH is quantum secure, why is it quantum secure? Exactly which part of the algorithm is proven to be NP-hard? Computing the isogeny function?
2
votes
1answer
49 views

How could you find the preimage of an isogeny function?

How do you know if an isogeny is surjective or not, and how do you tell how many points on E maps to E'? Does the answer lie in the degree of the isogeny function?
9
votes
1answer
643 views

Lattice-based cryptography

How viable is lattice-based cryptography in a "practical" setting? It has been said that lattice-based cryptography would be a "post-quantum" cryptography scheme, but is it feasibly implementable?
3
votes
1answer
145 views

What form of ECC can we use to make sure our newly invented ECC based crypto-systems are quantum secure?

It seems a lot of crypto-systems that are based on elliptic curves are susceptible to quantum computing attacks. Hence, what forms of ECC cryptosystems are quantum secure, and how can we prove that? ...
1
vote
1answer
129 views

Reverse Shamir's Secret Sharing Algorithm?

Shamir's Secret Sharing algorithm works by breaking a single secret to multiple parts. While it is trivial to implement the reverse in a $n$-out-of-$n$ scheme, how would one implement an $m$-out-of-$n$...
0
votes
0answers
51 views

Is SPHINCS signature secure?

https://eprint.iacr.org/2018/102.pdf offers possible attack against SPHINCS. How reasonable it is and which post-quantum signatures remains secure?
2
votes
2answers
87 views

Lattice generation from basis?

This might be a very short very obvious answer, because I've yet to come across a question similar to mine in my searches. Given a lattice L, with a good base B1 and a bad base B2, what stops an ...
1
vote
1answer
152 views

Key transport vs key encapsulation?

What exactly is the difference between key transport and key encapsulation? Either they seem to be used interchangeably, either I'm mixing stuff up.
2
votes
1answer
100 views

Will using large keys with Classic cryptographic algorithms beat quantum computers?

This is a purely theoretical question. Everyone is talking about quantum cryptography being the next big thing as quantum computers will be much faster than the computers we have today. So, from my ...
0
votes
1answer
54 views

Using Microsoft SIDH library for messages signing

SIDH library looks good but lacks documentation and samples. The only signature-related code was found at http://github.com/yhyoo93/isogenysignature/blob/master/tests/kex_tests.c appeared not able to ...
2
votes
1answer
124 views

Quantum Cryptography Used in a messaging application

Is it possible to create a messaging application and apply a quantum cryptography technique to encrypt the messages between two parties within the application?
3
votes
2answers
99 views

Is the IEEE 1363.1 standard of NTRU post-quantum secure?

I have a question regarding the IEEE 1363.1 standard for NTRU with padding, which offers CCA security. Does the IEEE standardized implementation offer post-quantum security as well? Also, what are ...
1
vote
1answer
135 views

Degree vs index of regularity

I'm studying the multivariate cryptography and specifically attacks using Groebner basis. On the complexity of such direct attacks, it is well-known that the most important parameter is the degree of ...
2
votes
1answer
107 views

Post-quantum authenticated key exchange with forward secrecy

Are there any post-quantum, forward-secure, hybrid, optionally authenticated key exchange protocols? Specifically, I am looking for one that can be deployed in a hybrid with X25519 + EdDSA.
3
votes
1answer
154 views

Discrete Gaussian Sampling role in Lattice-Based Crypto?

I'm reading up on how post-quantum cryptography works, and stumbled upon the notion of discrete Gaussian sampling. However, I can't understand where it fits in the greater picture - currently it feels ...
2
votes
1answer
81 views

Security of expanded key

Can somebody analyze this scheme and explain how (in?)secure it is? Assume that: The keys were initially securely exchanged All keys are truly random In this scheme: The key size is of length <...
8
votes
3answers
1k views

Largest integer factored by Shor's algorithm?

I'm studying Shor's quantum factoring algorithm. I was wondering what the largest integer is which they were able to factor with a small quantum computer. Does anybody has an idea about this?
0
votes
0answers
47 views

Breaking soft McEliece with soft Stern

I am nearly new in Code-based cryptography and I am trying to understand the soft Stern attack in [GJMS17] which the authors used to break the soft McEliece cryptosystem [BSC16]. The description of ...
8
votes
2answers
447 views

Why is pqRSA in the NIST PQC submissions?

In the NIST post-quantum cryptography workshop, the round one submissions included pqRSA. If memory serves, this is an implementation of RSA using the product of a very large number of 4096-bit primes ...
4
votes
1answer
84 views

SIKE: choice of n

The "Supersingular Isogeny Key Encapsulation" proposal submited to PQC-NIST (PDF) defines the value $n$ to be from set $\{192,256,320\}$ (see point 1.4). Does anybody have an idea to what it ...
0
votes
0answers
24 views

Why do we need 2X input bits in the circuit of Shor's quantum Algorithm? [duplicate]

The text that I am following to understand the factoring algorithm states that we need $m = 2\cdot\log(N)$ input qubits because we need to evaluate the oracle function for at least $N^2$ times. Please ...
3
votes
0answers
49 views

Ambainis quantum collision-finding alg; triple hash output lengths?

I just stumbled onto a series of 2017 papers about applying the Ambainis quantum collision-finding algorithm to hash functions. (disclaimer: I haven't read all of them in full yet): Post-quantum ...
3
votes
3answers
545 views

What telltale signs would indicate that quantum computers are about to become dangerous to classical cryptography?

What would be telltale signs that quantum computers become imminent and sizable danger to classical cryptography in commercial applications ? Make classical cryptography consist of symmetric ...
2
votes
1answer
277 views

Why do we need to use supersingular curve on SIDH?

if i'm not mistaken, the supersingular curve's endomorphism ring is non-abelian. but why does it matters? or is it not even related to its endomorphism ring?
2
votes
1answer
156 views

Why is the number of qubits used in Shor's factoring algorithm so high?

When preparing the initial state of the algorithm to factor $n$ he computes $q = 2^l$ such that $n^2 \leq q < 2n^2$. The first register then contains $l$ qubits. Why does this need to be so high. ...
-1
votes
1answer
69 views

What will happen to existing cyphertext when today's encryption is broken? [closed]

Even optimistically, I think we can all agree that many encryption algorithms that are widely used in production today will be "broken" sometime in the next decades. With "broken", I mean that (...
0
votes
0answers
37 views

Can NTRUPrime public keys be identified from ciphertext?

Is it possible to distinguish which NTRU public key a ciphertext/encrypted message is for? Assume the attacker has no plaintext or access to secret keys. I suppose this would be a form of key ...