# Compute a proof for a verifiable delay function

I am trying to solve the following problem:

Alice generates a RSA key $$(n, \phi)$$, she shares with Bob the value $$n$$, and $$y = g^{2^{t}}\;\text{mod}\; n$$ for $$g$$ a generator of the group $$\left(\mathbb Z/n\mathbb Z\right)^{*}$$ and $$t$$ a very large number for example $$2^{512}$$. She then asks Bob for an input $$z$$ ($$\neq y$$) and sends him a relatively small random prime (challenge) $$\ell$$ and $$\pi$$ a proof of $$y$$ such that $$\pi = g^{\left\lfloor\frac{2^t}{\ell}\right\rfloor}\;\text{mod}\; n$$ and so $$y = \pi^{\ell} g^r\; \text{mod} \; n$$ where $$r = 2^t \; \text{mod}\; \ell$$. Now Bob needs to find a proof $$\psi$$ for $$z$$ such that: $$z = \psi^{\ell} g^r\; \text{mod} \; n.$$

It is clear that if Bob has an access to $$\phi$$ he can find $$d = \ell^{-1}\;\text{mod}\; \phi$$ and solve the problem by chosing $$\psi = \left(z g^r\right)^d \;\text{mod}\; n$$. However in my case $$n$$ is large that it is almost impossible for me to compute the prime factorization of $$n$$ to find $$\phi$$. Can any one help me to find an idea of how to find $$\psi$$?

• Shall we read "$2^t$ a very large number for example $2^{512}$" where there is "$t$ a very large number for example $2^{512}$"? If not: for $n$ the product of two distinct primes $p$ and $q$, in order to compute $y=g^{(2^{(2^{512})})}\bmod n$, it looks like Alice must be able to factor $p-1$ and $q-1$, which is not a standard assumption in RSA. And uh, I have not yet found how Alice would computes $\pi$.
– fgrieu
Commented Dec 21, 2023 at 6:15
• Thank you for your comment. For computing $y$ Alice knows the private keys $p$ and $q$ or at least the value of $\phi$ Commented Dec 24, 2023 at 15:50

I manage to solve it. Indeed, Bob can send $$z = -y \;\text{mod} \; n$$ and then $$\psi$$ will be simply $$-\pi \; \text{mod}\; n$$.