Faonio, AntonioGonzález Vasco, María IsabelSoriente, ClaudioTruong, Hien Thi Thu2023-12-132023-12-132022-11Faonio, A., Gonzalez Vasco, M. I., Soriente, C. & Truong, H. T. T. (2022). Auditable Asymmetric Password Authenticated Public Key Establishment. In Beresford, A. R., Patra, A., Bellini, E. (eds), Cryptology and Network Security. CANS 2022. Lecture Notes in Computer Science, 13641 (122–142). Springer, Cham.978-3-031-20973-4https://hdl.handle.net/10016/39080Proceedings of: 21st International Conference on Cryptology and Network Security (CANS 2022), 13-16 November 2022, Abu Dhabi, UAE.Non-interactive zero-knowledge (NIZK) arguments allow a prover to convince a verifier about the truthfulness of an N P-statement by sending just one message, without disclosing any additional information. In several practical scenarios, the Fiat-Shamir transform is used to convert an efficient constant-round public-coin honest-verifier zero-knowledge proof system into an efficient NIZK argument system. This approach is provably secure in the random oracle model, crucially requires the programmability of the random oracle and extraction works through rewinds. The works of Lindell [TCC 2015] and Ciampi et al. [TCC 2016] proposed efficient NIZK arguments with non-programmable random oracles along with a programmable common reference string. In this work we show an efficient NIZK argument with straight-line simulation and extraction that relies on features that alone are insufficient to construct NIZK arguments (regardless of efficiency). More specifically we consider the notion of quasi-polynomial time simulation proposed by Pass in [EUROCRYPT 2003] and combine it with simulation and extraction with non-programmable random oracles thus obtaining a NIZK argument of knowledge where neither the zero-knowledge simulator, nor the argument of knowledge extractor needs to program the random oracle. Still, both the simulator and the extractor are straightline. Our construction uses as a building block a modification of the Fischlin’s transform [CRYPTO 2005] and combines it with the concept of dense puzzles introduced by Baldimtsi et al. [ASIACRYPT 2016]. We also argue that our NIZK argument system inherits the efficiency features of Fischlin’s transform, which represents the main advantage of Fischlin’s protocol over existing schemes.21eng© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG.Oblivious Pseudorandom FunctionsPassword AuthenticationPublic Key CryptographyServer-Aided Key Generationconference proceedingsInformáticaMatemáticasTelecomunicacioneshttps://doi.org/10.1007/978-3-031-20974-1_6open access122142Cryptology and Network Security: 21st International Conference, CANS 2022, Abu Dhabi, United Arab Emirates, November 13-16, 2022, Proceedings13641CC/0000034118