It has been proposed that a deep magma body beneath the east rift zone (ERZ) of Kilauea volcano, Hawaii, must be present in order to explain the observed deformation of the south flank. From November 1999 to June 2000, 29 IRIS-PASSCAL three-component seismographs were operated across Kilauea's ERZ and south flank. Using local earthquakes recorded by these stations, supplemented with data from the Hawaiian Volcano Observatory stations, we investigated the deep structure of the ERZ and south flank through two approaches: seismic velocity tomography and seismic attenuation tomography. Results along two north-northwest-south-southeast profiles are examined. The western profile shows a low-velocity region beneath and south of the Hilina Pali, and earthquakes at depth are sandwiched between a high Vp/Vs, high Q zone and a low Vp/Vs, low Q zone. The velocity and attenuation differences are interpreted to reflect the contrast in material properties between the overlying volcanic pile and the underlying fluid-rich ocean sediments and fractured, altered ocean crust beneath the south flank thrust fault. The eastern profile shows an anomalous feature with low Vp, low Vp/Vs, high Qp, and low Qs at about 7 km depth beneath the ERZ. The low Vp/Vs ratio is inconsistent with the presence of partial melt. Instead, this anomaly is attributed to a trapped reservoir of CO2. Our results do not support the existence of a sizable molten or partially molten body at depth beneath the ERZ. If the deep magma body exists, it must be relatively small. Based on synthetic resolution tests, an estimated limit on the maximum allowable cross-sectional size of the deep magma body is about 2 by 4 km.