AWS API Gateway authentication error IncompleteSignatureException using JWT with Auth0

I'm guessing you have AWS_IAM authentication enabled for your API Gateway endpoint. You need to disable that if you aren't planning to use it. If you plan to use AWS_IAM authentication in addition to JWT then you will have to send the JWT token using a different field.

From part 5 of the Auth0 tutorial you linked:

The final step is to pass the JWT to the method from the browser client. The standard method is with an Authorization header as a bearer token, and you can use this method if you turn off IAM authorization and rely solely upon the OpenID token for authorization (you will also need to map the Authorization header into the event data passed to the AWS Lambda function). If you are using IAM, then the AWS API Gateway uses the Authorization header to contain the signature of the message, and you will break the authentication by inserting the JWT into this header. You could either add a custom header for the JWT, or put it into the body of the message. If you choose to use a custom header, you'll also need to do some mapping for the Integration Request of the POST method

Based on the error message, it sounds like you've configured your API for AWS_IAM authentication. This requires your request be signed with AWS Signature Version 4.

In order to execute API Gateway functions you will need to do 1 of 3 things:

1. Get AWS credentials via IAM/STS as noted in the auth0 example and use those to sign your request.
2. As noted in Mark B's answer, follow the instructions in step 5 of the tutorial from auth0 and disable AWS_IAM auth and do the validation inside your Lambda.
3. Switch to use a custom authorizer to validate the JWT directly at the API Gateway layer. This would require you to take the code Auth0 provides to validate the token then build your own authorizer result.