On the protection of computation results of free-roaming agents against truncation and shred-not attacks

This thesis focuses on protecting partial results collected by free-roaming agents.; All existing partial result protection schemes are vulnerable to a known attack, the two-colluder truncation attack, in which a host with an agent at hand colludes with a previously visited host to discard all entries between the two visits. We propose a new protocol (N1) that prevents the two-colluder truncation attack in free roaming agents. The main technique is to require an external party, typically the preceding host, to co-sign the agent migration.; Another known attack to partial result protection protocols is the growing-a-fake-stem attack, which is the simultaneous attack of the two-colluder truncation attack and the insertion of one or more chained fake offers in place of the truncated results. Upon receiving the returning agent, the originator can detect the unsigned offers on the fake stem and discard them. In this thesis, we are interested in enabling the originator to identify the exact pair of colluders that administered the stemming attack. We present Protocol N2 for accomplishing this.; Roth noted that the security of the KAG protocols was relied on a shredding assumption where each host was required to shred the anonymous secret key of the next host after it has generated it. Dropping this shredding assumption, we note that Protocol P4 cannot achieve strong forward integrity and other security properties, including public verification on strong forward integrity, insertion resilience and truncation resilience. We propose a new protocol (N3) to achieve these securities without relying on the shredding assumption. Public verification on strong forward integrity can also be achieved. The main technique is a new partially blinded one-pass key pair agreement (PBOPKPA) scheme, which allows a sender to agree on an anonymous public key with a receiver without knowing the corresponding anonymous private key that is self-generated by the receiver.; We note that the computation costs of partial result protection protocols using digital signature and public-key encryption schemes are high. In order to improve the efficiencies, we propose using signcryption schemes instead. A signcryption scheme is a direct implementation of joint signature and encryption schemes. Protocol N3 supports different levels of verifications for different entities, such as the originator, the next host to be visited and the public. Existing signcryption schemes cannot meet these verification requirements. We propose a dual verifiable partial signcryption scheme (DVPS) and a multi-verifiable partial signcryption scheme (MVPS) to accomplish this goal. A new and efficient partial result protection protocol (N4) is proposed based on these new signcryption schemes. (Abstract shortened by UMI.)...