I database sono fatti per contenere tantissimi record, quindi non c'è problema ad avere una entry per ogni file.
Io opterei per la prima soluzione.
E' più facile fare
SELECT * FROM tab_file WHERE id_file=1 AND id_utente_a=3 AND id_utente_b=4;
per vedere se l'utente B ha accesso al file 1 dell'utente A, piuttosto che controllare se nel campo id_utente_b tra i tanti id c'è quello dell'utente che ti interessa.

Per quanto riguarda Facebook, quando tu condividi un contenuto non lo condividi con una persona, semplicemente viene messo sulla tua bacheca e chiunque ha accesso ad essa può vedere il contenuto, non è che nel db viene inserita una entry per ogni tuo amico.