They could also give huge boolean formulas, and ask the applicant to decide if it is satisfiable[1] or not. Simple yes or no answer, which is quite a hard (NP-hard) to come by.
While it is obvious that a satisfiable instance will have a simple yes-certificate, it is not known if for any unsatisfiable instance there is a short no-certificate (i.e. SAT is in NP, but believed not to be in coNP). The Jewish problems had to have simple solutions, while it could be hard to find a small proof of unsatisfiability of some large formula.
But then again, it would probably fool nobody.
[1] http://en.wikipedia.org/wiki/Boolean_satisfiability_problem