Public service delivery—such as the issuance of a passport—is a core function of public administrations worldwide. Traditionally, citizens and businesses are required to submit supporting documents (e.g., a certificate of family status) to verify their eligibility for a service. This document-based approach introduces many inefficiencies, including redundancy, overexposure of personal data, and increased bureaucracy. Specifically: (i) submitted documents often contain significantly more information than needed, unnecessarily exposing personal data; and (ii) public administrations usually request documents to verify facts already available within government systems, due to poor process design or lack of interoperability. A promising alternative is a shift from document-centric to data-centric public service delivery. By identifying only the specific data required from submitted documents and retrieving it directly through public administration web services, service provision can be streamlined and personal data exposure minimized. This paper presents and demonstrates the preparatory steps needed towards this paradigm shift through a case study of the Greek public administration. Our findings show that Greek Public administrations have an average maturity to proceed with this paradigm shift, and more relevant web services are required to enable broader automation.