Salesforce REST API how to avoid leaking sensitive data in query parameter

You have two options.

1. Parameterized Search API. This option is available out of the box with POST as the method. The API is a RESTful interface to Salesforce's text-based search engine. Normally, text-based search uses SOSL as the query language. Parameterized Search API skips SOSL and gives you an easier option to work with.

If you POST the following body to /services/data/v48.0/parameterizedSearch

{
   "q": "123456789",
   "sobjects": [
      {
         "name": "Contact",
         "where": "SSN__c = '123456789'"
      }
   ],
   "fields": ["id"]
}

you should see something like this as the response, assuming single record is returned by search (ID is redacted):

{
  "searchRecords" : [ {
    "attributes" : {
      "type" : "Contact",
      "url" : "/services/data/v48.0/sobjects/Contact/003..."
    },
    "Id" : "003..."
  } ]
}

The value of q key in the JSON payload must be the same as the value in the where key/clause. You're doing a full-text search on 123456789 across all objects and all fields in the search index. This could return many records..but you're filtering the search down in a structured way to guarantee that you'll only see Contact records where SSN__c = '123456789'. As long as the objects + fields you're trying to retrieve are present in the index the results you'll see via Parameterized Search in this specific example are going to be the same as that of a SOQL query via /query

2. Custom REST API (aka Apex REST / Apex web service). This is a typical implementation option for cases like yours. You can send whatever payload via POST and then process it however you like.

Apex class:

@RestResource(urlMapping='/findcontactbyssn')
global class ContactResource {
    @HttpPost
    global static void findContactBySSN() {
        SearchRequest input = (SearchRequest)JSON.deserialize(RestContext.request.requestBody.toString(),SearchRequest.class);
        Contact c = [SELECT Id FROM Contact WHERE SSN__c = :input.ssn];
        SearchResponse output = new SearchResponse();
        output.id = c.id;
        RestContext.response.responseBody = Blob.valueOf(JSON.serialize(output));
        RestContext.response.statusCode = 200;  
    }

    class SearchRequest {
      public String ssn {get;set;}
    }

    class SearchResponse {
      public String id {get;set;}
    }
}

POST to /services/apexrest/findcontactbyssn with

{
 "ssn": "12345678"
}

and you should see this response:

{
 "id": "003..."
}

AFAIK, salesforce only provides a GET method for executing SOQL queries. One can write their own REST endpoint in their org that accepts a query in body and execute it, but thats a waste of time in my opinion.

Query string parameters are secured over https. Its a common misconception, where people think whole url is open in plain text in transmission. When a request is made to an https url, first it establishes a Secure Tunnel to [instance-url].my.salesforce.com then transmits the rest of the url and any other data over the secure tunnel.

If you're worried about some man in the middle attack sniffing out the SSN from your query string, don't. One downside is, if you are accessing this url from a browser instead of a programmatic call, then there is a chance for browser to stored/cache for history or auto complete, then it won't be so good.

But I doubt if you would be able to do this via browser, as salesforce requires a bearer token set in Authorization header and there is no easy way that I know of to set headers while typing the url in the browser or clicking a link.

To know more about how query string is secure over https please refer to this stackoverflow question