You will need to be near the end of the game, the safest earliest time is after defeating both Dycedarg and Zalbag, and it might be better for you if you beat Dycedarg's Lucavi form as well. Afterwards, go to Warjilis Trade City and you should hopefully see a conversation take place. Then the path to Deep Dungeon should open. You can get Byblos there.
Deep Dungeon Tips -
Use Movement Ability MOVE-ITEM FIND in order to get the items in the Deep Dungeon. It's also very safe for you if you're level 99, though if the enemies level is determined by your average team level, they will also be level 99.
Item Co-Ordinates (x,y)
NOGIAS
Blaze Gun @ (2,2)
Glacier Gun @ (0,9)
Elixir @ (9,4)
Kiyomori @ (0,6)
TERMINATE
Blood Sword @ (6,7)
Elixir @ (2,10)
Elixir @ (4,0)
Save the Queen @ (0,1) [!!]
DELTA
to be cont.