Abstract: A new key-sieving algorithm used in impossible differential attacks on advanced encryption standard (AES) is proposed. In the new algorithm, table look-up technique is firstly applied to eliminate some error keys, and then a divide-and-conquer technique is adopted to sieve the others. It is shown that the new algorithm gains some advantage over previously published key-sieving algorithms with respect to the time complexity when proper independent variables are chosen in the function of the time complexity. Moreover, we improve the impossible differential attacks on AES proposed in INDOCRYPT2008 by means of the new algorithm, meanwhile the curves of time complexity are drawn and the best points are obtained. The memory accesses of attacks on 7-round AES-128, 7-round AES-192, 7-round AES-256, and 8-round AES-256 are reduced to 2116.35, 2116.54, 2116.35, and 2228.21 from 2117.2, 2118.8, 2118.8, and 2229.7, respectively, and in the meanwhile the data complexity keeps unchanged.