An apparatus and method with encrypted data neural network operation is provided. The apparatus includes one or more processors configured to execute instructions and one or more memories storing the instructions, wherein the execution of the instructions by the one or more processors configures the one or more processors to generate a target approximate polynomial, approximating a neural network operation, of a portion of a neural network model, using a determined target approximation region, for the target approximate polynomial, based on a first approximate polynomial generated based on parameters corresponding to a generation of the first approximate polynomial, a maximum value of input data to the portion of the neural network layer, and a minimum value of the input data, and generate a neural network operation result using the target approximate polynomial and the input data.