# Limiting how many key pairs someone can generate without compromising their keys

Is there any way to assign someone a limited quota for how many cryptographic key pairs they can generate (ECC, RSA, any algorithm), and preferably non-interactively? By non-interactively I mean there is no multiple handshake or multiple round trips between me and the person doing the generating and the relationship could perhaps be anonymous.

I'm imagining something where I generate, say, 50 tokens/certificates/whatevers and give them to someone. That person is then able to generate 50 key pairs and I am able to test to ensure that those 50 key pairs were properly entitled.

Of course the person could generate more key pairs without using my entitlements, but those would not check out.

I have a sense that something like this could be possible with homomorphic encryption or zero knowledge proofs or something similar but I can't think of a way to do it.

• What kind of system do you assume? Key Generation is an algorithm, and you can't keep a person from running the algorithm again with new randomness - especially if the algorithm does not involve any sort of interaction. In a PKI you could limit how often someone can request a certificate from the CA, but such a limitation does not involve any cryptography. From the question it is not clear what your actual goal is. – tylo Jul 28 '18 at 6:36

Let me try to rephrase your question in a way for which I might have an answer:

Is there a way for Alice to give Bob a "limited signing key" (LSK) such that:

1. Bob can freely generate up to $$n$$ keys (or other messages) and sign them using the LSK issued by Alice;
2. anyone can verify that these keys/messages were signed by an LSK that was issued by Alice to Bob;
3. as long the LSK is not used to sign more than $$n$$ keys/messages, it is not feasible for anyone who does not possess the LSK to forge a signature; and
4. if Bob does use the same LSK more than $$n$$ times, others will be able to forge signatures that appear to have been signed with the same LSK?

Honestly, I'm not sure if these requirements in any way match what you really want. However, I'll go ahead and answer this rephrased question and let you decide if it's useful to you.

In particular, I believe that a scheme meeting the requirements above could be constructed based on Lamport one-time signatures. Lamport signatures have the property that, if the same key is used to sign more than one message, forging a signature becomes much easier. Usually this is considered a disadvantage, but in your case it might be exactly what you want.

Specifically, for $$n = 1$$, Alice can generate a Lamport public/private key pair, sign the public key with her own (reusable) signing key along with any relevant metadata (like the fact that this particular key pair has been issued to Bob), publish the signed public key and its signature and send the corresponding private key to Bob.

Bob can then use the private key to sign anything he wants (such as the public half of another asymmetric key), and anyone else can verify that this signature matches the public Lamport key signed and published by Alice. But if Bob signs more than one message with the same key, it becomes possible for anyone with access to both signatures to create forgeries much more easily than they could with just one signature.

One potential issue to keep in mind is that the loss of security if Lamport keys are reused is gradual. Whereas normally, given one valid signature, forging a $$k$$-element Lamport signature requires $$2^k$$ attempts on average, with access to two signatures the average number of attempts needed drops to just $$2^{k/2}$$. (All this assumes that messages are hashed before signing, as they usually would be.) The problem here is that, if we choose $$k$$ conservatively to be large enough that $$2^k$$ attempts is definitely far beyond even the most powerful attacker's reach, it's possible that $$2^{k/2}$$ attempts may not be an entirely trivial task either, at least not for less powerful attackers.

Fortunately, there are ways to modify Lamport's scheme to make the security drop more abrupt. This will typically somewhat increase the length of the (already rather long) keys and signatures, but not necessarily by an unreasonable factor.

As for $$n > 1$$, at the moment I cannot think of a better scheme than simply issuing $$n$$ separate single-use Lamport keys. For all I know, there might be some clever way to handle this case more efficiently, but if so, I'm not aware of it.

• Your Kung-Fu Style is very good. I believe this might achieve what I want to achieve, since while it would be possible to generate more than N keys it would not be "advisable" and would compromise the generators' security or identity to do so. So there's an advantage to playing by the rules. I can't think of any other way. More specifically I can't think of a way to give someone the right to pick ONE random number while simultaneously not giving them a number or knowing anything about the number they pick... since I could of course just repeat the computation on my side. – Adam Ierymenko Nov 28 '18 at 16:02

Anybody can run any of the usual generators for asymmetric primitives as many times as they want. And they can do this without compromising the security of the private key. Generally the trust of a key pair by a user is however not in the private key, but in the public key or certificate around the public key.

Now you could embed a signed token in the certificate, but in that case you must make sure that the token cannot be reused. This could for instance be managed by a trusted third party, such as a Certificate Authority. You could for instance create a certificate extension and require a CA to validate that the token isn't reused. You then have another party to hold responsible if a duplicate token is ever found.

What you cannot do in this digital world is avoiding duplication. This can only be managed if you somehow manage to secure the processing of the data. For more information on that you'd have to look at digital rights management (DRM) rather than homomorphic encryption or zero-knowledge proofs - if you ask me.

And while I generally try and refrain from using buzz, this might be a case where blockchain technology could actually be helpful in case you don't want to use a CA / centralized management.

• Not a very detailed answer, but then again, the question is not all that detailed either... – Maarten Bodewes Jul 28 '18 at 17:42
• Yes my question was unclear. You're right that anyone can run any algorithm, and that's not what I was getting at. The question was whether there is some way to create certs blindly -- in other words put certs out there and allow people to claim them on a first come first serve basis. The more I think about it the answer may be no. Nothing that constrains key generation could do so without making it easier to crack the key. But I'll do more research. Maybe I haven't figured out how to ask my question properly. It's in my head but it's hard to explain. – Adam Ierymenko Jul 31 '18 at 12:09
• Yeah, I know that situation. I've posted many well structured answers, but posting a well received and understandable question is a different skill almost entirely. – Maarten Bodewes Jul 31 '18 at 15:25
• Okay here's a better attempt. I want to be able to generate a key/token X that I can give to you. You can then use X to generate one and only one key pair Y. I can prove that you generated Y with X, but I can't crack your private key. But... this is the most important part... Y is rigid with respect to X. You can only generate one and only one Y. The more I think about it the more I think this is probably impossible. – Adam Ierymenko Aug 2 '18 at 21:25
• It probably is not possible to make Y rigid with respect to X without making me (X's generator) able to obtain information about Y's secret... at least not without multiple interactions or a trusted third party. – Adam Ierymenko Aug 2 '18 at 21:26