Sela Navot

Starting from OpenAI’s October 2026 proof over ℂ, my Codex extended the upper bound of 9/4 on the matrix multiplication exponent to arbitrary fields and associative unital rings. This gives the clean theorem ω ≤ 2.25, the best known general bound as of October 2026.

Everything is AI-generated, and the proofs are verified in Lean. Both results have been accepted into the Palomar Registry (fields, rings).

I’m working through the concepts and proofs and preparing a human-readable tutorial. I’m no expert in computational algebra, so this will take some time. If you’d like to collaborate, do get in touch!

Secure multi-party computation (MPC) lets several parties jointly evaluate a function of their private inputs while learning nothing beyond the result. SPDZ is a widely used family of MPC protocols in the malicious security setting. Its security rests on the following invariant: every piece of preprocessing used in a computation must be generated under one shared authentication key. In principle, the preprocessing protocols enforce this invariant internally. We first show that a broken invariant enables a simple selective-failure attack that leaks an honest party's secret inputs. We then show that leading implementations fail to enforce it, letting a corrupted party present different keys across threads or runs and mount a practical attack.

Digital signatures are typically required to be existentially unforgeable (EUF), ensuring that no adversary can produce a valid signature on a new message that has not been signed before. A stronger notion, strong unforgeability (SUF), also ensures that adversaries cannot forge new signatures on messages that have already been signed. These notions are well understood for plain signatures, but defining them for distributed multi-signature protocols, where multiple signers jointly produce a signature via an interactive protocol, is more challenging. While EUF has been studied for multi-signatures (using multiple competing definitions), there is no general definition for SUF, even though multi-signature protocols are often used to produce strongly unforgeable plain signatures.

This thesis introduces one-more unforgeability (OMUF) as a convenient way to model SUF in distributed signing protocols, and arrives at the following conclusions:

• MuSig and Bellare-Neven multi-signatures satisfy OMUF, even when the first signing round is pre-processed before the message to sign is known, but become completely insecure if the second signing round is also pre-processed.
• MuSig2 satisfies OMUF, which is important due to its widespread use in Bitcoin.
• The HBMS and mBCJ schemes do not satisfy OMUF, despite the fact that both schemes distributively generate strongly unforgeable plain signatures. Additionally, our analysis reveals an issue with the existential unforgeability of mBCJ, which does not contradict its original security proof.

GUI-based web agents navigate websites by analyzing screenshots rather than HTML, offering a more intuitive approach to web interaction. However, this reliance on visual input introduces new threats, particularly during the visual grounding phase, where agents locate interface elements. We show that visual grounders can be reliably fooled by adversarially crafted third-party ads, even on otherwise trusted websites. Our attacks include Naive Confusion, which mimics real elements to mislead the agent, and an Invisible Attack, which hides perturbations in ads that appear normal to human users. These attacks require no control over the host site and minimal knowledge of the agent’s task, making them both practical and scalable.

Multi-signature schemes in pairing-free settings require multiple communication rounds, prompting efforts to reduce the number of signing rounds that need to be executed after the signers receive the message to sign. In MuSig and Bellare-Neven multi-signatures, the signing protocol does not use the message until the third (and final) signing round. This structure seemingly allows pre-processing of the first two signing rounds before the signers receive the message. However, we demonstrate that this approach compromises security and enables a polynomial time attack, which uses the algorithm of Benhamouda et al. to solve the ROS problem.