# Tagged Questions

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

14 views

### Message expansion in NTRU: why is it $\log_p(q)$-to-$1$?

Suppose that we are working with the original version of NTRU with parameters $(N,p,q,k,d_f,d_g,d_\phi)$. In this case we are working with the original NTRU with the digital envelope and the ...
38 views

### How would low-precision Gaussian sampling impact the security of BLISS?

For digital signature, I implemented BLISS in my cryptographic suite, and wrote the Gaussian sampler based on Lattice Signatures and Bimodal Gaussians. But unlike the reference implementation and ...
29 views

### In NTRU digital envelope, do everyone know the hash function $H$ used?

I have a simple question about the NTRU original cryptosystem using a digital envelope. The article can be found here: http://grouper.ieee.org/groups/1363/lattPK/submissions/ntru.pdf It is said that ...
42 views

### Choosing between RLWE-KEX methods.

Recently, I've been researching and implementing a bit of post-quantum cryptography, and I came across two RLWE-KEX algorithm for key exchange. The first one, which I implement in my software, is ...
65 views

### Distinguish two ciphers in Ring-LWE?

I am fairly new to this topic. so my question is: if I have $A=e_0a+e_1$ and $B=e_2a+e_3$ where $a$ is the agreed public parameter, $e_i \leftarrow \chi$ (drawn from the error distribution). if the ...
40 views

### In NTRU, if $N$ is not prime, prove that one can recover the private key by solving a lattice problem in dimension lower than $2N$

In the NTRU cryptosystem, it is suggested to take $N$ prime. I want to understand why. In Jeffrey Hoffstein, Jill Pipher and H. Silverman An Introduction to Mathematical Cryptography, they suggest (...
68 views

### Keyless Signature Infrastructures as a secure Post-Quantum Scheme

I came across a company that relies on hashing, similar to block chain technology. They explicitly stated in their white paper that hash based cryptographic schemes are inherently post-quantum ...
140 views

### SAT-Based Public Key Cryptosystem

I am researching post quantum cryptography and I've stumbled upon this article which presents a PKC with an np-complete (SAT) trapdoor. I was wondering if someone could help me understand the way the ...
49 views

65 views

### Why the exponent is a power of 2 in Ring-LWE?

I was reading some papers on Ring-LWE. I found almost all of them talk to choose the polynomial modulo $x^n+1$ where $n$ is a power of $2$. I did not understand why this condition is necessary?
414 views

### Is the “New Hope” Lattice Key Exchange vulnerable to a lattice analog of the Bernstein BADA55 Attack?

In the paper, "Post Quantum Key Exhange - A New Hope," the authors present a lattice-based key exchange based on the work of Chris Peikert. In this "New Hope" key exchange the authors try to gain ...
307 views

### Which elliptic curves are quantum resistant? [closed]

If I want to learn about quantum resistant crytography what are the best resources? Which type of elliptic curves should I be studying?
130 views

### Quantum vs. regular computing time to break ECC?

How long exactly would it take for a regular computer to crack an elliptic curve public/private key via bruteforce, vs. a quantum computer using Shor's algorithm with a couple thousand qubits? Can ...
235 views

### How many qubits are required to break RSA 2048 or 4096 with a universal quantum computer?

So in the news this week, IBM have created a universal quantum computer with 5 fully functional qubits. Logic and Moore's law dictates they will be able to scale this up to a lot more qubits within a ...
60 views

### BB84 quantum protocol

In BB84 protocol, when Alice and Bob make key distribution, what is the private thing? They select randomly bases and then make a measurement according to these bases. Used bases are private? I mean ...
70 views

### Understanding the Hidden Subgroup Problem specific to Integer Factorization

I've been reading about the Hidden Subgroup Problem (HSP), specifically trying to understand how it is related to the integer factorization problem. I've read What exactly is the impact of the hidden ...
53 views

### Why are the bit lengths of keys and digests equal in Lamport signatures?

In Lamport's one time signature scheme: One way function to convert a pseudo random number private key to a public key takes $\{0,1\}^n$ and returns $\{0,1\}^n$. Cryptographic hash function to ...
87 views

### Why is 128-bit considered “medium term” security?

Why is 128-bit encryption considered good enough for medium term security only? How is expected to be eventually broken? Quantum computing or brute force attack?
39 views

### Is an instruction similar to PCLMULQDQ valuable in post quantum key exchange?

This paper describes a Quantum Key Exchange based on the Ring Learning With Errors problem. When used with ECC, there is only a slight performance impact. Assuming this is the popularized approach ...
65 views

### Practical lattice based signatures and key exchange with strong security reduction

I am looking for practical lattice-based signatures and key exchange with strong security reductions. Specifically: Provable security under the relevant standard assumptions. Fast in software while ...
49 views

### McEliece variants that support signatures

Besides the Niederreiter cryptosystem, are there any other variants that support digital signatures? Can any of them sign arbitrary signatures unlike the Niederreiter cryptosystem? What are the key ...
38 views

### Best Attack Against HFE cryptosystem

I am looking for the best know attack against HFE cryptosystem. Reading this paper DEGREE OF REGULARITY FOR HFE I found the next claim However, Faugere and Joux demonstrated that we can solve and ...
75 views

### Would LWE problem be still secure if error were like this $e=2e_1$?

In the Learning with error problem, if the error term $e$ from equation $b=<a,s>/q+e$ were of this kind $e=2e_1$, where $e_1$ is chosen according to the probability distribution for the LWE ...
86 views

### Are CSPRNGs quantum-resistant?

It's fairly well known that Shor's algorithm kills RSA, DSA, ECDSA, DH, ... and that symmetric ciphers (AES and 3DES) and hashes (SHA-2, SHA-3) are safe as long as you double your key size / output ...
144 views

### List of post quantum cryptography protocols [closed]

What are the post quantum cryptography protocols that have been proposed until now? I know about McEliece cryptosystem, and LWE scheme. What are the others? Can you provide me a list or a website ...
73 views

### A topic for my master thesis on post quantum cryptography [closed]

I am a master´s student. I am interested to work on post quantum cryptography. None of my professors are offering any topic this year related to post quantum cryptography. However I have the freedom ...
16 views

### Why Sflash signature scheme is constructed in this way?

Sflash is a Multivariate signature scheme that was accepted by NESSIE in 2003, and completely broken in 2007 by a differential attack. Despite I know the total break of Sflash signature scheme and the ...
57 views

### How is McEliece chosen plaintext secure?

Suppose a challenger creates a McEliece encryption system where there is a public key consisting of a matrix $G$ representing some linear code, and a number $t$ for the number of errors. Then the ...
41 views

### Attack being kind of completely puzzled?

I am reading this paper "The security of Hidden Field Equations (HFE)" and at the end of the page 4 the author wrote: Thus, after all, this belief about every attack being kind of ”completely ...
33 views

### The security of Hidden Field Equations - sentence

I am reading this paper "The security of Hidden Field Equations (HFE)" and at the end of the page 3 the author wrote: The random oracle paradigm would be to ignore that the function formulae ...
82 views

### Secure entropy extractor for thermal noise collected from camera input?

I have read this paper (pdf) which talks about measuring the entropy of thermal noise collected from camera input. They estimate the minimum entropy at about 4 bits per pixel. Probably estimating 1 ...
208 views

### Finding the subgroup in isogeny-based cryptography

Isogeny-based cryptography is one of the newest post-quantum cryptography. Hardness of this system is based on finding isogeny between two elliptic curves. Also this is theorem: Elliptic curves ...
52 views

### Winternitz Signature in standard model

I am studying the Winternitz signature and I describe its algorithms in the next W-OTS Key Generation. Select the parameter $w\geq 2$ that is the bit size of the partitions of the message to be ...
245 views

### Secure, patent-free alternative to NTRU

I'm working on a P2P communications and chat framework, and am looking for a quantum-secure asymmetric key exchange algorithm which I can use to perform a key exchange of an AES-256 bit key. This is ...
71 views

### Fast Forward Hash Signatures

As a follow up to the Q/A session: Small Quantum Signatures - Reality check needed I have implemented the discussed idea for a new short-quantum-safe signature system using fast-forwarding hash. It ...
63 views

### Truncating ciphertexts on ring-LWE schemes

On the section 5.4 of the paper Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme, the authors explain how to discard some bits of the ciphertexts to get smaller ciphertexts and ...
170 views

### How to generate a bilinear group of prime order p for key generation

I am trying to implement an IEEE Paper In Cryptography. I read many reference regarding an RSA key generation. But i am confused with above statement. Please someone explain me What it says with ...
16 views

### How to generate a bilinear group of prime order p [duplicate]

I am trying to implement an IEEE Paper In Cryptography. I read many reference regarding an RSA key generation. But i am confused with above statement. Please someone explain me What it says with ...
247 views

### Can Grover's Algorithm be combined with a meet-in-the-middle attack?

We all know and love the meet-in-the-middle attack which basically makes double encryption pointless using a time-memory-tradeoff. Now there was recently the recommendation by the NSA to use double ...
199 views

### How is “post-quantum security” proven/shown?

Due to growing concerns over the threat of quantum computing to asymmetric cryptography (RSA, ECC, etc), a number of "quantum resistant" replacements have been proposed (SPHINCS, McBits, and many more)...
138 views

### Small Quantum Signatures - Reality check needed

I've been thinking a bit lately about how to get quantum resistant signatures fast and (relatively) small. One idea I've been keen on exploring is finding a crypto PRNG that allows fast-forwarding, e....
32 views

### Number of qubits and breaking hashes [duplicate]

Noting D-Wave's press release on a 1000 qubits quantum computer had me wondering... Does the number of qubits nonlinearly change the speed/rate at breaking a SHA256 hash? If someone makes a say 10,...
281 views

### Quantum on hash

Perhaps this has been answered before. Grover's algorithm should result in a 256 bit hash being complexity 128 bits to crack. I was wondering, what if you had a 512 bit hash , and xor'd the lower 256 ...