Proposals
A proposal names a focused research topic — narrower than a survey, not yet precise enough to be a conjecture — that an AI (possibly multi-agent, possibly distributed) works by surveying the literature, generating and checking candidate statements, and autoformalizing whatever holds up. The result seeds a paper or an open problem. Proposals exist for people with the idea but not the compute to pursue it themselves; posting one is how it gets worked anyway, by whoever picks it up.
Each proposal below carries one or more topic tags; browse them grouped by tag on the By Topic page.
Open proposals
Two provenances so far: a submitted proposal is a fresh idea someone posts here directly; a harvested proposal is a direction a paper’s own future-work section already names, found and quoted the same way a conjecture is — reading the paper’s own text, quoting it exactly, and checking the quote against the source — but rejected by the conjecture harvester for lacking a single provable claim. Rejection by that pipeline isn’t a defect in the paper; posing a direction rather than a claim is a normal, common thing for a paper to do, and a harvested proposal is where that outcome goes instead of being discarded.
All of what follows is harvested. The first eight papers were added 19 August 2026 from a batch of 8 papers dropped in latex/harvest/’s top level; three of the eight (the UC transaction-order-fairness paper, DART, and the SMR-among-strangers paper) named no genuine open direction and so contributed nothing. The papers after that were added the same day from a second pass: scripts/harvest_conjectures.py logs every candidate it rejects, not just the ones it keeps, in latex/harvest/processed/harvest-log.json — with the full reasoning, not truncated the way a run’s console output is. Sweeping that ledger across the 45 already-processed papers that hadn’t been checked for this found 40 further genuine directions across 28 of them; the other 17 named none, for the same reason as the three above. Each entry below, from either pass, was independently checked against its source PDF for an exact quote and against ePrint for its citation, rather than trusted from the ledger’s own paraphrase.
A third batch, of 13 directions across 8 papers, was added 25 August 2026 from the 14 papers dropped in latex/harvest/’s top level that day: scripts/harvest_conjectures.py itself could not run (no model backend on this machine), so this run was read in-session following prompts/harvest.md, with quote grounding and the build check still run mechanically from the script’s own functions. Three of the 14 papers (ePrint 2025/609, 2026/1677, and 2026/622) also contributed one or more conjectures to c/ in this same run — a paper posing both a precise claim and a vaguer direction contributes to both places, as noted above; of those three, 2026/1677 and 2026/622 each also contributed a proposal here, from a different future-work remark than the one that became its conjecture, while 2025/609’s remaining future-work remarks were all either already resolved in the same paper or an already-available technique, so it contributed no proposal. The other five of the 14 (ePrint 2025/140, 2025/293, 2024/1950, 2026/854, and 2026/931) named nothing that survived either the conjecture harvester or this proposal filter; the harvest ledger records the full reasoning for each.
A paper that already has a promoted conjecture on this site can still contribute a proposal here — a conjecture is one precise claim a paper poses; a proposal is a different, vaguer direction the same paper names elsewhere. They aren’t competing descriptions of the same gap.
Amey Shukla, Luke Demarest, Benjamin Fuller, Sohaib Ahmad, Caleb Manicke, Alexander Russell, Sixia Chen. Fuzzy Extractors are Practical: Cryptographic Strength Key Derivation from the Iris. CCS 2025. ePrint 2024/100.
Generalizing beyond the iris, and beyond the lab
Natural lines of future research include extending our results to different biometrics and understanding how the noise/entropy tradeoff is impacted by real-life use.
The paper’s entropy/error-rate analysis and its \(\zeta\)-sampling technique were built and validated for iris biometrics on curated datasets. Making progress here means two related but separable things: re-deriving or re-validating the noise/entropy tradeoff for other biometric modalities (face, fingerprint, ECG, and so on), and separately, characterizing how that tradeoff degrades under real deployment conditions – varying sensors, lighting, aging, population diversity – rather than lab data. Neither has a single claim attached; both are open-ended empirical and analytical programmes.
\(\zeta\)-sampling for PUF-based fuzzy extractors
We believe that \(\zeta\)-sampling could find applications in fuzzy extractors for physically uncloneable functions where confidence information is used, see for example Herder et al.
\(\zeta\)-sampling biases subset selection toward bits that are both stable (low error) and unpredictable. The authors suggest, without working out any of it, that the idea might carry over to fuzzy extractors built on physically unclonable functions (PUFs), which also produce per-bit confidence information. Progress would look like formulating a PUF-specific fuzzy extractor using \(\zeta\)-style weighting and analyzing whether it improves the key-length/reliability tradeoff over existing PUF fuzzy extractors – an idea transplant across domains, not a specific theorem.
Ghada Almashaqbeh, Sixia Chen, Alexander Russell. Competitive Policies for Online Collateral Maintenance. Cryptology ePrint Archive, Report 2024/1022.
Competitive collateral policies under condition-dependent settlement
An interesting open question is to develop competitive collateral policies that capture this setting where settling a transaction does not only depend on whether the remaining collateral \(C\) (i.e., pool liquidity) can cover it, but also on transaction-specific parameters to meet certain collateral-related conditions… We leave these questions as part of our future work directions.
Today a transaction is accepted in the paper’s model exactly when its value fits inside the remaining collateral. In automated market makers – the paper’s own motivating example – acceptance also depends on price or slippage conditions unrelated to raw collateral size, and even replenishing the pool can be conditionally rejected. The open direction is to define a model capturing these richer accept/reject rules and then re-derive competitive-ratio bounds – or show none exist – for natural online policies in it.
Adaptive, dynamic wallet and collateral policies
A potential extension to our model is considering adaptive policy management, where the size of the collateral and the number of wallets can be adjusted after each flush decision to account for these varying factors.
The current model fixes the number of wallets \(k\) and the collateral size \(C\) for the whole transaction stream and optimizes only the flush schedule. The open direction lets \(k\) and \(C\) themselves evolve in response to observed traffic, with online policies designed and analyzed for that richer, adaptive setting – a design-and-analyze programme, not a single provable statement.
Alexander Russell, Qiang Tang, Jiadong Zhu. Crooked Indifferentiability of the Feistel Construction. ASIACRYPT 2024. ePrint 2024/1456.
Multi-stage crooked indifferentiability
Ristenpart et al. has demonstrated that the replacement/composition theorem (Theorem 6) in the original indifferentiability framework only holds in single-stage settings. We remark that the same restriction also applies to our replacement/composition theorem (Theorem 7). We leave it as our future work to extend our crooked indifferentiability to the multi-stage settings where disjoint adversaries are split over several stages.
The paper’s main composition theorem lets a crooked-indifferentiable construction be swapped safely into any larger protocol, but only in “single-stage” settings, where one adversary attacks the whole system at once. Many real security games are multi-stage instead, with separate, non-communicating adversaries active at different points. The direction is a genuinely new composition theorem, or a new proof technique, that survives when attacking power is split across disjoint stages – a structural extension, not a single claim.
Broader applications and a practical construction
There are still many interesting questions remain to be explored: broader applications of crooked-indifferentiability, and whether we can have a truly practical construction.
Two open-ended invitations rather than one: finding other cryptographic constructions or settings where the crooked-indifferentiability framework itself gives useful guarantees beyond the Feistel case treated here, and whether a construction correcting a subverted (backdoored) random function can be made practically efficient rather than existing only in principle.
Peter Gaži, Zahra Motaqy, Alexander Russell. A Tight Analysis of GHOST Consistency. Cryptology ePrint Archive, Report 2024/1830.
Tight consistency analysis for proof-of-stake GHOST
Applicability to Proof-of-Stake GHOST. It is a natural and interesting question whether our analysis applies to proof-of-stake (PoS) analogues of the GHOST protocol.
The paper’s tight consistency analysis is done for proof-of-work GHOST, where block production follows a Poisson process. Proof-of-stake variants relevant to deployed systems (Ethereum’s Gasper/LMD-GHOST among them) introduce different adversarial features – notably lookahead into future lottery outcomes, and potential equivocation. The paper’s proof already handles adversarial lookahead but explicitly leaves the PoS setting, with its equivocation-mitigation mechanisms, unresolved. Progress means redoing the tight consistency-region analysis for a genuine PoS/committee-based GHOST variant, not carrying over the proof-of-work proof unchanged.
Lukas Aumayr, Jesus Diaz, Dimitar Jetchev, Aggelos Kiayias. Cardinal: Bridging Bitcoin with Ownership Preservation. Cryptology ePrint Archive, Paper 2025/2196.
Accountable peg-out
A current limitation lies in accountability during peg-out: bridge operators reveal secret keys to unlock the tokens in Bitcoin, enabling a malicious operator to potentially front-run the user. While our 1-out-of-n assumption mitigates this, a stronger solution would use multisignature shares instead of keys, allowing users to prove misbehavior. We leave this for future work.
In Cardinal’s peg-out step, an operator reveals an ephemeral private key so the user can claim their Bitcoin. Because the key is shared, once it is out nobody can tell after the fact whether the operator misused it or the user is falsely blaming the operator – the scheme has no way to pin blame. The paper gestures at a fix (replace raw key revelation with threshold or multisignature shares, so misuse leaves cryptographic evidence of who did what) but does not design, define, or prove anything about such a mechanism. Progress means building and formally defining an accountable peg-out protocol: specifying what “proof of misbehavior” means, designing the signature-sharing mechanism, and proving it achieves accountability without breaking Cardinal’s existing security and ownership-preservation guarantees.
Boaz Barak, Pravesh Kothari, David Steurer. Quantum Entanglement, Sum of Squares, and the Log Rank Conjecture. arXiv:1701.06321.
Strengthening and transplanting the sum-of-squares entanglement-detection technique
it is a fascinating open question to explore whether our techniques can be quantitatively strengthened to yield faster algorithms and/or extended for other problems such as the 2 to 4 norm and small set expansion
The paper gives a faster algorithm for detecting near-perfectly-separable quantum states via a sum-of-squares SDP. The direction is two-pronged and open-ended: push the same analysis for a better running-time exponent (no target rate is named), and separately try to transplant the technique to two structurally related problems – the 2-to-4 norm problem and small-set expansion – with no attempt at either sketched.
Boaz Barak. The Complexity of Public-Key Cryptography. Chapter in Tutorials on the Foundations of Cryptography. ePrint 2017/365.
A general theory of computational hardness
this research is still very much in its infancy, and we still do not even know the right way to formalize our conjectures, let alone try to prove them or study their implications. I do hope that eventually an explanatory theory of hardness will emerge, whether via convex optimization or other means
The survey closes by calling for a general theory explaining why certain problems are hard – built perhaps around the idea that sum-of-squares is optimal on a broad class of them. The author is explicit that nobody yet knows how to even state such a conjecture precisely. Progress would be any serious step toward formalizing what “SoS-optimality” should mean as a general principle, not a single proof.
Mohammad Etemad, Mohammad Mahmoody, David Evans. Optimizing Trees for Static Searchable Encryption. ePrint 2018/052.
Other matching heuristics for tree construction
one can also try to find other heuristic algorithms for finding the minimum (perfect) matching in weighted graphs and derive new forms of hybrid algorithms along the line of our Algorithm 3. For some of those algorithms, one might be able to prove a concrete bound on the optimality of the produced trees.
The paper’s tree-construction algorithm leans on one matching heuristic. The invitation is to try other matching heuristics, build analogous hybrid tree constructions from them, and possibly prove optimality bounds – no specific heuristic or bound is named.
Leakage from tree rearrangement
we leave further exploration of the impact of our tree rearrangements, as well as opportunities to control leakage by rearranging trees, as open problems.
The paper’s tree-optimizing and randomizing techniques change what a server can infer about queries and data, but the authors have no formal handle on what this leakage even is. Progress means working out what rearrangements actually reveal and how to design rearrangements that leak less – a definitional and empirical area, not a stated claim.
Boaz Barak, Samuel B. Hopkins, Aayush Jain, Pravesh Kothari, Amit Sahai. Sum-of-Squares Meets Program Obfuscation, Revisited. ePrint 2018/1237.
Classifying hard distributions of low-degree polynomials
More generally, understanding the structure of hard distributions for expanding families of constant-degree polynomials over the integers, is a fascinating and important area of study, which is strongly motivated by the problem of securely constructing iO.
The paper breaks specific obfuscation candidates built from low-degree-polynomial pseudorandom generators (a companion open question from the same paper is tracked as c/0044). The broader direction it names is to classify, in general, which distributions over constant-degree polynomial systems are computationally hard – a foundational mapping project much larger than any one candidate.
Sanjam Garg, Mohammad Hajiabadi, Mohammad Mahmoody, Ameer Mohammed. Limits on the Power of Garbling Techniques for Public-Key Encryption. CRYPTO 2018. ePrint 2018/555.
A general non-black-box separation for PKE from OWFs
when it comes to the case of non-black-box constructions of PKE from OWFs, no such general separations are known (and proving such results might in fact be impossible).
The paper proves a black-box separation ruling out one specific non-black-box technique (garbling) for building public-key encryption from one-way functions (a companion open question from the same paper is tracked as c/0017). The named direction is a general separation covering non-black-box techniques as a class – but the authors themselves flag that such a result might not even be obtainable, so there is no candidate technique to target, just an open area about the reach of non-black-box impossibility results.
Mohammad Mahmoody, Caleb Smith, David J. Wu. Can Verifiable Delay Functions be Based on Random Oracles?. ICALP 2020. ePrint 2019/663.
Escaping the perfect-uniqueness impossibility for VDFs
any approach for constructing VDFs in the ROM must either rely on non-black-box techniques or leverage imperfect soundness in a critical manner. Both of these possibilities represent intriguing avenues for further research.
The paper rules out perfectly-unique verifiable delay functions in the random oracle model (a companion open question from the same paper, on computational rather than perfect uniqueness, is tracked as c/0018 – now resolved). Since the impossibility argument specifically needs perfect uniqueness, it points to two unexplored escape routes for building VDFs anyway: non-black-box constructions, or constructions whose soundness is imperfect in some essential way. Neither route has a candidate construction attached.
Junbin Fang, Dominique Unruh, Jun Yan, Dehua Zhou. How to Base Security on the Perfect/Statistical Binding Property of Quantum Bit Commitment?. ePrint 2020/621.
A meaningful collapse-binding property for non-interactive commitments
We still do not know if any non-interactive quantum bit commitment based on quantum-secure one-way functions can satisfy some “meaningful” collapse-binding property that could be useful in applications yet.
Collapse-binding is a strong binding flavor known only from interactive schemes under stronger assumptions. The authors flag that no one knows whether a non-interactive scheme from plain quantum-secure one-way functions can achieve some useful analogue, without ever fixing what “meaningful” means. Progress means proposing a specific collapse-binding-style property for non-interactive commitments and either constructing a scheme meeting it or proving an obstruction.
Geoffroy Couteau, Pooya Farshim, Mohammad Mahmoody. Black-Box Uselessness: Composing Separations in Cryptography. ITCS 2021. ePrint 2021/016.
A general theory of monolithic black-box uselessness
This suggests developing a theory of monolithic uselessness, in which one can allow cross plantations of oracle calls in circuits that are given as input to both primitive P… and the auxiliary oracle Z, when these primitives have the properties that allows them to be monolithically extended. We leave the exploration of such lines of work, as an extension of black-box uselessness, for future work.
The paper’s black-box-uselessness results (three companion open questions from this paper are tracked as c/0019, c/0020, c/0021) are proved in the standard oracle-separation model, but the primitives it studies also admit a stronger “monolithic” model where circuits given to the primitive can call the primitive’s own oracle gates. The authors observe their results already survive this strengthening case by case, and invite building a general theory of uselessness in the monolithic setting rather than checking instance by instance.
Dominique Unruh. Compressed Permutation Oracles. ePrint 2021/062. Note: an erratum on the paper’s own front page withdraws its headline theorems (a flawed step breaks the argument, including the SHA3 collision-resistance result); reportedly re-established by later work, not independently checked here.
Simulator-based proofs for compressed permutation oracles
it is not clear how to efficiently simulate a random permutation, nor how to measure what oracle positions have been queried or how to otherwise perform actions that depend on the oracle queries performed so far. In particular, we do not know how to make indifferentiability proofs (or similar proofs involving simulators that “look inside” the random oracle). Overcoming these hurdles is an interesting open problem.
Independent of whether this specific paper’s bounds hold, the underlying gap is real: unlike Zhandry’s original compressed oracle for functions, the permutation version has no canonical basis for measuring or conditioning on what has been queried, so indifferentiability-style proofs (which need a simulator that looks inside the oracle) don’t carry over. Progress means developing a representation or measurement scheme that supports them.
Bernardo Magri, Giulio Malavolta, Dominique Schröder, Dominique Unruh. Everlasting UC Commitments from Fully Malicious PUFs. Journal of Cryptology 2022. ePrint 2021/248.
Adaptive corruptions for everlasting UC commitment from malicious PUFs
We leave the case of adaptive corruptions, in which the environment may corrupt any party adaptively during the execution of the protocol as an interesting open problem.
The paper’s construction and simulation (a companion open question from this paper, on removing the CRS, is tracked as c/0035) are argued only against a static adversary, who commits to which parties it corrupts before the protocol runs. Progress means handling an adversary that decides whom to corrupt on the fly – a strictly harder simulation problem with no stated obstruction, just an unaddressed strengthening of the security model.
Per Austrin, Hao Chung, Kai-Min Chung, Shiuan Fu, Yao-Ting Lin, Mohammad Mahmoody. On the Impossibility of Key Agreements from Quantum Random Oracles. CRYPTO 2022. ePrint 2022/218.
Three directions, alongside a companion open question from this paper tracked as c/0022 and a related conjecture at c/0023:
Reusing the quantum heavy-queries learner for other QROM separations
Our quantum-heavy query learner could pave the way for proving more separations in the quantum random oracle model.
An open invitation to reuse the paper’s new technical tool – a quantum heavy-queries learner – to attack other QROM separation questions the paper doesn’t specify.
Communication-complexity lower bounds for QROM key agreement
It is interesting to see whether their techniques can be combined with ours to prove similar lower bounds on the communication complexity of key agreement in the QROM model.
Splices this paper’s attack techniques with a separate communication-complexity framework (Haitner et al.), with no target bound named.
Relating the Polynomial Compatibility and Aaronson–Ambainis conjectures
our conjecture and the AA conjecture do not seem to be directly comparable, and it would be interesting to prove implications in either direction between them.
Asks whether this paper’s own Polynomial Compatibility Conjecture and the separately-known Aaronson-Ambainis conjecture imply one another, without picking a direction or a proof strategy.
José Bacelar Almeida, Denis Firsov, Tiago Oliveira, Dominique Unruh. Leakage-Free Probabilistic Jasmin Programs. CPP 2025. ePrint 2023/1514.
Leakage-freeness for possibly-divergent programs
lifting it to a sensible notion of leakage-freeness of possibly divergent programs would force us to move to a termination-sensitive characterization of non-interference in EC, which we left as future work.
The paper’s framework assumes termination is checked separately, sidestepping programs that might loop forever while leaking secrets through how long they run. Progress means inventing a workable definition of leakage-freeness that accounts for divergence itself, then encoding it in EasyCrypt – a definitional and formalization programme with no candidate definition yet.
Jaiden Fairoze, Sanjam Garg, Somesh Jha, Saeed Mahloujifar, Mohammad Mahmoody, Mingyuan Wang. Publicly-Detectable Watermarking for Language Models. CIC 2024. ePrint 2023/1661.
The theoretical limits of publicly-detectable watermarking
it would be interesting to uncover the theoretical limitations of what properties a publicly-detectable watermark could hope to achieve.
Characterize, in general, which combinations of properties – robustness, distortion-freeness, detectability – a publicly-detectable watermark can simultaneously achieve: a “map the possibility space” question, not a single theorem.
New robustness notions for publicly-detectable watermarks
future work could seek to bring down the concrete complexity of an edit-distance robust watermark or develop new techniques that permit other notions of robustness.
Invents techniques for robustness properties beyond edit-distance robustness, with no specific notion named.
Abtin Afshar, Geoffroy Couteau, Mohammad Mahmoody, Elahe Sadeghi. Fine-Grained Non-Interactive Key-Exchange: Constructions and Lower Bounds. EUROCRYPT 2023. ePrint 2023/571.
3-party NIKE from non-pairing algebraic assumptions
our result is a natural first step towards proving a stronger negative result for a basic question of whether 3-NIKE can be based merely on simple algebraic assumptions without pairing.
The paper’s lower bound (companion open questions from this paper are tracked as c/0024 and c/0025) only rules out 3-party NIKE in Maurer’s weak generic-group model. It explicitly frames its result as one step toward a much broader, unformalized question – whether any non-pairing algebraic assumption can support 3-party NIKE at all.
José Bacelar Almeida, Denis Firsov, Tiago Oliveira, Dominique Unruh. Schnorr Protocol in Jasmin. ePrint 2023/752.
Applying leakage-freeness definitions to Kyber
We believe that our new definitions of leakage-freeness would come in handy especially because Kyber is a probabilistic algorithm which also makes use of rejection sampling.
The paper introduces new EasyCrypt leakage-freeness definitions for Schnorr’s rejection sampling, then suggests – without attempting it – that the same definitions could characterize whether Kyber’s own rejection-sampling implementation leaks.
Dominique Unruh. Towards Compressed Permutation Oracles. ASIACRYPT 2023. ePrint 2023/770.
Alongside the CPO-soundness question tracked as c/0036 (open) and its corollaries c/0037 and c/0038 (resolved), three further directions:
Post-quantum security of permutation-based hashing
we do not know anything about the post-quantum security of cryptosystems built from invertible permutations, such as the industry-standard SHA3.
The paper frames its own CPO conjecture as merely a first step toward closing this gap. Progress on the full direction means establishing any post-quantum security property – collision-resistance, collapsing, or indifferentiability – for sponge-type constructions like SHA3 against quantum adversaries.
A workable decompression operator for permutations
it might be possible to find some operator that approximately implements CFO^perm and that has an easy description and that does not grow the state too much during a query. But we were unable to find such an operator.
The desiderata are named (simple description, bounded state growth) but no candidate operator is known.
maybe this approach is also one way to extend the compressed oracle technique to more complex cases such as oracles with non-independently chosen outputs or similar. We did not manage to use it for the random permutation case, but maybe future work will.
An explicitly speculative direction with no attached technique.
Abtin Afshar, Kai-Min Chung, Yao-Ching Hsieh, Yao-Ting Lin, Mohammad Mahmoody. On the (Im)possibility of Time-Lock Puzzles in the Quantum Random Oracle Model. ePrint 2023/932.
Extending QROM time-lock-puzzle impossibility to VDFs
It is possible that using (a generalization of) our techniques one could extend our impossibility results to such classes of VDFs as well, though we leave this exploration for the full version of this paper.
The paper’s QROM impossibility results are proved for time-lock puzzles specifically (a companion open question from this paper is tracked as c/0028); verifiable delay functions are a closely related sequential primitive for which analogous impossibilities are known classically. The paper names no obstruction to the generalization, only that the exploration itself is left for later.
Sam Buxbaum, Mohammad Mahmoody. A Note on the Minimality of One-Way Functions in Post-Quantum Cryptography. IACR CiC 2024. ePrint 2024/2095.
Post-quantum minimality for other primitives
For other complicated primitives, it remains open to study their minimality in the post-quantum world (for the appropriate class of primitives).
The paper proves one-way functions minimal post-quantumly for one named case (signatures; a companion open question on non-black-box reductions is tracked as c/0029). It explicitly leaves undefined which further primitives, or what “appropriate class” even means, beyond that one case.
Sandro Coretti, Matthias Fitzi, Aggelos Kiayias, Giorgos Panagiotakos, Alexander Russell. High-Throughput Permissionless Blockchain Consensus under Realistic Network Assumptions. CRYPTO 2025. ePrint 2025/1115.
Porting DAG-based BFT protocols to the permissionless, adaptive setting
the above protocols are designed for the permissioned setting and would have to be adapted suitably to work in a permissionless environment while retaining adaptive security, which appears non-trivial… one needs to show that they remain secure in the QUEQ model, and if they are not, determine whether they can be suitably adapted.
The paper names a concrete route (player replaceability plus sortition) but carries it out for none of the standard DAG/BFT protocols (Narwhal/Bullshark, Mir-BFT, Prism, and so on). Progress means picking one, formalizing its permissionless adaptation, and proving or disproving security in the paper’s own network model.
Matthias Fitzi, Aggelos Kiayias, Laurent Michel, Giorgos Panagiotakos, Alexander Russell. Efficient and Proof-of-Useful-Work Friendly Local-Search for Distributed Consensus. ePrint 2025/2091.
A compact, on-chain-postable certificate of ML training work
The same does not hold for deep neural networks models (with many millions of weights) typical of modern machine learning to prove completion of work and disseminate these results to peers is infeasible with current on chain storage capacities. Addressing this challenge is an open question.
The paper’s framework needs a computational proof-of-work state compact enough to post on-chain; local search satisfies this, but ML training does not, since model weights run to millions of parameters. No candidate certificate design is offered.
Marian Dietz, Julia Kastner, Stefano Tessaro. On the Impossibility of Round-Optimal Pairing-Free Blind Signatures in the ROM. CRYPTO 2026. ePrint 2026/090.
Bypassing the round-optimality barrier with a non-group assumption
a potential avenue to bypass our impossibility result is to introduce additional computational assumptions unrelated to the group.
The paper proves round-optimal pairing-free blind signatures impossible in the generic-group-plus-random-oracle model (a companion open question from this paper is tracked as c/0013). This gestures at a way out – some hardness assumption disconnected from the group structure – without naming a candidate.
Alexandru Cojocaru, Aggelos Kiayias, Yu Shen, Petros Wallden. Proactive Secret Sharing without Erasures. ePrint 2026/1072.
Direct, specialized constructions for threshold signatures and encryption
we anticipate that focusing to specific threshold primitives, such as signatures or threshold encryption, may enable more efficient constructions or using weaker assumptions. While out of scope for the present work, this is an interesting direction for future work.
The paper’s constructions (a companion open question from this paper is tracked as c/0039) go through a general “secret usability” abstraction rather than building threshold signatures or decryption directly. No efficiency target or crisp claim is named for the specialization.
Damiano Abram, Marshall Ball, Juan Garay, Aggelos Kiayias. Permissionless Consensus from a Common Random String. CRYPTO 2026. ePrint 2026/1179.
Section 5 of the paper, “Extensions and Open Questions,” names three directions alongside the companion open questions from this paper tracked as c/0040 and c/0041:
A seeded proof-of-work compatible with distributed samplers
A potential means for mitigating this would be to use a seeded proof of work as defined by Ball et al. Unfortunately, the stretch and soundness of their construction is incompatible with the loss encountered with distributed samplers.
The protocol’s messages are as long as the party-count bound; shrinking them needs a seeded-PoW variant whose parameters actually fit this setting, which the known construction’s don’t.
Sequential composition and dynamic difficulty adjustment
The sequential composition of multiple instances of our consensus problem is another interesting direction for future work. Of particular interest also would be to eliminate the need for continuously providing an upper bound on the number of parties and allow the parties/protocol to dynamically adjust the PoW difficulty…
Two linked goals: running many instances of the protocol back-to-back safely, and removing the requirement that parties know an upper bound on how many participants exist.
Removing the CRS and minimizing assumptions
two pivotal questions for future work are to (a) remove all setup and show feasibility in the plain model (without a CRS), and (b) to minimize assumptions. Accomplishing either of these goals will require novel ideas.
Both goals are named with no partial approach offered, and the authors themselves flag that either will need genuinely new ideas.
Marc Roeschlin, Evangelos Markakis, Raghav Bhaskar, Aggelos Kiayias. Incentivizing Geographic Diversity for Decentralized Systems. FC 2026. ePrint 2026/758.
Collusion that harms rather than profits
future work should consider colluding behaviors where dishonest players undermine honest participants without gaining a direct reward.
The paper’s collusion-resistance analysis is entirely utility-based: a dishonest coalition is modeled as trying to avoid detection for reward. This asks what happens when attackers act to harm honest participants rather than to profit – an adversary type the reward-based game can’t represent, so answering it means building a different model.
A multi-tiered, richer strategy space
a multi-tiered system and a richer strategy space… including multiple spoofing targets.
Generalizes the paper’s binary honest/dishonest choice, with no specific target statement.
Kaijie Jiang, Stefano Tessaro, Hoeteck Wee, Chenzhi Zhu. Tweed: Adaptively Secure Lattice-Based Two-Round Threshold Signatures. EUROCRYPT 2026. ePrint 2026/417.
Identifiable abort for Tweed
we do not achieve identifiable abort – some recent works reiterate that this can be quite complex in the lattice setting, and defer investigating achieving it to future work.
Distinct from the resolved open question from this paper tracked at c/0046. Identifiable abort lets participants pin blame on whichever party caused a threshold-signing session to fail; recent lattice papers show how to get it in other schemes, but grafting that machinery onto Tweed’s specific two-round construction without breaking its adaptive security or communication profile is unattempted here.
Pyrros Chaidos, Pooya Farshim, Denis Firsov, Dimitar Jetchev, Aggelos Kiayias, Markulf Kohlweiss, Anca Nitulescu. Crossing with Confidence: Formal Analysis and Model Checking of Blockchain Bridges. ePrint 2026/292.
A meaningful SPV-style bridge in the paper’s formal model
It remains an open question whether relaxing xcVal and other DO bridge components can yield a secure and meaningful SPV-style bridge in our formal model.
The paper’s framework validates bridges against the sender chain’s full state; SPV-style light-client bridges only check proof-of-work validity, a much weaker check. “Meaningful” is left undefined by the paper, so the first step is formulating the right restricted definition, not proving anything against an existing one.
Further security notions in the same formal framework
other notions of security can be formulated using the approach we put forth here.
An open invitation to extend the paper’s definitional framework to properties it doesn’t name (censorship-resistance, fairness, and so on), with no candidate definition offered.
Rutchathon Chairattana-Apirom, Nico Döttling, Julian Loss, Stefano Tessaro, Benedikt Wagner. Tight Lattice-Based Signatures without Trapdoors from Search LWE. CRYPTO 2026. ePrint 2026/953.
A tight QROM proof from a search assumption
obtaining a tight proof from a search assumption for a Fiat-Shamir-like signature in the QROM remains an important open question.
Distinct from the open question from this paper tracked at c/0047. The paper’s tightness result holds only against a classical random oracle; a quantum adversary querying the hash in superposition is out of scope, and the paper notes the question is only interesting up to an efficiency threshold it doesn’t itself pin down.
Extending tightness to the multi-user setting
Extending our results to the multi-user setting is an important avenue for future work.
Whether the tight single-key reduction survives when many users share a random oracle and an adversary can attack any of them, without the security loss degrading with the number of users.
Raghav Bhaskar, Pooya Farshim, Matthias Fitzi, Aggelos Kiayias. Beyond Blockchain Ballots: UC-Secure Layer-2 Voting and Governance. CSF 2026. ePrint 2026/1521.
UC realizations with many bulletin-board managers
Our F_BB already models more than one bulletin-board manager, but we leave its UC realizations with many BBMs for future work.
The protocol is proved secure only for a single, trusted bulletin-board manager; decentralizing this role, so no single manager can silently drop votes, is named with no obstruction given and no candidate protocol sketched.
Modeling monetary stakes and a game-theoretic incentive analysis
An extended ideal functionality that models the monetary aspects of the protocol (e.g., slashing of funds)… We leave this treatment (together with game-theoretic analysis) to future work.
Two open, unspecified deliverables: a richer definition tying voting misbehavior to on-chain stakes and penalties, and a game-theoretic argument that the resulting incentives actually discourage cheating.
Eliana Carozza, Geoffroy Couteau. On Threshold Signatures from MPC-in-the-Head. IACR ePrint Archive 2024/1897.
Grand unification of MPC-in-the-Head and VOLE-in-the-Head
We believe that it would be possible in theory to have a “grand unification” of all MPC-in-the-Head and VOLE-in-the-Head security analyses in a general formal framework, and from there to provide a formal generic way to derive a CEUF-CMA threshold-friendly scheme and an accompanying threshold signing protocol. However, coming up with such a grand unification framework is out of the scope of this work (and we expect it to be challenging, to say the least).
The paper’s own recipe for turning an MPC-in-the-Head signature into a threshold-friendly one is worked out case by case, against specific base schemes. The direction is a single formal framework covering both the MPC-in-the-Head and VOLE-in-the-Head families at once, from which the threshold-friendly transform and its security proof would fall out generically rather than being re-derived per scheme – a unification programme, not a single claim.
Antonina Bondarchuk, Olive Chakraborty, Geoffroy Couteau, Renaud Sirdey. Downlink (T)FHE Ciphertexts Compression. IACR ePrint Archive 2024/1921.
Rescaling before truncation for BGV, BFV, and CKKS
It is worth mentioning that the RLWE ℓ-truncation technique can be applied to BGV, BFV, and CKKS RLWE ciphertexts. As these FHE cryptosystems use composite ciphertext modulus, it is natural to think of reducing it via rescaling before applying ℓ-truncation and sending the final result to the client. We leave this idea as a perspective for future explorations.
The paper’s truncation compression technique is developed for schemes with a single-modulus ciphertext. Adapting it to composite-modulus schemes (BGV, BFV, CKKS) by first rescaling down to a smaller modulus and then truncating is named as a natural next step, with no analysis of how much compression the combination would actually buy or whether rescaling first costs anything elsewhere.
Compression for partially-filled RLWE ciphertexts
As a perspective, developing compression techniques practically applicable to partially-filled evaluated RLWE ciphertexts is an interesting follow-up research question.
The paper’s own compression technique assumes a fully-packed ciphertext; using the naive fix on a partially-filled one would require padding to full size first, which the paper notes would most likely cancel the benefit. A technique that compresses a partially-filled ciphertext directly, without that padding tax, is left unexplored.
Yevgeniy Dodis, Daniel Jost, Shuichi Katsumata, Thomas Prest, Rolfe Schmidt. Triple Ratchet: A Bandwidth Efficient Hybrid-Secure Signal Protocol. IACR ePrint Archive 2025/078; EUROCRYPT 2025.
Bit-dropping on the encapsulation key
Lastly, note that similarly to Kyber, we do not perform bit-dropping on the encapsulation key. Since this seems to require a non-trivial analysis, unlike the simpler bit-dropping on the ciphertext, we leave this optimization for future work.
Katana’s bit-dropping optimization shrinks the ciphertext by discarding low-order bits of certain coefficients, but the paper does not attempt the same trick on the encapsulation key, flagging (without elaborating) that the correctness/security analysis would be more involved there. The direction is working out that harder analysis and applying bit-dropping to the encapsulation key too, for a further reduction in Triple Ratchet’s total message size.
Yevgeniy Dodis, Bernardo Magri, Noah Stephens-Davidowitz, Yiannis Tselekounis. Guarding the Signal: Secure Messaging with Reverse Firewalls. IACR ePrint Archive 2025/1172; CRYPTO 2025.
A subversion-resilient post-quantum X3DH
We leave the construction of a subversion-resilient PQ-X3DH as future work.
The paper’s firewall-friendly key-exchange handshake is a (subversion-resilient) variant of X3DH built on classical Diffie-Hellman-style assumptions. A post-quantum analogue – one that keeps the reverse-firewall subversion-resilience guarantee while relying only on post-quantum assumptions – is named as future work with no candidate construction sketched.
Firewall rerandomization under an additional encryption layer
We note that, in the presence of an additional layer of encryption, such as TLS, it is not straightforward how the firewall would rerandomize the traffic, and we leave this as an interesting open problem.
A reverse firewall works by rerandomizing the ciphertexts and messages a (possibly compromised) party sends, so subverted randomness cannot leak. When the traffic is wrapped in an outer encryption layer such as TLS, the firewall no longer has plaintext access to rerandomize against, and the paper leaves open how – or whether – a firewall can still do its job in that setting.
Lea Thiemt, Paul Rösler, Alexander Bienstock, Rolfe Schmidt, Yevgeniy Dodis. Generic Anonymity Wrapper for Messaging Protocols. IACR ePrint Archive 2025/1619; ACM CCS 2025.
Modifying the Double Ratchet directly for anonymity
For avoiding redundancy, it remains an interesting open problem to modify messaging protocols like the DR directly for offering anonymity.
The paper’s generic wrapper adds anonymity to an existing messaging protocol (such as the Double Ratchet) from the outside, at the cost of some redundant computation the wrapper and the wrapped protocol both do. Building anonymity into a protocol like the Double Ratchet directly, rather than wrapping it, is named as the natural way to remove that redundancy, with no design sketched for how.
Anonymity guarantees beyond message content
Our work is only effective with further, complementary measures for comprehensive anonymity and it provokes future research in multiple directions. This includes anonymous contact discovery and communication initialization, routing that leverages the guarantees of our constructions for fully (i.e., not only sender-)anonymous messaging, anonymous session synchronization in multi-device settings, or plausible anonymity in the broader messaging app environment, which includes hiding contacts in the address book.
The paper’s wrapper anonymizes message content and metadata within an established session, but the surrounding infrastructure – discovering contacts, initiating a session, synchronizing state across a user’s several devices, and the messaging app’s own address book – can still deanonymize a user even when every message itself is protected. Each named gap is its own construction-and-definition task, not a single statement.
Benedikt Auerbach, Yevgeniy Dodis, Daniel Jost, Shuichi Katsumata, Rolfe Schmidt. How to Compare Bandwidth Constrained Two-Party Secure Messaging Protocols: A Quest for A More Efficient and Secure Post-Quantum Protocol. Cryptology ePrint Archive 2025/2267.
Session-handling in the vulnerable-message-set methodology
Investigating the effect of session-handling to our methodology remains an interesting open problem.
The paper’s vulnerable-message-set framework for comparing secure-messaging protocols assumes a single, uninterrupted session; it does not account for protocols that must recover after a party’s session state is lost or reset. Extending the methodology to handle session-handling and state-loss resilience, in the style of Cremers et al.’s analysis of Signal’s own session layer, is left as its own investigation.
Capturing root-key forward secrecy in the vulnerable-message-set metric
The translation from vulnerable epochs to vulnerable messages captures neither the forward-secrecy gained by including the root key in the key schedule, nor the maintained security of the root chain under insecure updates. While we consider addressing this shortcoming an interesting open question for future work…
The paper’s own metric for comparing secure-messaging protocols, built by translating an underlying key-agreement scheme’s vulnerable epochs into vulnerable messages, is acknowledged to systematically undercount protection: it misses forward secrecy the root key itself provides, and security the root chain retains even after an insecure update. A refined translation that captures both effects is left open.
James Bartusek, Nir Bitansky, Yevgeniy Dodis, Rachit Garg, David J. Wu. Fair-Weather No More: Guaranteed Efficiency in Secure Group Messaging. IACR Cryptology ePrint Archive 2026/1677.
CGKA security against fully active adversaries
We remark that the security of CGKA against active adversaries has some history of study in the “TreeKEM” paradigm, and extending the security of our DBE paradigm to active adversaries remains an important direction for future work… we leave the formalization of this claim and extension to security against more powerful active adversaries to future work.
The paper’s security model tolerates only a limited form of active behavior (message dropping and delaying); it conjectures, without proof, that its protocol also resists reordering attacks, and leaves both the formalization of that claim and a security model covering genuinely active adversaries – who can inject or modify messages, not merely delay them – as future work.
Per-party storage independent of group size
In contrast, our incremental DBE scheme has the property that each party in principle only needs to store its own aggregated key and not the complete set of public keys for all group members. However, doing so would require relaxing some security guarantees in the resulting CGKA and we do not explore this optimization here.
The paper’s CGKA constructions have every party locally store the full roster of the group’s public keys, even though its underlying incremental broadcast-encryption primitive does not strictly require this. Dropping that requirement to get per-party storage independent of group size is flagged as possible only at the cost of weakening some (unspecified) security guarantee, and the resulting trade-off is not worked out.
Yevgeniy Dodis, Shachar Lovett, Daniel Wichs. Locally Computable High Independence Hashing. IACR Cryptology ePrint Archive 2026/622.
Unifying bit-local and word-local hash constructions
Currently we have two separate but related constructions for almost independent hashing: one for bit-local hash functions and one for word-local hash functions. It would be nice to unify them into a single construction that works for all word sizes \(1 \le w \le n^2\).
The paper builds its almost-\(k\)-wise-independent hash families two different ways depending on the word size regime, rather than from one construction spanning every word size. A single unified construction covering the whole range – including the intermediate word sizes where, as c/0066 records, no matching construction of either kind is currently known – is named as a desirable simplification, distinct from that page’s own question of narrowing the locality gap itself.