acceptodds
Under review as a conference paper at ICLR 2027

Determined but Unreachable: Cryptographic Barrier to Language Generation

Abstract

Can examples determine a language while leaving the production of even one new word out of reach? We show that this happens exactly when one-way functions exist. With one-way functions, attaching to every word a statistically binding but computationally hiding commitment to the key of a pseudorandom-function graph gives an efficiently presented family in which one example determines the language except with probability , yet every efficient generator has negligible probability of producing an unseen valid word within any polynomial horizon. With exponentially secure primitives the barrier extends to total running time , which is tight up to the constant in the exponent. For the converse we view a family through its sampling map, which sends a hidden description and coins to the examples: the posterior is the projection of the uniform measure on a fibre, and a point of the fibre whose language lies inside the target enumerates fresh words forever. Classical universal posterior sampling in the absence of one-way functions, stated jointly with the hidden target and padded across lengths, then yields efficient generators that match every generator allowed to draw posterior samples, at infinitely many lengths. Hence one-way functions exist if and only if posterior sampling helps generation, and hard instances for generation and for identification exist under the same condition. Since the Bayesian generator idealizes in-context learning as implicit posterior inference, the result also shows that this idealization can be computationally out of reach even when a single example suffices statistically.

Primary area:
learning theory
Keywords:
language generation, language generation in the limit, computational learning theory, one-way functions, cryptographic lower bounds, distributional inversion, posterior sampling, statistical-computational gap

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_g86COpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

I am not an expert at this area. As far as I understand, this paper shows an interesting result that OWF exists if and only if there is a family of languages with the following properties:

  1. One sample l∈L is sufficient to pin down the target language L
  2. Any PPT algorithm given access to polynomial many samples in L, has negligible probability of writing even one unseen sample from the target language.
Critical strengths

The paper gives a clean answer to a theoretical question.

I didn't find errors in the security proofs.

Critical weaknesses

I don't know how the result can be translated to real language models or ordinary classes such as regular languages.

Questions for authors

In real life, we not only believe OWF exist, but also somehow believe the ideal cipher model. In this case, your result is trivial, is my understanding correct?

1 comment
AuthorsOpenReview ↗

Response to Reviewer g86C

Thank you for the review and for checking the security proofs. The paper makes no claim about trained language models; for ordinary classes it gives a necessary condition for regular families, and relative to an ideal cipher the hard direction is immediate, while the equivalence, in particular its converse, does not follow from that model.

W1 (real language models and regular languages).

I don't know how the result can be translated to real language models or ordinary classes such as regular languages.

Regular languages. For a family whose languages are recognized by automata with at most q(n)=poly(n)q(n)=\mathrm{poly}(n) states, a strong gap requires that examples longer than q(n)q(n) appear only with negligible probability within polynomial horizons (Appendix L, "Regular families"). The reason is pumping: an example ww with ∣w∣≥q(n)|w|\ge q(n) has a split w=xyzw=xyz with ∣xy∣≤q(n)|xy|\le q(n), ∣y∣≥1|y|\ge 1 and xyiz∈LSxy^iz\in L_S for every i≥0i\ge 0. A generator that tries the O(∣w∣2)O(|w|^2) candidate splits, one per round, and outputs xyizxy^iz with ii large enough that the word is longer than every example, produces a fresh valid word at the round of a correct split, in polynomial time. So in automaton families the barrier would need sources that almost never emit long words; whether natural regular or context-free families can exhibit it is open (Appendix L, Section 7).

Language models. The theorem concerns the Bayesian idealization of in-context learning as implicit posterior inference (Xie et al., 2022), not trained models, and the Ethics statement says so. What it does say about that idealization is two-sided. First, for the witness the Bayesian generator (one posterior draw, then enumeration) succeeds after a single example, while every efficient generator has negligible success, so an explanation of in-context generation that appeals to the Bayesian ideal needs a computational premise in addition to a statistical one. Second, the converse (Theorem 4.2, Remark 4.4) names that premise: such a strong gap forces the process that produced the data to be distributionally one-way. We have added a paragraph to Section 7 that states both points and the boundary.

Q1 (ideal cipher).

In real life, we not only believe OWF exist, but also somehow believe the ideal cipher model. In this case, your result is trivial, is my understanding correct?

For the hard direction alone, largely yes; for the theorem, no. Relative to an ideal cipher or random oracle OO with 2λ2\lambda-bit outputs, the family Lk={(i,O(k,i))}L_k=\lbrace (i,O(k,i))\rbrace already has the property: an example fixes kk except with probability about 2−λ2^{-\lambda}, since each of the other 2λ−12^\lambda-1 keys agrees at the observed index with probability 2−2λ2^{-2\lambda}, and a fresh word needs an oracle value at an unqueried point. Two parts of the result do not follow from that belief.

  1. The theorem is an equivalence. The converse (Theorem 4.2) says that without one-way functions every family that posterior sampling can generate is efficiently generatable, with inverse-polynomial success, at infinitely many lengths. No idealized model gives this: relative to an ideal cipher one-way functions exist, so its hypothesis is never met there.
  2. The hard direction uses only one-way functions, and the converse shows that nothing weaker suffices. In the standard model a pseudorandom function need not make its key identifiable: two keys may agree on every likely example (first paragraph of Section 5). The ideal cipher supplies identifiability by assumption; in the paper the commitment tag supplies it (Lemmas 5.1 and 5.3), for every instantiation, because binding is statistical. Statements proved in idealized models also need not hold for any concrete instantiation (Canetti, Goldreich and Halevi, J. ACM 2004, for the random oracle model).

The same new paragraph of Section 7 also covers idealized models.

Presentation. We have added a plain-language walk-through of the witness to the introduction (after Theorem 1.1) and separated the classical ingredients from the new ones there; the general response lists all changes, which are in blue in the revised PDF.

We are glad to answer further questions.

Reviewer_rgjyOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper asks whether examples can contain enough information to identify a language while still leaving efficient algorithms unable to generate a new valid string. It shows that such gaps exist if and only if ordinary one-way functions exist.

Critical strengths
  1. The paper asks an interesting question: can examples give us enough information to identify a language, yet still leave us unable to generate even one new valid string efficiently? This makes the distinction between having enough data and being able to use it clear.

  2. The result goes beyond constructing a hard example: it connects the existence of this gap to the existence of one-way functions in both directions. This gives a clear characterization of the problem under the paper's assumptions.

Critical weaknesses
  1. The converse seems to offer limited novelty beyond existing conditional-sampling results [A, B]. These already provide the key step of sampling from the posterior. Appendix L also explains how they can reproduce the Bayesian generator over finite horizons. The theorem is different, but it is unclear what substantial new technical obstacle the converse resolves.

  2. I am also unconvinced that the construction provides enough new insight. The commitment tag makes the language identifiable while hiding the key. Pseudorandomness then makes fresh outputs hard to generate. This combination is useful, but the paper needs to explain what it teaches us beyond these familiar cryptographic properties.

  3. The connection to natural language generation remains weak. The hard task involves hidden keys and commitment tags, with success defined by an exact cryptographic rule. The paper does not explain what these features capture about natural language or in-context learning. This supports an abstract impossibility result, but leaves the application motivation unconvincing.


[A] Naor, Moni, and Guy N. Rothblum. "Learning to impersonate." Proceedings of the 23rd international conference on Machine learning. 2006.

[B] Hirahara, Shuichi, and Mikito Nanashima. "Learning in pessiland via inductive inference." 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2023.

Questions for authors
  1. What technical obstacle in the converse cannot be handled by existing conditional-sampling results together with standard error bounds and padding?

  2. Beyond making the language identifiable from one example, what broader insight or consequence does the commitment-based construction provide for generation?

  3. What features of natural language generation or in-context learning are captured by the commitment-based examples, beyond the general task of producing a new valid output?

  4. Can the claimed upper bound be justified without assuming that a key matching one observation will also work on unseen inputs?

4 comments
AuthorsOpenReview ↗

Response to Reviewer rgjy (1/3)

Response to Reviewer rgjy (1/3)

Thank you for the review. Q4 is right about the attack written at the end of the proof of Proposition E.1; the correct search, over the tag's seed, is the one panel (a) of Figure 5 already notes, and with it no theorem changes and the bound of Proposition E.1 is unchanged. On W1/Q1, the converse introduces no new inversion or conditional-sampling technique, and the revised introduction now credits both classical ingredients; the contribution we claim is the equivalence, with the rigidification construction on the hard side.

W1 and Q1 (what the converse adds to [A, B]).

What technical obstacle in the converse cannot be handled by existing conditional-sampling results together with standard error bounds and padding?

None that requires a new technique. With the right statement, the converse is conditional sampling, error bounds and padding, and the paper claims neither classical ingredient (Appendix L): preimages of a sampler as posterior draws are used in Naor and Rothblum's proof of their Theorem 4.2, and conditional sampling without one-way functions, at infinitely many input lengths, is due to Impagliazzo and Levin, to Ostrovsky and Wigderson, and to Hirahara and Nanashima. The contribution we claim is the equivalence, with the rigidification construction on the hard side. What the converse had to get right is which quantity is sampled and at which lengths:

  1. Lengths. Without one-way functions, Ostrovsky and Wigderson give conditional sampling at infinitely many input lengths of one samplable distribution. A strong gap is refuted only by success at infinitely many description lengths of the family. Lemma 4.1 moves one fixed inverter there by padding: the inverter serves every block of lengths, is good in infinitely many blocks, and the generator never needs to know which length is good. This is why the equivalence is with ordinary one-way functions, whereas Naor and Rothblum's learnability equivalence is with almost one-way functions.
  2. The weak gap. Refuting a weak gap needs success above 1−ϵ1-\epsilon. Choosing a length in the block at random, as in Theorem 4.2(i), loses a factor of the block size. Theorem 4.2(ii) instead uses the jj-th length at round N0+jN_0+j; this works because one fresh valid word suffices. The same step gives the identification corollary (Corollary 6.3).
  3. What is sampled. As in Naor and Rothblum, the object sampled is the hidden description, not further examples: a continuation of the example stream drawn close to the source repeats an observed word with probability tending to one. Theorem 3.1 composes qq such draws (a hybrid bound) with an arbitrary posterior-sampling generator, jointly with the target.

On the remark in Appendix L: for families identifiable from polynomially many examples and a polynomial horizon, extrapolating a stream that appends an enumeration of the target, plus padding, also gives the converse. Sampling the description is what covers every posterior-sampling generator, including Example H.1, where the Bayesian generator fails. Each step is short once stated. What the statement adds is the exact condition, and its premise needed care: with no statistical premise a gap need not involve computation (Example 2.8), so no converse could hold; a premise stated through the Bayesian generator alone still gives an equivalence, but it excludes families that are easy to generate (Example 2.7) and the hard family of Example H.1, so only the posterior-sampling premise makes the statement say that posterior sampling helps generation. The revised introduction ("What is classical and what is new", Section 1) now separates the classical parts from ours explicitly.

AuthorsOpenReview ↗

Response to Reviewer rgjy (2/3)

Response to Reviewer rgjy (2/3)

Q4 (the matching attack in Proposition E.1).

Can the claimed upper bound be justified without assuming that a key matching one observation will also work on unseen inputs?

Yes. We read "upper bound" as the matching attack at the end of the proof of Proposition E.1 (from "For the matching upper bound"), and the objection is correct for it: the attack enumerates the graph of the first key k′k' with Fk′(i)=Fk(i)F_{k'}(i)=F_k(i), and pseudorandomness says nothing about whether such a key agrees with kk at the indices the generator then outputs; for some secure pseudorandom functions it does not. The right search is over the tag's seed, as panel (a) of Figure 5 notes and as Appendix D does coordinate by coordinate.

For z′∈{0,1}λz'\in\lbrace 0,1\rbrace^\lambda with blocks ρj′\rho_j' of Eλ(z′)E_\lambda(z'), accept z′z' if Cj⊕Gλ(ρj′)∈{03λ,R}C_j\oplus G_\lambda(\rho_j')\in\lbrace 0^{3\lambda},R\rbrace for every jj, and read off kj′k_j' (if the first example is the revealing word, read kk from it). If R∉ΔλR\notin\Delta_\lambda, every accepted seed gives k′=kk'=k, because kj′≠kjk_j'\ne k_j would force

R=Gλ(ρj)⊕Gλ(ρj′)∈Δλ.R=G_\lambda(\rho_j)\oplus G_\lambda(\rho_j')\in\Delta_\lambda .

The true seed is accepted, and the seed and the mask are independent and uniform, so testing a fixed list of M≤2λM\le 2^\lambda seeds succeeds with probability at least M2−λ(1−2−λ)M2^{-\lambda}(1-2^{-\lambda}); the generator then outputs the first unseen word of the target's enumeration (the revealing word, unless that was the example). Each test costs poly(λ)\mathrm{poly}(\lambda), and binding is statistical, so this holds for every instantiation of GλG_\lambda, EλE_\lambda and FF. With the lower bound of Proposition E.1 under 2cλ2^{c\lambda}-security, the least total time giving constant success lies between 2cλ/32^{c\lambda/3} and 2λpoly(λ)2^{\lambda}\mathrm{poly}(\lambda), that is, it is 2Θ(λ)2^{\Theta(\lambda)} with λ=⌊n/5⌋\lambda=\lfloor n/5\rfloor, which is the tightness claim. The lower bound is unaffected: the hidden-check distinguisher of Theorem 5.5 needs only that the true key passes its check at a fresh index. We have replaced the attack at the end of the proof of Proposition E.1 with this argument (in blue), and "key search" after Theorem 5.5 and "exhaustive key search" after Proposition E.1 with "exhaustive search over the tag's seed". Re-checking Proposition E.1 also led to two corrections in its hypotheses (the order of quantifiers in the definition of s(λ)s(\lambda)-security, and counting the time to compute the horizon inside the budget), now made in Appendix B and Proposition E.1; its bound is unchanged.

W2 and Q2 (what the construction gives for generation). Beyond one-example identifiability:

  1. A sample-complexity and timescale separation. One example suffices information-theoretically, while every efficient generator needs superpolynomially many to succeed with non-negligible probability. Yet an efficient generator succeeds eventually on every complete enumeration of every target (Theorem 6.1(3)), so success in the limit says nothing about polynomial horizons.
  2. A universal witness. Instantiated from Levin's universal one-way function, the construction gives one explicit family that has a strong gap if and only if one-way functions exist (Remark 6.2); the same threshold holds for identification (Corollary 6.3).
  3. A transfer for keyed families. Lemma 5.3 makes any keyed family identifiable, with error at most 2−⌊n/5⌋2^{-\lfloor n/5\rfloor} after one example and 1/(eN)1/(eN) after NN, using no hardness assumption, since binding is statistical. Under one-way functions and for keyed families with light-tailed sources, Lemma 5.4 bounds an efficient generator's success by the chance that an efficient algorithm built from it produces a fresh word of the untagged family, or its key, plus the other terms of Eq. (13). Within polynomial horizons, hardness of that task therefore transfers to a statistically identifiable family. A pseudorandom-function graph alone need not be identifiable, since two keys may agree on every likely example. Relative to a random oracle this step would be free (Section 7); in the standard model the tag supplies it for every keyed family and every instantiation, and the converse shows that one-way functions, the assumption it uses, are also necessary.
  4. What is forced. By Remark 4.4, a strong gap in a family generatable with posterior samples makes the family's own padded sampling map distributionally one-way (not necessarily one-way in the stronger sense; Appendix H). The construction realizes this with ordinary one-way functions.
AuthorsOpenReview ↗

Response to Reviewer rgjy (3/3)

Response to Reviewer rgjy (3/3)

W3 and Q3 (natural language and in-context learning). Beyond producing a new valid word, the commitment examples capture no feature of natural language, and the paper claims none; success is membership in the target language, as in Kleinberg and Mullainathan (2024). The theorem concerns the idealization of in-context learning as implicit posterior inference (Xie et al., 2022). For the witness, the Bayesian generator (one posterior draw, then enumeration) succeeds after one example with probability at least 1−2−⌊n/5⌋1-2^{-\lfloor n/5\rfloor}, while every efficient generator has negligible success; by Remark 4.4, such a strong gap forces the data-generating process to be distributionally one-way. For families of automata with poly(n)\mathrm{poly}(n) states, the pumping argument of Appendix L shows that a strong gap needs long examples to be rare. We have added a paragraph to Section 7 on this, and the abstract's last sentence now states that the result makes no claim about trained models.

If the repaired argument for Q4 and the account above of what the equivalence and the construction add answer your concerns on soundness and contribution, we would appreciate it if you would reconsider your assessment.

Thank you for the response. My questions 2 and 4 are addressed, but I still think the novelty and connection to natural language generation are limited. For novelty, I appreciate the clarifications, but the contribution still seems minor beyond existing techniques. Regarding the applicability, the setting is idealized to an extent that it does not contribute much to real-world language generation (to my understanding). I will maintain my original score.

Reviewer_y6vZOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper asks whether examples can statistically determine a language while every efficient algorithm still fails to produce even one new valid word from it. It shows that such gaps exist if and only if one-way functions exist. For the hard direction, every word carries a binding but hiding commitment to the key of a pseudorandom-function graph. One example then pins down the language except with exponentially small probability, yet every efficient generator has negligible probability of producing an unseen valid word within any polynomial number of rounds. For the converse, the paper treats the process that generates examples as a function.

Critical strengths
  1. The paper gives an exact equivalence between a learning question and the existence of one-way functions. It covers strong and weak gaps, generation and identification, and has a converse under standard one-way functions.

  2. The general construction for making a family identifiable without making generation easier is a tool others can reuse. The converse handles subtle points, such as coupling jointly with the hidden target and padding across lengths, and is supported by illustrative examples.

Critical weaknesses
  1. Most ingredients are known (distributional inversion, preimages as posterior samples, universal extrapolation, commitment schemes). The contribution lies mostly in combining them and framing the question. I am not very familiar with the area, but it seems on the technique side it has limited novelty.

  2. I found that the presentation is dense and the framing is overstated.

  3. The link to in-context learning is one sentence, the authors make no claim about trained models, and the construction is highly artificial. The paper may fit a theory venue such as COLT.

Questions for authors
  1. Which parts of the converse don’t follow directly from Hirahara & Nanashima (2023) and Naor & Rothblum (2006)?

  2. Does the barrier survive a notion of identifiability that rules out encoding the key in every example?

  3. Is there any natural family (e.g., context-free, small circuits) where you expect the gap?

  4. What concrete implication does this have for in-context learning or trained language models?

2 comments
AuthorsOpenReview ↗

Response to Reviewer y6vZ (1/2)

Response to Reviewer y6vZ (1/2)

Thank you for the review and for its list of ingredients. We agree with W1 as far as techniques go: the converse introduces no new inversion or conditional-sampling technique, and the contribution we claim is the equivalence, with the rigidification construction on the hard side; we also agree that the presentation is too dense, and W2 below lists the changes in the revised PDF.

W1 and Q1 (what does not follow from Hirahara and Nanashima (2023) and Naor and Rothblum (2006)).

No tool of the converse is new; the parts that do not follow directly from those two papers are the three steps listed below. The paper claims neither classical ingredient of the converse (Appendix L): preimages of a sampler as posterior draws are used in Naor and Rothblum's proof of their Theorem 4.2, and conditional sampling without one-way functions, at infinitely many input lengths, is due to Impagliazzo and Levin, to Ostrovsky and Wigderson, and to Hirahara and Nanashima. The contribution we claim is the equivalence, with the rigidification construction on the hard side (Lemma 5.3 makes any keyed family identifiable, and for keyed families with light-tailed sources Lemma 5.4 shows that, within polynomial horizons and under one-way functions, the tag makes generation easier only by negligible terms). What the converse had to get right is which quantity is sampled and at which lengths:

  1. Lengths. Without one-way functions, Ostrovsky and Wigderson give conditional sampling at infinitely many input lengths of one samplable distribution. A strong gap is refuted only by success at infinitely many description lengths of the family. Lemma 4.1 moves one fixed inverter there by padding: the inverter serves every block of lengths, is good in infinitely many blocks, and the generator never needs to know which length is good. This is why the equivalence is with ordinary one-way functions, whereas Naor and Rothblum's learnability equivalence is with almost one-way functions.
  2. The weak gap. Refuting a weak gap needs success above 1−ϵ1-\epsilon. Choosing a length in the block at random, as in Theorem 4.2(i), loses a factor of the block size. Theorem 4.2(ii) instead uses the jj-th length at round N0+jN_0+j; this works because one fresh valid word suffices. The same step gives the identification corollary (Corollary 6.3).
  3. What is sampled. As in Naor and Rothblum, the object sampled is the hidden description, not further examples: a continuation of the example stream drawn close to the source repeats an observed word with probability tending to one. Theorem 3.1 composes qq such draws (a hybrid bound) with an arbitrary posterior-sampling generator, jointly with the target.

Each step is short once stated. What the statement adds is the exact condition, and its premise needed care: with no statistical premise a gap need not involve computation (Example 2.8), so no converse could hold; a premise stated through the Bayesian generator alone still gives an equivalence, but it excludes families that are easy to generate (Example 2.7) and the hard family of Example H.1, so only the posterior-sampling premise makes the statement say that posterior sampling helps generation. The revised introduction ("What is classical and what is new", Section 1) now separates the classical parts from ours explicitly.

W2 (dense presentation, overstated framing). We agree on density. We read "overstated" as referring to the last sentence of the abstract (in-context learning) and to the "What is new" list; if another passage is meant, we would be glad to revise it too. The revised PDF makes these changes, in blue, and the main text now ends on page 10, within the limit:

  • a plain-language walk-through of the witness after Theorem 1.1: each word carries a header that statistically fixes the key but looks random, and an unseen word requires the pseudorandom function's value at a new index, or the key itself;
  • the "relative point of view" paragraph rewritten without measure-theoretic terms, which stay in Section 2;
  • "What is new" split into classical and new parts, as above;
  • the abstract's last sentence now states that the result makes no claim about trained models;
  • each class (Kpost\mathcal K_{\mathrm{post}}, Kpid\mathcal K_{\mathrm{pid}}) defined in words before its symbol.
AuthorsOpenReview ↗

Response to Reviewer y6vZ (2/2)

Response to Reviewer y6vZ (2/2)

W3 and Q4 (in-context learning, artificial construction). The construction is artificial by design: it is the witness for a lower bound, and the converse applies to every presented family, natural or not. The paper makes no claim about trained models. What the theorem says concerns the idealization of in-context learning as implicit posterior inference (Xie et al., 2022). For the witness, the Bayesian generator (one posterior draw, then enumeration) succeeds after one example, while every efficient generator has negligible success, so an explanation that appeals to the Bayesian ideal needs a computational premise as well as a statistical one. The converse names that premise: by Remark 4.4, such a strong gap forces the process that produced the data to be distributionally one-way. We have added a paragraph to Section 7 that states this and its boundary. On venue: the question extends the language-generation-in-the-limit line of Kleinberg and Mullainathan (NeurIPS 2024).

Q2 (identifiability without encoding the key in every example). If one example determines the language, the encoding cannot be avoided: that example must carry the language's identity, and the tag makes this an explicit field. More generally, Remark 4.4 shows that whenever a family generatable with posterior samples has a strong gap, its own padded sampling map is distributionally one-way (not necessarily one-way in the stronger sense; Appendix H), however its identifiability arises. The converse holds for every presented family, so a stronger notion of identifiability constrains only the hard direction. We have not studied a version in which no single example determines the language, and we make no claim about it.

Q3 (natural families). If "small circuits" means languages whose membership is computed by polynomial-size circuits with the description hard-wired, the witness is such a family: membership is decidable in polynomial time (Definition 2.1). For regular families recognized by automata with poly(n)\mathrm{poly}(n) states there is no strong gap unless long examples are rare: an example longer than the number of states can be pumped into fresh valid words in polynomial time (Appendix L, "Regular families"). For context-free families we make no conjecture; Section 7 lists them as open.

If the revised presentation, the account of what the converse adds, and the scope of the claims address your concerns, we would appreciate it if you would reconsider your assessment.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General response (1/2)

General Response (1/2)

We thank the three reviewers. This comment summarizes the changes in the revised PDF, where changed text is in blue; each reviewer thread has the details.

What the reviews state as strengths. "an exact equivalence between a learning question and the existence of one-way functions" (Reviewer y6vZ); "connects the existence of this gap to the existence of one-way functions in both directions" (Reviewer rgjy); "a clean answer to a theoretical question" (Reviewer g86C). Reviewer y6vZ also describes the construction that makes a family identifiable without making generation easier as "a tool others can reuse".

1. The introduction is revised for readability (Reviewer g86C, Reviewer y6vZ W2; Reviewer rgjy rated presentation 2). Two reviewers rated the presentation 1, and we agree that the introduction is too dense. We have added a plain-language walk-through of the witness after Theorem 1.1 (each word carries a header that statistically fixes the key but looks random, and an unseen word requires the pseudorandom function's value at a new index, or the key itself), rewritten the "relative point of view" paragraph without measure-theoretic terms, and defined each class in words before its symbol (Section 2). The main text now ends on page 10, within the limit.

2. The converse uses classical tools, and the main text now says so (Reviewer rgjy W1, Reviewer rgjy Q1, Reviewer y6vZ W1, Reviewer y6vZ Q1). The converse introduces no new inversion or conditional-sampling technique: preimages of a sampler as posterior draws are used in the proof of Theorem 4.2 of Naor and Rothblum (2006), and conditional sampling without one-way functions, at infinitely many input lengths, is due to Impagliazzo and Levin (1990), Ostrovsky and Wigderson (1993) and Hirahara and Nanashima (2023). The contribution we claim is the equivalence, with the rigidification construction on the hard side. What the converse had to get right is which quantity is sampled and at which lengths: one inverter, good at infinitely many lengths, serves every block of description lengths, which makes the equivalence hold for ordinary rather than almost one-way functions (Lemma 4.1); cycling through lengths across rounds keeps success above 1−ϵ1-\epsilon for the weak gap (Theorem 4.2(ii)); and the hidden description, not further examples, is sampled (Theorem 3.1). Each step is short once the statement is fixed, which is why the paper claims the equivalence rather than a new technique. The revised introduction ("What is classical and what is new") now separates the classical parts from ours.

3. The matching attack in the proof of Proposition E.1 is corrected (Reviewer rgjy Q4). The matching attack at the end of the proof enumerated the first key that agrees with one observed value, which pseudorandomness does not justify. The repaired attack searches over the tag's seed, as panel (a) of Figure 5 already notes; by statistical binding (Lemma 5.1), every accepted seed yields the true key unless the mask is bad, which has probability at most 2−λ2^{-\lambda}. The least total time giving constant success is therefore 2Θ(λ)2^{\Theta(\lambda)}, which is the sense of "tight up to the constant in the exponent". We have also fixed two issues found while re-checking: the quantifier order in the definition of s(λ)s(\lambda)-security (Appendix B) and the time budget for computing the horizon in Proposition E.1. No theorem or lemma changes, and the bound of Proposition E.1 is unchanged.

4. Scope with respect to language models (Reviewer g86C W1, Reviewer rgjy W3, Reviewer rgjy Q3, Reviewer y6vZ W3, Reviewer y6vZ Q4). The paper makes no claim about trained models. The theorem concerns the idealization of in-context learning as implicit posterior inference: for the witness, the Bayesian generator (one posterior draw, then enumeration) succeeds after one example while every efficient generator has negligible success, and by Remark 4.4 such a strong gap forces the data-generating process to be distributionally one-way. For families of automata with polynomially many states, a pumping argument (Appendix L) shows that a strong gap requires long examples to be rare. The abstract's last sentence now states that the result makes no claim about trained models, and Section 7 has a new paragraph on in-context learning, natural classes and idealized models (Reviewer g86C Q1).

AuthorsOpenReview ↗

General response (2/2)

General Response (2/2)

Revisions (in blue in the revised PDF).

ChangeWhereRaised by
Plain-language walk-through of the witnessSection 1, after Theorem 1.1Reviewer g86C, Reviewer y6vZ
"Relative point of view" without measure-theoretic terms; classes defined in wordsSections 1 and 2Reviewer y6vZ
"What is new" split into classical and new partsSection 1Reviewer rgjy, Reviewer y6vZ
Seed-search attack replaces the one-point key testProof of Proposition E.1; sentences after Theorem 5.5 and after Proposition E.1Reviewer rgjy
Quantifier order in s(λ)s(\lambda)-security; time budget for the horizonAppendix B; Proposition E.1Reviewer rgjy
Abstract's last sentence: no claim about trained modelsAbstractReviewer rgjy, Reviewer y6vZ
Paragraph on in-context learning, natural classes, idealized modelsSection 7Reviewer g86C, Reviewer rgjy, Reviewer y6vZ

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.