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
3
votes
0answers
47 views

Lattice Based Cryptography domain

Some cryptosystems operate on the domain of the form $\mathbb{Z}_q[x]/\langle x^n-1\rangle$ and others operate on $\mathbb{Z}_q[x]/\langle x^n+1\rangle$. What's the security impact of the two forms?
4
votes
1answer
53 views

Why is the vector sampled from Gaussian or Subgaussian distribution in lattice-based cryptography?

I have known that the vector is sampled from Gaussian distribution in lattice-based cryptography because the distribution of the vector $\mod{\mathcal{P}(\mathbf{B})}$ approximates to uniform ...
1
vote
0answers
46 views

Canonical embedding vs. plaintext slots in Ring-LWE

I'm working on the canonical embedding mentioned in [LPR10] and [LPR13]. What confuses me is that the difference and the relationship between the canonical embedding and the concept of ''plaintext ...
1
vote
0answers
27 views

Precise Definition of 1-out-of-2 Oblivious Transfer

What's the precise definition for 1-out-of-2 OT? and what's the best way to show that it can't be achieved under unconditionally secure setting? I am reading about it and just couldn't get my head ...
0
votes
1answer
42 views

Public points in SIDH

I was going through a presentation titled "SIKE in Hardware" by professor Reza Azarderakhsh. On the page $10$ of the presentation he introduces a variable $w$. Could you please explain what the ...
2
votes
1answer
51 views

How secure is a hash based signature scheme after signing assuming quantum computers?

Consider a hash based signature scheme that requires taking the $k$-bit hash of an arbitrary length message to be signed (e.g. Lamport one-time signature scheme). My understanding is, assuming that ...
3
votes
0answers
70 views

Check validity of generated parameters for SIDH

In section 4.1 of the paper Towards Quantum-Resistant Cryptosystems From Supersingular Elliptic Curve Isogenies by Feo, Jao and Plût it is described how you generate valid parameters for the SIDH ...
2
votes
1answer
53 views

Post-quantum alternative to ElGamal? (public key verifiability)

Are there any alternatives to ElGamal that would be resistant/annoying to quantum machines? I would like to preserve public key derivability/verifiability -- ability to ensure existence of ...
2
votes
1answer
48 views

What's the difference beteween SIDH and SIKE?

I'm a semi newbie in crypto (I've had that uni course of discrete math that includes basic cryptography principles) and wanted to go a bit further in isogeny graphs. I have downloaded the C ...
2
votes
1answer
37 views

Calculation of failure probability in basic Ring-LWE-DH key agreement

This is the basic unauthenticated Ring-LWE-based Diffie-Hellman key exchange, based on Peikert's Ring-LWE KEM: (from BCNS15) Alice and Bob have shared public polynomial $a$ randomly drawn from $R_q = ...
4
votes
1answer
81 views

Is McEliece secure with non-binary Goppa codes?

A binary Goppa code with codewords of length $n$ bits that can fix $t$ errors with a polynomial over $GF(2^m)$ can encode $k = n - mt$ bits long data. That is one needs to add $mt$ check bits to fix $...
4
votes
1answer
151 views

Complete Attack on RLWE Key Exchange with reused keys, without signal leakage

I am studying a research paper "Complete Attack on RLWE Key Exchange with reused keys, without signal leakage" . On page number 21 to 28, there is toy example explaining the scheme. I am unable to ...
2
votes
1answer
76 views

SIDH: key agreement - why does it work?

In SIDH both parties agree on the key in following way: Alice calculates a kernel $R = mPB + nQB$ Thanks to Velu formulas (and further improvements), she can now compute isogeny $\phi_a$ She uses $\...
0
votes
2answers
74 views

SIDH cryptosystem question

I'm trying to understand the SIDH cryptosystem and got confused at this point: Alice fixes base $\{P_A,Q_A\}$ so that it generates $E_0[l_A^{e_A}]$. Then she chooses secret parameters $m_A,n_A$ and ...
2
votes
0answers
46 views

Gentry-Halevi’s Fully-Homomorphic Encryption and hermite factor

In section 7.2, page 18 in Chen-Nguyen paper regarding BKZ 2.0, they point out different Hermite factors related to Gentry-Halevi FHE. More precisely, it is said that the critical Hermite factor for ...
1
vote
0answers
85 views

RSA vs. Super Computer vs. Quantum Computer

I know that RSA is known to be secure in the current landscape of computing, and I know that RSA is known to be broken in the world of quantum computing and cryptography. I have two questions, can ...
2
votes
0answers
44 views

IETF Recommendations for preparation for PQC- clarify in what way they are referring to bits

Which bits are being referred to when it is said by the IETF, "Continue to avoid baking-in algorithms, either explicitly or implicitly (e.g. via maximum field sizes)" ? Does that mean leave enough ...
1
vote
1answer
111 views

How resistant are stream ciphers like Salsa20 or ChaCha in a post-quantum world?

What kind of quantum computer would be required, if it is possible to break such ciphers?
1
vote
1answer
68 views

NTRUSign (considered broken) as a one or few time PQ signature scheme

As many know, original NTRUSign is considered broken as signatures leak information about the private key. It takes a number of signatures to accomplish a break though, with the original break paper ...
2
votes
1answer
71 views

How does the Signature Scheme in Picnic Works

I am trying to understand how signature scheme proposed to NIST, Picnic, works. The propossal uses ZKboo and ZKboo++ as their basis. I can see how the ZKPoK works, where the witness x is some key ...
3
votes
1answer
100 views

Does the block size of a symmetric cipher impact the security of the cipher itself? [duplicate]

Will a 128 bit block have some security implication in post-quantum cryptography?
2
votes
1answer
60 views

Can I connect the hardness of a linear short integer solution problem to that of SIS problem?

As we know, SIS problem is defined as: for a function $f_A(s)$=$As$, where $A$ is a fixed, randomly-chosen matrix in $\mathbb{Z}_q^{r \times n}$, it is hard to find elements $s \in \mathbb{Z}_q^{n}$ ...
3
votes
0answers
133 views

How does post quantum key exchange in OpenSSH 8 work?

OpenSSH 8 supports a post quantum KEX, namely sntrup4591761x25519-sha512@tinyssh.org It says in its description that it is basically NTRU + ECC X25519. However, I have tried but cannot understand how ...
0
votes
0answers
23 views

Minimal secure index of quasi-cyclic codes for code-based cryptography

It is well-known that keys (generator matrices) of code-based cryptography are very large for its practical usage. To reduce them scientists propose to use families of quasi-cyclic codes. I remind ...
0
votes
0answers
41 views

Regarding the isogeny path problem

Given two elliptic curves, it is hard to calculate an isogeny of large degree between them. Does this only apply to supersingular isogenies or to ordinary ones as well? Additionally, is the mapping ...
6
votes
1answer
109 views

Why doesn't “Classic McEliece” need scrambling?

The original McEliece scheme uses two random matrices S and P to scramble the generator matrix and uses $\mathsf S·\mathsf G·\mathsf P$ as the public key. The Niederreiter variant also does about the ...
0
votes
0answers
58 views

Dilithium signature scheme - Public key derivation

Good day! I am very new to Cryptography but I want to make sure I understand the concept of the scheme correctly before using it to our system. So I was looking at post quantum signature schemes, and ...
4
votes
0answers
64 views

Why is it safe to generate the secret key and masking vectors using rejection sampling in CRYSTALS-Dilithium?

In CRYSTALS-Dilithium module lattice-based digital signatures, the secret key vectors $s_1, s_2$ with coefficients in $[-\eta, \eta]$ and the signature masking vector $y$ with coefficients in $(-\...
2
votes
0answers
134 views

Quantum Resistant Algorithms and types: PKE vs PKEs vs KEM vs KEMs vs DSS

I am trying to wrap my head around the second round Quantum Resistant Algorithm candidates currently under the NIST PQC Effort. Can someone verify if the following is a correct summary of the 17-...
5
votes
1answer
116 views

Can I replace DH by a post-quantum key exchange in IBAKE for post-quantum identity-based authenticated key exchange?

IETF RFC 6539 IBAKE - Identity Based Authenticated Key Exchange describes a Hybrid key exchange using both Identity based cryptography and a standard ephemeral elliptic curve Diffie-Hellman key ...
7
votes
0answers
94 views

Differences between “NewHope” and “NewHope-simple”

The well-known paper described a key exchange (KE) scheme named "NewHope" on USENIX 2016. The authors then proposed "NewHope-Simple" - a PKE/KEM scheme. They also submitted "NewHope for NIST" - ...
1
vote
1answer
68 views

Cost of upgrading to PQCrypto

We already have recommendations on what PQCrypto to use: PDF (page 11) Symmetric encryption Thoroughly analyzed, 256-bit keys: AES-256 Salsa20 with a 256-bit key Symmetric ...
2
votes
1answer
117 views

NIST security categories (post quantum)

Here (https://www.safecrypto.eu/pqclounge/round-2-candidates/) are collected all the proposals which passed the first round of NIST Post-Quantum Cryptography Standardisation process. What does the ...
2
votes
1answer
71 views

Niederreiter cryptosystem

I can't understand how Niederreiter cryptosystem works. If $c=mH^{'T}$ than why we cannot compute $m$ directly by multiplying $c$ with the $(H^{'T})^{-1}$? Can you give me an example of a "fast ...
1
vote
1answer
114 views

CSIDH: 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
36 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
59 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 ...
6
votes
1answer
151 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 IND-CPA or IND-CCA secure. I know what CPA and ...
0
votes
0answers
90 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
163 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 ...
12
votes
1answer
167 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 ...
1
vote
2answers
427 views

Are zero-knowledge proofs quantum-resistant?

Are zero-knowledge proofs quantum-resistant?
3
votes
1answer
114 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 ...
3
votes
1answer
93 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
270 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
176 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
448 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
93 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 ...
5
votes
0answers
76 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
87 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 ...