This is from the result of the recent breakthrough by Chatterjee, Ghosh, Gurjar, Raj, and Theireuff. This also has some cool connections with coding theory. We will explore the decision version of the problem in the talk.

In this talk, we will discuss the work titled "Succinct Computational Secret Sharing for Monotone Circuit" co-authored by George Lu, Shafik Nasser and Brent Waters. This work was published in ASIACRYPT 2025. In this paper, the authors present a novel computational secret sharing scheme for monotone Boolean circuits that achieves substantially shorter share sizes than previously known constructions in the standard model. Their scheme attains a public share size of 𝑛 + poly(𝜆, log |𝐶 |) and a user share size of 𝜆, where 𝑛 denotes the number of users, 𝐶 is the monotone circuit and 𝜆 is the security parameter, thus effectively eliminating the dependence on the circuit size. This marks a significant improvement over earlier approaches, which exhibited sizes that grew with the number of gates in the circuit. The construction makes use of indistinguishability obfuscation and injective one-way functions.

We construct a two-round protocol for $n$ parties to securely compute any Boolean circuit $C$ from random bit-OT correlations and black-box use of a pseudorandom function. The protocol communicates $O(n^2|C|\kappa)$ bits, where $|C|$ denotes the circuit size and $\kappa$ is the computational security parameter. The protocol is secure against any static semi-honest adversary corrupting up to $n-1$ parties. Communication quadratic in the number of parties can be achieved from OT or OLE correlations using several rounds of interaction. In contrast, the best previously known communication bounds for two-round MPC in this setting are cubic in the number of parties, as achieved by Garg, Ishai, and Srinivasan (TCC 2018) and Lin, Liu, and Wee (TCC 2020). Our protocol overcomes this cubic communication overhead while retaining the optimal round complexity of two.

I will give a talk about one of the most interesting currently open problems in social choice theory: determining the optimal Condorcet dimension of ordinal elections. Given an ordinal election, in which each voter ranks the candidates in order of preference, a Condorcet winning set is a set of candidates with the property that no group consisting of at least half the voters unanimously prefers the same candidate outside the set to every candidate in the set. The Condorcet dimension of an election is the minimum size of a Condorcet winning set in that election. I will show how to derive the best known lower bound of 3 and present a recent simple proof of the best known upper bound of 5.

In this talk we will study the problem of constructing highly nonlinear vectorial maps F: \F_2^n \to \F_2^m. Concretely, we want an F and an A = A(m,n)> 0 as small as possible, so that for every affine map L: \F_2^n \to \F_2^m (of the form L(x) = M x + b ) we have: agree(F, L) := |{ x \in \F_2^n | F(x) = L(x) }| \leq A. Such questions have been studied by Nyberg, Carlet and Ding, Liu, Mesnager and Chen, Nagy, and Biryukov, Turecek, and Udovenko. There is a classical method of constructing such functions from bent-functions and Fourier analytic ideas; the best bound achievable by this method is: A(m,n) = \Theta(2^{n-m} + 2^{n/2}), and in particular, is never smaller than 2^{n/2}. In this work, we show how to construct highly nonlinear functions beyond this Fourier bound. Concretely, we show how to construct for every \gamma>0, a function F: \F_2^n \to \F2^m with m = O{\gamma}(n), achieving A(m,n) \leq (1 + \gamma)^n. Surprisingly, we even achieve the same quantitative behavior for the much harder question of having low agreement with m-tuples of degree d polynomials Q: \F_2^n \to \F2^m, with m = O{\gamma, d}(n). All our results generalize to all finite fields \F_q in place of \F_2. Our methods are based on a new connection to classical results on counting solutions to systems of polynomial equations via algebraic methods. This connection brings us to basic questions in combinatorics, about graphs and hypergraphs with simultaneously a small number of edges and independent sets. Based on joint work with Swastik Kopparty and Shanthanu S. Rai.

The central goal of secure multiparty computation (MPC) is to design a communication protocol for $n$ parties $P_1, P_2, \dots, P_n$, where $P_i$ holds private input $x_i$, to jointly compute a distributed functionality $f(x_1, \dots, x_n)$. We require that each party learns nothing about the private inputs of the other parties (beyond what is revealed by the output of the functionality). In this talk, we will see the working of the IPS protocol compiler, which allows us to build MPC protocols that remain secure when a dishonest majority of the parties are corrupted, from component protocols that satisfy weaker security guarantees. The IPS paradigm is of particular interest in the design of black-box MPC protocols from minimal cryptographic assumptions. This talk is based on the paper "Founding Cryptography on Oblivious Transfer – Efficiently" by Yuval Ishai, Manoj Prabhakaran and Amit Sahai.