Mobile phone-based applications (apps) can promote faster targeted actions to control COVID-19. However, digital contact tracing systems raise concerns about data security, system effectiveness, and their potential to normalise privacy-invasive surveillance technologies. In the absence of mandates, public uptake depends on the acceptability and perceived legitimacy of using technologies that log interactions between individuals to build public health capacity. We report on six online deliberative workshops convened in New South Wales to consider the appropriateness of using the COVIDSafe app to (...) enhance Australian contact tracing systems. All groups took the position (by majority) that the protections enacted in the app design and supporting legislation were appropriate. This support is contingent on several system attributes including: the voluntariness of the COVIDSafe app; that the system relies on proximity rather than location tracking; and, that data access is restricted to local public health practitioners undertaking contact tracing. Despite sustained scepticism in media coverage, there was an underlying willingness to trust Australian governing institutions such that in principle acceptance of the new contact tracing technology was easy to obtain. However, tensions between the need to prove system effectiveness through operational transparency and requirements for privacy protections could be limiting public uptake. Our study shows that informed citizens are willing to trade their privacy for common goods such as COVID-19 suppression. But low case numbers and cautionary public discourses can make trustworthiness difficult to establish because some will only do so when it can be demonstrated that the benefits justify the costs to individuals. (shrink)