In this paper, we present a parity-based fault detection architecture of the S-box for designing high performance fault detection structures of the Advanced Encryption Standard. Instead of using look-up tables for the S-box and its parity prediction, logical gate implementations based on the composite field are utilized. After analyzing the error propagation for injected single faults, we modify the original S-box and suggest a fault detection architecture for the S-box. Using the closed formulations for the predicted parity bits, we propose a parity-based fault detection scheme for reaching the maximum fault coverage. Moreover, the overhead costs, including space complexity and time delay of our modified S-box and the parity predictions are also compared to those of the previously reported ones.