Path validation has been explored as an indispensable security feature for the future Internet. Motivated by the Path-Aware Networking Research Group (PANRG) under the Internet Engineering Task Force (IETF) and Internet Research Task Force (IRTF), it gives end-hosts more control over packet forwarding and ensures that the forwarding history is verifiable. The main idea is to require that routers add proofs in packet headers for other routers to verify. We identify linear-scale proofs as the essential efficiency barrier of existing path validation solutions. In this paper, we propose Atomos to validate network paths with constant-size proofs. To this end, we construct a noncommutative homomorphic asymmetric-key encryption scheme. Asymmetric cryptography minimizes the number of proofs needed and saves time in processing proofs. The homomorphism we design yields constant-size proofs. It limits the header-space overhead and outperforms existing linear-scale counterparts when the path length exceeds a value that is usually small. Furthermore, the proposed encryption scheme is noncommutative so that any deviation from the forwarding path can be detected. We explore a series of design strategies for security and efficiency. The evaluation results show that Atomos yields not only shorter proofs but also faster validation than existing solutions.

In multisignature scheme, verifiying the signing order is sometimes very important. A multisignature scheme in which generated signatures reflect the structure of signers, e.g. signing order, is called structured multisignature scheme and many such schemes have been proposed so far. Structured multisignature schemes are dedicated to represent not only serial/parallel signer structures but also mixture of serial and parallel signer structures. In most structured schemes, the signature size depends on the number of signers. There are some structured schemes which can generate fixed-size signatures, but these schemes do not have order-flexibility, i.e. public keys arranged for one signer structure cannot be used for other signer structure. On the other hand, a sequential multisignature scheme is one type of structured multisignature schemes, which is dedicated to represent the serial signer structure. Some sequential multisig-nature scheme like sequential aggregate signature schemes can generate fixed-size signatures and have order-flexibility but no structured aggregate signature scheme has been proposed so far. In this paper, we construct a structured aggregate scheme which provides order-flexiblity, the fixed-size signature and applicability to mixed signer structures by extending the sequential aggregate signature scheme by Boldyreva et al.