In this work we study the feasibility of knowledge extraction for succinct non-interactive arguments of knowledge (SNARKs) in a scenario that, to the best of our knowledge, has not been analyzed before. While prior work focuses on the case of adversarial provers that may receive (statically generated) {\em auxiliary information}, here we consider the scenario where adversarial provers are given {\em access to an oracle}. For this setting we study if and under what assumptions such provers can admit an extractor. Our contribution is mainly threefold.

First, we formalize the question of extraction in the presence of oracles by proposing a suitable proof of knowledge definition for this setting. We call SNARKs satisfying this definition O SNARKs. Second, we show how to use O-SNARKs to obtain formal and intuitive security proofs for three applications (homomorphic signatures, succinct functional signatures, and SNARKs on authenticated data) where we recognize an issue while doing the proof under the standard proof of knowledge definition of SNARKs. Third, we study whether O-SNARKs exist, providing both negative and positive results. On the negative side, we show that, assuming one way functions, there do not exist O-SNARKs in the standard model for every signing oracle family (and thus for general oracle families as well). On the positive side, we show that when considering signature schemes with appropriate restrictions on the message length O-SNARKs for the corresponding signing oracles exist, based on classical SNARKs and assuming extraction with respect to specific distributions of auxiliary input.

The classical Benjamin-Ono equation v_t + v v_x = e_1 J[v_{xx}] with periodic boundary conditions is a completely integrable system for v: T → R on the unit circle T, where J is the Hilbert transform. Let H denote the Hardy space on the circle, |0> in H the vacuum, and L(v) the Toeplitz operator with symbol v. Building on the work of Nazarov-Sklyanin (2013), we show that the infinitely-many \ell=0,1,2,3,… conservation laws T_{\ell}(v|e_1) of the classical Benjamin-Ono system are moments of a conserved density given by the spectral shift function of L(v) + e_1 d/dx and its (0,0) minor. Moreover, Nazarov-Sklyanin (2013) also treat the canonical quantization of this system, associating to classical conservation laws T_{\ell}(v|e_1) an infinite hierarchy of commuting operators \hat{T}_{\ell}(v|e_2,e_1) with \hbar = - e_1 e_2 simultaneously diagonalized on Jack polynomials with parameter \alpha = - e_1 / e_2. Their eigenvalues on Jacks depend only on the profile of the *anisotropic* Young diagram built from rectangles of size (e_2, e_1). Just like in the classical case, we realize the slopes of a profile of an anisotropic Young diagram as a spectral shift function in the sense of Krein (1953). The talk will begin with the general framework of Kerov’s Markov-Krein correspondence (1998). These constructions are new even for Schur polynomials e_1 + e_2 = 0 that relies on the first Szegö theorem (1915). As time permits, we introduce a family of combinatorial objects called ``ribbon paths” that are for random partitions what ribbon graphs are for random matrices at general \beta /2 = -(e_2/e_1) >0.

In a one-counter automaton (OCA), one can produce a letter from some finite alphabet, increment and decrement the counter by one, or compare it with constants up to some threshold. It is well-known that universality and language inclusion for OCAs are undecidable. In this paper, we consider OCAs with counter observability: Whenever the automaton produces a letter, it outputs the current counter value along with it. Hence, its language is now a set of words over an infinite alphabet. We show that universality and inclusion for that model are PSPACE-complete, thus no harder than the corresponding problems for finite automata. In fact, by establishing a link with visibly one-counter automata, we show that OCAs with counter observability are effectively determinizable and closed under all boolean operations.