Shielded kudos authorization: abstract and PRF approach

[kike]

The Kudos design suggests authorizing receiver-specific logic via signatures. This makes sense, and it probably suffices in many scenarios.

Still, it may be fruitful to abstract away the authorization mechanism, and explore other alternatives to implement the abstraction.

An abstract interface would consist in a pair of algorithms Authorize and VerifyAuthorization:

• Receivers generate a pair (secret,addr). They publish the address addr and keep secret private. Whoever knows secret owns addr. For example, a key pair (sk,pk) of a signature scheme.
• Receivers authorize policies \rho by generating a “proof of authorization” denoted with \sigma.
  Authorize(secret,\rho)\rightarrow \sigma
  For example by signing \rho with sk. The generation of \rho happens offline. It is not enforced by any resource logic.
• The kudos logic enforces the authorization \sigma on policy \rho is valid with respect the receiver address addr.

VerifyAuthorization(addr,\rho,\sigma)\rightarrow \{0,1\}

The obvious requirement being that it is computationally unfeasible to generate a valid \sigma for \rho and addr without knowing secret. For signatures, this is given by the difficulty of forging.

Authorizing via PRFs

Let \mathcal{F}:=\{F_{s}:\{0,1\}^k\rightarrow\{0,1\}^\ell\ |\ s\in\{0,1\}^n \} be a family of pseudo-random functions.

An address addr is a hiding commitment to the chosen PRF index s. Anyone knowing the index s and the commitment opening r owns the address.

addr = Commit(s;r)

secret = (s,r)

A policy is identified with a k-bitstring \rho\in\{0,1\}^k. The policy is authorized applying the PRF to \rho. The owner also computes a zero-knowledge proof of correct authorization. The proof \pi is for the relation

\mathcal R = \left\{((addr,eval,\rho);(s,r))\ |\ addr = Comm(s;r)\land eval = F_s(\rho)\right\},

where (addr,eval,\rho) is the instance of \mathcal{R}. The authorization is \sigma = (eval,\pi), and it is verified by verifying the proof

VerifyAuthorization_{PRF}(addr,\rho,\sigma) = ZKP.Verify((addr,eval,\rho),\pi)

Leveraging the knowledge soundness of the proof system, it should be computationally unfeasible to generate a valid \sigma without knowing s and r.

Why bother. Regarding what for this approach is useful, below I list a few things that come to mind.

• Defining addresses as (hiding) commitments allows to use the “commit-and-prove” paradigm to show extra properties on the user identity (the index s).

• Unlike authorizing via signatures, in the PRF approach \sigma = (eval,\pi) reveals no information about the policy \rho because the PRF evaluation eval looks random (and \pi is zero-knowledge). This means that \sigma can be part of the instance in a shielded kudo. Allowing to revoke policies via publicly blacklisting \sigma. On the downside, the logic circuit is probably more expensive. It involves verifying \pi as part of the authorization verification.

• We could explore whether this is well suited for policy delegation. Whatever this means at this stage.

[vveiln]

@kike

Receivers

I think in general context there is no notion of a receiver. For example, if we are authorising a burn, who is the receiver?

@kike

The generation of \rho happens offline. It is not enforced by any resource logic.

What do you mean by this? \rho is most likely to be a transaction or a transaction representative, and I’m not sure what it means here that it isn’t enforced by any resource logic and that it is generated offline.

@kike

A policy is identified with a k-bitstring \rho\in\{0,1\}^k

Can you give an example of such policy and what it translates to in the context of an authorised action?

@kike

reveals no information about the policy \rho because the PRF evaluation eval looks random

Perhaps I’m not understanding your idea correctly, but if the policy is a set of public data, we don’t need to hide it? So I assume the policy is something else but I don’t understand what it is that you intended to describe. Could you maybe also describe it less abstractly, instantiating the relevant fields such as policy with what it actually is in the context of building a valid kudos transaction?

[kike]

@vveiln

I think in general context there is no notion of a receiver. For example, if we are authorising a burn, who is the receiver?

It only makes sense when there is a receiver who sets up a receiving policy \rho. In the kudos design, for transferring with conditional receive and the kudos-to-anything cases (which both use signatures, I think).

@vveiln

@kike

The generation of \rho happens offline. It is not enforced by any resource logic.

What do you mean by this? \rho is most likely to be a transaction or a transaction representative, and I’m not sure what it means here that it isn’t enforced by any resource logic and that it is generated offline.

Sorry, that was a typo. I meant the generation of \sigma happens offline. (e.g. the generation of the signature). For signatures, it is not enforced that the signature is generated correctly. But for the PRF it is (it is a side effect: the verification of the authorization consists in verifying a zkp of correct generation. But not that I wanted to enforce correct generation explicitly).

@vveiln

@kike

A policy is identified with a k-bitstring \rho\in\{0,1\}^k

Can you give an example of such policy and what it translates to in the context of an authorised action?

For example, the receive authorization logic of the proposal. I presume it will be a circuit or a SNARK verifying key. In order to pass it through a PRF (or sign it) it needs to be interpreted as a bunch of bits/bytes. The bitlength of the circuit/verifying key must fit in the domain of the PRF (or in the domain of the messages to be signed).

@vveiln

Perhaps I’m not understanding your idea correctly, but if the policy is a set of public data, we don’t need to hide it? So I assume the policy is something else but I don’t understand what it is that you intended to describe. Could you maybe also describe it less abstractly, instantiating the relevant fields such as policy with what it actually is in the context of building a valid kudos transaction?

This has to do with this issue. Therein, I think you were concerned about re-using signatures of policies with the same public key. Like re-using the signature of a revoked policy. Translating to the PRF, re-using an evaluation eval = PRF_s(\rho_{rvk}) for the same address addr = Commit(s;r).

For signatures, putting \sigma (the signature) as part of the instance leaks the policy \rho that is signed: just try to verify the signature using different policies until a match is found.

For PRFs, putting \sigma = PRF_s(\rho) in the instance does not leak \rho, because \sigma is pseudorandom as long as s is not known. So, we can revoke policies by including \sigma in a public list, and during verification check \sigma is not in that list.

[vveiln]

@kike

It only makes sense when there is a receiver who sets up a receiving policy \rho. In the kudos design, for transferring with conditional receive and the kudos-to-anything cases (which both use signatures, I think).

Yes, but if we abstract authorisation, we will use it everywhere in this form, including for all other kinds of authorisation.

@kike

For example, the receive authorization logic of the proposal. I presume it will be a circuit or a SNARK verifying key. In order to pass it through a PRF (or sign it) it needs to be interpreted as a bunch of bits/bytes. The bitlength of the circuit/verifying key must fit in the domain of the PRF (or in the domain of the messages to be signed).

Ah, I see. I confused “identified” and “represented”.

@kike

For PRFs, putting \sigma = PRF_s(\rho) in the instance does not leak \rho, because \sigma is pseudorandom as long as s is not known. So, we can revoke policies by including \sigma in a public list, and during verification check \sigma is not in that list.

Who is generating \sigma? If the user has to generate it every time it has to be used, it is pretty much equivalent to having the user being online for the authorisation, which is undesirable. If the user generates it once, then the prover is not incentivised to re-randomise it. From what I see, it works the same way as for signatures (the user can always re-randomize the signature, and the prover is not incentivised to do so).