A matrix challenge for breaking obfuscation (proposed by Colin)

Let $d=2000$, and let $C_0,C_1,C_2,C_3$ be secret $d \times d$ matrices with each entry chosen uniformly at random from $\{-10,-9,\dots,9,10\}$. Suppose we are given the polynomial $$\det(x_0C_0+x_1C_1+x_2C_2+x_3C_3) \in \mathbb{Z}[x_0,x_1,x_2,x_3]$$ as a list of coefficients. Help me recover $C_0,C_1,C_2,C_3$, in the following sense – find matrices $C_0',C_1',C_2',C_3'$ with entries in $\mathbb{Q}$, bit-complexity not too high, such that there exist $U,V \in \mathrm{GL}(\mathbb{Q};d)$ with $C_i' = UC_iV$ for each $i$.

Motivation

Solving this problem would make progress toward breaking a proposed obfuscation scheme for affine determinant programs (ADP) (the paper has more information on both ADP and the scheme).

For us, an affine determinant program is a collection $A_0, A_1, A_2, ..., A_k$ of square matrices over $\mathbb{F}_2$; to evaluate the program on an input $(x_1, x_2, \ldots, x_k)$, one simply computes the determinant $$\operatorname{det}(A_0 + x_1 A_1 + x_2 A_2 + \cdots + x_k A_k).$$

The main idea of the obfuscation scheme is as follows:

• Lift the matrices $A_i$ over $\mathbb{F}_2$ to matrices $C_i$ over $\mathbb{Z}$, with small integer coefficients. (In other words: think of $A_i$ as a matrix of zeros and ones, and add a randomly chosen small even integer to each entry.)
• Choose some very large odd number $q$, and think of the matrices $C_i$ as matrices over $\mathbb{Z} / q \mathbb{Z}$.
• Choose two random matrices $U$ and $V$ of determinant $1$ over $\mathbb{Z} / q \mathbb{Z}$, and publish $U C_i V$ for each $i$.

Given the matrices $U C_i V$, anyone (evaluator or attacker) can compute the value of the integer determinant $$\operatorname{det}(U C_0 V + \sum x_i U C_i V) = \operatorname{det}(C_0 + \sum x_i C_i)$$ (at least in the range where that determinant is less than $q$). What can an attacker do with black-box access to the determinant? A solution to this problem would let the attacker recover the matrices $C_i$, which would almost certainly render this obfuscation scheme useless.