International Association for Cryptologic Research

International Association
for Cryptologic Research


Huang Lin


Efficient Range Proofs with Transparent Setup from Bounded Integer Commitments 📺
We introduce a new approach for constructing range proofs. Our approach is modular, and leads to highly competitive range proofs under standard assumption, using less communication and (much) less computation than the state of the art methods, and without relying on a trusted setup. Our range proofs can be used as a drop-in replacement in a variety of protocols such as distributed ledgers, anonymous transaction systems, and many more, leading to significant reductions in communication and computation for these applications. At the heart of our result is a new method to transform any commitment over a finite field into a commitment scheme which allows to commit to and efficiently prove relations about bounded integers. Combining these new commitments with a classical approach for range proofs based on square decomposition, we obtain several new instantiations of a paradigm which was previously limited to RSA-based range proofs (with high communication and computation, and trusted setup). More specifically, we get: - Under the discrete logarithm assumption, we obtain the most compact and efficient range proof among all existing candidates (with or without trusted setup). Our proofs are 12% to 20% shorter than the state of the art Bulletproof (Bootle et al., CRYPTO'18) for standard choices of range size and security parameter, and are more efficient (both for the prover and the verifier) by more than an order of magnitude. - Under the LWE assumption, we obtain range proofs that improve over the state of the art in a batch setting when at least a few dozen range proofs are required. The amortized communication of our range proofs improves by up to two orders of magnitudes over the state of the art when the number of required range proofs grows. - Eventually, under standard class group assumptions, we obtain the first concretely efficient standard integer commitment scheme (without bounds on the size of the committed integer) which does not assume trusted setup.
How to Construct Space Efficient Revocable IBE from Non-monotonic ABE
Since there always exists some users whose private keys are stolen or expired in practice, it is important for identity based encryption (IBE) system to provide a solution for revocation. The current most efficient revocable IBE system has a private key of size $\mathcal{O}(\log n)$ and update information of size $\mathcal{O}(r \log(\frac{n}{r}))$ where $r$ is the number of revoked users. We describe a new revocable IBE systems where the private key only contains two group elements and the update information size is $\mathcal{O}(r)$. To our best knowledge, the proposed constructions serve as the most efficient revocable IBE constructions in terms of space cost. Besides, this construction also provides a generic methodology to transform a non-monotonic attribute based encryption into a revocable IBE scheme. This paper also demonstrates how the proposed method can be employed to present an efficient revocable hierarchical IBE scheme.
Cryptanalysis of An Oblivious Polynomial Evaluation Protocol Based On Polynomial Reconstruction Problem
Huang Lin Zhenfu Cao
In 1999, Naor and Pinkas \cite {NP99} presented a useful protocol called oblivious polynomial evaluation(OPE). In this paper, the cryptanalysis of the OPE protocol is presented. It's shown that the receiver can successfully get the sender's secret polynomial $P$ after executing the OPE protocol only once, which means the privacy of the sender can be violated and the security of the OPE protocol will be broken. It's also proven that the complexity of the cryptanalysis is the same with the corresponding protocols cryptanalyzed.
Short Group Signature without Random Oracles
We construct a short group signature which is proven secure without random oracles. By making certain reasonable assumptions and applying the technique of non-interactive proof system, we prove that our scheme is full anonymity and full traceability. Compared with other related works, such as BW06, BW07, ours is more practical due to the short size of both public key and group signature.