TY - GEN

T1 - On the existence of extractable one-way functions

AU - Bitansky, Nir

AU - Canetti, Ran

AU - Paneth, Omer

AU - Rosen, Alon

PY - 2014

Y1 - 2014

N2 - A function f is extractable if it is possible to algorithmically "extract," from any adversarial program that outputs a value y in the image of f; a preimage of y. When combined with hardness properties such as one-wayness or collision-resistance, extractability has proven to be a powerful tool. However, so far, extractability has not been explicitly shown. Instead, it has only been considered as a non-standard knowledge assumption on certain functions. We make two headways in the study of the existence of extractable one-way functions (EOWFs). On the negative side, we show that if there exist indistinguishability obfuscators for a certain class of circuits then there do not exist EOWFs where extraction works for any adversarial program with auxiliary-input of unbounded polynomial length. On the positive side, for adversarial programs with bounded auxiliaryinput (and unbounded polynomial running time), we give the first construction of EOWFs with an explicit extraction procedure, based on relatively standard assumptions (e.g., sub-exponential hardness of Learning with Errors). We then use these functions to construct the first 2-message zero-knowledge arguments and 3-message zeroknowledge arguments of knowledge, against the same class of adversarial verifiers, from essentially the same assumptions

AB - A function f is extractable if it is possible to algorithmically "extract," from any adversarial program that outputs a value y in the image of f; a preimage of y. When combined with hardness properties such as one-wayness or collision-resistance, extractability has proven to be a powerful tool. However, so far, extractability has not been explicitly shown. Instead, it has only been considered as a non-standard knowledge assumption on certain functions. We make two headways in the study of the existence of extractable one-way functions (EOWFs). On the negative side, we show that if there exist indistinguishability obfuscators for a certain class of circuits then there do not exist EOWFs where extraction works for any adversarial program with auxiliary-input of unbounded polynomial length. On the positive side, for adversarial programs with bounded auxiliaryinput (and unbounded polynomial running time), we give the first construction of EOWFs with an explicit extraction procedure, based on relatively standard assumptions (e.g., sub-exponential hardness of Learning with Errors). We then use these functions to construct the first 2-message zero-knowledge arguments and 3-message zeroknowledge arguments of knowledge, against the same class of adversarial verifiers, from essentially the same assumptions

UR - http://www.scopus.com/inward/record.url?scp=84904361123&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84904361123&partnerID=8YFLogxK

U2 - 10.1145/2591796.2591859

DO - 10.1145/2591796.2591859

M3 - Conference contribution

AN - SCOPUS:84904361123

SN - 9781450327107

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 505

EP - 514

BT - STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing

PB - Association for Computing Machinery

T2 - 4th Annual ACM Symposium on Theory of Computing, STOC 2014

Y2 - 31 May 2014 through 3 June 2014

ER -