Possible to use an accumulator to “license” or restrict the qty of certificates being used?

Suppose in a future version of x509 PKI, it is possible to limit the quantity of certificates being used, what would that look like?

Here is a concept that won't work in the real world, but illustrates what I'm trying to do:

1. The child CA sends a list of primes to the parent CA (the prime is the public key of an issued certificate and therefore unique)
2. The parent CA checks the quantity of primes, and if it's less than the license threshold, it creates the product of those primes. (quasi-commutative hash)
3. The parent CA signs the result of #2
4. Each validator (web client) gets the signed result of #2, and ensures membership of the public key in the accumulator

The reason I ask is because I'm working with a different crypto system developed by a 3rd party, and was told I need to constrain its usage somehow. The design of the 3rd party system is similar to PKI, and therefore many of the thoughts are transferrable.

In short: The parent CA would sign the public key of an n-time signature scheme, as opposed to the public key of a signature scheme which is valid for an unbounded number of signatures (the current design).

n-time signature schemes are usually just constructed by generating n instances of a one-time signature scheme and then accumulating their public keys together into one public key.

The child CA would present their n-time public key (along with a proof that the public key accumulates only n OTS instantiations) to the parent CA to be signed, just like usual.

• Every "signature scheme which is valid for an unbounded number of signatures (the current design)" is "an n-time signature scheme". $\:$ However, for direct constructions of n-time signature schemes, your suggestion would allow for somewhat-short arguments that the child CA misbehaved. $\;\;\;\;$ – user991 Jan 13 '15 at 6:15
• This answer doesn't work. I think you are confused about what a $n$-time signature scheme is. A $n$-time signature scheme is a signature scheme that is secure as long as it is used only $n$ times. There is no guarantee that it's impossible to sign $n+1$ messages, and indeed every $n$-time signature scheme I've ever seen does allow signer to sign $n+1$ messages if he wishes (though this could enable others to forge additional signatures). – D.W. Jan 14 '15 at 23:59
• @RickyDemer: No, because $n$ is an upper bound. – Bren2010 Jan 15 '15 at 4:41
• @D.W., "Impossible" isn't a constructive concept in cryptography. Instead, in cases like this, it's common to setup systems such that behaving badly voids the entire instance. For $n$-time signatures, as you know, signing $n + 1$ messages allows forgeries. Another place where I can think of this happening is in contract-signing--I can convince you I've signed the contract, but you can't convince anybody else that I've signed it without revealing your private key. – Bren2010 Jan 15 '15 at 4:55
• @Bren2010 : $\:$ "No, because n is an upper bound" on what? $\;\;\;\;$ – user991 Jan 15 '15 at 5:11

That scheme is effectively the same as having the parent CA counter-sign all issued certificates, since the parent will have to make a new signature (on a new accumulator) for each newly issued certificate.

What are the features you want from such a scheme?

To frame the question, here's a trivial scheme: client sends certificate request to child "CA"; child signs certificate request (it doesn't issue a certificate, it just signs the request); child forwards signed request to parent; parent issues certificate if child is under its limit of certificates.

What you need now is to enumerate all the ways you want your scheme to be different than this one. For example, do you need confidentiality from the parent as to the certs issued? Do you want to avoid the requirement for the parent to have to be online and signing whenever the child wants to issue a certificate?

• YEa, I thought about that after I posted... perhaps the parent could sign a list of pre-approved primes. I'm trying to figure out which crypto would support this feature.. – goodguys_activate Jan 12 '15 at 19:45
• Primes are the private keys in RSA; the public parts are the modulus and exponent. If you pre-approve those, someone other than the client has to generate the keypairs, so the private keys would be held by someone other than the certificate end-user. That breaks most security guarantees. It would be equivalent to having the parent CA pre-generate and issue a certain number of certificates and store them in, say, PKCS 12 containers, and then just send those to the client. – Reid Rankin Jan 12 '15 at 20:18
• What if the prime was simply a "factor" in the private key? e.g. CA-issued prime * client issued prime = a non prime number used as the private key – goodguys_activate Jan 12 '15 at 21:49
• I know I'm being awfully negative, but this is an interesting problem, and I don't see an obvious solution. Like I said in my answer, the first step is to define the problem properly; then we can work on solving it. From your comments, I think what you're looking for is a way for the CA to pre-issue "tickets" of some type such that client certs have to use one to be validly signed. The CA doesn't need to know anything about the final client cert to issue the ticket. However, if two client certs appear with the same ticket, some or all of the security guarantees break. Is that fair to say? – Reid Rankin Jan 13 '15 at 5:09
• @makerofthings7: In that case, perhaps to avoid confusion you should edit the question with the updated requirements? – Reid Rankin Jan 15 '15 at 1:45

WITHDRAWN

Bren2010's solution is a good one if you can choose your crypto primitives. However, if you're looking for a solution that uses stuff supported by existing X.509 implementations, you could issue the child CA a ECDSA key and a list of pre-approved nonces. A single re-use of a nonce is enough to allow the child CA key to be calculated, so the child would have to use each one on the list only once.

You'd have to implement some extra code in whatever client relies on the scheme, in order to reject signatures from the child CA which aren't on the list of approved nonces.

UPDATE

Turns out that this is a stupid idea. In ECDSA, the nonce is secret, and revealing it would allow private key calculation just like re-using it would. I should have taken my own advice and avoided messing around inside crypto primitives!

• This would also be somewhat more space-efficient than a constructed n-time signature scheme. It's not post-quantum, though! – Reid Rankin Jan 13 '15 at 15:17
• This proposed solution doesn't work. A signer can still re-use the nonce to sign multiple messages. Therefore, this scheme doesn't prevent a child CA from issuing more than the allowed number of certificates. (Of course, if the child CA does issue more than the allowed number of signatures, it might allow others to forge signatures that look like they came from the child CA, so it might have some negative consequences for the child CA, but that's a bit delicate and isn't quite what the question asked for.) – D.W. Jan 15 '15 at 0:00
• @D.W.: Yeah, sure, it CAN, but by doing so it leaks its private key to the world, making all its signatures useless. – Reid Rankin Jan 15 '15 at 0:17
• Understood. But as I wrote... "that isn't quite what the question asked for". The question asked us to prevent issuing more than $n$ certificates. The answer doesn't mention this caveat. If the answer proposes a scheme that achieves something less than what was asked for, and where it might not be obvious that this is the case, it would be helpful to explain the limitations, describe what properties it does achieve, and explore whether the resulting scheme might still be adequate in practice or not. I suspect some child CA's might potentially be OK with their private key leaking. – D.W. Jan 15 '15 at 0:24
• @D.W.: But it does satisfy the revised requirements the OP and I worked out in the comments on my first answer, which complained about the requirements not being specific enough. – Reid Rankin Jan 15 '15 at 1:41

Not sure if this is what you're looking for but using a bilinear accumulator, you can actually restrict the number of accumulated items.

Specifically, if during the trusted setup phase you generate $q$-SDH parameters $\left(g^{s^i}\right)_{0\le i \le q}$, then the bilinear accumulator $A = g^{\prod_i{s - x_i}}$ is bounded: You can only add up to $q$ items (i.e., $x_i$'s) to the accumulator.

You can even ensure items are added in an append-only fashion: Given an old accumulator $A=g^{a(s)}$ and a new accumulator $A'=g^{a(s)u(s)}$, where $u(s) = {(s - x_{i+1})\cdots(s-x_j)}$ are the new items, the append-only proof is $g^{u(s)}$ and can be verified using the bilinear map: $e(g, A') \stackrel{?}{=} e(A, g^{u(s)})$.