I was wondering something similar. If Party B acquires Party A's anonymized-but-subject-to-HIPAA data and successfully deanonymizes it, who is liable? If the data is deanonymized, doesn't this mean the data wasn't sufficiently anonymized to begin with and Party A has some liability? Is Party B also liable since their goal from the start was to deanonymize the data?

Hopefully ICA susceptible De-anonymization techniques are no longer HIPAA best practice. Or perhaps this is a study to prove that newer additive and multiplicative techniques, are also susceptible to De-anonymization attacks.

I have to sign documents saying who can view my info when I go for a checkup.

I'd find another doctor if Facebook ever showed up on there.

I would think it would be illegal for the medical side to share and for Facebook to use their massive data collection in this manner if it's not buried in their impenetrable privacy statement.

Absolutely. If both parties can match people in their lists, they can find out who is who even if the lists contain some random ids instead of names.

Those laws are just for you and I.