What permissions are required on cross-referenced object to avoid API Post error in Salesforce?

I'm trying to use the API to create an instance of a custom object. The custom object includes a reference to a Contact. The API user has permission to create the custom object, but only has read permission on Contacts. Unfortunately, I'm getting an error "insufficient access rights on cross-reference id" and the id of the Contact I'm trying to reference on my custom object.

I'd like to keep the permission set on the API user as limited as possible, what permissions are needed on the Contact in order to avoid the error when setting a Contact reference on another object?