eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2023/180

Asymmetric Trapdoor Pseudorandom Generators: Definitions, Constructions, and Applications to Homomorphic Signatures with Shorter Public Keys

Jinpeng Hou, Nanjing University of Science and Technology
Yansong Gao, Data61
Anmin Fu, Nanjing University of Science and Technology
Jie Chen, East China Normal University
Xiaofeng Chen, Xidian University
Yuqing Zhang, University of Chinese Academy of Sciences
Willy Susilo, University of Wollongong
Josef Pieprzyk, Data61
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 space-efficient 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 one-dimension 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)
PDF
Category
Public-key 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
2023-05-29: last of 4 revisions
2023-02-13: received
See all versions
Short URL
https://ia.cr/2023/180
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.