  In classic settings of garbled circuits, each gate type is leaked to improve
both space and speed optimization. Zahur et al. have shown in EUROCRYPT 2015
that a typical linear garbling scheme requires at least two $\lambda$-bit
elements per gate with a security parameter of $\lambda$, which limits their
efficiency. In contrast to typical garbled circuits, gate-hiding garbled
circuits have the potential to drastically reduce time costs, although they
have been underappreciated.
  We propose the first skipping scheme for gate-hiding garbled circuits to
enhance the efficiency of evaluation by observing prime implicants. Our scheme
introduces skip gates to eliminate the need to calculate the entire circuit,
enabling unnecessary execution paths to be avoided. We also introduce two
variants of our scheme that balance security with parallelism. A proof of
hybrid security that combines simulation-based and symmetry-based security in
semi-honest scenarios is presented to demonstrate its security under
gate-hiding conditions. Our scheme will inspire new directions to improve the
general garbling scheme and lead to more practical ones.
