Post-Quantum Crypto

What are your favorite primitives? Do they have working implementations yet? I'm a fan of sntrup4591761 for encryption and SPHINCS+ for signatures, but supersingular isogenies look promising too, especially for that sweet sweet perfect forward secrecy using ephemeral keys. The basic idea behind hash-based signatures like sphincs is hilarious. Lamport signatures consist of generating random bitstrings (secret) and hashing them to make the public key. Then to sign a message you just reveal certain secret bitstrings depending on the bits of the digest you are signing. https://libpqcrypto.org/ https://github.com/cloudflare/sidh https://en.wikipedia.org/wiki/NTRU https://en.wikipedia.org/wiki/Supersingular_Isogeny_Key_Exchange https://en.wikipedia.org/wiki/Lamport_signature

>What are your favorite primitives? Do they have working implementations yet? As I'm kinda new to cryptography I can't say. I know the basics and the classical cryptography like RSA, ECC, GPG and TLS but in PQCrypto I just grasped the surface. I started reading the book mentioned in pqcrypto.org, but for know I like the idea behind lattice-based cryptography. So I hope to start soon to understand what you really mean with that question.

I started reading those: I thought they could help here; I hope it's a good reason to bump and find someone else to talk with.

>>7687 If OP doesn't engage a conversation I'll basically transform this thread in a cryptography introduction and discussion thread with books and stuff.

Luckily we're still pretty far away from quantum breakage of traditional crypto. At least according to credible quantum physicists. But maybe people also ought to consult credible security researchers? Hmm. Seems like one of those things that might possibly have a sudden breakthrough and surprise us as well. In five years? Nah. In fifty? Most likely.

>>8283 as pqcrypto.org try to explain, better ready than not.

How's porting our zk-SNARKS and other zero knowledge primitives to post-quantum going? This soykaf is like magic when you first learn about it, would suck for it all to disappear when qunatum becomes a thing.

>>8289 according to this answer [1] >Zero-knowledge proof (ZKP) systems can be post quantum secure, but they need not be. It all depends on the cryptography on which the security of the ZKP rests. To simplify, Zero-knowledge Proof systems can rely on postquantum and non-postquantum, so afaik ZKP are post quantum secure if they rely on post quantum primitives. So it can be reimplemented in a second moment if the current version rely on non post quantum primitives. I'll suggest to read the rest of the answer and the answer below that: >[see above] >There exist ZKPs that only use collision-resistant hash functions and hence are plausibly post quantum secure. Popular examples include Hyrax, Aurora, or zkSTARK. >Other notable ZKPs like Bulletproofs or libsnark rely on cryptographic assumptions which are known to be vulnerable to quantum attacks (e.g. hardness of discrete log in certain elliptic curve groups). >Informally, post-quantum cryptosystems strive to remain secure even in the scenario that the attacker has a large quantum computer. Precisely, the basic hard assumptions such as DLP, BDH and so on are not secure in this scenario. >Regarding the Zero-Knowledge proof systems, it depends on the setup phase and model of working in each ZK proof scheme. For instance, ZK-SNARKs are based on a trusted setup which is executed by a third trusted party. At this point, we suppose these schemes are secure because there is no adversary to find a solution for some hard problems in the polynomial time. So a quantum attacker is able to compromise the security by attempting to find a solution for the claimed hard problem. Each user who has the master key is able to do some malicious activities. I should emphasize that if the setup phase in this schemes is based on some quantum-resistant hard assumptions so this scheme will resist against this kind of attack. >Conversely, in the ZK-STARKs, there is no third trusted party to produce secure parameters and the prover and verifier just use some plain parameters which are based on pure mathematics instead of a master key. So in this model, there is no secure parameter with some assumptions based on hard problems. You can take a look at this post. LINK [2] [1] https://crypto.stackexchange.com/questions/64081/are-zero-knowledge-proofs-quantum-resistant [2] https://crypto.stackexchange.com/questions/56327/what-are-zk-starks/63229#63229

>>8283 for all new to PQCrypto, I'd suggest to take a look :) >Post-quantum cryptography:Cryptography designed under the assumption that the attacker (not the user!) has a large quantum computer. https://fahrplan.events.ccc.de/congress/2018/Fahrplan/events/9926.html

>>8283 why wouldn't some researcher go bizerk and steal 10 billion of bitcoin.

https://www.youtube.com/watch?v=zsLwPCRv49Y Watch out! Customs are looking for Bitcoin. They don't know what the fuarrrk it is, but they're looking for it.

>>8332 Anon, I don't get why you posted that here, that's not cryptographic related: the misunderstanding of Bitcoin from TSA is not cryptography.

>>7687 OP tell us more, what do you know about PQCrypto? Can you share that with us?

>>7687 Can anybody explain how good one time cyphers work against quantum encryption? What I mean by that is that you have a notepad for example, and each page has a separate cypher, and then once a message is sent, then the page is destroyed, and both the sender and receiver use the same cypher only one time, and the cyphers themselves are basically pseudo-random so that there is a low probability of them being detected. Although very labor intensive, are they still viable against quantum decryption technologies?

>>8492 >Can anybody explain how good one time cyphers work against quantum encryption? I think you are confusing a bit: - quantum encryption isn't still a reality, but when it will be used, theoretically no one could crack it (if done right) - Post Quantum Cryptography is a set of cryptosystems[1] that is resistant from factorization using quantum computer, see this easy explanation to understand[2] > One Time Cypher do you mean Post Quantum [see above] or One Time Pad? One Time Pad is cryptographically secure as you need the entire key and the entire cipher to recover the message, instead public key cryptography usually is based on the hardness of factorization, tho I don't know if I can really explain how this works here as I might need an entire thread just to teach you this: you might want to take a look at this course if you are interested[3] So if I have understood correctly, your example is correct and no they are not viable: we usually derive key from a more simple key that we exchange, like in PGP (encrypt a key using RSA) or DH Key Exchange (compose a key together without sharing it), but we need something not based on factorization right now. [1] https://en.wikipedia.org/wiki/Cryptosystem [2] https://www.youtube.com/watch?v=lvTqbM5Dq4Q [3] https://www.coursera.org/learn/crypto

>>7687 can you teach us cryptography?

>>8492 one-time pads(which I think you're describing) are the only possible perfectly-secure cryptosystems, and are still strong against quantum computer attacks. They have numerous disadvantages though. Some caveats: you can use each key *once*, you need a secure method of distributing and storing keys, and the keys need to be perfectly random, not just pseudo-random. I might be getting a job directly related to post-quantum cryptography soon. So far it seems like they're not choosing a particular cipher for their cryptosystem, instead making it pluggable, which is a good idea IMO. Also: most quantum algorithms terminate with the correct answer with probability 1, but it's important to note that probability 1 is not the same thing as a thing definitely happening. For an example: if you choose a random real number between 0 and 1 from a flat distribution, the probability of choosing any particular number is 0, but you could still end up picking it.

>>8934 >storing keys Is there any good way to do this on a computer, or will you always have to depend on lesser encryption to secure the pad?

>>8936 exactly, you would always be relying on less secure encryption if you encrypted the keys. Similarly you would always be relying on a lock to secure them physically. In practice, spies would hide the pads, and in the event that they were caught the pads would be laced with magnesium so they burned instantly

>>8938 What about a combination of the two? A hardware device that dispenses keys one at a time and purges each key as it's dispensed. - computer sends plaintext to device - device passes the bits through the top key in the stack[1], destroying it in the process - device sends ciphertext back to computer You don't have to worry about past communications being decrypted, because the keys are never cached anywhere. You don't have to worry about future communications being decrypted, because you'll know if your device is stolen. Even if the computer is compromised, it won't be able to read the key because all input sent to the device is dumbly turned into ciphertext and sent back out. [1] or just one long key, since you're not dealing with pieces of paper anymore

>>8327 they would have to do it slowly because market would die immediately when found out. then someone would release a quantum proof "Bitcoin QT" fork from a snapshot of the block before the attack. Making a fork like this before the attacks become possible would be more profitable for someone intelligent enough to be this destructive. I wish I was skilled enough to apply QT-proof mathematics to cryptocurrency >>8283 They say us black projects are usually around 50 years ahead of the "known" technology. Sometimes I wonder if they already have some form of quantum crypto breaking tech, we know about their massive ASIC farms but maybe there's more. The fact that Google's quantum achievements are allowed to be publicized makes me think "they" might be farther ahead than we know

>>8946 dont forget that several other countries have tried to flaunt how powerful their quantum capabilities are, but I am not well versed in the subject. Am I understanding the system properly where quantum cryptographic systems deal with using entanglement as a cypher to determine if items have been tampered with, and only the end users can utilize the full system? Plz no bully, my only experience with quantum systems involves reading a lot about quantum radar for precise object identification. I read a little about DARPA secured communications and how they used a combination of fiber and photon entanglement as a cryptographic technology.

next week I'll open a cryptography thread on lambda

>>8946 > we know about their massive ASIC farms but maybe there's more Can you share resources on this?

>>8984 >Am I understanding the system properly where quantum cryptographic systems deal with using entanglement as a cypher to determine if items have been tampered with, and only the end users can utilize the full system? that requires specialized hardware. Generally when people say "post-quantum cryptography" they mean cryptography that can be computed on a classical computer but still can't be broken on a quantum computer. There are various propositions for cryptosystems that may or may not do this; they all have drawbacks(huge key sizes and unknown security guarantees are common)

is there anyone on isogeny?

>>10714 >>10327 >>10325 >>9333 I think we should move our questions/answers/discussion on /lambda/ dunno if just copying and pasting everything there.