Does side-channel attacks offer any difficulty to Stinson's concept of `provable security'? Here's a quote from Douglas Stinson:


  “[i]f a cryptosystem can be ‘broken’ in some specific way, then it
  would be possible to efficiently solve some well-studied problem that
  is thought to be difficult. For example, it may be possible to prove a
  statement of the type “a given cryptosystem is secure if a given
  integer n cannot be factored.” [...] [B]ut it must be understood that
  this approach only provides a proof of security relative to some other
  problem, not an absolute proof of security. This is a similar
  situation to proving that a problem is NP-complete [...].”


Source: Stinson, D. R. (2006). Cryptography, Theory and Practice. Chapman
and Hall, CRC, 3rd edition. Chapter 2, section 2.1, page 45.

Say there is a proof that a cryptosystem $X$ satisfies Stinson's definition.  An attacker builds a method to break $X$ by side-channel attacks.  Does that offer any trouble to the definition or to my proof?  Or would you say side-channel attacks have nothing to do with provable security?
Say there is a proof that a cryptosystem X satisfies Stinson's definition. An attacker builds a method to break X by side-channel attacks. Does that offer any trouble to the definition or to my proof?


Not generally: The proof covers the algorithm, and side channel attacks target the implementation. 

If someone threatens to hurt you unless (or until) you give them your private key, that doesn't violate the provable security claim of the algorithm. 

The algorithm is an abstract idea, and the provable security guarantee would indicate that no other abstract idea (algorithm) could violate the security without providing a solution to another abstract problem.


  Or would you say side-channel attacks have nothing to do with provable security?


More or less, yes; You can't have provable security against rubber hose cryptanalysis, you can't provide security if the attacker is watching over your shoulder as you perform the algorithm with pencil and paper, you can't have security if your program prints it's state at every step of the way to a log file the adversary has access to, etc.

Basically

Proofs rest on assumptions (even if they're not stated explicitly). If you violate those assumptions, then you can skirt around the guarantees provided by the proof. 

This is one reason why provably secure algorithms would ideally be combined with side channel resistant techniques (e.g. constant time code, blinding, etc) and formally verified implementations.