  We consider a random walk $Y$ moving on a \emph{L\'evy random medium}, namely
a one-dimensional renewal point process with inter-distances between points
that are in the domain of attraction of a stable law. The focus is on the
characterization of the law of the first-ladder height $Y_{\mathcal{T}}$ and
length $L_{\mathcal{T}}(Y)$, where $\mathcal{T}$ is the first-passage time of
$Y$ in $\mathbb{R}^+$. The study relies on the construction of a broader class
of processes, denoted \emph{Random Walks in Random Scenery on Bonds} (RWRSB)
that we briefly describe. The scenery is constructed by associating two random
variables with each bond of $\mathbb{Z}$, corresponding to the two possible
crossing directions of that bond. A random walk $S$ on $\mathbb{Z}$ with i.i.d
increments collects the scenery values of the bond it traverses: we denote this
composite process the RWRSB. Under suitable assumptions, we characterize the
tail distribution of the sum of scenery values collected up to the first exit
time $\mathcal{T}$. This setting will be applied to obtain results for the laws
of the first-ladder length and height of $Y$. The main tools of investigation
are a generalized Spitzer-Baxter identity, that we derive along the proof, and
a suitable representation of the RWRSB in terms of local times of the random
walk $S$. All these results are easily generalized to the entire sequence of
ladder variables.
