J. Alwen, Y. Dodis, M. Naor, G. Segev, S. Walfish et al., Public-Key Encryption in the Bounded-Retrieval Model, LNCS, vol.6110, pp.113-134, 2010.
DOI : 10.1007/978-3-642-13190-5_6

M. Bellare and S. Goldwasser, New paradigms for digital signatures and message authentication based on non-interative zero knowledge proofs, CRYPTO'89, pp.194-211, 1989.

M. Bellare and T. Ristenpart, Simulation without the Artificial Abort: Simplified Proof and Improved Concrete Security for Waters??? IBE Scheme, LNCS, vol.14, issue.4, pp.407-424, 2009.
DOI : 10.1007/11426639_7

O. Blazy, S. Kakvi, E. Kiltz, and J. Pan, Tightly-secure signatures from chameleon hash functions. unpublished, p.2013

D. Boneh and M. K. Franklin, Identity-based encryption from the Weil pairing, LNCS, vol.2139, pp.213-229, 2001.

J. Chen, H. W. Lim, S. Ling, H. Wang, and H. Wee, Shorter IBE and Signatures via Asymmetric Pairings, PAIRING 2012, pp.122-140, 2012.
DOI : 10.1007/978-3-642-36334-4_8

J. Chen and H. Wee, Fully, (Almost) Tightly Secure IBE and Dual System Groups, CRYPTO 2013, Part II, pp.435-460, 2013.
DOI : 10.1007/978-3-642-40084-1_25

C. Cocks, An Identity Based Encryption Scheme Based on Quadratic Residues, 8th IMA International Conference on Cryptography and Coding, pp.360-363
DOI : 10.1007/3-540-45325-3_32

R. Cramer and V. Shoup, A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack, LNCS, vol.1462, issue.98, pp.13-25
DOI : 10.1007/BFb0055717

R. Cramer and V. Shoup, Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption, LNCS, vol.2332, pp.45-64, 2002.
DOI : 10.1007/3-540-46035-7_4
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.6205

Y. Dodis, E. Kiltz, K. Pietrzak, and D. Wichs, Message Authentication, Revisited, EUROCRYPT 2012, pp.355-374, 2012.
DOI : 10.1007/978-3-642-29011-4_22

A. Escala, G. Herold, E. Kiltz, C. Ràfols, and J. Villar, An algebraic framework for Diffie-Hellman assumptions, CRYPTO 2013, Part II, pp.129-147, 2013.

C. Gentry and A. Silverberg, Hierarchical ID-Based Cryptography, ASI- ACRYPT 2002, pp.548-566, 2002.
DOI : 10.1007/3-540-36178-2_34

J. Groth and A. Sahai, Efficient Non-interactive Proof Systems for Bilinear Groups, LNCS, vol.4965, pp.415-432, 2008.
DOI : 10.1007/978-3-540-78967-3_24

D. Hofheinz and T. Jager, Tightly secure signatures and public-key encryption, CRYPTO 2012, pp.590-607, 2012.

C. S. Jutla and A. Roy, Shorter Quasi-Adaptive NIZK Proofs for Linear Subspaces, ASIACRYPT 2013, Part I, pp.1-20, 2013.
DOI : 10.1007/s00145-016-9243-7

E. Kiltz and G. Neven, Identity-based signatures, 2009.

E. Kiltz, K. Pietrzak, M. Stam, and M. Yung, A New Randomness Extraction Paradigm for Hybrid Encryption, LNCS, vol.28, issue.4, pp.590-609, 2009.
DOI : 10.1007/BFb0054019

A. B. Lewko, Tools for Simulating Features of Composite Order Bilinear Groups in the Prime Order Setting, EUROCRYPT 2012, pp.318-335, 2012.
DOI : 10.1007/978-3-642-29011-4_20

A. B. Lewko and B. Waters, Why Proving HIBE Systems Secure Is Difficult, EUROCRYPT 2014, pp.58-76, 2014.
DOI : 10.1007/978-3-642-55220-5_4

M. Naor and O. Reingold, Number-theoretic constructions of efficient pseudo-random functions, 38th FOCS, pp.458-467, 1997.

M. Naor and O. Reingold, On the construction of pseudo-random permutations, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing , STOC '97, pp.189-199, 1997.
DOI : 10.1145/258533.258581

R. Sakai, K. Ohgishi, and M. Kasahara, Cryptosystems based on pairing, SCIS 2000, 2000.

A. Shamir, Identity-Based Cryptosystems and Signature Schemes, CRYPTO'84, pp.47-53, 1984.
DOI : 10.1007/3-540-39568-7_5

B. Waters, Dual System Encryption: Realizing Fully Secure IBE and HIBE under Simple Assumptions, LNCS, vol.5677, pp.619-636, 2009.
DOI : 10.1007/978-3-642-03356-8_36

B. R. Waters, Efficient Identity-Based Encryption Without Random Oracles, LNCS, vol.3494, pp.114-127, 2005.
DOI : 10.1007/11426639_7

H. Wee, Dual System Encryption via Predicate Encodings, LNCS, vol.2014, issue.8349, pp.616-637, 2014.
DOI : 10.1007/978-3-642-54242-8_26
URL : https://hal.archives-ouvertes.fr/hal-01094703

M. We-note-that-both, M. , and S. Secure, The security proof from Section 3 can be easily adapted to show both schemes are SPR-CMA secure. Here we just outline the ideas. For MAC NR [D k ], we first use the Q-fold D k -MDDH assumption to make the answers all Eval queries random; next, we store a list of (h 0 [·], h 1 [·]) values to make the output of Chal(m * ) random and consistent with Eval(m * ) One can also adapt the proof of MAC HPS

C. Lemma, 8 There exists an adversary B 1 with T(B 1 ) ? T(A) and Adv D k ,GGen (B 1 ) ? | Pr

C. Lemma, 10 There exists an adversary B 2 with T(B 2 ) ? T(A) and Adv spr-cma MAC (B 2 ) ? | Pr