UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Cryptography in the multi-string model

Groth, J; Ostrovsky, R; (2007) Cryptography in the multi-string model. In: Menezes, A, (ed.) Advances in Cryptology - CRYPTO 2007. (pp. 323 - 341). Springer Berlin Heidelberg Green open access

[thumbnail of MultiStringModelFull.pdf] PDF

Download (278kB)


The common random string model introduced by Blum, Feldman and Micali permits the construction of cryptographic protocols that are provably impossible to realize in the standard model. We can think of this model as a trusted party generating a random string and giving it to all parties in the protocol. However, the introduction of such a third party should set alarm bells going off: Who is this trusted party? Why should we trust that the string is random? Even if the string is uniformly random, how do we know it does not leak private information to the trusted party? The very point of doing cryptography in the first place is to prevent us from trusting the wrong people with our secrets.In this paper, we propose the more realistic multi-string model. Instead of having one trusted authority, we have several authorities that generate random strings. We do not trust any single authority; we only assume a majority of them generate the random string honestly. This security model is reasonable, yet at the same time it is very easy to implement. We could for instance imagine random strings being provided on the Internet, and any set of parties that want to execute a protocol just need to agree on which authorities' strings they want to use.We demonstrate the use of the multi-string model in several fundamental cryptographic tasks. We define multi-string non-interactive zero-knowledge proofs and prove that they exist under general cryptographic assumptions. Our multi-string NIZK proofs have very strong security properties such as simulation-extractability and extraction zero-knowledge, which makes it possible to compose them with arbitrary other protocols and to reuse the random strings. We also build efficient simulation-sound multi-string NIZK proofs for circuit satisfiability based on groups with a bilinear map. The sizes of these proofs match the best constructions in the single common random string model.We suggest a universally composable commitment scheme in the multi-string model. It has been proven that UC commitment does not exist in the plain model without setup assumptions. Prior to this work, constructions were only known in the common reference string model and the registered public key model. One of the applications of the UC commitment scheme is a coin-flipping protocol in the multi-string model. Armed with the coin-flipping protocol, we can securely realize any multi-party computation protocol.

Type: Proceedings paper
Title: Cryptography in the multi-string model
Event: Free Preview Advances in Cryptology - CRYPTO 2007 27th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2007
Location: Santa Barbara, CA
Dates: 2007-08-19 - 2007-08-23
ISBN-13: 978-3-540-74142-8
Open access status: An open access version is available from UCL Discovery
DOI: 10.1007/978-3-540-74143-5_18
Publisher version: http://dx.doi.org/10.1007/978-3-540-74143-5_18
Language: English
Additional information: This is the author's accepted version of this published conference proceeding. The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-540-74143-5_18
Keywords: common random string model, multi-string model, non-interactive zero-knowledge, universally composable commitment, multi-party computation, noninteractive zero-knowledge, NP
UCL classification: UCL
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/13310
Downloads since deposit
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item