There are two obvious possible solutions to this from the city:

(1) tiny print on the parking signs that says you consent to be chalked, creating an explicit contract

(2) sell the rights to manage the city's parking to a private entity using private contractors to chalk with no prescription on methodology, rendering the "search" non-governmental in nature