Cloud computing offers multiple benefits to users by offloading them of the tasks of setting up complex infrastructure and costly services. However, these benefits come with a price, namely that the Cloud Service Customers (CSCs) need to trust the Cloud Service Providers (CSPs) with their data, and additionally being exposed to integrity and confidentiality related incidents on the CSPs. Thus, it is important for CSCs to know what security assurances the CSPs are able to guarantee by being able to quantitatively or qualitatively compare CSPs offers with respect to their own needs. On the other hand, it is also important for CSPs to assess their own offers by comparing them to the competition and with the CSCs needs, to consequently improve their offers and to gain better trust. Thus there is a basic need for techniques that address the Cloud security assessment problem. Although a few assessment methodologies have recently been proposed, their value comes only if they can be efficiently executed to support actual decisions at run time. For an assessment methodology to be practical, it should be efficient enough to allow CSCs to adjust their preferences while observing on the fly the current evaluation of CSPs’ offers based on the preferences that are being chosen. Furthermore, for an assessment methodology to be useful in real-world applications, it should be efficient enough to support many requests in parallel, taking into account the growing number of CSPs and the variety of requirements that CSCs might have. In this paper, we develop a novel Cloud security assessment technique called Moving Intervals Process (MIP) that possesses all these qualities. Unlike the existing complex approaches (e.g., Quantitative Hierarchical Process – QHP) that are computationally too expensive to be deployed for the needed on-line real-time assessment, MIP offers both accuracy and high computational efficiency. Additionally, we also show how to make the existing QHP competitively efficient.