In this work, we show the hardness of finding a Nash equilibrium, a \PPAD-complete problem, based on the quasi-polynomial hardness of the decisional assumption on groups with bilinear maps introduced by Kalai, Paneth and Yang [STOC 2019]. Towards this goal, we construct an {\em unambiguous} and {\em updatable} delegation scheme under this assumption for deterministic computations running in super-polynomial time and polynomial space. This delegation scheme, which is of independent interest, is publicly verifiable and non-interactive in the common reference string (CRS) model. It is {\em unambiguous} meaning that it is hard to compute two different proofs for the same statement. It is {\em updatable} meaning that given a proof for the statement that a Turing machine $M$ reaches configuration $\conf_T$ in $T$ steps, one can {\em efficiently} generate a proof for the statement that $M$ reaches configuration $\conf_{T+1}$ in $T+1$ steps.

Recently, J.-J. Shen, C.-W. Lin and M.-S. Hwang (Computers & Security, Vol 22, No 7, pp 591-595, 2003) proposed a modified Yang-Shieh scheme to enhance security. They claimed that their modified scheme can withstand the forged login attack and also provide a mutual authentication method to prevent the forged server attack. In this paper, we show that the Shen-Lin-Hwang scheme cannot resist the forged login attack either. The intruder is able to forge a valid forge request of a legitimate user Ui and then successfully impersonate him by intercepting a login request sent by Ui and registering a smart card.

In 1988, Harn, Laih and Huang proposed a password authentication scheme based on quadratic residues. However, in 1995, Chang, Wu and Laih pointed out that if the parameters d b a , , and l are known by the intruder, this scheme can be broken. In this paper, we presented another attack on the Harn-Laih-Huang scheme. In our attack, it doesn’t need to know the parameters and it is more efficient than the Chang-Wu-Laih attack.