In Knife of Dreams, Perrin negotiates a truce with a bunch of Seanchan, and he hands their leaders a letter from Suroth. (edits and emphasis mine)
From his left gauntlet he pulled a folded, grease-stained piece of paper.
Tylee's eyebrows rose as she read it. Perrin had the short text by heart. The bearer of this stands under my personal protection. In the name of the Empress, may she live forever, give him whatever aid he requires in service to the Empire and speak of it to none but me. He had no idea who Suroth Sabelle Meldarath was, but if she signed her name to something like that, she had to be important.
Where does he get this letter from? I don't recall Perrin being near any Seanchan before this, except in The Great Hunt at Falme, but he doesn't get any letter from any High Lady there as far as I remember. So, when and where does Perrin get this letter?