Paper 2026/1021

Schnorr-like Proofs of Knowledge for Hidden Oil Subspaces in UOV

Abstract

A UOV public key hides a distinguished linear subspace: the public-coordinate image of the central oil-coordinate subspace. In central coordinates, the homogeneous quadratic part of each UOV polynomial contains no oil-oil monomials. Consequently, for every honestly generated UOV public key, each public homogeneous quadratic form vanishes when restricted to this hidden oil subspace. We formalize the hidden oil-subspace relation and construct a Schnorr-like Sigma protocol that proves knowledge of such a subspace without revealing it. The witness consists of matrices $B,W$ satisfying $WB=I_o$ and $Q_k(Bz)\equiv 0$ for all public quadratic forms $Q_k$. The prover masks the witness linearly and responds to a challenge $c$ with $Z=A+cB$, $Y=E+cW$, yielding a protocol with computational 3-special soundness and computational honest-verifier zero knowledge. We prove a generic uniqueness theorem: in the random homogeneous UOV model, the hidden oil subspace is, with overwhelming probability, the unique $o$-dimensional common zero subspace. The uniqueness bound is explicit and negligible for UOV-type parameters. This strengthens the interpretation of the protocol as proving knowledge of the unique hidden oil subspace, rather than merely some oil-like subspace. We provide empirical observations on small parameters and discuss applications and limitations.