Skip to content

Review Fiat-Shamir construction #529

Open

Description

@kevaundray

Tracking issue for reviewing and updating the fiat shamir construction.

@khovratovich noted that the duplex construction looks insecure, and we can likely get an efficient secure version

Activity

  1. kevaundray commented on Oct 7, 2026

    @kevaundray
    CollaboratorAuthor

    From Dmitry: "Implement the duplex interface using the Blake2s/2b hash/compression functions . Support long absorb-squeeze patterns. Optimize for the total compression function calls. Prefer a construction yielding 128 bits of provable security in the [CO25] or [SAFE] paradigms"

  2. mal1keth commented on Nov 11, 2026

    @mal1keth

    I'd like to help with this on main, but I first want to understand what is left.

    As far as I can tell from git, the issue is older than main's current transcript. #552, #607 and #620 reworked the BLAKE2s one on riscv-exploration, and main got its Keccak-f[1600] duplex later, in #636. Since Nov 9 there is also formal/. As I read formal/statement.tex, it proves knowledge soundness of a Lean transcription of the verifier in the random-permutation model, duplex included (LeanVM.knowledgeSoundness_holds), and the Rust is tied to that transcription by differential tests. Does that close this issue for main? Or is it about riscv-exploration's transcript?

    Two notes from reading the transcript:

    • The duplex has one non-injectivity. A permutation forced by a fifth absorbed scalar is the same permutation as a challenge drawn with four scalars waiting. I brute-forced all operation sequences up to length 11 and found no other. The Lean handles it by decoding each permutation from the verifier program's position (formal/lean_vm/LeanVM/Protocol/Compile/Rom/Decode.lean), but the spec's §8 doesn't mention it. Would a sentence there be welcome?
    • formal/statement.tex lists programs that evaluate their own proof's Fiat-Shamir duplex (the KRS25 setting) and soundness across recursion levels as not proved. The deployed guest does evaluate Keccak-f, including to recompute its children's challenges. KRS25's attack runs GKR, with no committed trace, over a circuit general enough to compute the hash. leanVM's uncommitted-trace GKRs are the bus's grand products, which their Remark 3 sets aside, and the Keccak-f circuit, which commits a state every 12 rounds. If it would help, I can write up how far their attack is from that.

    Last, which construction was the original concern about: #523's step on riscv-exploration, main's BLAKE2s chain at the time, or duplex challengers in general?

    Notes, with the brute force and the measurements: mal1keth/leanVM .contrib/529-analysis.md

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions