Sela Navot

Randomly permuting secret data vectors is a core building block in many privacy-preserving protocols, including those for analytics, advertising, and communication. Existing approaches either rely on computation-heavy public key cryptography and zero-knowledge proofs or scale poorly for large vectors due to use of a quasilinear-sized permutation network. This work presents a preprocessing approach to enable fast linear-time online shuffles in the malicious-secure two-party computation (2PC) setting. We propose FLOSS, a 2PC protocol for securely computing any interactive arithmetic permutation circuit, a notion we introduce to capture how higher level protocols are built on secret-shared field arithmetic and permutations. We show how secret-shared sorting (a subprotocol in data analytics) can be described as an arithmetic permutation circuit, and can thus be compiled to an efficient online 2PC protocol using FLOSS. Our implementation and evaluation confirm FLOSS performs online shuffles fast: shuffling 2²⁰ elements in under 500ms, greater than 800× faster than state-of-the-art alternatives.

This paper initiates the study of one-more unforgeability for multi-signatures and threshold signatures as a stronger security goal, ensuring that ℓ executions of a signing protocol cannot result in more than ℓ signatures. This notion is widely used in the context of blind signatures, but we argue that it is a convenient way to model strong unforgeability for other types of distributed signing protocols. We provide formal security definitions for one-more unforgeability (OMUF) and show that the HBMS multi-signature scheme does not satisfy this definition, whereas MuSig and MuSig2 do. We also show that mBCJ multi-signatures do not satisfy OMUF, as well as expose a subtle issue with their existential unforgeability (which does not contradict their original security proof). For threshold signatures, we show that FROST satisfies OMUF, but ROAST does not.

This paper proposes POPSTAR, a new lightweight protocol for the private computation of heavy hitters, also known as a private threshold reporting system. In such a protocol, the users provide input measurements, and a report server learns which measurements appear more than a pre-specified threshold. POPSTAR follows the same architecture as STAR (Davidson et al., CCS 2022) by relying on a helper randomness server in addition to a main server computing the aggregate heavy hitter statistics. While STAR is extremely lightweight, it leaks a substantial amount of information, consisting of an entire histogram of the provided measurements (but only reveals the actual measurements that appear beyond the threshold). POPSTAR shows that this leakage can be reduced at a modest cost (~7x longer aggregation time). Our leakage is closer to that of Poplar (Boneh et al., S&P 2021), which relies however on distributed point functions and a different model which requires interactions of two non-colluding servers to compute the heavy hitters.

I’ve been experimenting with state-of-the-art AI models and Lean. Starting from OpenAI’s October 2026 proof that ω ≤ 2.25 over the complex numbers, my Codex extended the bound to arbitrary fields and then arbitrary associative unital rings. The proofs and manuscripts are AI-generated, with the proofs checked in Lean.

As of October 2026, this is the best known general upper bound on the matrix multiplication exponent over fields and rings.

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.