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

Sampling polinomials in NTRUEncrypt

Some time ago I read an explanation of the key generation process of NTRUEncrypt, where it was stated that a polynomial $f$ should have "small" coefficients. It defined the number $df$, ...
0
votes
0answers
11 views

Sources about NTRUEncrypt implementations

I'm looking for any source that explains the final implementation of NTRUEncrypt for the NIST's third round as simple as possible. I have been trying to understand it directly from the submitted code ...
1
vote
1answer
88 views

Identification Schemes and Internet of Things

I was reading an article titled "A Novel Method for Polar Form of Any Degree of Multivariate Polynomials with Applications in IoT" (doi:10.3390/s19040903) I read the following statement: &...
4
votes
0answers
58 views

Challenging $O(2^{n/2})$ for hash collisions using quantum computers

In "Finding Hash Collisions with Quantum Computers by Using Differential Trails with Smaller Probability than Birthday Bound" the authors Akinori Hosoyamada and Yu Sasaki state that it may ...
1
vote
5answers
248 views

Is it theoretically possible to create an unbreakable cipher?

I know this question might sound strange, but is it theoretically possible to create an unbreakable cipher if we don't consider bruteforce? Some of us believe that it is possible to create ciphers and ...
0
votes
2answers
137 views

I need a pathway for studying Lattice-Based Cryptography

I realize that I need a study pathway for post quantum cryptography. I started to study post quantum crypto by reading NIST PQC $3^{rd}$ round submissions of the lattice based schemes (saying lets ...
0
votes
1answer
88 views

Submission to NIST

I have a paper on post quantum cryptography about Key-establishment Algorithms, that I wish to submit it to the National Institute of Standards and Technology (NIST) I found on their website that the ...
2
votes
1answer
32 views

Differences between Extractors and Privacy Amplification for Quantum Random Generators

We know that for the last step of QRNG: we need to separate quantum and classical noises from each other so we use extractors, after extractor we need privacy amplification step. At this point: if ...
5
votes
1answer
148 views

What are the public key and output sizes for the four remaining PQC KEM candidates?

Currently there are only 4 direct candidates left that provide KEM. Generally performance seems to be "OK" for those candidates. However, the key and encapsulated key sizes (i.e. the output ...
0
votes
1answer
38 views

How to deal with concrete security against lots of queries?

In general, $O(1/\epsilon^2)$ queries are required to distinguish between two distributions that are statistically close at most $\epsilon$. This informal state deals with the required number of ...
1
vote
1answer
57 views

Post-quantum asymmetric encryption algorithms

One could use Falcon-512 for establishing a private and public key for an asymmetric context. Whereas in a symmetric context, we could use firesaber/saber/variants in order to obtain a shared secret ...
1
vote
0answers
49 views

Solving RLWE modulo a prime ideal

Suppose you have the following set up for RLWE: $K$ is a cyclotomic field of degree $n$ over $\mathbb{Q}$, and $p\in\mathbb{Z}$ is a prime integer that splits as follows in $R = \mathcal{O}_K$: $p\...
0
votes
0answers
14 views

Is there decisional version of module-SIS problem?

We have a challenger who computes and gives the adversary the following: random matrix A sampled from the ring $R^{k \times l}_q$ random vector b from the ring $R^{l}_q$ random vector x from the ring ...
0
votes
1answer
43 views

why Niederreiter cryptosystem is not a candidate in NIST PQC competition?

Seemingly, Niederreiter cryptosystem is faster than McEliece, and it can also be used to implement digital signature. Why isn't this scheme appear in NIST post quantum competition?
6
votes
2answers
282 views

Is this variant of Diffie-Hellman viable and quantum resilient?

In this paper the author suggests using a variant of Diffie-Hellman which involves floating-point numbers of arbitrary size in the generation of a shared secret. There are no primes, calculations are ...
1
vote
1answer
96 views

Why all multivariate schemes restrict themselves to polynomials of degree 2

If we note all multivariate schemes restrict themselves to polynomials of degree 2. I was wondering why they do it. After looking on the internet, I came to know that they do it for the efficiency. My ...
1
vote
1answer
82 views

Are MAC algorithms and digital signatures secure from quantum computers? If not, why?

I understand that asymmetric encryption is fundamentally deemed useless under Shor's Algorithm, and understand that symmetric encryption is somewhat quantum-resistant as long as the key-length is ...
1
vote
1answer
79 views

Can we use a Merkle Tree structure to reduce digest size?

A 2nd preimage attack is possible on the standard Merkle tree as pictured below. I'm aware that we can add identifiers (to differentiate nodes) to the input of each hash as discussed in the link. If ...
1
vote
0answers
29 views

HQC Duplicated Reed-Muller Codes

I'm having trouble with a definition in the HQC Specification. From page 25f., in section 2.5.5.: What does it mean to duplicate a code? Is it repeating each bit, similar to a repetition code? ...
0
votes
1answer
53 views

How long it takes for new cryptographic results to become generally accepted?

Suppose there is a new scheme, for the sake of argument let's call it a CEPQSS - CryptoEnthusiast's Post-Quantum Signature Scheme. Now most practitioners aren't convinced that using this is a good ...
1
vote
2answers
52 views

Can we place the WOTS scheme into a Merkle tree structure?

In post-quantum signature schemes that are (to put it simply) built out of merkle trees, they usually employ some sort of OTS scheme on the very bottom leaves. I.e WOTS Winternitz scheme. A ...
0
votes
1answer
44 views

CKKS security estimation for Palisade

My question is rather practical and specific. I am trying to setup an efficient CKKS scheme in Palisade. To this end, the automatic choice for secure parameters has to be turned off and I rely on the ...
2
votes
0answers
40 views

Rounding function used in Saber Key Exchange

In Saber: Module-LWR based key exchange, the authors use a rounding function called $\textit{bits}$, defined (in page 3) as follows: $bits(x, i, j)$, with $j \leq i$, gives $j$ consecutive bits of a ...
0
votes
1answer
59 views

Is it secure to repeatedly rehash a digest to extend the digest length?

Upon reading through the source code of Rainbow, a post-quantum signature algorithm, I found a hashing function that, using SHA-512, produced a variable length digest. This was achieved was by ...
3
votes
1answer
107 views

Famous ideal lattices

I am wondering if there exist some special rings $R$ that gives us, under the canonical embedding, some special lattices, like the root lattices, Barnes-Wall lattices, Leech lattices, ... In more ...
1
vote
1answer
31 views

Guessing the Secret in RLWE Search-to-Decision

In On Ideal Lattices and Learning with Errors over Rings, the authors prove a search-to-decision reduction by guessing the RLWE secret $s$, and using the guess to transform a sample from $\mathfrak{q}...
0
votes
1answer
47 views

Voronoi regions of lattices with dimensions $\leq 16$

Is there any idea about calculating the exact Voronoi regions of lattices with dimensions $\leq 16$? Thank you!
0
votes
0answers
42 views

Is there anyone intrested in quantum fully homomorphic encryption?

Recently, I have read a paper named "Classical Homomorphic Encryption for Quantum Circuits". The author claims a quantum scheme that can apply an encrypted (like GSW encryption) bit to ...
3
votes
2answers
443 views

Distribution of the Difference of Uniformly Random Elements

In the search to decision reduction of 'On Ideal Lattices and Learning with Errors over Rings', the authors implicitly use the fact that the difference of distinct, uniformly random elements of a (...
0
votes
1answer
83 views

BIKE: Bit Flipping Key Encapsulation - Inverse encryption / decryption

I'm trying to understand white paper about BIKE Asymmetric crypt. And actually read about the inverse matrix that needs to be produced for decryption. My concern is: Can I actually encrypt data with ...
2
votes
1answer
151 views

Complexity of Gaussian Elimination over a Finite Field

I read somewhere that the complexity of solving a Linear $n\times n$ system over a Finite Field $\Bbb F_q$ using Gaussian Elimination is $\mathcal{O}(n^3)$ operations in $\Bbb F_q$. What's the role of ...
2
votes
1answer
54 views

Dual of a complex lattice

We know that for a real full-ranked lattice $\Lambda$, with real square matrix $\mathbf{B}$, the dual lattice $\Lambda^{\vee}$ has matrix $(\mathbf{B}^{-1})^T$. Now If we have a complex lattice with $...
8
votes
2answers
217 views

Error Correcting Code VS Lattice

I'm not an expert in PQ-Crypto. As I understood Error Correcting Code and Lattice based crypto. The cryptographic assumptions are very similar. And the key-difference for me is the nature of the noise....
3
votes
2answers
111 views

Ring-LWE in other fields

Can someone please tell me why in R-LWE we always make use of Cyclotomic fields, and specially those with degree equals to a power of $2$? Can we use another fields without losing in hardness of the ...
2
votes
0answers
62 views

Avoid storing the whole message when signing with SPHINCS+

Unlike pretty much every other signature scheme that I am aware of (excluding Picnic, the original SPHINCS, and SPHINCS-gravity) SPHINCS+ requires that the whole message be available during the ...
3
votes
0answers
51 views

It is possible to prove this in zero knowledge?

Let $\mathcal{R}_q = \mathbb{Z}_q/\langle x^n + 1 \rangle$, with $n$ a power of $2$. Suppose that we sample $\mathbf{r} \leftarrow \mathcal{R}_q^m$ uniformly at random with the property that $0 < ||...
1
vote
0answers
68 views

Quantum computers and elliptic curves

I know, that quantum computers can theoretically break the discrete logarithm problem using the shor algorithm. The problem with quantum computers is not the time, but the space ( the needed qubits ). ...
0
votes
1answer
47 views

How SPHINCS+ Hash Signature ADRS structure define

can anyone help me to elaborate the structure of ADRS with example ( tree ADRS, layer ADRS, keypair ADRS etc)used to generate root SPHINCS+ signature. Also can some one help me to describe tree hash ...
1
vote
1answer
258 views

What basic knowledge is required to understand SIKE?

I'm interested in learning about Supersingular Isogeny based Key Encapsulation mechanism. Currently, I only know all the basic knowledge about how standard Elliptic Curve Cryptography, works, using ...
0
votes
1answer
104 views

Code used for McEliece cryptosystem

In the McEliece cryptosystem, the choose of the code is known to the attacker? And if a structural attack succed, and the attacker find a generator matrix of the code how the attacker found the ...
1
vote
0answers
55 views

Non-post quantum primitives in MPC protocols: for and against?

Is it acceptable from a security point of view for an MPC protocol to use non-post quantum cryptographic primitives? Note that except for secret sharing, which provides information-theoretic security, ...
2
votes
1answer
178 views

Chaining one-time signatures

To introduce the notation for the question, consider a one-time signature algorithm: There are a private signing key $sk$ and a corresponding public key $pk$, generated by $Gen(seed)$. To sign a ...
1
vote
0answers
83 views

Which are the most Promising Post-quantum Public Crypto Primitives in the Face of a Quantum Apocalypse?

I'm fairly new to the fundamentals of post-quantum cryptography. So, please forgive me for such a direct question. Searching Google opened up a whole lot of amazing ideas that are thought to be ...
1
vote
1answer
64 views

Understanding a method of vector multiplication

Recently, I attempted to implement the HQC Post-Quantum KEM in (almost) pure python. In the scheme specification whitepaper, it states the following: Here is a simplified version of the function I ...
1
vote
0answers
62 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 ...
4
votes
0answers
112 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 ...
3
votes
1answer
69 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
257 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
24 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
34 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 ...

1
2 3 4 5
9