On computationally complex instances of the c-optimal experimental design problem: breaking RSA-based cryptography via c-optimal design

Abstract

We study the computational complexity of the problem to find a c-optimal experimental design over a finite experimental domain. We construct instances of the problem which are computationally very difficult: we show how any algorithm for c-optimality can be used for integer factoring and hence for breaking the RSA cryptographic protocol.

These ‘hard’ instances can also be used as a benchmark for testing algorithms for finding c-optimal designs.

Keywords

• c-optimal experimental design
• RSA
• cryptography