Abstract: The aim of this study an incremental encryption scheme that can reduce the necessary recomputation of blocks insertion and deletion on an encrypted data. Both of privacy and integrity of the encrypted data are guaranteed. The scheme has very good property of incrementality in the case that the underlying block cipher is far complicated than the simple mathematic operations such as Addition/Subtraction. It bases on the block encryption mode that is parallelizable and integrity assured.