Yao, “Protocols for Secure Computations,” FOCS 1982, pp. 160–164 — poses secure two-party computation and the two-millionaires problem.
Yao, “How to Generate and Exchange Secrets” (extended abstract), FOCS 1986, pp. 162–167 — the talk where garbled circuits were first shown, though the written paper itself doesn’t contain the construction.
Goldreich, Micali, Wigderson, “How to Play Any Mental Game,” STOC 1987, pp. 218–229 — the first written description of Yao’s garbled-circuit technique, and a completeness theorem for MPC generally.
Kolesnikov, Schneider, “Improved Garbled Circuit: Free XOR Gates and Applications,” ICALP 2008, pp. 486–498 — free XOR gates.
Zahur, Rosulek, Evans, “Two Halves Make a Whole: Reducing Data Transfer in Garbled Circuits Using Half Gates,” EUROCRYPT 2015, pp. 220–250 — half-gates.

See History for how these fit together chronologically, and Applications for where several of these ideas get used in practice.

Textbook

Evans, Kolesnikov, and Rosulek, A Pragmatic Introduction to Secure Multi-Party Computation — a free, complete textbook covering MPC from Yao’s garbled circuits through implementation techniques and malicious security. The natural next step if you want the full treatment beyond a single AND gate.

Corrections and additions welcome — see About for how to propose a change to this page or anything else on the site.

Further reading