Restricting Record Access for Specific Users in Salesforce

Question

Use Case:

We have a single profile with permission sets to manage access.

Example Situation:

Users: User A and User B share the same profile and permission set. Record Access: A contact record, Contact XYZ, is accessible to both User A and User B due to existing sharing rules. Client Request: Client XYZ requests that User B should not have any visibility of their record. User B should not even be aware that Contact XYZ exists in the system.

Challenge:

Since sharing rules have already granted access, the requirement is to revoke User B's access to specific records while maintaining the same profile and permission sets.

How can we solve this challenge? Thanks in advance.