## Appendix A.1.2. Security Proof  
**Lemma A1** (Group Mutual Authentication Security). : _If the underlying symmetric encryption scheme used in our authentication scheme is secure against adaptive chosen ciphertext attacks (IND-CCA2) and the SampleD function used in our scheme achieves one-way-ness, then our authentication scheme can achieve secure mutual authentication between the manager and the users._  
Proof. : **Part I** (The Authenticity of the Manager):  
Assume that an attacker interacts with a simulator via the game defined in Definition A1. The simulator simulates the **Setup Phase** and **Training Phase** like those in the proposed scheme. Then, the simulator simulates the **Challenge Phase** as follows. First, the attacker sends \(t_{i}\) to the simulator. Then, the simulator computes \(d_{B_{i}}=SampleD\left(w_{B_{i}},s,0,t_{i}\right)\) and chooses two numbers \(r_{i}^{0},r_{i}^{1}\). Next, the simulator sets \(m_{0}=\left(d_{B_{i}},\ r_{i}^{0}\right)\) and \(m_{1}=\left(d_{B_{i}},\ r_{i}^{1}\right)\), and sends \(m_{0},\ m_{1}\) to the IND-CCA2 game for symmetric encryption as the challenge messages. After receiving the challenge ciphertext \(c^{*}\) from the IND-CCA2 game, the simulator sends \(c^{*}\) to the attacker. Then, the simulator receives \(b\) from the attacker, and the simulator sends \(b\) to the decryption oracle of the IND-CCA2 game. In the case that \(Q^{\prime}>1\) (Figure A3), the simulator parses the returned plaintext as \(\left(sk^{\prime},\ R_{i}^{\prime}\right)\). Then the simulator outputs \(0\) if \(sk^{\prime}\oplus R_{i}^{\prime}=r_{i}^{0}\), and outputs \(1\) if \(sk^{\prime}\oplus R_{i}^{\prime}=r_{i}^{1}\). In the case that \(Q^{\prime}=1\) (Figure A4), the simulator parses the returned plaintext as \(\left(r^{\prime},\ h\right)\). Then the simulator outputs \(0\) if \(h=H\big{(}r_{i}^{0}\big{)}\), and outputs \(1\) if \(h=H\big{(}r_{i}^{1}\big{)}\). If the attacker is able to pass the authentication with non-negligible advantage, then the plaintext in \(b\) should be correct. Therefore, the simulator is able to make a correct guess based on the decryption result of \(b\), and win the IND-CCA2 game with the same advantage as the attacker. **Part II** (The Authenticity of the User, Figure A5):  
Assume that an attacker interacts with a simulator via the game defined in Definition A1, and the attacker sends a user set \(U\subseteq\{1,\ \ldots,Q\}(|U|=Q^{\prime})\) to the simulator. To simulate the **Setup Phase**, the simulator chooses \(B_{i}\) such that \(A^{\prime}=\{A\parallel\sum_{i=1}^{Q^{\prime}}(B_{i}-B_{i^{*}})\}\), where \(i\in U\) and \(B_{i^{*}}\) is the target user that the attacker wants to impersonate. Other system parameters are set the same as in the proposed scheme. The simulator then simulates the **Training Phase** as in the proposed scheme. In the **Challenge Phase**, the simulator first outputs \(t_{i}\) to the attackers, and obtains \(a_{i}\) from the attacker. Then, the simulator performs as in the proposed scheme to obtain \(d_{B_{i}}\), and check whether \(F_{B_{i}}d_{B_{i}}=t_{i}\ mod\ q\). If the formula holds--which means that the attacker passes the authentication and thus wins the game--then the attacker can be viewed as an inverter for the function SampleD. Therefore, we are able to break the one-way-ness of SampleD with the same advantage as the attacker. \(\Box\)\(U\subseteq\{1,...,Q\},|U|=Q^{\prime},i^{*}\in U\)  
The simulator:  
1. Set \(B_{i\in U}\) such that \(A^{\prime}=\{A\parallel\Sigma_{i=1}^{Q^{\prime}}B_{i}-B_{i^{*}}\}=F_{B_{i}}\)  
2. Publish the parameters  
**Lemma A2** (Session Key Security). : _If the symmetric encryption used in our authentication scheme is secure against adaptive chosen ciphertext attacks (IND-CCA2), then our scheme is a secure key exchange scheme._  
Proof. : Assume that an attacker interacts with a simulator via the game defined in Definition A2. The simulator simulates the **Setup Phase** and **Training Phase** as in the proposed scheme. Then, the simulator simulates the **Challenge Phase** as follows.