Matrix decomposition problem over integer ring is presented. Solving methods are discussed and it is showed, that this problem is hard computational problem regard to computer memory resources. A key agreement protocol based on matrix decomposition problem is presented.