# League of Identity: distributed identity-based encryption and authentication from Google and other providers
Vincenzo Iovino, Aragon ZK Research, November 2023.

## Problem statement
We wish a system that satisfies the following properties.
A user should be able to use his existing Google (or Facebook, Twitter, etc.) account or digital id card to engage in other distributed systems, e.g. a blockchain or a Decentralized Autonomous Organization (DAO). Moreover, we would also like to add identity-based encryption functionalities to these systems, namely a user Alice should be able to encrypt a message for the email address [e-mail] without interacting with Bob and Bob, just using his ability to log into Google, should be able to decrypt ciphertexts associated to his email address.
### Why do we need crypto?
Consider the following scenario.
We want to allow people to use a DAO only if the users own a valid Gmail address.
A trivial solution is to have a gateway that performs the following task. A user proves to the gateway that he is able to log into Google and the gateway authorizes the user to sign transactions in the blockchain. For example the gateway can provide to the authorized user a valid public and secret key pair and can add such public key to the DAO.
The issue here is that the gateway should be fully trusted. The gateway can indeed authorize any user to participate in the DAO and can associate any user to any Gmail address, even if the address is not owned by the user.
Moreover, it is not clear here how to efficiently enable identity-based encryption (IBE) that is one of our main goals.

#### Applications

A notable application of our system is to enable anonymous id-based crypto payments, see [here](https://hackmd.io/noiVZo2dTJ6Wiejt2IJvMg?both#Anonymous-identity-based-payment-system-AnonIBP)

Other applications include the creation of DAOs based on real-world identities or organizations or e.g. the DAO of influencers having >500k followers, etc. These DAOs can have at same time verifiability for the members and encrypted proposals, see [here](https://github.com/vincenzoiovino/LoI.SmartContracts/tree/main?tab=readme-ov-file#daos-of-google-business-domains).

## Our model
We envision the following model and we will later show how to implement it.

We assume that there is a set of $n$ nodes who share a master secret key $MSK$, that is each node $i\in [n]$ keeps a share $MSK_i$ of $MSK$ and a given threshold $t$ of the nodes (e.g., the majority) can reconstruct $MSK$.
Corresponding to $MSK$ there is a master public key $MPK$ that is a public parameter of the system.

A user Bob with email [e-mail] can log into Google and gets from Google what is called an OAuth 2.0 access token. This is a well-defined string that can be verified using public Google APIs and is associated to the google email address [e-mail] of the user Bob.
The user Bob then sends his access token to a subset $S$ of the nodes of cardinality $t$. Each node $i\in S$ replies with a share $Token^{i}_{Bob}$ and from the $t$ shares Bob can reconstruct a token $Token_{Bob}$.
Such token can be used in two ways.
* For encryption/decryption. A user Alice can encrypt a message $m$ using just the master public key $MPK$ and the email address [e-mail] to produce a ciphertext $CT$. Only Bob, having $Token_{Bob}$ can decrypt $CT$ and get $m$.
* Authentication and signatures. The token can be used to sign a message $m$ in the following sense. The signature algorithm takes as input the token $Token_{Bob}$ associated to the email [e-mail], the master public key $MPK$ and a message $m$ (e.g., the transaction to sign) and produces a signature $\sigma$. This signature is a well-defined string that can be transmitted with a transaction.
The verification algorithm takes as input the master public key $MPK$, the email [e-mail] and the signature $\sigma$ and outputs $1$ or $0$ to denote acceptance or rejection of the signature. The signature should satisfy the usual properties of digital signatures adapted to this context, namely completeness and unforgeability (e.g., hardness of computing signatures of messages for which no signature was observed before). The token can be also used to authenticate interactively in a way that a user Alice is able to verify the identity of the user Bob but Alice is unable to reuse the transcript of the protocol to impersonate Bob (that is, Bob can convince Alice to be the actual Bob but after this interaction Alice is unable to convince Charlie of the false claim "I am Bob"). Furthermore, we envision that the verification of the signature should be efficient for web3 applications. For instance, it is efficient to verify signatures of digital identity cards off-chain but verification on Ethereum of such signatures consumes too much GAS to be practical.

The previous properties enable very powerful applications. Only users with access tokens from Google and similar services can participate in a blockchain or DAO. Moreover, one can extract useful info from the access tokens like pictures of the users. Such pictures and additional info can be profitably used in the blockchain.
As an example the access token for Instagram could be used to extract info about the number of followers of users and create a DAO of influencers.
As another example profile pictures could be exploited in the following way: a group of people can add the same banner to their own profile pictures (e.g., a banner about some social cause) to create a DAO of people united by the some cause.
### The token validity.
For some applications a token should not be valid forever (accounts can be deleted or blocked). One can associate e.g. a month+year to the token so it can be publicly visible for which period a token is associated.
An alternative solution would be to resort to more advanced functional encryption systems like wildcards IBE or Hidden Vector Encryption that would allow to decrypt past ciphertexts with a single token.

### Verifiability and security
In the context of our system there are different levels of verifiability.
The best property would be to guarantee that even if all nodes in the League of Identity network collude together, they cannot forge valid signatures under identities they do not control.
Note however that for encryption and privacy the security would always rely on threshold assumptions: a sufficiently large set of nodes can always break the privacy.

Having verifiability based on threshold assumptions is more general and offers more flexibility. Some providers can only offer online deniable verification for their access tokens or for particular features (e.g. linking the identity to a phone number).
Therefore, in this work we assume that the providers's access tokens are verified online by the LoI nodes and thus the verifiability is under a threshold assumption.

### Threshold security against providers
In the basic setting providers like Google must be trusted. It is possible to consider the following variant. Let us assume for simplicity that Bob has a Facebook account with email address $[e-mail]$.
Bob logs into both his Google and Facebook account to request the respective access tokens and sends both access tokens to the League of Identity nodes which grant to Bob a token for a joint $google+facebook$ identity. Abstractly, the provider can be seen as the interesction of both Google and Facebook.
In this way, the security of Bob can be broken only if Google and Facebook collude together.

### Incentives for nodes to join the system

We envision a way to incentivize to join the LoI coalition using Ethereum or any other blockchain that comes with a cryptocurrency.
A user Bob can encrypt under a node public's key a request for his identity by additionally providing his access token and all information needed as in an online authentication phase.
A node decrypts the request and can encrypt the answer (i.e., the token share) under e.g. the Bob's public key (given by his Ethereum account).
Bob decrypts the answer and can use the so obtained token share as in the standard authentication flow.
Bob will send some coins to the smart contract in the first token share request. If the node's answer is an an invalid token share Bob can signal it by publishing the decrypted invalid share and the smart contract can check that.
If no invalid token share is sent in e.g. 48 hours then the node can withdraw the coins left by Bob into the smart contract.

### Group encryption/signatures
In the natural way, a token can be also associated to a domain, for instance all the members of $@oldcrypto.com$ should be able to decrypt ciphertexts associated with this domain.
For signatures, one has different options.
If anonymity is not needed, the system can trivially check a signature under the Bob's identity $[e-mail]$ and additionally check domain membership.

Another option to additionally guarantee a weak anonymity property is to make the LoI nodes grant identities of the form $[e-mail]$, where $AccessToken$ is the provider's access token a user uses to authenticate to LoI.
The LoI nodes should just check that the access token is valid and was not previously used by the same user to which the access token refers to (so to guarantee that Bob can get only a single token for each time period). In this way each user can uniquely sign messages in an anonymous way under the assumption that the LoI nodes be trusted for privacy.
Note that this functionality shares some similarities but it is different from the notion of group signatures used in the crypto literature.
In the [anonymity](https://hackmd.io/noiVZo2dTJ6Wiejt2IJvMg?both#Anonymous-signatures) section we will provide full anonymity solutions for signatures.
Our IBE described next is anonymous by design as well.

## Our implementation
We are in a bilinear group $(G_1,G_2,G_T,e)$ of type 3 and we assume the groups to be of prime order $p$ with generators resp. $g_1,g_2,g_T=e(g_1,g_2)$.

We assume that the nodes perform a Distributed Key Generation (DKG) procedure to compute shares $MSK_i\in Z_p$ of the master secret key $MSK\in Z_p$ in a way that the master public key can be set to $MPK=g_2^{MSK}$ and a subset $S$ of $t$ shares allow to reconstruct $MSK=\sum_{i\in S} MSK_i\ mod\ p$.

We don't discuss any specific DKG protocol here since the previous properties can be achieved using several known DKG protocols, e.g., one can use the same DKG protocol used for the drand system.

We can additionally assume that when new nodes enter or leave the system, a new DKG procedure is run to re-share the same master secret key and master public key. This is not really necessary but simplifies the treatment. We will also skip details regarding the validity of tokens.

In our system the share computed by each node $i\in S$ in response to a valid access token for email [e-mail] is $Token^{i}_{Bob}=H([e-mail])^{MSK_i},$ where $H$ is an hash to point function that maps to $G_1$ and is indifferentiable from a random oracle.

From the $t$ values $Token^i_{Bob}$ for $i\in S$, Bob can reconstruct $Token_{Bob}=\prod_{i\in S} Token^i_{Bob}=H([e-mail])^{MSK}$.

This can be used for encryption and authentication/signatures as follows.
### Encryption
* (Anonymous) Encryption. Alice, on input a message $m$ to encrypt and email [e-mail] and master public key $MPK$ can choose random value $s\in Z_p$ and compute:
$A=g_2^s, B=m \oplus H_T(g_{id})$, where $g_{id}=e(H([e-mail]),MPK^s)$ and $H_T$ is a function that maps $G_T$ into bit strings of some length compatible with the message that is indifferentiable from a random oracle.
Decryption of a ciphertext $CT=(A,B)$ can be done computing the following: $e(Token_{Bob}, A)$ and, by construction of the token and by the bilinear property, the latter value equals $g_{id}$ so $m$ can be recovered as $H_T(g_{id}) \oplus B$.
The previous system is exactly the Boneh-Franklin's IBE and as such it is IND-CPA secure and can be boosted to IND-CCA security via the Fujisaki-Okamoto's transform.
Our IBE is anonymous, that is it hides both the message and the identity.
[Later](https://hackmd.io/noiVZo2dTJ6Wiejt2IJvMg?both#Anonymous-IBE-with-anonymous-ZK-proof-of-decryption) we will show how to tweak the previous IBE system so as to construct an anonymous deposit system that enables a sender Alice to encrypt a witness in favour of a receiver Bob by specifying Bob's identity. The witness is needed to perform a withdrawal of the deposit made by Alice. However, the witness alone is not sufficient as Alice knows it as well. Therefore, in order to claim the deposit Bob will need to send the witness along with an additional proof that is only computable by Bob and not by Alice. Moreover this proof is anonymous and zero-knowledge and does not leak the identity of Bob. Overall, only Bob will be able to withdraw the deposit without disclosing his identity.

### Authentication/Signatures
* Authentication/signatures. We first focus on the signature case.
The user has a token $Token_{Bob}$, the master public key $MPK=g_2^{MSK}$, chooses a random value $r\in Z_p$ and computes the following.
$C=MPK^r=g_2^{MSK\cdot r},E=g_1^r$, and $F=Token_{Bob}^r=H([e-mail])^{MSK\cdot r}$.
Moreover, the user computes a proof $\pi$ of knowledge of the exponent $r$ in $E$, that is a non-interactive Schnorr's proof except that in the proof the challenge is set to the hash of the concatenation of $E$ with the first message of the Schnorr's protocol and the message $m$ (and identity). This binds $m$ (and the identity) to the proof $\pi$.
The signature $\sigma$ of the message $m$ consists of tuple $(C,E,F,\pi)$.
The verifier needs to verify the following.
It first verifies that $e(E,MPK)=e(g_1,C)$. This convinces the verifier that $C=g_2^{MSK\cdot r}$ and $E=g_1^r$.
Then the verifier verifies that $e(H([e-mail]),C)=e(F,g_2)$. This convinces the verifier that $F=H([e-mail])^{MSK\cdot r}.$ For the latter verification $[e-mail]$ is a public input known to the verifier.
Then the verifier verifies that $\pi$ is a Schnorr proof computed including $m$ (and the identity) in the challenge as explained above. Since a valid Schnorr's proof for this statement can be computed only with knowledge of $r$, the verifier is convinced that the user knows a valid token $Token_{Bob}$ for the identity without disclosing the token and since only Bob can get the token from the nodes this is a proof that the signature was from Bob.
Authentication can be done using the Schnorr's protocol in an interactive way and without binding the challenge to any message.

#### Our IBS and hybrid threshold identity-based signature
The reason of our IBS construction (and not adopting other schemes in the literature) is that we envision a scheme which be distributed as ours is and at the same time may be also extended to support threshold signatures.
Indeed, our IBS is distributed by the design.
Moreover, the identity itself could be related to the public value $E=g_1^r$ such that $r$ is seen as a secret shared among $n$ parties in a threshold way. Then the Schnorr's signature relative to $E$ can be replaced by a threshold Schnorr's signature (e.g. FROST) computed among the parties. Our design allows that in a trasparent way.
As an example of an application, a group of people in the administration department of $oldcrypto.com$ can share the email address $[e-mail]$ but they do not want a single member of the department to be able to sign transactions on behalf of all the group. So, they can request a token for $[e-mail]||E$ where $E$ is a Schnorr's public key whose secret key is shared among the members of the department in a threshold way. The LoI grants that token by just checking the ownership of the email address, so virtually each member of the department who can control the email account can get a token for any suffix value $E$. The group will identify itself on the blockchain using the identity $id=[e-mail]||E$.
The token for $id$ itself cannot be used to sign a message $m$ without additionally computing a Schnorr's signature for $m$ with respect to the value $E$. The latter Schnorr's signature in turn can be only computed by a sufficient number of the members of the group collaborating together.

### Ethereum-friendliness
To verify a LoI signature on Ethereum we would need some tweaks to achieve a version that is efficiently verifiable "on-chain".
First of all, the bilinear group should be set to bn254 that is the only one for which currently Ethereum precompiles are available.
An issue is that there are no precompiles for any hash to point function and their implementations in EVM can be GAS consuming.
A solution is to just use hash and pray point functions as we did in our [implementation](https://hackmd.io/noiVZo2dTJ6Wiejt2IJvMg?both#PoC-implementation).
This issue will be neglected in the near future when Ethereum will include precompiles for bls12-381 which are going to include hash to point functions as well.

### Anonymous signatures

Suppose that on-chain one wants to verify a signature for an identity of the form $[e-mail]$ in a way that convinces the verifier that the domain is $oldcrypto.com$ but without revealing the string Bob to the verifier.
Using general-purpose SNARK proofs this problem can be solved and the hash of the token can be used as nullifier for voting and similar purposes. Unfortunately, the circuit for this SNARK needs to compute expensive pairing operations.

#### Anonymity with unlinkability: a basic approach
There are applications in which nullifiers are not necessary. For instance, users would like to send transactions to a blockchain just disclosing their domain name while hiding their username.
Furthermore, *unlinkability* can be a desiderata: the user should be able to create new accounts in the blockchain in a way that such accounts can be linked only to the group but not to his full identity.

We can trivially achieve this as follows (later we show other better approaches).
The user Bob can request to a first subset of the nodes shares that allow to reconstruct the token $Token_{Bob||r_1}=H([e-mail]||r_1)^{msk}$ for the identity $[e-mail]||r_1$ and similarly requests to a second subset the shares corresponding to a token for a different randomness $r_2$. This can be extended to any number of subsets $l$ but for simplicity we restrict our explanation to $l=2$.

Then Bob can compute $T= H([e-mail]||r_1)\cdot H([e-mail]||r_2)$ and the signature can be changed to be identical to before except for the following:
The equation $e(H([e-mail]),C)=e(F,g_2)$ is replaced with $e(T,C)=e(F,g_2)$ and in addition the user proves, using a NIZKPoK/zk-SNARK, that $T$ has the right form with respect to the public input $oldcrypto.com$ without revealing any other information (in particular hiding the substring $bob$ and the random values) and the corresponding verifier verifies such proof.
Observe that, until two nodes (generally $l$) from different subsets do not collude together, no node can infer information about $T$ and hence about the identity of Bob.

The value $T$ in this case can serve as account identifier for Bob, that is Bob can show that it is member of the group $oldcrypto.com$ using the NIZKPoK/zk-SNARK proof of well-formdness for $T$ and after that he can sign transactions with respect to $T$ without the need of recomputing or presenting any such proof again, and so saving the corresponding verification computation for the smart contract.
The value $T$ must be also included as pre-image of the Fiat-Shamir's challenge of the Schnorr's signature, indeed replacing the identity.

Finally, observe that the user $Bob$ does not need to remember the random values $r_1, r_2, ...$. Indeed Bob can get a standard token for his identity (the one which does not involve randomness) and use it as seed for a PRF to compute all such random values.
#### Anonymity with unlinkability: a combinatorial approach
We can boost the anonymity to information theoretical one can apply the following trick.

The user Bob chooses a set $S$ of random values $r_1,\ldots, r_m$ for e.g. $m=2^{20}$ and requests from each node (precisely, a subset of nodes of size equal to the threshold of the network) all the token shares that allow to reconstruct the set $S_{Tok}$ consisting of the values $Tok_{Bob||r_i}$ for the identities $[e-mail]||r_i, i=1,\ldots,m$. (Precisely, each node can get from Bob a seed $r$ from which all values $r_i$'s can be derived.)
Then the user can choose e.g. $k=13$ random indices $i_1,\ldots, i_{13}\in [m]$ and compute the value $T=\prod_{j\in[13]} Tok_{Bob||r_{i_j}}$.
In this way, the trivial attack for any given node to test whether a value $T$ is for Bob is to brute force over $m^{13}=2^{260}$ possible subsets of cardinality $13$ in the set of the $[m]$ tokens. It can be shown that for this choice of the parameters the value $T$ hides the set $S$.
The user will register on-chain the value $T$ by providing a NIZKPoK/zk-SNARK proof $\pi$ of the fact that $T$ is well-formed with respect to the domain $oldcrypto.com$.
The corresponding circuit for the proof $\pi$ does only compute $k$ hash to point applications (which can be reduced to Poseidon/Poseidon2 computations) and $k-1$ non-native point additions.
To claim information-theoretical anonymity, the proof $\pi$ should be for a NIZKPoK/zk-SNARK with statistical ZK.
The total communication from all nodes to Bob is about $t*2^{20}*48$ bytes $=t*48.8$ Mbytes, where $t$ is the threshold of the system (the number of nodes needed to reconstruct a token from a set of $t$ token shares). This may be acceptable in view of the fact that the value $T$ is registered into the smart contract only once for all the time life of the $T$'s account, and thus the corresponding proof and verification as well.

#### Anonymity with unlinkability: a blind signature approach
We can achieve anonymity in a simple way by using a blind signature approach.
The user Bob chooses two random values $r,s$, set $T=H([e-mail]||r)$, and sends $A=T^s$ to the nodes with a NIZKPoK/zk-SNARK proof $\pi$ that $A$ equals $T^s$ and the pre-image of $T$ is $[e-mail]$ concatenated with a secret value $r$ that is provided as secret witness in the proof.
After the node $i$ verifies the proof, node $i$ can grant the randomised token share $T^{s\cdot MSK_i}$. The user can de-randomise it and get the token share for $T$ and from all of the token shares can reconstruct the token $T^{MSK}$ for $T$.
The user will register in the blockchain that he is allowed to participate as member of $oldcrypto.com$ by providing a NIZKPoK/zk-SNARK proof $\pi_T$ that $T$ is well-formed with respect to such domain and can then use $T$ in any IBS signature with respect to identity $T$ without requiring the verification algorithm to check the pre-image of $T$ or any proof for $T$. The proof $\pi_T$ is very simple since it essentially accounts to a proof of pre-image and does not require non-native point multiplications as it is instead the case for the proof $\pi$ sent from the user to the nodes in the authentication phase.

#### Trade-offs among the different approaches to anonymity with unlinkability

The first trivial approach requires the threshold $t$ to be small compared to the total number of nodes so as to be able to pick up many subsets of size $t$ which do not intersect together.

The combinatorial and blind signature approaches have different trade-offs.
The blind signature approach requires less communication with the nodes.
The combinatorial approach offers *re-usability*: the set $S_{Tok}$ can be re-used to compute different values $T, T', T'', ...$ corresponding to different random subsets of values in $S_{Tok}$. Instead, in the blind signature approach, each time the user wants to create an unlinkable anonymou account $T$ the user needs to perform a new interaction with the nodes.
The latter requires circuits that compute a single non-native point multiplication whereas the former requires circuits that compute $k$ non-native point additions, where $k$ is the repetition parameter.

#### Hybrid anonymity with nullifiers for voting
The previous approaches to anonymity with linkability can be boosted to implement a form of *hybrid anonymity* with nullifiers that prevent double voting while hiding the identity only to third parties outside the group.
That is the group of $oldcrypto.com$ would like to run an election in a way that its members can vote only once and each ballot should hide the identity of the member to third parties (but not to members of the group).
To achieve that the group can publish a voting proposal along with a commitment to a random value $r$ known by all members of the group. The value $r$ can for instance be encrypted with our IBE so that only members of the group can retrieve it. Then we can use the approach of e.g. blinded signature by additionally forcing the signer to prove that the randomness used in the signature corresponds to the value $r$ committed to in the proposal. So each member can vote but only once.

#### Anonymity with linkability via the blind signature approach

The previous blind signature approach to achieve anonymity can be tweaked to replace unlinkability with linkability, thus enabling e-voting applications.
We need to assume the LoI threshold $t$ to be larger than $2/3$ of the nodes.
Each node $i$ chooses some randomness value $r_i$ for each user (the node will use different randomness for different users computed e.g. with a random oracle) and communicates this value only to the corresponding user at authentication time.
Recall that in the aforementioned protocol the user Bob set $T=H([e-mail]||r)$, where $r$ wa chosen randomly by himself.
Bob now replaces $r$ with a list of values $r_{i_1}, ..., r_{i_t}$ and when Bob authenticates to node $i$ the proof is changed so that Bob proves that the $i$-th value in the list is equal to $r_i$.
For the linkability, Bob should be unable to perform this protocol with two different subsets of nodes in the same voting period.
Therefore, we require the Bob's requests to be recorded on a blockchain, and the honest nodes will refuse to answer to Bob if he already got a token from a different subset of $t$ nodes in the same period.
An issue here is that if Bob gets the shares to construct the token and by mistake Bob deletes them, he needs to re-perform the protocol with the same subset of nodes and here we lose the advantages of threshold cryptography: if only one node in that subset is unavailable Bob will be unable to get his token. The issue can be bypassed as follows.
The shares that allow Bob to reconstruct his anonymized (and linkable) token for the given time period must be IBE-encrypted under a temporary (and non-anonymized) key and published on the chain so that Bob can at any time reconstruct the anonymized token without the need of recontacting any node.
## Anonymous identity-based payment system (AnonIBP)
Recently, some financial apps enable payments via phone numbers and other real world identities.
Similarly, we propose what we term an *Anonymous Identity-Based Payment* (AnonIBP) system.
In AnonIBP, Alice can perform a bank transfer in favour of Bob by just specifying a phone number of Bob $phone_{Bob}$.
Our system allows to port this functionality to Ethereum and other blockchains very efficiently.
If Alice wants to send $n$ coins to Bob, she can do the following.
Use our [identity-based encryption system](#Encryption) to compute a ciphertext $CT$ encrypting a random nonce $x$ for the identity $id=phone_{Bob}$, compute $y=Hash(x)$ and send to a smart contract $n$ coins along with the pair $(CT, y)$.
Bob can get from the LoI nodes the token relative to his phone number $phone_{Bob}$ and decrypt $CT$ to get $x$ and send to the smart contract $x$. The smart contract verifies that $Hash(x)=y$ and if the check is successful it transfers the $n$ coins to Bob (that is, the coins are sent to the Eth account that invoked the smart contract).
Notice that our IBE system is anonymous so the ciphertext also hides the identity.
We can also avoid to store the ciphertext on-chain: you can use for example a url shortner that compresses a fake link encoding the ciphertext to a short string $s$, store $s$ on-chain and then Bob use $s$ to recover the ciphertext from the url shortner service.
The GAS cost for deposits and withdrawals would be very minimal.

Note that this on-chain payment system can be seen as a variant of the [Bank3 for Wallets](https://github.com/vincenzoiovino/bank3) system and as, stressed therein, it is *not* a coin mixer.

### Fully-secure AnonIBP via ZK proofs of correct decryption
An issue with the system, as described before, is that the sender can always withdraw on behalf of the receiver at any time. This is not a problem only in the handshake case, that is when sender and receiver can communicate at deposit time: in that case the receiver Bob can request the sender Alice to deposit a ciphertext computed by him.
The issue can be bypassed as follows.
#### EVM-friendly approach
The sender Alice (who wants to deposits crypto assets in favour of the receiver Bob) can choose a random value $r\in Z_p$, compute an IBE ciphertext $CT$ for the Bob's identity $id$ and message $r$, compute $D=H(id)^r$, and deposits on-chain the values $CT$ and $D$.
Bob can verify that a payment is withdrawable by him performing the following check: use his own token for the identity $id$ to decrypt $CT$ and get $r$ and check that $D=H(id)^r$. The check is carried out off-chain in e.g. Bob's browser. The property we want to ensure is that if this check passes then Bob should be convinced that the payment is withdrawable by him and only by him.

In order to withdraw, Bob chooses a random value $s\in Z_p$, compute $E=D^s$, a non-interactive Schnorr's proof of knowledge $\pi$ of dlog of $E$ in base $D$ (i.e., knowledge of $s$), the re-randomized token $Token_{Bob}'=Token_{Bob}^{r\cdot s}=H(id)^{msk\cdot r\cdot s}$ and sends to the smart contract the values $E,\pi,Token_{Bob}'$. (Note that Bob knows $r$ since Bob can decrypt the IBE ciphertext $CT$ as above.)
The smart contract verifies $\pi$ and checks that $e(Token_{Bob}',g_2)=e(E,MPK)$.
As before, Bob needs to include the withdrawal address as part of the FS challenge of the proof $\pi$. The idea is that the security property we wish is satisfied due to the fact that if these checks pass then $Tok_{Bob}'$ is a correct re-randomized token, where the re-randomization is done with the values $r,s$ resp. corresponding to $CT$ and $\pi$ and thus Bob knows a valid token for identity $id$ and this is enough to conclude that the smart contract was invoked by the legitimate Bob.

#### Withdrawals in favor of non-crypto users
We supposed for simplicity that the withdrawal will be in favor of an Eth address.
A natural extension is to enable withdrawal in favor of other non-crypto users (that is, Gmail, Facebook, phone numbers, etc.).
Indeed, a user Bob will be need to withdraw in favor of an Eth address only when he will need to swap the token/coins or exchange for fiat.

Of course, this withdrawal in favor of non-crypto users consumes GAS. The GAS cost could be paid by a service that retains a fee for that so that the users will be able to make this withdrawal without having crypto and even without having a Wallet at all.

#### Unconditional withdrawal security
One issue with the system as described now is that a sufficiently large coalition of malicious nodes can steal users' funds.
We now propose a variant in which a malicious coalition can break privacy but not steal funds.
Instead of having a deposit in the form of $(CT, H(id)^r)$, where $CT$ is a ciphertext under the receiver's identity $id$ that encrypts the random value $r$ and $H$ is a hash to point function, we can have the following.
The deposit is changed to $(CT, y=Hash(id||r))$, where $CT$ is as before and $Hash$ is a ZK-friendly hash function. Then the withdrawal proof is changed so that the receiver Bob proves the following statement: I know a valid JWT credential $CD$, a randomness value $r$ and identity $id$ such that $CD$ is e.g. a valid Gmail credential for email $id$ AND $id||r$ is a valid preimage of $y$. Also, we skip the detail that the proof should be tied to some withdrawal address, this is easily done.
The first part of the AND is what SUI Network did for the ZKLogin project, so the complexity here would increase of just a simple proof of preimage.
Observe that here the smart contract needs the Google's PK as public parameter exactly as done for the ZKLogin project.

#### Batch withdrawals
The system can be generalized so that Bob can withdraw $n$ deposits with a much lower cost than $n$ independent withdrawals.
#### Privacy against timing attacks
A privacy attack can be done by an adversary that can control both a single threshold node and the miners who see the data retrieved by Bob.
For instance if Bob requests a token for his identity and soon after retrieves a deposit for a certain identifier, the adversary can infer that that deposit was in favor of Bob. There are standard countermeasures against this issue.
Stronger privacy can be added as follows.

Bob could request to the nodes a token for the value $H([e-mail])^r$, for some randomness $r$, by sending a SNARK proof that this value is correct with respect to some JWT credential obtained by e.g. Google.
In this case the nodes are able to verify Bob's credential in ZK and can grant the randomized token shares by means of which Bob can reconstruct the value $H([e-mail])^{msk\cdot r}$ and remove the blind factor to get the token $H([e-mail])^{msk}$. In this way the nodes will not be able to trace the activities of Bob on-chain.

Notice however that the adversary, colluding with Google, can still break the privacy of Bob. This is unavoidable.
The natural countermeasure for Bob is to wait for sometime before retrieving blockchain data after having obtained the token and/or to retrieve as more as possible deposits from the blockchain.

#### Time-limited security
If the Bob's token is compromised then any future deposit in favor of Bob is at risk as well.
One can consider token validity so to bind deposits to certain time slots, e.g. months. This would make the system much slower as the user should retrieve one token for each time slot and try decrypting each deposit one by one.
One possibility is to have the posit consisting of two ciphertexts. The first ciphertext is encrypted under the Bob's identity $[e-mail]$ and encrypts the time slot $T$ (e.g. the current month) and serves to confirm that the deposit is for Bob and is related to the given time slot. The second ciphertext is the standard deposit ciphertext as before expect that it is encrypted under the identity $[e-mail]||T$. In this case if the token for $[e-mail]$ is compromised the attacker can only break the Bob's privacy but not withdraw on his behalf. Moreover each token $[e-mail]||T$ allows only to withdraw deposits for that particular time slot and thus an hacker taking temporary control of Bob's device (e.g. reading his memory) cannot make damage in the future.

Another solution would be to resort to generalization of AnonIBE. For instance, one could consider a system where a ciphertext is associated with identity $id||T$ and tokens are associated to $id||T'$ in a way that decryption is only possible if $T'\ge T$. Such efficient cryptosystems exist (e.g. Hidden Vector Encryption) and could be used if combined with efficient anonymous proofs of decryption tailored for them.

## PoC implementation
You can find [here](https://github.com/aragonzkresearch/leagueofidentity/tree/master) a PoC implementation of the system described in this note.