How could an offline app verify a signature from one of many private keys?

Question

I have a situation where an offline app needs to be able to verify whether some data was created by a set of privileged users of the app. These privileged users will each have one private key of some sort that can be used to sign this data. Any user (privileged or not) must be able to verify that the data came from a privileged user.

I'm not sure what the number of privileged users is going to be, but for the sake of discussion we can assume it will be no more than 100,000. And the app being offline means it can't rely on connecting to a server to verify any data or update itself.

I know one possible way to do this with public-key cryptography would be to generate all of the needed public/private key pairs ahead of time, include all of the public keys in the app itself, and give each privileged user one private key. Then signed data from privileged users could include some metadata that identifies which public key should be used to verify its signature.

However, I'm not sure what the security implications of that method is. I'd also like to keep my app as compact as possible. If I used 2048-bit RSA encryption then the size of 100,000 public keys would be just under 25 MB. In this day that's not too bad but it'd be nice if that space requirement wasn't there.

So my two questions are:

1. Are there any significant problems with the above approach?

2. Is there a cryptography method available that would allow me to do the above without needing to include so many public keys? Ideally it would also a) allow a practically unlimited number of private keys to be generated after the app is released, and b) not have the signatures be anonymous, though neither of those are strictly necessary.

I'm also open to alternative approaches for accomplishing what I'm after. My understanding of cryptography is admittedly not so deep so I may be missing or misunderstanding something.

Answer 1

You seem to be the person that is responsible for the private keys or at least the app. In that case you should look into PKI: public key infrastructure.

The most well known PKI infrastructure is that for TLS certificates. If you take a look at the certificate store of your favorite browser you'll see that there are no certificates there for your favorite services. Instead there is a set of trusted certificates of different certificate issuers. These are used to sign other certificates, in the end one of these certificates is the certificate of the end user, in this case a web server. This end-user is certificate is called a leaf certificate. The first certificate in the chain is called a root certificate. The certificates together look like a certificate tree.

The idea of a PKI is that the public key is part of the certificate. In the end this public key is trusted because there is a chain of certificates leading to a certificate that is trusted.

---

So you should become your own CA: you will create a self-signed root certificate, which is shipped with (and therefore trusted) by your app. You sign other certificates using the private key that is part of the key pair for the root certificate. Now the users can use their private key to create a signature, and have that signature be accompanied by the certificate that contains the public key of the user. Once that certificate is trusted by chain verification to the root certificate, the public key is trusted and can be used to finally verify the signature.

Generally PKIX is used, which uses a specific type of certificates called X.509 certificates. There is pre-made software that can be used to create certificates. An example is openssl ca.

---

The difficulty with your approach is not the security - public key or certificate pinning is a valid approach. The problem is the management: each time you add a key you need to update all your software. That is not the case if you can verify a certificate chain, only one certificate needs to be trusted. A certificate can also contain things such as identity, issuer, validity period, key usage and more.

Note that revoking a certificate or public key can be more tricky. You may need e.g. an Online Certificate Revocation Status protocol server so certificates and public keys can be trusted to be still valid.