One possible solution, as already @Bart has pointed out, is to use abstract classes instead of interfaces. A possible problem connected with this concept is a single-inheritance issue.
Another solution could be a separation of the "private" interfaces in a different package which doesn't need to be published together with your service package thought this method can quite ruin semantics of the interfaces, specially if one logical interface would have "private" and "public" part.
Last work around which has come to mind is to utilize some patter e.g. Double dispatch or Visitor could be useful.