M. Abdalla, P. Fouque, V. Lyubashevsky, and M. Tibouchi, Tightly-secure signatures from lossy identification schemes, Eurocrypt '12, pp.572-590, 2012.
URL : https://hal.archives-ouvertes.fr/hal-01094318

M. Abe, G. Fuchsbauer, J. Groth, K. Haralambiev, and M. Ohkubo, Structure-preserving signatures and commitments to group elements, Crypto '10, pp.209-236, 2010.

M. Abe, K. Haralambiev, and M. Ohkubo, Signing on elements in bilinear groups for modular protocol design, Cryptology ePrint Archive, 2010.

M. Abe, B. David, M. Kohlweiss, R. Nishimaki, and M. Ohkubo, Tagged One-Time Signatures: Tight Security and Optimal Tag Size, PKC '13, pp.312-331, 2013.
DOI : 10.1007/978-3-642-36362-7_20

S. Arita and K. Tsurudome, Construction of Threshold Public-Key Encryptions through Tag-Based Encryptions, ACNS '09, pp.186-200, 2009.
DOI : 10.1007/978-3-642-01957-9_12

C. Bader, D. Hofheinz, T. Jager, E. Kiltz, and Y. Li, Tightly-Secure Authenticated Key Exchange, TCC 2015, 2015.
DOI : 10.1007/978-3-662-46494-6_26

M. Bellare, A. Boldyreva, and S. Micali, Public-Key Encryption in a Multi-user Setting: Security Proofs and Improvements, Eurocrypt '00, pp.259-274, 2000.
DOI : 10.1007/3-540-45539-6_18

M. Bellare, A. Boldyreva, K. Kurosawa, and J. Staddon, Multi-recipient encryption schemes: How to save on bandwidth and computation without sacrificing security, In IEEE Trans. on Information Theory, issue.11, pp.53-3927, 2007.

M. Bellare and P. Rogaway, Random oracles are practical, Proceedings of the 1st ACM conference on Computer and communications security , CCS '93, pp.62-73, 1993.
DOI : 10.1145/168588.168596

M. Bellare and P. Rogaway, The Exact Security of Digital Signatures-How to Sign with RSA and Rabin, Eurocrypt '96, pp.399-416, 1996.
DOI : 10.1007/3-540-68339-9_34

J. Black, P. Rogaway, and T. Shrimpton, Encryption-Scheme Security in the Presence of Key-Dependent Messages, Selected Areas in Cryptography (SAC'02), pp.62-75, 2002.
DOI : 10.1007/3-540-36492-7_6

O. Blazy, C. Chevalier, D. Pointcheval, and D. Vergnaud, Analysis and Improvement of Lindell???s UC-Secure Commitment Schemes, ACNS '13, pp.70-87, 2014.
DOI : 10.1007/978-3-642-38980-1_34

O. Blazy, E. Kiltz, and J. Pan, (Hierarchical) Identity-Based Encryption from Affine Message Authentication, Crypto '14, pp.70-87, 2014.
DOI : 10.1007/978-3-662-44371-2_23

URL : https://hal.archives-ouvertes.fr/hal-01239920

M. Blum, P. Feldman, and S. Micali, Non-interactive zero-knowledge and its applications, Proceedings of the twentieth annual ACM symposium on Theory of computing , STOC '88, pp.103-112, 1988.
DOI : 10.1145/62212.62222

D. Boneh, X. Boyen, and H. Shacham, Short Group Signatures, Crypto '04, pp.41-55, 2004.
DOI : 10.1007/978-3-540-28628-8_3

D. Boneh, X. Boyen, and S. Halevi, Chosen-Ciphertext Secure Threshold Public-Key Encryptino Without Random Oracles, CT-RSA '06, pp.226-243, 2006.

D. Boneh and M. Franklin, Identity-Based Encryption from the Weil Pairing, Earlier version in Crypto '01, pp.586-615, 2003.
DOI : 10.1137/S0097539701398521

D. Boneh, S. Halevi, M. Hamburg, and R. Ostrovsky, Circular-Secure Encryption from Decision Diffie-Hellman, Crypto '08, pp.108-125, 2008.
DOI : 10.1007/978-3-540-85174-5_7

J. Camenisch, N. Chandran, and V. Shoup, A Public Key Encryption Scheme Secure against Key Dependent Chosen Plaintext and Adaptive Chosen Ciphertext Attacks, Eurocrypt '09, pp.351-368, 2009.
DOI : 10.1007/BFb0054113

R. Canetti and M. Fischlin, Universally Composable Commitments, Crypto '01, pp.19-40, 2001.
DOI : 10.1007/3-540-44647-8_2

J. Cathalo, B. Libert, and M. Yung, Group Encryption: Non-interactive Realization in the Standard Model, Asiacrypt '09, pp.179-196, 2009.
DOI : 10.1007/978-3-642-10366-7_11

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

B. Chevallier-mames, An Efficient CDH-Based Signature Scheme with a Tight Security Reduction, Crypto '05, pp.511-526, 2005.
DOI : 10.1007/11535218_31

J. Coron, On the Exact Security of Full Domain Hash, Crypto '00, pp.229-235, 2000.
DOI : 10.1007/3-540-44598-6_14

J. Coron, Optimal Security Proofs for PSS and Other Signature Schemes, Eurocrypt '02, pp.229-235, 2002.
DOI : 10.1007/3-540-46035-7_18

R. Canetti, Universally composable security: a new paradigm for cryptographic protocols, Proceedings 2001 IEEE International Conference on Cluster Computing, pp.136-145, 2001.
DOI : 10.1109/SFCS.2001.959888

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

A. Fiat and A. Shamir, How To Prove Yourself: Practical Solutions to Identification and Signature Problems, Crypto '86, pp.186-194, 1986.
DOI : 10.1007/3-540-47721-7_12

M. Fischlin, B. Libert, and M. Manulis, Non-interactive and Re-usable Universally Composable String Commitments with Adaptive Security, Asiacrypt '11, pp.468-485, 2014.
DOI : 10.1007/978-3-642-25385-0_25

P. Fouque and D. , Threshold Cryptosystems Secure against Chosen-Ciphertext Attacks, Asiacrypt '01, pp.351-368, 2001.
DOI : 10.1007/3-540-45682-1_21

URL : https://hal.archives-ouvertes.fr/inria-00565272

S. Galbraith, J. Malone-lee, and N. Smart, Public key signatures in the multi-user setting, Information Processing Letters, pp.263-266, 2002.
DOI : 10.1016/S0020-0190(01)00338-6

S. Galbraith, K. Paterson, and N. Smart, Pairings for cryptographers, Discrete Applied Mathematics, pp.3113-3121, 2008.
DOI : 10.1016/j.dam.2007.12.010

J. Garay, R. Ishai, H. Kumaresan, and . Wee, On the Complexity of UC Commitments, Eurocrypt '14, pp.677-694, 2014.
DOI : 10.1007/978-3-642-55220-5_37

URL : https://hal.archives-ouvertes.fr/hal-01094702

J. Groth, Simulation-Sound NIZK Proofs for a Practical Language and Constant Size Group Signatures, Asiacrypt '06, pp.444-459, 2006.
DOI : 10.1007/11935230_29

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

D. Hofheinz, All-But-Many Lossy Trapdoor Functions, Eurocrypt '12, pp.209-227, 2012.
DOI : 10.1007/978-3-642-29011-4_14

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

D. Hofheinz, T. Jager, and E. Knapp, Waters Signatures with Optimal Security Reduction, PKC '12, pp.66-83, 2012.
DOI : 10.1007/978-3-642-30057-8_5

?. {1, 4,49] enabling tight KDM-CCA2 security would require to prove ?() linear pairing product equations, each of which takes 3 group elements. For example, the simulation-extractable proof of [4] ? which allows eliminating (D 0 , D 1 , D 2 ) from the ciphertext ? requires Groth-Sahai commitments to (M, W 1 , W 2 ) = (M, g ? 1 , g ? 2 ) and NIWI proofs for the equations e(C 0 /M, g) = e(g 0 , W 1 ) · e(h 0 , W 1 ) and e(C i , g) = e(g i , W 1 ) · e(h i , W 2 ) for each , }, which demands 12 log p + 69 group elements in an instantiation with the signature scheme of [49]. This incurs a total of 16 log p + 70 group elements per ciphertext. Our ciphertexts only take 4 log p + 45 group elements, which is nearly 75% shorter than in the best previous tightly secure KDM-CCA2 system for any realistic security parameter. Our scheme is ? up to an additive overhead of 42 group elements ? essentially as efficient as its KDM-CPA variant. Although it remains significantly less efficient than Hofheinz's KDM-CCA2-secure construction [39], it turns out to be the most efficient scheme with (nearly) tight KDM-CCA2 security to date. The security in the sense of Definition 5 is proved using standard arguments and we omit the details of the proof, which proceeds exactly like the one of, the above system Appendix A.1]. It naturally reduces the KDM-CCA2 security of the system to the KDM-CPA security of the BHHO construction the multi-user setting, 2019.