Identity System

[chris13524]

We need an identity system that will satisfy the following conditions:

• be post-quantum safe
• a universally identifiable public ID
  • the ability to sign content using this ID
  • the ability to encrypt content using this ID
• implement organizations

Post-quantum Safe

Due to the impeding risk of quantum computers breaking the common RSA scheme (and several others), a new crypto system needs to be created that is quantum-proof. Take a look at pqcrypto.org for more technical information.

A Universally Identifiable Public ID

Similar to PGP, each entity needs to have a public ID that is different from everybody else. One should be able to use this public ID to prove that signed data originated from the owner of the ID. One should also be able to encrypt data that only the owner of that ID can decrypt.

Implement Organizations

A current problem is that in order for organizations (as opposed to an individual) to have an ID, one must either:

1. store the private key in a secure location (such as a HSM) with individuals given access with physical keys
2. separate the private key and distribute it among individuals

Both of these approaches have problems.

For the first one: this requires a physical location in the world to store the private key. This means that due to natural disasters or other causes, the private key could become inaccessible or lost (thus dissolving the organization). Smaller organizations may not be able to afford round-the-clock security of such a facility and thus should not be required.

For the second: permanently giving away part of the private key would allow enough individuals over a period of time to fully compromise the ID.

[garretyoder]

I'm confused as to why you're worried about quantum computers.

[ethanrjones97]

On point one I think we need to work on making our various secure algorithm very modular. As we saw with the recent breaking of SHA-1 and git, if the implementation is too embedded in the system we'll be in a world of hurt. This could present some compatibility problems, however I think security should always take the high ground here.

When it comes to those algorithms being post-quantum, I think were at the mercy of researchers here as I'm unaware of "the RSA of the post-quantum world" and until that happens and has been throughly tested our hands are tied. Luckily it seems quantum computers are only capable of reducing the security bits of most algorithms to a point that can be avoided by just having larger key sizes.

I have no comments currently on organization, by which I think you mean "CAs"?

[ethanrjones97]

@garretyoder https://youtu.be/JhHMJCUmq28?t=5m43s

[chris13524]

I agree with your idea about the modularity. Such a system should be able to be upgraded relatively easily as problems are found and patched.

By organization, I'm referring to the ability for businesses, cooperations, non-profits, etc. to be able to handle an ID without requiring such a complex security setup. Currently, smaller organizations would simply have to trust their IT guy to not leak the private key. Take SSL certificates for example, you must trust the guy with access to the private key. This isn't as big of an issue with SSL because the certificate could simply be revoked and gotten again, but putting trust in a root authority is not something I think we want to pursue in Project Asiago.

Given the O notation for Shor's algorithm (O((log x)^2*(log log x)(log log log x))) and general number field sieve (the most efficient classical algorithm measuring O(e^(1.9*((log x)^(1/3))*(log log x)^(2/3)))), I'm able to calculate that factoring at 2048-bit key would take about 5.8*10^32(log+log+x)%5E(2%2F3))) whereas on a quantum computer, it would only take around [2.910^7](https://www.wolframalpha.com/input/?i=y%3D((log+x)%5E2*(log+log+x)(log+log+log+x));+x%3D2%5E2048) this is a huge difference in speed.

If were were to upgrade to 4096-bit, the classical algorithm now takes 3.5*10^46(log+log+x)%5E(2%2F3))) while the quantum one takes only [1.310^8](https://www.wolframalpha.com/input/?i=y%3D((log+x)%5E2*(log+log+x)(log+log+log+x));+x%3D2%5E4096). While the classical algorithm slows down dramatically, we see little effect on the quantum one. Even after increasing the key size to around 128KiB (131072-bit), we only see the quantum algorithm taking 2.3*10^11;+x%3D2%5E131072) while the classical is taking a whopping 1.2*10^188*(log+log+x)%5E(2%2F3))). I was unable to test any larger examples due to WolframAlpha not giving me answers anymore. I can only imagine how much larger the key must be in order to reach comparable 2048-bit security. With this in mind, I do not believe larger keys would be a viable option.

[ethanrjones97]

What current quantum computers have this ability currently? I think we should rely on the most battle tested algorithms right now and keep it modular so we don't rush to adopt something broken by possibly even classical computers.

[chris13524]

Of course, that would assume the post-quantum algo would be able to encrypt and sign just like RSA would have.

[ethanrjones97]

How do you figure? It should just be replacing n problem with something other than factoring.

[chris13524]

Well I suppose the original parameters require it to be able to sign and encrypt, so whatever post-quantum algorithm is picked, it would need to support both those features.