A stochastic approach for estimating the permeability between rough-walled rock fracture surfaces is presented. In the present analysis, the Reynolds lubrication equation, which is adopted for analyzing fluid flow through a rough surface of rock fracture, is solved as a stochastic partial differential equation using perturbative expansion method. The results are compared with the numerical deterministic analysis for randomly generated aperture distributions. The analytical results are in a good agreement with numerical results obtained by the Monte Carlo approach. Through the present analysis, a fourth-order accurate approximation to the effective permeability of a single joint is given in terms of the mean, the standard deviation, and the spatial correlation, so that the effect of higher-order terms is clarified more accurately than the classical second-order approximation.