A system obtains a weight matrix associated with a linear operation, the weight matrix comprising a first non-zero value and a second non-zero value that is a negative value. The system decomposes the weight matrix into a first binary matrix indicating positions of the first non-zero value and a second binary matrix indicating positions of the second non-zero value. The system encrypts vector elements of an input vector using an encryption scheme to obtain an encrypted input vector. For each row of the first and second binary matrices, the system homomorphically processes selected encrypted elements of the encrypted input vector to generate at least two intermediate encrypted aggregates corresponding to respective contribution signs. The system generates an output element for each row based on a combination of the intermediate encrypted aggregates.