One of the most successful working examples of virtualor ganizations, computational grids need authentication mechanisms that inter-operate across domain boundaries. Public Key Infrastructures (PKIs) provide sufficient flexibility to allow resource managers to securely grant access to their systems in such distributed environments. However, as PKIs grow and services are added to enhance both security and usability, users and applications must struggle to discover available resources—particularly when the Certification Authority (CA) is alien to the relying party. This paper presents how to overcome these limitations of the current grid authentication model by integrating the PKI Resource Query Protocol (PRQP) into the Grid Security Infrastructure (GSI).