Forgery attack on the RPC incremental unforgeable encryption scheme
We describe a forgery attack on the RPC incremental unforgeable encryption scheme. The attack allows an adversary to forge a new ciphertext with probability 1/2 using 2r/2 incremental update queries, where r is the parameter of random values used in the RPC scheme and is at most half the block length of the block cipher used. However, the original analysis claimed that on the order of 2r queries would be needed. When applying the attack to the scheme using a block cipher with 128-bit block length and assuming r = 48 as suggested in the original article of the RPC scheme, the adversary can obtain a forgery with probability 1/2 after 224 update queries. Even in the case of 256-bit RPC scheme with r = 64, the required number of queries is only 232. We also propose two methods to strengthen the RPC scheme for defeating the proposed attack.