Shielded kudos authorization: abstract and PRF approach

Applications
1

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.