Card-based cryptography performs a secure computation using a deck of playing cards through a series of physical actions, such as shuffling a sequence of cards. In 1989, the first card-based protocol called the five-card trick was proposed to compute the two-input AND function. The five-card trick needs a practical shuffling action called a random cut only once, which shifts a sequence of cards by a random offset. Subsequent research aimed to extend the five-card trick to compute any Boolean function and to reduce the number of cards required to compute it, but Mizuki, Kumamoto, and Sone in 2012 showed that the five-card trick itself can be done with four cards. This Mizuki–Kumamoto–Sone protocol uses the minimal number of cards required for computing two-input Boolean functions (as long as we encode an input bit with two cards); however, it needs a practical step of shuffling action twice, and the question of minimizing the number of steps, particularly the number of shuffling, remains an open problem. In this study, we negatively answer this problem; we prove that any four-card AND protocol cannot be realized using only a single practical shuffle. This implies that the Mizuki–Kumamoto–Sone protocol utilizes the minimal number of practical shuffles. For this, we enumerate all possible practical shuffles and prove that applying any one of them only once either cannot compute the AND function or leak information about the input.