F-SFE — Two-party secure function evaluation

F-SFE (Two-party secure function evaluation) is part of Secret Sharing and MPC in the UC functionality encyclopedia. Status: a canonical, well-established UC functionality.

No box is printed for this under this name, and this page says so rather than inventing one. It is the first entry on the site in that state, and the reason to have it is that “the definition is folklore” is a real finding about the literature — one a reader is entitled to before they go looking.

Secure function evaluation is the subject of the papers cited below, not an object in them. Yao asked the question, Goldreich, Micali and Wigderson answered it in general, and Canetti, Lindell, Ostrovsky and Sahai brought it into the UC framework — but none of the three prints a functionality called \(\mathcal{F}_{\textsc{sfe}}\). What the UC paper prints instead are the pieces it builds with, and its general result is stated as a theorem about arbitrary well-formed functionalities rather than as a single box.

Why there is no box

The harvest, and what it found. scripts/uc_source.py resolved every reference on this page and scanned each paper’s text layer for interface boxes. Canetti, Lindell, Ostrovsky and Sahai prints five: \(\mathcal{F}_{\mathsf{bc}}\), \(\mathcal{F}_{\mathsf{cp}}\), \(\mathcal{F}_{\mathsf{mcom}}\), \(\mathcal{F}_{\mathsf{ot}}\) and \(\mathcal{F}_{\mathsf{zk}}\) — and no \(\mathcal{F}_{\mathsf{sfe}}\). The record is in _src/sources.json. Yao 1982 and Goldreich–Micali–Wigderson 1987 print none at all, which is expected: both predate ideal-functionality notation by a decade or more, exactly as F-OT’s Rabin reference does.

And this is not an extraction failure. Three of the false negatives this encyclopedia has hit were mechanical — a name set with a diacritic, a page id naming two functionalities, a paper whose glyphs do not survive the text layer. None applies here: the UC paper’s extracted prose is clean, and its five boxes were found and read. Two of them, F-CP and F-MCOM, are written up on this site from that very paper.

Why the paper does not print one. Its general feasibility result is a compiler: commit-and-prove suffices to realize any well-formed multi-party functionality, by way of zero knowledge and the one-to-many transformation. Stated that way, there is nothing to draw a box around — the theorem quantifies over functionalities instead of exhibiting one. A two-party SFE box would be an instance of the conclusion, not a premise of the argument, and the paper had no need to write it down.

What the closest printed things are

  • A general-purpose evaluation box does exist elsewhere, and it is now written up here. Katz, Maurer, Tackmann and Zikas print both an SFE and a reactive-MPC functionality in their treatment of synchronous computation, each parameterized by a round schedule with per-party delays. Those are F-fairSFE and F-MPC as of 23 August 2026. Neither retires this page: both arrive loaded with synchrony machinery this page’s title does not imply, both are \(n\)-party rather than two-party, and the round budget is a parameter a bare two-party SFE box would not carry. What they do settle is that the absence recorded here is an absence in the papers this page cites, not in the literature.
  • The pieces are all here. F-CP, F-COM, F-ZK and F-OT are written, each from a printed source. Anyone wanting to use two-party SFE in this framework composes those; anyone wanting to cite a definition of it needs one of the two options below.

What would resolve this

Two honest routes, and they are different pieces of work:

  1. Find a paper that prints it. A forward search for a UC-framework paper that writes down a two-party SFE functionality under that name — not a compiler theorem, not a synchronous variant with a round schedule. If one exists, this page becomes an ordinary entry. The three references below are not that paper, and the harvest establishes it rather than assuming it.
  2. Decide the encyclopedia does not need the slot. If two-party SFE is genuinely the conclusion of a compiler rather than an assumption anybody hybridizes against, the page may be better retired than filled. That is an editorial decision about what the 104 slots are for, and it is not one a transcription can make.

Until one of those happens, this page’s definition field reads No canonical definition, which scripts/uc_status.py treats as a claim a human may write and a script may not — the one status value it will not derive, precisely because it is an assertion about the literature.

Formal artifacts

No machine-checked formalization yet, and none is possible before there is a definition to formalize.

References:

  • Canetti, Lindell, Ostrovsky, and Sahai. Universally composable two-party and multi-party secure computation. In 34th ACM Symposium on Theory of Computing (STOC), pages 494–503, 2002. Read at ePrint revision 20030714:190611. The paper this page’s title comes from, and the one that does not print the box: its five printed functionalities are listed above and in _src/sources.json, and its general result is the compiler described above. Authors, venue and page range confirmed against DBLP.
  • Yao. Protocols for secure computations. In 23rd IEEE Symposium on Foundations of Computer Science (FOCS), pages 160–164, 1982. The origin of the question. Prints no functionality; at 1982 it predates the notation entirely.
  • Goldreich, Micali, and Wigderson. How to play any mental game. In 19th ACM Symposium on Theory of Computing (STOC), pages 218–229, 1987. The general feasibility result. Prints no functionality, and the harvester could not fetch it — the URL is a DOI landing page rather than a PDF — so the statement that it prints none rests on the literature rather than on a scan of this copy.