Put each painting in an artsy frame whose edges are each different, colorful pattern. When the user photographs the painting, they’ll include all (or even most) of the frame, and distinguishing the frames is easy.
Embedding a QR code or simply a barcode somewhere and you're done. Maybe hide it like a watermark so it does not show to the naked eye and doing some Fourier transform in the app won't require a network connection nor lot of processing power.
the article does mention that the client rejected a similar approach. steganography seems like a bad choice for a museum setting where you don't own the images.
Embedding a QR code or simply a barcode somewhere and you're done. Maybe hide it like a watermark so it does not show to the naked eye and doing some Fourier transform in the app won't require a network connection nor lot of processing power.