Knowledge, Computed

For anyone who has ever nodded along to a paper that waved its hands at "extractability" and hoped no one would ask for the actual extractor, the result lands. In May 2014, four cryptographers posted a construction that solves a 25-year-old puzzle. The question: how do you build a one-way function whose image values come with an automatic witness, without trusting any number-theoretic magic?

The paper is "On the Existence of Extractable One-Way Functions" by Nir Bitansky, Ran Canetti, Omer Paneth, and Alon Rosen, published at the 46th ACM Symposium on Theory of Computing (STOC '14) in New York. The four authors give the first construction of an extractable one-way function (EOWF) under a standard cryptographic hardness assumption, sub-exponential Learning with Errors. In the same breath, they show that extractability cannot survive the moment you give the adversary unbounded polynomial advice, not if indistinguishability obfuscation is also real. This is a rigorous, two-sided result: a new primitive, and a sharp boundary on what that primitive can possibly mean.

The result sits inside a long arc of theoretical work that started with Goldwasser, Micali, and Rackoff in 1989, ran through Canetti and Dakdouk in 2008, and bent through the extractable-collision-resistant-hash and SNARK work of Bitansky, Canetti, Chiesa, and Tromer. It is the EOWF half of a story that was, until now, only half told.

​The paper at a glance

• Title: On the Existence of Extractable One-Way Functions
• Authors: Nir Bitansky (Tel Aviv University), Ran Canetti (Boston University and Tel Aviv University), Omer Paneth (Boston University), Alon Rosen (Efi Arazi School of Computer Science, IDC Herzliya)
• Venue: Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC '14), New York, May 31 - June 3, 2014
• DOI: 10.1145/2591796.2591859
• Conference publication date: 31 May 2014
• IACR ePrint archive number: 2014/402
• Conference acceptance rate: 91 of 319 submissions, 29%
• Funding sources: Israel Science Foundation, European Research Council, Check Point Institute for Information Security, IBM Ph.D. Fellowship, NSF

​The trapdoor at the heart of every zero-knowledge argument

The story starts in 1985, when Goldwasser, Micali, and Rackoff introduced the notion of zero-knowledge proofs. A prover wants to convince a verifier of a statement, like "I know this secret number." The trick is to prove it without revealing the number itself.

The cleanest way to make this work, the Feige-Lapidot-Shamir paradigm, asks the verifier to send a "trapdoor commitment" at the start of the protocol. If the verifier is honest, the prover uses the trapdoor to construct a real argument. If the verifier is cheating, the simulator extracts a trapdoor from the verifier's code and uses it to fake the prover's message. Knowledge, in this picture, means "the simulator can extract something useful from your code."

The thing that has always made the simulator's job possible is the assumption that the underlying trapdoor commitment is, in a precise sense, "knowable." That is what the Knowledge of Exponent assumption (KEA) says about discrete-log groups: if an efficient program outputs a value in the image of a particular exponentiation map (raising a number to a power in a group), the program must know a discrete log. In the late 1990s, Hada and Tanaka showed that this kind of assumption is what makes three-round zero-knowledge possible at all. Bellare and Palacio sharpened that connection in 2004.

The problem is that KEA and its cousins are non-falsifiable. You cannot write down a polynomial-time adversary that breaks the assumption, because the only way to argue about the adversary's "knowledge" is to be an extractor yourself, and you cannot write down the extractor without already knowing the answer. This is the same kind of problem that Bitansky, Canetti, Chiesa, and Tromer ran into in their 2012 paper on extractable collision-resistant hash (ECRH) functions, the work that became the foundation of the SNARK constructions driving Zerocash and other production systems. The ECRH work, the SNARKs that followed, and the entire "from ECRH to SNARKs" arc all rode on similar ground. The 2014 paper is the EOWF half of the same story.

​A primitive that should have existed already

An extractable one-way function family f comes with two guarantees. First, it is one-way: given a random image y, no efficient adversary can produce a valid preimage. Second, it is extractable: for every efficient adversary A (with the right kind of advice), there is an efficient extractor E that takes A's code and, whenever A outputs a value y in the image of f, outputs a preimage x with f(x) = y. Intuitively, if you can produce an image point, you must know a preimage, and there is a mechanical procedure that pulls that preimage out of your code.

The Canetti-Dakdouk line of work in 2008 and 2009 showed that such objects, formalized first as Extractable Perfectly One-Way Functions and then more generally as EOWFs, are extremely useful. They imply three-round zero-knowledge, succinct non-interactive arguments, and other clean protocols. But every construction on the table, the ones from ICALP 2008 and TCC 2009, came with the same nonstandard knowledge assumption that has been bothering cryptographers for years. The question of whether EOWFs can exist from any "standard" assumption was wide open. Bitansky, Canetti, Paneth, and Rosen's paper is the answer.

The question is delicate because the term "adversary" hides a parameter that does most of the work: the auxiliary input z that the adversary gets alongside its random tape. A long, precomputed table that encodes hard instances, that is an auxiliary input. If z is allowed to be of unbounded polynomial length, extraction seems to demand impossibly strong properties. If z is bounded, a more reasonable regime, the same machinery starts to work.

​Two halves of one answer

The paper splits the problem into two halves and answers each on its own terms.

The positive half, bounded advice. If the adversary's auxiliary input z is of bounded polynomial size in the security parameter, the four authors construct an EOWF under the sub-exponential hardness of the Learning with Errors (LWE) problem. The construction is non-black-box: the extractor reads the adversary's code as a string and runs it, with help from privately verifiable P-delegation schemes introduced by Kalai, Raz, and Rothblum at the same STOC.

The core techniques are rooted in Barak's 2001 non-black-box simulation and the Barak-Lindell-Vadhan refinement. Both had been waiting for a concrete payoff like this one for more than a decade. The team had already shown, in their own earlier 2013 ePrint "How To Construct Extractable One-Way Functions Against Uniform Adversaries," that the positive construction works in this bounded-advice setting. The STOC paper is the merged, journal-ready version of that result alongside the impossibility.

The negative half, unbounded advice. If the adversary's auxiliary input z can be of unbounded polynomial size, the same primitive becomes incompatible with indistinguishability obfuscation. The team shows that if a sufficiently expressive iO exists, then no EOWF with auxiliary-input extraction can exist. The argument adapts the Goldwasser-Kalai 2005 obstruction, combined with their own impossibility-of-obfuscation-with-auxiliary-input work. As a corollary, KEA on discrete-log groups, in the strong "holds for all polynomial-time adversaries with arbitrary auxiliary input" form, cannot coexist with general iO. The companion ePrint puts it bluntly: "one must fall."

The picture this draws is clarifying. If you want EOWFs that work against adversaries with arbitrarily large precomputed advice, you have to give up on iO. If you want iO, you have to give up on the strongest form of KEA. The bounded-advice regime, which the construction actually delivers, is the one where both can peacefully coexist, and it is the regime that the paper shows is rich enough to build the entire standard toolkit of zero-knowledge and succinct arguments on top of.

​The construction, in plain language

The visual above walks through the four key components of the paper's argument. Section ① is the basic setting: an EOWF maps preimages x to images y, and the goal is to recover x whenever an efficient adversary outputs a valid y. Section ② is the heart of the construction. The adversary A is a program, and the paper gives a concrete procedure E that takes A's source code as input. E runs A to obtain a candidate y, then unwraps y using a witness structure baked into the function family. The output is a valid x with f(x) = y. The "non-black-box" label matters. Most earlier work could only treat adversaries as oracles, which is too weak for this kind of extraction. Section ③ shows the two regimes in parallel: the green POSITIVE box is the bounded-advice result, where the construction succeeds under sub-exponential LWE. The red NEGATIVE box is the unbounded-advice impossibility, where iO pulls the rug out. Section ④ traces the downstream consequence: the 2-message zero-knowledge argument built from the EOWF, with the verifier's first message being a trapdoor commit y and the prover replying with a single short argument.

The construction uses two layered ingredients. The first is a privately verifiable P-delegation scheme, the kind of object that Kalai, Raz, and Rothblum introduced at the same conference. P-delegation encodes a hard instance of a problem so that the code that solves it can be verified privately by anyone holding a public key. The second is the non-black-box wrapper that takes an adversary A, embeds A's code into a verification equation, and uses the structure of the EOWF to recover a witness. The combination is delicate, but the design is fully explicit. There are no hidden knowledge assumptions, and every reduction runs in concrete polynomial time.

Sub-exponential LWE gives the construction its hardness. LWE is one of the more trusted post-quantum assumptions, and it has been the bedrock of lattice-based cryptography since Regev's 2005 work.

​Findings, claims, and what is now on the table

The paper delivers two kinds of results: constructive primitives and matching impossibilities.

Constructions.

• First explicit EOWF under standard assumptions. Under the sub-exponential hardness of LWE, there exists a family of one-way functions f such that, for every polynomial-time adversary A with bounded polynomial advice z, there is a polynomial-time extractor E that, on input (⟨A⟩, z) and on A(z) outputting y in the image of f, outputs x with f(x) = y. This is the first such construction that does not rest on a non-falsifiable knowledge assumption.
• First 2-message zero-knowledge argument for NP from standard assumptions. Building on the EOWF and the Feige-Lapidot-Shamir trapdoor paradigm, the authors give a 2-message ZK argument for any NP language under essentially the same sub-exponential LWE assumption. Prior to this work, round-optimal 2-message ZK constructions required non-standard knowledge assumptions.
• First 3-message zero-knowledge argument of knowledge from standard assumptions. As a corollary of the 2-message construction, the authors obtain a 3-message ZK argument of knowledge (ZK-AoK) for NP under the same assumption. The 3-message round count is tight by the Goldreich-Krawczyk lower bound, so this is the best one can hope for among the standard "no auxiliary-input" assumptions.

Impossibilities and connections.

• Sharp impossibility for unbounded advice. If indistinguishability obfuscation for all polynomial-size circuits exists, then EOWFs with auxiliary-input extraction for unbounded polynomial advice do not exist. The same obstruction rules out the strongest forms of KEA on discrete-log groups.
• Connection to ECRH and SNARKs. The paper is the natural companion to the Bitansky-Canetti-Chiesa-Tromer ITCS 2012 work on ECRH. The 2012 paper showed that ECRH families imply succinct non-interactive arguments. The 2014 paper shows that EOWF families imply 2-message ZK. Together, the two halves of the "extractable functions" story are now closed on the constructive side.
• The "one must fall" corollary. The companion ePrint 2013/641 by Bitansky, Canetti, and Paneth puts the impossibility in standalone form. If a sufficiently expressive iO exists, then auxiliary-input extractable one-way functions do not, and in particular KEA on discrete-log groups does not survive arbitrary polynomial-time adversaries with arbitrary advice.

The construction has a modular structure. Two workhorses do the heavy lifting: the non-black-box machinery of Barak, refined by Barak, Lindell, and Vadhan, and the privately verifiable P-delegation of Kalai, Raz, and Rothblum. Anyone trying to push the construction further, to handle larger advice classes, to instantiate it from different lattice assumptions, to bring in other extraction paradigms, has a clear scaffold to work with.

​Why the result reshapes the map

The result changes three things at once.

First, it retires a long-standing open problem. The question of whether EOWFs can be built from falsifiable assumptions was open for at least the six years between Canetti and Dakdouk's 2008 introduction of the primitive and 2014. Researchers knew that EOWFs would imply 3-message ZK and other clean protocols, but every construction needed the kind of knowledge assumption that cannot be tested by an efficient adversary. The paper's bounded-advice construction, sitting on sub-exponential LWE, is the first falsifiable, polynomially verifiable foundation. The field can now build cryptographic protocols on top of EOWFs without the same foundation-worrying that has dogged KEA-based protocols.

Second, it sharpens the conceptual map around iO. The 2013 crop of results had begun to turn iO from a curiosity into a tool. Garg, Gentry, and Halevi published candidate multilinear maps at EUROCRYPT 2013. Garg, Gentry, Halevi, Raykova, Sahai, and Waters published candidate iO and functional encryption for all circuits at FOCS 2013. Sahai and Waters showed how to use iO at STOC 2014, and Hohenberger, Sahai, and Waters showed how to replace random oracles with iO in full-domain-hash applications. By 2014, it had become clear that iO would imply an enormous collection of cryptographic objects: puncturable PRFs from Boneh and Zhandry, functional encryption for all circuits, two-round secure computation, and more.

What was less clear was what iO would rule out. Bitansky, Canetti, Paneth, and Rosen are among the first to show that iO is genuinely incompatible with a long-standing cryptographic assumption, and in doing so they force the community to choose. You can have your iO, or you can have your fully general KEA, but the paper makes a sharp case that the strongest forms of both cannot be obtained simultaneously.

Third, it offers a concrete new path to short zero-knowledge. The first 2-message ZK argument for NP from a falsifiable assumption is a structural result, not a tuning optimization. It is the kind of result that gets cited in any future paper that needs "round-optimal ZK from standard assumptions." The work in this paper is the citation that will appear in those papers for the foreseeable future.

​The questions that stay open

The paper is honest about what it does not deliver. The non-black-box extractor in the positive construction needs to read the adversary's code as a string, and that requires the auxiliary input to be small enough that the extractor can handle it as part of its own bounded advice. If you want extraction against adversaries with arbitrarily large precomputed advice, you are back in the negative regime, and iO closes the door.

Three open threads are worth flagging.

• Beyond LWE. The construction leans on the specific structure of LWE for the witness-wrapping step. It is natural to ask whether the same non-black-box machinery can be instantiated from other falsifiable assumptions, especially in pre-quantum settings like CDH, DDH, or RSA, where the ECRH constructions have been more tentative. The paper does not settle this, and the answer is likely to require a different flavor of witness structure.
• Ratcheting down the advice bound. The bounded-advice regime is natural, but the bound is concrete. Can the construction tolerate advice of size slightly super-polynomial without losing sub-exponential LWE? The impossibility result gives a hard ceiling, but the gap between "bounded poly" and "unbounded poly" is wide.
• Tighter EOWF-to-SNARK bridge. The 2012 ECRH paper had a "back again" direction that was famously subtle. The EOWF paper takes care of the forward direction (EOWF to 2-message ZK), but the analogous "back again" question, whether 2-message ZK implies EOWF, is a different story, and one of the threads that the Bitansky-Canetti-Chiesa-Tromer "Hunting of the SNARK" work will later chase.

There is also a more architectural question. The construction in this paper is not yet "practical." The non-black-box wrapper adds constants, the LWE parameter choices that give sub-exponential hardness are aggressive, and the prover's computational cost in the 2-message ZK argument is dominated by the underlying delegation machinery. Whether this construction can be made small enough to drive real systems, or whether it will remain a foundational result whose practical descendants will look very different, is an open question.

​Sources

• Nir Bitansky, Ran Canetti, Omer Paneth, and Alon Rosen. "On the Existence of Extractable One-Way Functions." Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC '14), New York, NY, May 31 - June 3, 2014. ACM. DOI: 10.1145/2591796.2591859. ACM Digital Library
• Nir Bitansky, Ran Canetti, Omer Paneth, and Alon Rosen. "On the Existence of Extractable One-Way Functions." IACR Cryptology ePrint Archive, Paper 2014/402, June 2, 2014. ePrint
• Nir Bitansky, Ran Canetti, and Omer Paneth. "How To Construct Extractable One-Way Functions Against Uniform Adversaries." IACR Cryptology ePrint Archive, Paper 2013/468, August 2, 2013. ePrint
• Nir Bitansky, Ran Canetti, and Omer Paneth. "Indistinguishability Obfuscation vs. Auxiliary-Input Extractable One-Way Functions: One Must Fall." IACR Cryptology ePrint Archive, Paper 2013/641, 2013. ePrint
• Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. "From Extractable Collision Resistance to Succinct Non-Interactive Arguments of Knowledge, and Back Again." Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (ITCS '12), pp. 326-349, 2012. ACM Digital Library; IACR ePrint 2011/443
• Ran Canetti and Ronny Ramiz Dakdouk. "Extractable Perfectly One-Way Functions." Proceedings of ICALP 2008, pp. 449-460. IACR ePrint 2008/187
• Ran Canetti and Ronny Ramiz Dakdouk. "Towards a Theory of Extractable Functions." Proceedings of TCC 2009, pp. 595-613.
• Boaz Barak. "How to Go Beyond the Black-Box Simulation Barrier." Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS 2001), Las Vegas, NV, October 14-17, 2001, pp. 106-115. Author copy
• Boaz Barak, Yehuda Lindell, and Salil P. Vadhan. "Lower Bounds for Non-Black-Box Zero-Knowledge." Journal of Computer and System Sciences 72, no. 2 (2006): 321-391.
• Yael Tauman Kalai, Ran Raz, and Ron D. Rothblum. "How to Delegate Computations: The Power of No-Signaling Proofs." Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC '14), New York, NY, May 31 - June 3, 2014, pp. 485-494. ACM Digital Library
• Shafi Goldwasser and Yael Tauman Kalai. "On the Impossibility of Obfuscation with Auxiliary Input." Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), Pittsburgh, PA, October 23-25, 2005, pp. 553-562.
• Shafi Goldwasser, Silvio Micali, and Charles Rackoff. "The Knowledge Complexity of Interactive Proof Systems." SIAM Journal on Computing 18, no. 1 (1989): 186-208.
• Shai Hada and Tetsuya Tanaka. "On the Existence of 3-Round Zero-Knowledge Protocols." Proceedings of the 18th Annual International Cryptology Conference (CRYPTO '98), Santa Barbara, CA, August 23-27, 1998, pp. 408-423. Springer
• Mihir Bellare and Adriana Palacio. "The Knowledge-of-Exponent Assumptions and 3-Round Zero-Knowledge Protocols." Proceedings of the 24th Annual International Cryptology Conference (CRYPTO 2004), Santa Barbara, CA, August 15-19, 2004, pp. 273-289. IACR ePrint 2004/008
• Uriel Feige, Dror Lapidot, and Adi Shamir. "Multiple Non-Interactive Zero-Knowledge Proofs Under General Assumptions." SIAM Journal on Computing 29, no. 1 (1999): 1-28.
• Oded Goldreich and Hugo Krawczyk. "On the Composition of Zero-Knowledge Proof Systems." SIAM Journal on Computing 25, no. 1 (1996): 169-192.
• Amit Sahai and Brent Waters. "How to Use Indistinguishability Obfuscation: Deniable Encryption, and More." Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC '14), New York, NY, May 31 - June 3, 2014, pp. 475-484. IACR ePrint 2013/454
• Susan Hohenberger, Amit Sahai, and Brent Waters. "Replacing a Random Oracle: Full Domain Hash from Indistinguishability Obfuscation." Proceedings of EUROCRYPT 2014, pp. 201-220. IACR ePrint 2013/509
• Sanjam Garg, Craig Gentry, Shai Halevi. "Candidate Multilinear Maps from Ideal Lattices." Proceedings of EUROCRYPT 2013, pp. 1-17.
• Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters. "Candidate Indistinguishability Obfuscation and Functional Encryption for All Circuits." Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013), pp. 40-49. IACR ePrint 2013/451
• Oded Regev. "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography." Journal of the ACM 56, no. 6 (2009), Article 34, pp. 1-40.