7 ms·
I work on homomorphic encryption, and there are some rumors circulating that, if this checks out, it will break some of the leading FHE schemes like BFV, where
by j2kun 3y ago
I work on homomorphic encryption, and there are some rumors circulating that, if this checks out, it will break some of the leading FHE schemes like BFV, where the moduli used are quite large (in the hundreds of bits or even over a thousand bits).
- ilya_m 3y ago… only if scalable quantum computers exist.
- warkdarrior 3y agoIf scalable quantum computers do not exist, we do not need PQC.
- foota 3y agoHemomorphic encryption is not the same thing as post quantum crypto?
- deknos 3y agoHomomorphic Encryption does often use lattice mathematics
- Ar-Curunir 3y agoBut classically secure FHE is still a useful thing (even if it is broken by hypothetical quantum computers).
- Beldin 3y agoNo, they're orthogonal terms. Homomorphic encryption is encryption where a specific operation on ciphertexts (e.g., ×) translates into an operation on the underlying plaintexts (e.g., +). With fully homomorphic encryption, there are even two such ciphertext operations (and corresponding plaintext operations). Post quantum crypto is cryptography that cannot be broken by a quantum computer. This is rather nebulous, since we haven't yet discovered all possible algorithms that can run on quantum computers. Before you know it, someone comes along and finds a new efficient algorithm for quantum computers that breaks something thought to be post-quantum. Which is what is happening here - if the results stand up under scrutiny. Sidenote: it may turn out that any crypto scheme which supports some operation on ciphertexts that translates into an operation on the plaintexts is quantum-resilient (or, vice versa, quantum-vulnerable). But tgat would require a fornal proof.
- sgt101 3y agoWe need PQC about 20 years before practical, scalable gate quantum computers appear (if they can do all the right gates). I think that this will be signaled when someone factors a 32 bit integer on one. At that point I guess it'll be about 20 years before someone can factor a 2048 bit integer, and I'll get twitchy about what I am sending over the wire with PKI. My feeling is that all my secrets from 20 years ago are irrelevant to life now so I feel 20 years of warning is quite sufficient.
- adastra22 3y agoWe are within 20 years of scalable quantum computers already.
- adrianN 3y agoThe record for integer factoring on quantum computers was on the order of factoring fifteen into three times five the last time I checked. Can we do three digits now?
- baby 3y agoThe last time I checked they even cheated to factor fifteen
- WJW 3y agoYou should check again. Numbers like 1099551473989 have been factored successfully by now. The arxiv link in the sibling post is a good start.
- adgjlsfhk1 3y agobiggest number factored by a quantum computer isn't the right question. the right question is biggest number factored using a polynomial time algorithm. the answer to that as far as I know of still 15 (although I would be interested in papers that show more progress)
- Ar-Curunir 3y agoFHE is still only known from lattices, and has nothing to do with post-quantum computers.
- odyssey7 3y agoI wouldn't bet against the existence of a modern Bletchley Park analogue.