Abstract: In this work we report on a practical design, and a working prototype implementation, of a public-key anti-counterfeiting system based on the Electronic Product Code (EPC) standard for supply chain RFID tags. The use of public-key cryptography simplifies deployment, reduces trust issues between the tag integrator and tag manufacturer, eliminates the need for on-line checks by a central authority, and protects user privacy. Contrary to earlier claims of impracticality, we demonstrate that EPC tags are capable of performing full-strength public-key encryption. The crucial element in our system is WIPR, a recently-proposed variant of the well known Rabin encryption scheme, that enjoys a remarkably low resource footprint (less than 4700 gate equivalents for a complete ASIC implementation) -- for a full-strength 1024-bit encryption. Our prototype system consists of an ultra-high frequency (UHF) tag running custom firmware, which communicates with a standard off-the-shelf reader. No modifications were made to the reader or the air interface, proving that high-security anti-counterfeiting tags and standard EPC tags can coexist and share the same infrastructure. Surprisingly, we identify that the time bottleneck is not the tag's computation time: the delay is dominated by inefficiencies in the way the reader implements the EPC standard. The insights from our performance measurements let us identify how a few simple changes to the reader can drastically improve the system throughput.