Show simple item record

dc.contributor.author
Couteau, Geoffroy
dc.contributor.author
Katsumata, Shuichi
dc.contributor.author
Ursu, Bogdan
dc.contributor.editor
Canteaut, Anne
dc.contributor.editor
Ishai, Yuval
dc.date.accessioned
2020-12-22T10:02:30Z
dc.date.available
2020-12-21T13:44:51Z
dc.date.available
2020-12-22T10:02:30Z
dc.date.issued
2020
dc.identifier.isbn
978-3-030-45726-6
en_US
dc.identifier.isbn
978-3-030-45727-3
en_US
dc.identifier.issn
0302-9743
dc.identifier.issn
1611-3349
dc.identifier.other
10.1007/978-3-030-45727-3_15
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/457823
dc.description.abstract
We provide new constructions of non-interactive zero-knowledge arguments (NIZKs) for NP from discrete-logarithm-style assumptions over cyclic groups, without relying on pairings. A previous construction from (Canetti et al., Eurocrypt’18) achieves such NIZKs under the assumption that no efficient adversary can break the key-dependent message (KDM) security of (additive) ElGamal with respect to all (even inefficient) functions over groups of size 2λ, with probability better than poly(λ)/2λ . This is an extremely strong, non-falsifiable assumption. In particular, even mild (polynomial) improvements over the current best known attacks on the discrete logarithm problem would already contradict this assumption. (Canetti et al. STOC’19) describe how to improve the assumption to rely only on KDM security with respect to all efficient functions, therefore obtaining an assumption that is (in spirit) falsifiable. Our first construction improves this state of affairs. We provide a construction of NIZKs for NP under the CDH assumption together with the assumption that no efficient adversary can break the key-dependent message one-wayness of ElGamal with respect to efficient functions over groups of size 2λ, with probability better than poly(λ)/2cλ (denoted 2−cλ-OW-KDM), for a constant c=3/4 . Unlike the previous assumption, our assumption leaves an exponential gap between the best known attack and the required security guarantee. We also analyse whether we could build NIZKs when CDH does not hold. As a second contribution, we construct an infinitely often NIZK argument system for NP (where soundness and zero-knowledge are only guaranteed to hold for infinitely many security parameters), under the 2−cλ-OW-KDM security of ElGamal with c=28/29+o(1), together with the existence of low-depth pseudorandom generators.
en_US
dc.language.iso
en
en_US
dc.publisher
Springer
en_US
dc.subject
Non-interactive zero-knowledge arguments
en_US
dc.subject
Pairing-free groups
en_US
dc.subject
KDM security
en_US
dc.title
Non-interactive Zero-Knowledge in Pairing-Free Groups from Weaker Assumptions
en_US
dc.type
Conference Paper
dc.date.published
2020-05-01
ethz.book.title
Advances in Cryptology – EUROCRYPT 2020
en_US
ethz.journal.title
Lecture Notes in Computer Science
ethz.journal.volume
12107
en_US
ethz.journal.abbreviated
LNCS
ethz.pages.start
442
en_US
ethz.pages.end
471
en_US
ethz.event
39th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt 2020) (virtual)
en_US
ethz.event.location
Zagreb, Croatia
en_US
ethz.event.date
May 10-14, 2020
en_US
ethz.grant
Preparing Cryptography for Modern Applications
en_US
ethz.publication.place
Cham
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::09693 - Hofheinz, Dennis / Hofheinz, Dennis
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::09693 - Hofheinz, Dennis / Hofheinz, Dennis
en_US
ethz.grant.agreementno
724307
ethz.grant.fundername
EC
ethz.grant.funderDoi
10.13039/501100000780
ethz.grant.program
H2020
ethz.date.deposited
2020-12-21T13:44:59Z
ethz.source
FORM
ethz.eth
yes
en_US
ethz.availability
Metadata only
en_US
ethz.rosetta.installDate
2020-12-22T10:02:40Z
ethz.rosetta.lastUpdated
2021-02-15T22:47:40Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Non-interactive%20Zero-Knowledge%20in%20Pairing-Free%20Groups%20from%20Weaker%20Assumptions&rft.jtitle=Lecture%20Notes%20in%20Computer%20Science&rft.date=2020&rft.volume=12107&rft.spage=442&rft.epage=471&rft.issn=0302-9743&1611-3349&rft.au=Couteau,%20Geoffroy&Katsumata,%20Shuichi&Ursu,%20Bogdan&rft.isbn=978-3-030-45726-6&978-3-030-45727-3&rft.genre=proceeding&rft_id=info:doi/10.1007/978-3-030-45727-3_15&rft.btitle=Advances%20in%20Cryptology%20%E2%80%93%20EUROCRYPT%202020
 Search print copy at ETH Library

Files in this item

FilesSizeFormatOpen in viewer

There are no files associated with this item.

Publication type

Show simple item record