this if I understand you right you're trying to declare all the methods of your concrete class in the interface?!?
Well, as you said method declarations inside an interface are implicitly public but that's OK. You should only declare the methods which belong to the public API of a class, i.e. the methods which should be called by client code! So just leave out the private methods in the interface definition. This has nothing to do with the public interface of you class. Without the interface you concrete class at the moment offers only one public method "verify" to clients. A client of your code won't (and can't) care of the private methods as long as the one and only public method does its job. You only created the private helper methods to keep your code clean instead of putting everything into one big method. That's definitely a good decision but it is not relevant for the public interface!
You can look at this from another point of view. If it WOULD be possible to declare private methods in an interface then you would tell an implementing class HOW it should do its work but the reasoning behind an interface is not to tell HOW something should be implemented but just WHAT functionality has to be implemented by a concrete class. Therefore it's easy to have multiple concrete classes which implement the same interface without caring about how they do their work internally as long as they fulfill the contract of the public API (= interface).
If you wish to inherit your helper functions and reuse their implementation details in derivative classes then you can make the package or protected level access and have this class implement the public interface. Other classes would extend this base class and so have the same interface plus access to some of the implementation details.