Abstract Stealth address is a known technique to ensure the privacy (anonymity) of a recipient participating in a certain transaction in a distributed blockchain scenario. However, most existing stealth address schemes require linear judge time and search time $\mathcal{O}(n)$, where $n$ is the number of transactions of a certain block, so the only way to claim transactions for a recipient is to traverse the transaction list to find out whether an ever-arrived transaction belongs to him. To overcome this drawback, we proposed the notion of Fast Stealth Address (FSA), a novel approach that simultaneously preserves privacy and improves search efficiency of recipients. We give a generic construction of FSA scheme under subgroup membership assumption related to factoring and instantiate concrete schemes based on specific number-theoretic assumptions. Our framework mainly improves on two aspects: (i) allowing constant recognize time $\mathcal{O}(1)$ to judge whether a certain block contains recipient’s transactions and (ii) allowing logarithmic search time $\mathcal{O}(\log{n})$ to find out the precise transactions intended for a recipient. We formalize the security model of an FSA scheme and provide provable security analysis to ensure the security of our constructions. Besides, we implement our schemes to measure their real-world performance on several metrics and give comparison results to stealth address scheme utilized by Monero.

Multi-client delegatable computation over outsourced data is an important research area in the context of cloud computing. The main target of it is to produce a function value taken data owned by different users as input while assuring the correctness of the derived result efficiently verifiable. Multi-key homomorphic signature (MK-HS), which allows for computations over signed data originating from multiple users while providing authenticity for the output value, is considered as an elegant primitive to fulfill the above functionality. However, we figure out several deficiencies in the context of MK-HS: (1) the model of MK-HS inevitably induces the participation of a large set of distinct public keys during the procedures of evaluation and verification, which leads to high communication and computation complexity; (2) current MK-HS schemes based on standard assumptions cannot prevent insider corruption attack; (3) the signature succintness of existing MK-HS constructions is far from optimal. In this work, we aim to seek a more appropriate approach for realizing multi-client delegatable computation. Our main result is the introduction of a new model we callmessage-oriented key-homomorphic signatures($\mathsf {moKHS}$). This model provides more lightweight definitions and inherently resists to insider corruption attacks. Besides, we provide a$\mathsf {moKHS}$construction based on standard lattices which supports circuits of bounded polynomial depth, and it achieves weak security and input-independent efficiency (in an amortized sense). Furthermore, we present a transformation to obtain an adaptively-secure one from any weakly-secure$\mathsf {moKHS}$scheme. Notably, the signature obtained by our$\mathsf {moKHS}$scheme achievesoptimalsuccinctness in the sense that its size is independent of both the number of users involved in the computation and the input size of the program. All these improvements show that$\mathsf {moKHS}$is a more preferable candidate for applications of delegating computation involving multiple users.

Abstract Homomorphic message authentication codes (MACs) allow a user to outsource data to an untrusted server and verify the correctness of returned computation results over the outsourced data. Many cloud applications need delegation computations over outsourced data with dual capabilities. On one hand, they need to keep the outsourced data secret such that the server cannot trace and infer any sensitive information from the computation results. On the other hand, the user should be able to efficiently verify the computation results. Unfortunately, the state-of-the-art homomorphic MAC schemes are not so desirable due to either poor privacy or low verification efficiency. In this paper, we first put forward a new cryptographic primitive called privacy-preserving homomorphic MACs (PHMAC) that simultaneously provides data privacy and efficient verification. Then, we present a PHMAC construction capable for the evaluation of polynomials of fixed degree $d\geq 1$, in which the tag does not reveal any information of underlying authenticated data while being verifiable in constant time (in an amortized sense). As an application, we give a generic construction of homomorphic authenticated encryption (HAE) from proposed PHMAC and homomorphic encryption. Benefited from the functionalities of underlying PHMAC scheme, the derived HAE enjoys stronger authenticity and supports larger classes of functions than that of Lai et al. (Verifiable Computation on Outsourced Encrypted Data. In Computer Security—ESORICS 2014—19th European Symposium on Research in Computer Security, Wroclaw, Poland, September 7–11, Part I, pp. 273–291. Springer, Berlin). Such HAE enables verifiable delegation computations over growing outsourced encrypted data in an efficient way.