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

Filter by
Sorted by
Tagged with
1
vote
0answers
47 views

Post-quantum crypto based on undecidable problems

Usual post-quantum crypto, like the isogeny-based algorithm, has its value lying in that no one yet has found a quick way to break it with quantum computer. This makes me wonder why don't we build ...
1
vote
0answers
37 views

Quantum resistant voting scheme

I am looking for a fully (or partially) implemented quantum resistant e-voting scheme. I know the problems and issues that one deals (from an efficient and secure point of view) whenever he decides to ...
4
votes
0answers
80 views

How are the constants found in the AVX2 implementation of CRYSTALS-KYBER round 2 generated?

The post-quantum lattice-based cryptosystem CRYSTALS-KYBER which has made it to the second round of NIST PQC includes two implementations: 1) a baseline reference implementation in C and 2) an ...
2
votes
0answers
34 views

Quantum-secure obfuscation

My question is a follow-up to a recent question regarding quantum-secure time-lock puzzles (TLPs). TLPs can be built (in principle) from indistinguishability obfuscation (iO) [BGJ+,BGL+] as noted in ...
3
votes
3answers
187 views

Is there a quantum-safe time lock?

Most successive squaring time lock puzzles I've seen appear to be broken by Shor's algorithm. Is there another practical and efficient time lock protocol that is not broken by Shor's algorithm? If not,...
1
vote
0answers
23 views

Ring (or Ideal) version of Boyen's signature

Boyen's signature is a well-known post quantum digital signature scheme. It's a lattice based scheme that uses a trapdoor of the lattice $\Lambda^{\perp}(A)$ and it's security is based in the SIVP ...
1
vote
1answer
30 views

Reduction of decison SIS

In Lyu12, Lemma 3.6 is as follows. Lemma 3.6 For any non-negative integer $\alpha$ such that $gcd(2\alpha+1, q)=1$, there is a polynomial time reduction from the $SIS_{q, n, m, d}$ decsion ...
0
votes
2answers
61 views

What is the implication for differential privacy if $\epsilon = 0$?

In pure differential privacy, the parameter $\epsilon$ represents the desired privacy loss. The smaller the $\epsilon$ is, the more privacy we can obtain. What happens when we want the privacy loss $\...
3
votes
1answer
61 views

Hardware Gaussian random numbers for lattice-based cryptography

I have been recently reading about lattice-based cryptography. I read that a key aspect of such protocols rely on added Gaussian noise on lattices, and which therefore require highly efficient and ...
6
votes
0answers
101 views

Can LWE be NP-hard?

Regev's reduction shows that LWE is quantumly at least as hard as CVP with an approximation factor of $n/\alpha$ for $0<\alpha<1$. But I just watched this talk which said that if $\sqrt{n/\log n}...
1
vote
1answer
32 views

average-case SIS and average-case BDD

In lattice based cryptography, we say the average-case SIS (short integer solution) problem because it is such kind problem " $A \stackrel{\$}{\leftarrow} \mathbb{Z}^{n\times m}_{...
0
votes
0answers
92 views

Is chaos-based cryptography quantum-resistant?

Recently, I have been learning chaos-based cryptography. Is the Chebyshev map-based encryption algorithm quantum-resistant?
0
votes
1answer
54 views

Suppose $H(X) \rightarrow Y$ is collision resistant. Is $H$ also one-way?

If we have $H(X) \rightarrow Y$ and it is collision resistant. Can we say that $H$ is also one-way? And if that is true can you give me an example?
0
votes
0answers
73 views

Is XChacha20 - Poly1305 Quantum resistant?

This is a question just out of curiosity, as I am a newbie to Post Quantum Cryptography. I have read several articles where they emphasize that current standardised symmetric encryption algorithms (...
1
vote
0answers
31 views

Block size of BKZ algorithm and related security of CRYSTALS-Kyber

Security of lattice-based schemes in the NIST Posto-Quantum Project often relies on the complexity of dual attack. Complexity of this attack depends on the running time of lattice basis reduction ...
1
vote
0answers
38 views

Primal and dual attack against NTRU

I am looking at the primal attack against schemes in the second round of the NIST Post-Quantum Standardization Project. The cost of primal attack usually comes from an estimate described in NewHope ...
2
votes
2answers
80 views

If we don't trust current PQ algorithms enough to use them on their own why should we trust them for a hybrid?

The second question my students have asked me about PQ/Classical Hybrids is about why we think they are good for protecting information with a long security lifetime. If we don't trust current PQ ...
1
vote
1answer
59 views

Are PQ/Classical Hybrid Key Exchanges a reflection of how little we trust PQ cryptography primitives?

My students have asked me some questions about why there are standards being developed for hybrid public key systems with both a classical and a post-quantum component. Given that when elliptic ...
1
vote
0answers
68 views

How decode works in CCA1 scheme based on MP12 construction?

In Section 6.3 from MP12 we have that $encode(m) = Sm$, for $S$ any basis of $\Lambda(G^t)$. Then I have: $S = \begin{pmatrix} 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256\...
1
vote
0answers
40 views

Multibit LWE Encryption

What's the simplest way to encrypt multiple bits with LWE public key cryptosystem? Some paper say use a different secret key for each bit of the message. Does that mean the length of the message ...
0
votes
1answer
85 views

Trying to Understand Ring Learning With Error Encryption

I'm trying to understand the following RLWE encryption scheme from this Chris Peikert's paper Say i choose $q = 97$, $n=8$ and the polynomial $a = 96 x^8+30 x^7+76 x^6+12 x^5+57 x^4+77 x^3+70 x^2+49 ...
6
votes
1answer
113 views

Decision to Search LWE when modulus $q=p^e$

I am reading Applebaum et al.. In Lemma 1. (page 7), Applebaum et al. proved the decision to search reduction when the modulus $q=p^e$ for prime $p$. In the proof, they define the hybrid ...
0
votes
0answers
18 views

How does a rectilinear filter used for QKD-BB84 detect both horizontal and vertical polarizations?

When using the BB84 algorithm for QKD, you arbitrarily choose which of two filters (bases) to use when detecting a photon: rectilinear or diagonal. If you choose rectilinear, you can detect ...
0
votes
0answers
35 views

How is QKD (Quantum Key Distribution) advantageous over McEliece/AES?

I don't understand the popularity of the idea of QKD (often coupled with OTP). From what I can tell, a quantum-safe key exchange algorithm like McEliece has just as much security while being able to ...
1
vote
0answers
55 views

Help on Algebraic Side Channel Attacks

I am a master student in computer security, I am preparing a dissertation thesis in the theme is: Algebraic cryptanalys by auxiliary channels, I need reference on this theme (book, thesis, ...), and ...
2
votes
1answer
80 views

Can quantum algorithms solve the approximate GCD hard problem efficiently?

Some cryptographic schemes are based on the hardness of this problem. The answer to this question determines if those schemes are quantum resistant or not. There are a number similar questions but ...
3
votes
1answer
82 views

Randomness of Decision Learning With Error Problem

I read the statement of the Decision Learning with error problem is: distinguish between $(\vec a, \langle \vec a, \vec s \rangle + e)$ from uniformly random samples. Can anyone explain what does ...
0
votes
1answer
48 views

Quantum Secure Signing Algorithm with a 256 bit signature & key. Am I missing anything? Can I remove tradeoff?

So I was looking at Lamport signatures and trying to figure out if there is a way to reduce the key size and signature. I stumbled across something that is tiny (125 times smaller signatures and 500 ...
4
votes
2answers
141 views

what does output parameters of lwe estimator stands for?

I want to use lwe estimator to find classical and quantum security of my proposed key exchange protocol. On this website, I want to understand the output of sage code on lwe estimator given bellow. ...
1
vote
1answer
66 views

What are the security implications of knowing the private polynomial $\mathcal{F}$

First, affine transformations $S,T$ are defined by $S=A_1+v_s, T=A_2+v_t$. Let the private polynomial function $\mathcal{F}$ be known. The short description of the public key map is $P(X) = T \circ \...
4
votes
0answers
61 views

Help with cryptanalysis of branching in schemes based on Multivariate Public Key Cryptography

I'm familiarized with the structure of branching found in Multivariate Cryptography, as it allows us to partition a $n$-tuple over $F_{q}$ into a $k$-tuple where the $i$-th element is in $F_{q^{\...
1
vote
1answer
69 views

Winternitz One Time Signature

I happened to watch Mr. Bill Buchanan lecture that explains Winternitz one time signature scheme (https://www.youtube.com/watch?v=eqMMlcN4zSc). The scheme shown in the lecture is susceptible to ...
4
votes
2answers
258 views

Key Exchange vs Key Encapsulation

From what I understand, the steps of a key exchange protocol are Alice and Bob each encrypt something using their public key and private key and send the result to each other Alice and Bob each do ...
0
votes
1answer
31 views

In the SIKE known answer tests, why is there only one secret key?

I'm looking at the SIKE known answer tests and am realizing that I'm confused on all the different terms in a Diffie-Hellman key exchange. From the Wikipedia page, I would think there would be a ...
0
votes
0answers
38 views

PQC schemes & theory on academic courses

This question doesn't cover any technical aspects of PQC but I would want to know if undergraduate computer scientists study at a good level any of the available PQC schemes in literature during their ...
0
votes
2answers
92 views

Advice for a high schooler intending to read about post-quantum crptography

I'm a high schooler who is interested in learning about post-quantum cryptography. I would like to read some papers of post-quantum public key algorithms, shortlisted by NIST: https://csrc.nist.gov/...
6
votes
1answer
88 views

Is LPN not as important as LWE and SVP?

I've been learning about lattice cryptography and have noticed that most resources such as this survey by Chris Peikart, the Winter School on Lattice Cryptography etc don't include material on LPN, ...
0
votes
0answers
53 views

recommended encryption algorithms to create an encrypted communication application

I have just turned 17 and I have been developing in Java for a few years. Recently I have been interested in a language called rust, I have also been made aware of privacy issues by some of my friends....
3
votes
1answer
108 views

Multivariate cryptography - easily invertible quadratic map

I am reading through multivariate cryptography and in every source I have seen, the secret map $P$ is described as "easily invertible" or "easy to invert". What exactly does it mean "easily ...
2
votes
1answer
193 views

Do any NIST PQC have “homomorphic” public keys, in the sense that any two pubkeys derive a combination pubkey?

Background: The MathMesh crypto platform (refs at the bottom) is a newly-proposed technology stack which has been somewhat cheekily called a "Grand Unified Theory of Security on the Internet". Its "...
1
vote
1answer
85 views

Why does solving the underlying polynomial system “break” the multivariate cryptosystem

I was wondering why exactly does solving a polynomial system (directly or indirectly) "break" a multivariate cryptosystem as a digital signature. I realize that the exact reason differs from system ...
2
votes
1answer
221 views

Transition to post-quantum cryptography

Classical asymmetric cryptography is commonly based on the Discrete Logarithm Problem and Integer Factorization, which are known to be solvable with a quantum computer if it has the ability to run ...
1
vote
0answers
100 views

How to find kernel of isogeny from the dual isogeny

Let $E$ be a supersingular elliptic curve over $\mathbb{F}_{p^2}$, where $p = \ell_A^{e_A} \ell_B^{e_B} f \pm 1$ for some primes $\ell_A, \ell_B$. Let $R \in E[\ell_A^{e_A}]$ be a point of order $\...
1
vote
0answers
52 views

McEliece crytography Example [closed]

Please could someone kindly give an example of McEliece cryptosystem with a detailed explanation, most especially, the decoding aspect
2
votes
2answers
306 views

After Google's breakthrough: When will quantum computers break today's encryption?

Google announced a breakthrough on the way to building usable and useful quantum computers. Since I'm not a cryptographer, I wanted to ask when quantum computers will be able to break the crypto ...
0
votes
1answer
66 views

Post-Quantum Public Key Cryptography with EC math properties

Is there any quantum resistant public key cryptography with similar properties of elliptic curves? Assuming lowercase for scalars and uppercase for points. The properties I'm interested are: Reusing ...
2
votes
0answers
51 views

Post-quantum aggregate / multi signatures

Are there any practical post-quantum aggregate / multi signatures? Currently, the aggregate / multi signature schemes seem to be limited to pre-quantum elliptic curve assumptions only, e.g., [BDN18], [...
2
votes
0answers
44 views

Why round off vector sampling from continuous Gaussian distribution not directly sample from discrete Gaussian distribution

For any vector $\mathbf{c}$, real $s > 0$, and lattice $\Lambda$, define the probability distribution $D_{\Lambda, s,\mathbf{c}}$ over $\Lambda$ by $$D_{\Lambda, s,\mathbf{c}}(\mathbf{x})=\frac{...
0
votes
1answer
131 views

Is CECPQ2 forward secure?

Is the CECPQ2 key exchange, as deployed by Google[1] and Cloudflare[2] in TLS 1.3 forward secure against quantum computers? I know that it is using HRSS+SKY as the post-quantum part of the key ...
2
votes
1answer
132 views

Post-Quantum security of Pseudo-Random Functions

I am wondering what is the exact post-quantum security of a PRF. I know that for most symmetric mechanisms, it is assumed it is sufficient to double the key size, but I am looking for a more precise ...

1
2 3 4 5
8