# A Universal Privacy-Preserving Multi-Blockchain Aggregated Identity Scheme
## 3 System Design
### Management of the Authorized Addresses
#### 3.4.2 Construction of the Accumulator  
After mapping the address information to prime numbers, we add these prime numbers to an RSA accumulator and then store the obtained accumulator value in the smart contract. As the prime elements can be very large, using the construction of [PERSON] [32] may lead to overflow due to excessive exponents. Therefore, the RSA accumulator is constructed in the following way: Initialize the accumulator as \(g\), then add the mapped primes \(\mathrm{P}=\{\mathrm{p}_{1},\mathrm{p}_{2},\ldots,\mathrm{p}_{\mathrm{m}}\}\) to the accumulator to obtain a new accumulator value \(acc\), where \(n\) and \(g\) are the public keys generated by the user, as shown in Equation (1):  
\[acc=g^{s}\pmod{n},\ \ \ S=\prod_{i=1}^{m}p_{i}. \tag{1}\]  
For an element \(x\) in the set \(P\), a membership witness is generated, as shown in Equation (2):  
\[\pi=g^{s/x}\pmod{n}. \tag{2}\]  
The membership witness is then verified. If the equation holds, \(x\) must belong to the set \(P\), as shown in Equation (3):  
\[acc=\pi^{x}\pmod{n}. \tag{3}\]  
When the user wants to authorize a new address, they map it to a prime number \(x^{\prime}\) then update the accumulator value, as shown in Equation (4). The user invokes the contract to update the accumulator value. The witness of membership of other elements should be updated, as shown in Equation (5):  
\[acc^{\prime}=acc^{x^{\prime}}\pmod{n}, \tag{4}\]  
\[\pi^{\prime}=\pi^{x^{\prime}}\pmod{n}. \tag{5}\]  
When the user revokes the authorization of an address, the extended Euclidean algorithm is first used to find the inverse \(r\) of \(x\) with respect to \(\phi(n)\). Then, \(r\) is used to  
Figure 3: Mapping the address information to a prime number. update the accumulator value and the membership witnesses of other elements, as shown in Equations (6)-(8):  
\[r=x^{-1}\pmod{\phi(n)}, \tag{6}\]  
\[acc^{\prime}=acc^{\prime}\pmod{n}, \tag{7}\]  
\[\pi^{\prime}=\pi^{r}\pmod{n}. \tag{8}\]  
```
Miller-Rabin primality test Input:  bigNumber \(n\),\(k\) Output:  bool isPrime // Lines 1-4 are edge cases that return immediately. If \(n\) is 2 or 3, return true. If \(n\) is less than 2 or even, return false. 1: if (\(n==2\bigm{|}\bigm{|}n==3\)) 2: return true; 3: if (\(n\pmod{2}==0\bigm{|}\bigm{|}n<2\)) 4: return false; // Lines 5-9 compute \(d\) and \(s\), such that \(n-1=2^{s}*d\), where \(d\) is odd. This is done so that we can write \(n\)-1 as a power of 2 times an odd number. 5: \(s=0\), \(d=n-1\); 6: while (\(d\pmod{2}==0\)) {
7:\(d=d/2\); 8:\(++s\); 9:} //Line 10 initializes an array of base values to test. These are predefined values that have been shown to be effective in practice. 10: \(bases=[2,325,9375,28,178,450,775,9,780,504,17,955,265,022]\); //The following loop (lines 11-22) is the main body of the test. It checks if \(n\) is prime. The outer loop (// line 11) repeats \(k\) times, using a different base value each time. 11: WitnessLoop: do{ //Line 12 selects the base value to use for this iteration of the test. 12:\(a=bases[k-1]\); 13:\(//\) if \(n\) is prime, \(n\) must satisfy A or B // Lines 14-15 handle the case A. If this is true, skip to the next iteration of the outer loop. 14: if (\(a^{d}\pmod{n}==1\))//A 15: continue; // Lines 16-19 handle the case B. If this is true, skip to the next iteration of the outer loop. 16: for(\(j=0\) to \(s-1\)) do (\(//\) B 17: if (\(a^{2j}d\pmod{n}==1\)) 18: continue WitnessLoop; 19: } //If neither of the above cases is true, then \(n\) is composite and return false. 20: if(\(j==s\)) 21: return false; 22: while(\(k--\)); //If all \(k\) iterations of the outer loop without returning false, then \(n\) is probably prime and return true. 23: return true;
```  
**Algorithm 7**Deterministic variant of the Miller-Rabin primality test. ```  Miller-Rabin primality test Input:  bigNumber \(n\),\(k\) Output:  bool isPrime // Lines 1-4 are edge cases that return immediately. If \(n\) is 2 or 3, return true. If \(n\) is less than 2 or even, return false.