In say a 2 of 3 multi-sig setup, do such private keys (base 58 or even Hexadecimal) exist under the hood.
Any cryptographic key of any type, Bitcoin or other, on a computer, is representable in hexadecimal, in octal, in binary, in base58, in base64 and in any other representation used on computers. The keys are just numbers and the various encodings listed are just different visual representations of the same number.
From what I have read, a multisig setup uses the private and public keys that are usable for ordinary transactions.
In https://en.bitcoin.it/wiki/Multi-signature it says:
Creating a multi-signature address with Bitcoin-Qt
A 2-of-3 multisig address can be created by following these steps:
Gather (or generate) 3 bitcoin addresses, on whichever machines will be participating, using
getaccountaddress RPC commands (or copy and paste from the GUI).
Get their public keys using the
validateaddress RPC command 3 times.
Then create a 2-of-3 multisig address using addmultisigaddress; e.g.,
bitcoind addmultisigaddress 2 '["044322868cb17d64dcc22185ae2d4493111d73244c3668f8ac79ecc79c0ba8d30a6756d0fa20157 709af3281cc721c7f53321a8cabda29b77900b7e4fe0174b114","..second pubkey..","..third pubkey.."]'
addmultisigaddress returns the multi-signature address. Be a little careful, the public keys are raw hexadecimal and don't contain checksums like bitcoin addresses do. You can then send funds into that 2-of-3 transaction using the normal sendtoaddress/sendmany RPC commands, or the GUI (or anything that's been updated to recognize multisig addresses)
I think that the suggested use of
getnewaddress in step one shows that keys used are the ones we are familiar with from ordinary single-key transactions.