Long Term R&D: PQ security (proposal)

Roadmap
1

1. Summary

This is a motion proposal for the long-term R&D of the DFINITY Foundation, as part of the follow-up to this post: Motion Proposals on Long Term R&D Plans (Please read this post for context).

This project’s objective

In the future attackers may be aided by quantum computers. Quantum algorithms can break some of the cryptographic assumptions the Internet Computer relies on, specifically they can break the discrete logarithm assumption. A quantum-capable adversary could thus forge signatures used in the IC. Predictions of when quantum computers will be powerful enough to break the discrete logarithm problem vary, with a small minority of experts believing it could be within the next 5 years. The IC must therefore be hardened against quantum-capable attackers.

2. Discussion lead

Jens Groth

3. How this R&D proposal is different from previous types

Previous motion proposals have revolved around specific features and tended to have clear, finite goals that are delivered and completed. They tended to be measured in days, weeks, or months.

These motion proposals are different and are defining the long-term plan that the foundation will use, e.g., for hiring and organizational build-out. They have the following traits and patterns:

  1. Their scope is years, not weeks or months as in previous NNS motions
  2. They have a broad direction but are active areas of R&D so they do not have an obvious line of execution.
  3. They involve deep research in cryptography, networking, distributed systems, language, virtual machines, operating systems.
  4. They are meant to match the strengths of where the DFINITY foundation’s expertise is best suited.
  5. Work on these proposals will not start immediately.
  6. There will be many follow-up discussions and proposals on each topic when work is underway and smaller milestones and tasks get defined.

An example may be the R&D for “Scalability” where there will be a team investigating and improving the scalability of the IC at various stages. Different bottlenecks will surface and different goals will be met.

3. How this R&D proposal is similar to what we have seen

We want to double down on the behaviors we think have worked well. These include:

  1. Publicly identifying owners of subject areas to engage and discuss their thinking with the community
  2. Providing periodic updates to the community as things evolve, milestones reached, proposals are needed, etc…
  3. Presenting more and more R&D thinking early and openly.

This has worked well for the last 6 months so we want to repeat this pattern.

4. Next Steps

Developer forum intro posted
1-pager from the discussion lead posted
NNS Motion proposal submitted

5. What we are asking the community

  • Ask questions
  • Read 1-pager
  • Give feedback
  • Vote on the motion proposal

Frankly, we do not expect many nitty-gritty details because these are meant to address projects that go on for long time horizons.

The DFINITY foundation’s only goal is to improve the adoption of the IC so we want to sanity-check the projects we see necessary for growing the IC by having you (the ICP community) tell us what you all think of these active R&D threads we have.

6. What this means for the existing Roadmap or Projects

In terms of the current roadmap and proposals executed, those are still being worked on and have priority.

An intellectually honest way to look at this long-term R&D project is to see them as the upstream or “primordial soup” from which more baked projects emerge from. With this lens, these proposals are akin to asking, “what kind of specialties or strengths do we want to make sure DFINITY foundation has built up?”

Most (if not all) projects that the DFINITY foundation has executed or is executing are borne from long-running R&D threads. Even when community feedback tells the foundation, “we need X” or “Y does not work”, it is typically the team with the most relevant R&D area that picks up the short-term feature or project.

2 Likes
2

Please note:

Some folks gave asked if they should vote to “reject” any of the Long Term R&D projects as a way to signal prioritization. The answer is simple: “No, please, ACCEPT” :wink:

These long-term R&D projects are the DFINITY’s foundation’s thesis at R&D threads it should have across years (3 years is the number we sometimes use internally). We are asking the community to ACCEPT (pending 1-pager and more community feedback of course). Prioritization can come at a separate step.

3

Hi @JensGroth, This is one of the most portant things to do now. In one of Dominic’s blog posts he mentions the quantum-safe-cryptography, but doesnt give specifics. For anyone who doesnt know, Quantum computing will hit the public-sector by a storm and out of nowhere. IBM already has now a working quantum computer that is open to the public! that anyone can use to run quantum-algorithms on (through the web), and many universities and research centers, and private companies are already using it and exploring quantum-computing and quantum-algorithms, and some even building their own quantum-computers.

image
image1006×552 32.9 KB

This is what is available now for the public, imagine what governments and militarys around the world have in their labs… .

I am looking forward to some more specifics, like which signature schemes and crypto-algorithms are quantum-safe?

4

Post-quantum security

Objective: Make the IC secure against quantum-capable attackers.

Discussion leads: Jens Groth, Andrea Cerulli

Background: In the future attackers may be aided by quantum computers. Quantum algorithms can break some of the cryptographic assumptions the Internet Computer relies on, specifically the hardness of computing discrete logarithms. A quantum-capable adversary could thus forge signatures used in the IC. Predictions of when quantum computers will be powerful enough to break the discrete logarithm problem vary, with a small minority of experts believing it could be within the next 5 years. Hardening the IC against quantum-capable adversaries is a significant effort and already now attackers are known to harvest ciphertexts to later be decrypted with quantum computers, so it makes sense to start early on making the IC post-quantum secure.

Open research questions, topics and key milestones:

  • Determine versatility, efficiency and cryptanalytic resilience of primitives to be believed to be post-quantum secure and select appropriate security parameters. Existing symmetric key primitives such as AES and SHA are believed to be post-quantum secure. For public-key encryption the current front-runner is lattice-based cryptography. For signatures there are both lattice-based and hash-based candidates, however, lattice-based signatures may be more versatile in building more sophisticated signatures e.g. threshold signatures
  • Evaluate the quantum computing landscape annually and continuously monitor the cryptanalytic landscape to inform choices of primitives we rely on and determine appropriate security parameters
  • Invent appropriate post-quantum schemes, when there is no existing solution. Some of the schemes in the IC are non-trivial to translate to the post-quantum world, e.g., threshold relay or non-interactive DKG. An alternative when no such scheme exists is to modify the IC protocol so that it relies on a different type of cryptographic scheme.
  • Prove all schemes are secure under appropriate cryptographic assumptions. There are pitfalls to avoid here, a common mistake is to assume a cryptographic scheme is secure as long as it is based on post-quantum secure primitives. This is not always the case, so the IC must rely on schemes that have security reductions testifying to post-quantum robustness. There are also schemes where classical definitions of security fail, the classical binding property of commitment schemes does for instance not suffice against quantum-capable attackers.
  • Develop, implement and deploy alternatives to the current cryptographic suite. Some of the schemes the IC uses are already believed to be post-quantum secure or likely to be provided by the cryptographic community, e.g., hash functions and TLS. Others, such as the multi-signatures and threshold signatures are likely to require new implementations
  • Work with the community to specify requirements for post-quantum security on the user side. How to provide PQ-safe wallets, user authentication, libraries to verify PQ-safe communication from the IC.
  • Transition to post-quantum security: how to protect dormant users with staked ICP, how to protect confidentiality of encrypted data, assess whether quantum computers will come as an evolution or a revolution, and how to prepare for the latter scenario

Skills and expertise: Cryptographers versed in post-quantum cryptography, with lattice-based cryptography as the current front runner. The Research Team and the Crypto Library team will work jointly on the initiative.

How to work with the community: On the research side, the project is suitable for collaboration with researchers in and outside of academia. The developer community can contribute to the creation of tools that make canister smart contracts post-quantum secure. Community discussions can guide the requirements for post-quantum security and settle on standards and best practices for the IC.

What we are asking the community:

  • Review comments, ask questions, give feedback
  • Vote accept or reject on NNS Motion
  • Participate in technical discussions as the motion moves forward
8 Likes
5

Sorry for this useless messages but I need to say this : you are stars guys, stars. I am so admirative. This thread topic about quantum possible issues is impressive. Thank you for everything.

10 Likes
6

While other blockchains are worried about next week’s token price, the Internet Computer is already preparing for a post-quantum contingency…

5 Likes
7

@levi IBM has a quantum computer with 127 physical qubits. Note however that physical qubits are unstable. To get logical qubits that are stable, you need error correction on the physical qubits. According to this article, IBM is planning an 1121-qubit quantum computer that would give you a handful of logical qubits. So there is still a lot of engineering to be done before standard cryptography is threatened.

3 Likes
8

Proposal is live: Internet Computer Network Status

9

I applaud the effort.
Planning for cryptographic algorithm obsolecence is important and a huge effort.

Please ensure within scope resources to construct a MOTOKO cryptographic library that can be used for smart contracts and and not just to address the backend ICP. Correct implementation and verification of algorithms is complex and should not be left in the hands of the inexperienced.

A full sute of cryptographic services are required covering:
Encryption (e.g. Symmetric and Asymetric including Elliptic Curve)
Key Establishment Schemes
Digital Signatures
Secure Hash Algorithms
Message Authentication Codes
Key Derivation Functions
Deterministic Random Bit Generators

This should include both Post-Quantum Encryption Algorithms {e.g. NTRU,Classic McEliece, CRYSTALS-KYBER) and Post-Quantum Digital Signatures {e.g. CRYSTALS-DILITHIUM, FALCON,Rainbow}.

Also, services to provide homomorphic encryption should be a consideration.

Sound cryptography with an array of capabilities is what will be a key differentiator going forward for smart contracts on the ICP.

10

Hello everyone, more specifically, hi @JensGroth,

Hope you are well !

Here is my question : Isn’t it a bad idea to stake ICP for 8 years WITH a Ledger hardwallet, whereas they could see their cryptography overwhelmed by PQ while ICP could have reached their own PQ security. I don’t see any concrete mention of PQ on Ledger cie’s own forum, whereas ICP does. Would you recommend to not stake for 8 years with Ledger ?

Maybe the ICP internet identity would be a better choice, eventually, since it would benefit of ICP upgrades in such a scenario. I mean, people having created their neurons through internet identity could benefit of quantum security reached by Dfinity, whereas those having used a Ledger Hardwallet, if Ledger would not have reached the quantum security (while Dfinity would have), would have to remain compromised for the rest of their dissolve delay.

And in same order of concern : would someone having created a neuron under the current security protocol, could migrate toward the quantum protocol, once discovered ? Or would we see a separations between neurons having to stay with the ancient protocol, and the new ones ?

Thanks a lot.

Regards

11

Hi Roman.

The general answer is indeed migration, i.e., we need to update the authentication mechanism for the neuron’s controller, e.g., update from a principal based on a non-post-quantum public key to a principal based on a post-quantum key.
As your question hints at, there are some subtleties in this, e.g., usually you cannot transfer neurons to new principals and there are differences in what can be done depending on your setup (ledger, air gapped computer, NNS frontend or another wallet). Regardless, the priority should be to enable PQ security for all neuron holders, so even if that entails a one-off permission to switch principal that would be a much better option than keeping neuron holders locked with non-PQ-secure control over their neuron.
I’d recommend basing your neuron setup on current security considerations. IMO the NNS frontend dapp, which uses Internet Identity, is great for small amounts due to convenience and ledger/air-gap better for large amounts since they do not rely on the security of an online machine.

3 Likes
12

Thank you so much for this explanation @JensGroth.

1 Like
13

Jens, I’ve looked at a list of your publications and it is very encouraging. I’m curious about a few things to help keep attention on this subject, if you don’t mind taking the time to share your thoughts.

One thing that convinced me to invest in ICP was the team’s early attention to the security challenges presented by quantum computing. From the very beginning Dfinity was already preparing for long term threats to the IC, and had enough knowledge and foresight to see this coming.

Could you speak to your own analysis of the current rate of advancement in quantum computing? Are threats developing any slower or faster than anticipated? Knowing what we do today, and aware that there are some organizations working diligently on quantum tech in secret, by what year would you like to see the IC hardened against PQ attacks? Is there encrypted data in the IC that could be harvested today and cracked in future years that can’t be easily migrated?

On a related note, are there any parts of the IC that you think could take particular advantage of quantum computing (threshold relay consensus, data privacy)? Is anyone at Dfinity actively studying quantum programming?

I understand that this problem is still a ways off, and I don’t mean to be a thorn in anyone’s side :slightly_smiling_face: My concern is for the long term health of the IC, and I appreciate your time and expertise.

4 Likes
14

Fwiw, I have pinged @JensGroth on your question. This thread is a bit old so I do not think he saw it.

15

Thank you, I realize I should have replied to him directly so I appreciate that.

1 Like
16

Thanks for the ping @diegop, I had indeed missed this question.
Hi @Jonathan. I’m not a quantum computer expert myself, so I rely on information by those who do research in that area, e.g., the quantum threat timeline report linked in the OP. My guess 5 years ago based on discussions with experts was early 2030s and quantum computing is moving a bit slower than I expected back then, e.g. quantum supremacy came later than I thought it would. Predictions vary though, so I’d say the target for us should be sooner. We do not have a set target year, but in my personal opinion 2025 sounds reasonable to aim for.
We’re giving higher priority to more time sensitive features so PQ safety is not a topic we’re investing much into at this very moment, but we have started an initial investigation into which PQ-secure lattice-based schemes could be good candidates for us to work with.
The platform is mostly focused on preserving integrity and does not offer much in terms of confidentiality. Encryption is used to protect secret key material, e.g., keys subnets use to certify outputs and threshold ECDSA signing keys. But all of those keys are for dlog-based signature schemes and have to be changed anyway when we migrate to PQ safe crypto.
Dapps building on the IC that rely on encryption should also consider the PQ safety aspect.
Quantum computers (and also other quantum tech that does not realize a quantum computer) have interesting properties so I’d certainly expect there are theoretical advantages and protocols that can achieve new features that are useful in the blockchain space. We are not looking into that though due to the long time horizon.

2 Likes
17

Now that NIST has published final versions of the PQ algorithm standard yesterday, will this ripple into the ICP Long Term PQ Security roadmap?

FIPS 203

Module-Lattice-Based Key-Encapsulation Mechanism Standard

FIPS 204

Module-Lattice-Based Digital Signature Standard

FIPS 205

Stateless Hash-Based Digital Signature Standard

4 Likes
18

Also curious on this topic, as it is one of the first things people ask me after the penny has dropped on the potential of ICP. And here we are talking CIO/CTOs and probably CISOs will be asking it before I am even done presenting ICP…

IBM expect their quantum machines to be stable and running by 2025 if you talk to them and are already selling a lot of PQ projects to, e.g., banks. So it would be nice to say “in ICP/UTOPIA this will be handled through… to be implemented by early 2025”

Thanks!

1 Like
19

The timeline may have just gotten shorter.

Many companies are already working on “quantum-safe” encryption methods to protect against future quantum attacks. However, the Chinese research emphasizes that such measures may need to be implemented urgently to safeguard sensitive information.

"The growing threat from quantum computers requires immediate attention to ensure the security of our digital future,” the researchers warned in the paper.

“The early and widespread use of quantum computers could wreak havoc, enabling new advanced cyberattacks that are impossible using classical computers,” Kaur said. “Post-quantum cryptography (PQC) is the solution to this problem.”

20

Yeah, looks like banks are also already looking into quantum secure transport protocols as well HSBC becomes first bank to join quantum-secured metro network in UK

Curious if there has been any further research or updates by dfinity in this regard

1 Like