We study when (dual) Vandermonde systems of the form ${V}_T^{{(\intercal)}} \cdot \vec{z} = s\cdot \vec{w}$ admit a solution $\vec{z}$ over a ring $\mathcal{R}$, where ${V}_T$ is the Vandermonde matrix defined by a set $T$ and where the "slack" $s$ is a measure of the quality of solutions. To this end, we propose the notion of $(s,t)$-subtractive sets over a ring $\mathcal{R}$, with the property that if $S$ is $(s,t)$-subtractive then the above (dual) Vandermonde systems defined by any...

Let $d \geq 1$ be an integer and $R_1$ be a finite ring whose elements are called {\bf block}. A $d$-block universal hash over $R_1$ is a vector of $d$ multivariate polynomials in message and key block such that the maximum {\em differential probability} of the hash function is ``low''. Two such single block hashes are pseudo dot-product (\tx{PDP}) hash and Bernstein-Rabin-Winograd (\tx{BRW}) hash which require $\frac{n}{2}$ multiplications for $n$ message blocks. The Toeplitz construction...

Bogdanov and Lee suggested a homomorphic public-key encryption scheme based on error correcting codes. The underlying public code is a modified Reed-Solomon code obtained from inserting a zero submatrix in the Vandermonde generating matrix defining it. The columns that define this submatrix are kept secret and form a set $L$. We give here a distinguisher that detects if one or several columns belong to $L$ or not. This distinguisher is obtained by considering the code generated by...

A {\em black-box} secret sharing scheme for the threshold access structure $T_{t,n}$ is one which works over any finite Abelian group $G$. Briefly, such a scheme differs from an ordinary linear secret sharing scheme (over, say, a given finite field) in that distribution matrix and reconstruction vectors are defined over the integers and are designed {\em independently} of the group $G$ from which the secret and the shares are sampled. This means that perfect completeness and perfect privacy...