As ML models become increasingly complex and integral to high-stakes domains such as finance and healthcare, they also become more susceptible to sophisticated adversarial attacks. We investigate the threat posed by undetectable backdoors, as defined in Goldwasser et al. [2022], in models developed by insidious external expert firms. When such backdoors exist, they allow the designer of the model to sell information on how to slightly perturb their input to change the outcome of the model. We develop a general strategy to plant backdoors to obfuscated neural networks, that satisfy the security properties of the celebrated notion of indistinguishability obfuscation. Applying obfuscation before releasing neural networks is a strategy that is well motivated to protect sensitive information of the external expert firm. Our method to plant backdoors ensures that even if the weights and architecture of the obfuscated model are accessible, the existence of the backdoor is still undetectable. Finally, we introduce the notion of undetectable backdoors to language models and extend our neural network backdoor attacks to such models based on the existence of steganographic functions.

Abstract. In the [Formula: see text]- Consensus-Halving problem, a fundamental problem in fair division, there are [Formula: see text] agents with valuations over the interval [0,1], and the goal is to divide the interval into pieces and assign a label “[Formula: see text]” or “[Formula: see text]” to each piece, such that every agent values the total amount of “[Formula: see text]” and the total amount of “[Formula: see text]” almost equally. The problem was recently proven by Filos-Ratsikas and Goldberg [ Proceedings of the 50 th Annual ACM Symposium on Theory of Computing, 2018, pp. 51–64; Proceedings of the 51 st Annual ACM Symposium on Theory of Computing, 2019, pp. 638–649] to be the first “natural” complete problem for the computational class PPA, answering a decade-old open question. In this paper, we examine the extent to which the problem becomes easy to solve if one restricts the class of valuation functions. To this end, we provide the following contributions. First, we obtain a strengthening of the PPA-hardness result of Filos-Ratsikas and Goldberg [ Proceedings of the 51 st Annual ACM Symposium on Theory of Computing, 2019, pp. 638–649] to the case when agents have piecewise uniform valuations with only two blocks. We obtain this result via a new reduction, which is in fact conceptually much simpler than the corresponding one in Filos-Ratsikas and Goldberg [ Proceedings of the 51 st Annual ACM Symposium on Theory of Computing, 2019, pp. 638–649]. Then, we consider the case of single-block (uniform) valuations and provide a parameterized polynomial-time algorithm for solving [Formula: see text]- Consensus-Halving for any [Formula: see text], as well as a polynomial-time algorithm for [Formula: see text]. Finally, an important application of our new techniques is the first hardness result for a generalization of Consensus-Halving, the Consensus-[Formula: see text]-Division problem [F. W. Simmons and F. E. Su, Math. Social Sci., 45 (2003), pp. 15–25]. In particular, we prove that [Formula: see text]-Consensus-[Formula: see text]-Division is PPAD-hard.

We resolve the computational complexity of three problems known as Necklace Splitting, Consensus-Halving, and Discrete Ham sandwich, showing that they are PPA-complete. For NECKLACE SPLITTING, this result is specific to the important special case in which two thieves share the necklace. These are the first PPA-completeness results for problems whose definition does not contain an explicit circuit, thus settling the status of PPA as a class that captures the complexity of such “natural' problems.

We study the search problem class PPA_q defined as a modulo-q analog of the well-known polynomial parity argument class PPA introduced by Papadimitriou (JCSS 1994). Our first result shows that this class can be characterized in terms of PPA_p for prime p. Our main result is to establish that an explicit version of a search problem associated to the Chevalley - Warning theorem is complete for PPA_p for prime p. This problem is natural in that it does not explicitly involve circuits as part of the input. It is the first such complete problem for PPA_p when p ≥ 3. Finally we discuss connections between Chevalley-Warning theorem and the well-studied short integer solution problem and survey the structural properties of PPA_q.

In the ε-Consensus-Halvingproblem, a fundamental problem in fair division, there are n agents with valuations over the interval [0,1], and the goal is to divide the interval into pieces and assign a label "+" or "-" to each piece, such that every agent values the total amount of "+" and the total amount of "-" almost equally. The problem was recently proven by Filos-Ratsikas and Goldberg[18,19] to be the first "natural" complete problem for the computational class PPA, answering a decade-old open question.

Polynomial Pigeonhole Principle (PPP) is an important subclass of TFNP with profound connections to the complexity of the fundamental cryptographic primitives: collision-resistant hash functions and one-way permutations. In contrast to most of the other subclasses of TFNP, no complete problem is known for PPP. Our work identifies the first PPP-complete problem without any circuit or Turing Machine given explicitly in the input, and thus we answer a longstanding open question from [Papadimitriou1994]. Specifically, we show that constrained-SIS, a generalized version of the well-known Short Integer Solution problem (SIS) from lattice-based cryptography, is PPP-complete. In order to give intuition behind our reduction for constrained-SIS, we identify another PPP-complete problem with a circuit in the input but closely related to lattice problems. We call this problem BLICHFELDT and it is the computational problem associated with Blichfeldt's fundamental theorem in the theory of lattices. Building on the inherent connection of PPP with collision-resistant hash functions, we use our completeness result to construct the first natural hash function family that captures the hardness of all collision-resistant hash functions in a worst-case sense, i.e. it is natural and universal in the worst-case. The close resemblance of our hash function family with SIS, leads us to the first candidate collision-resistant hash function that is both natural and universal in an average-case sense. Finally, our results enrich our understanding of the connections between PPP, lattice problems and other concrete cryptographic assumptions, such as the discrete logarithm problem over general groups.

Occupational fraud affects many companies causing them economic loss and liability issues towards their clients and other entities. Detecting internal fraud requires significant effort since a huge amount of data produced by diverse systems (which are mostly in textual form) has to be processed with little automated support. In this paper, we exploit the advantages of information visualization and present a system that aims to detect occupational fraud in systems which involve a pair of entities (e.g., an employee and a client). The main visualization is a spiral on which the events are drawn according to their time-stamp. Suspicious events are considered those which appear along the same radius or on close radii. The system ranks both entities according to the specifications of the auditor and a video file of their activity is generated such that events with strong evidence of fraud appear first. The system is equipped with several visualizations that facilitate the detection procedure.