Paper 2023/180
Asymmetric Trapdoor Pseudorandom Generators: Definitions, Constructions, and Applications to Homomorphic Signatures with Shorter Public Keys
Abstract
We introduce a new primitive called the asymmetric trapdoor pseudorandom generator (ATPRG), which belongs to pseudorandom generators with two additional trapdoors (a public trapdoor and a secret trapdoor) or backdoor pseudorandom generators with an additional trapdoor (a secret trapdoor). Specifically, ATPRG can only generate public pseudorandom numbers $pr_1,\dots,pr_N$ for the users having no knowledge of the public trapdoor and the secret trapdoor; so this function is the same as pseudorandom generators. However, the users having the public trapdoor can use any public pseudorandom number $pr_i$ to recover the whole $pr$ sequence; so this function is the same as backdoor pseudorandom generators. Further, the users having the secret trapdoor can use $pr$ sequence to generate a sequence $sr_1,\dots,sr_N$ of the secret pseudorandom numbers. ATPRG can help design more spaceefficient protocols where data/input/message should respect a predefined (unchangeable) order to be correctly processed in a computation or malleable cryptographic system. As for applications of ATPRG, we construct the first homomorphic signature scheme (in the standard model) whose public key size is only $O(T)$ that is independent of the dataset size. As a comparison, the shortest size of the existing public key is $O(\sqrt{N}+\sqrt{T})$, proposed by Catalano et al. (CRYPTO'15), where $N$ is the dataset size and $T$ is the dimension of the message. In other words, we provide the first homomorphic signature scheme with $O(1)$sized public keys for the onedimension messages.
Note: Fixed some misuses of symbols: the symbol $m_i[j]$ in equations (4) and (6) are changed to $\overline{m}[j]$, and the symbol $n$ on page 24 is changed to $N$.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint.
 Keywords
 Pseudorandom GeneratorsHomomorphic SignaturesStandard Model
 Contact author(s)

jinpenghou @ njust edu cn
garrison gao @ data61 csiro au
fuam @ njust edu cn
s080001 @ e ntu edu sg
xfchen @ xidian edu cn
zhangyq @ ucas ac cn
wsusilo @ uow edu
josef pieprzyk @ data61 csiro au  History
 20230529: last of 4 revisions
 20230213: received
 See all versions
 Short URL
 https://ia.cr/2023/180
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/180, author = {Jinpeng Hou and Yansong Gao and Anmin Fu and Jie Chen and Xiaofeng Chen and Yuqing Zhang and Willy Susilo and Josef Pieprzyk}, title = {Asymmetric Trapdoor Pseudorandom Generators: Definitions, Constructions, and Applications to Homomorphic Signatures with Shorter Public Keys}, howpublished = {Cryptology ePrint Archive, Paper 2023/180}, year = {2023}, note = {\url{https://eprint.iacr.org/2023/180}}, url = {https://eprint.iacr.org/2023/180} }