New emerging digital technologies are evolving at an unprecedented pace. These advancements create increasing expectations for public sector organizations. However, we do not yet know much about the processes of these organizations when approaching emerging technologies. Such early innovation processes are critical to be able to reap the benefits of emerging technology. In this paper we have conducted a case study of a Nordic government agency to explore how a potentially paradigm-changing idea, involving blockchain, evolves through an innovation process. We investigate how an agency approach paradigm-changing ideas in relation to emerging technology using the concept of need-solution pairing. Our contribution shows 1) how search focus shifts over time - focus can be more about the solution, the need or the (need-solution) pairing and, 2) how conceptualization of technology plays an important role in the proceeding innovation process. The findings increase our understanding of innovation processes in the public sector.