This paper deals with discrete second order Sturm-Liouville Boundary Value Problems (DSLBVP) where the parameter λ, as part of the difference equation, appears nonlinearly in the boundary conditions. We focus on the case where the boundary condition is given by a cubic equation in λ. We first describe the problem by a matrix equation with nonlinear variables such that solving the DSLBVP is equivalent to solving the matrix equation. We develop methods to finding roots of the characteristic polynomial (in the variable λ) of the involved matrix. We further reduce the problem to finding eigenvalues of a matrix pencil in the form of A-λB. Under certain conditions, such a matrix pencil eigenvalue problem can be reduced to a stabdard eigenvalue problem, so that existing computational tools can be used to solve the problem. The main results of the paper provide the reduction procedure and rules to identify the cubic DSLBVPs which can be reduced to standard eigenvalue problems. We also investigate the structure of the matrix form of a DSLBVP and its effect on the reality of the eigenvalues of the problem. We give a class of DSLBVPs which have only real eigenvalues.