There is a well-established culture of early prototyping when designing digital interactive systems, such as paper prototyping and wireframe methods. The culture of designing physical objects is somewhat different: early explorations of form is still prototyped via 2D sketches or renderings, but - mostly because of the construction effort involved - prototyping of actual physical objects is deferred to later stages. A problem occurs when designing mixed physical-digital systems, such as tangible user interfaces (TUIs) on interactive surfaces: the high degree of interactivity means that early prototyping is vital, yet there is no viable process for prototyping both the physical and digital aspects simultaneously on a low-fidelity (low-fi) level. Our solution is Paperbox, a toolkit for exploring design ideas for tangible interaction on interactive surfaces. It supports the early exploration of different form factors and immediately provides digital interactivity for the low-fidelity TUI prototypes built with it. We observed our toolkit in use in various settings: as a brainstorming tool by junior designers; in the development of a consumer electronics product in a large industrial company by senior designers; and in a usability study comparing the effect of different levels of fidelity on the outcome. The lessons learnt will enable others to replicate and extend our approach.