abstract: We consider a random walk moving on a Lévy random medium, namely a one-dimensional renewal point process with i.i.d. inter-distances in the domain of attraction of a stable law. The focus is on the characterization of the law of the first-ladder height and length of the process. The study relies on the construction of a broader class of processes, denoted as Random Walks in Random Scenery on Bonds (RWRSB), consisting of a scenery which associates two random variables with each bond of the integer lattice Z (corresponding to the two possible crossing directions of that bond) and a random walk S on Z with i.i.d increments that collects the scenery values of the bond it traverses. Under suitable assumptions, we characterize the tail distribution of the sum of the scenery values collected up to the first-passage time in the positive semi-axis. This setting will be applied to obtain results for the laws of the first-ladder length and height of random walks in Lévy media, with an additional application in the context of the (generalized) Lévy-Lorentz gas. The main tools of investigation are a generalized Spitzer-Baxter identity 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. (Joint work with Alessandra Bianchi and Giampaolo Cristadoro).