An Improved Range Proof with Base-3 Construction

Günsay, Esra
Onur, Cansu Betin
Cenk, Murat
Zero-knowledge protocols (ZKPs) allow a party to prove the validation of secret information to some other party without revealing any information about the secret itself. Appropriate, effective, and efficient use of cryptographic ZKPs contributes to many novel advances in real-world privacy-preserving frameworks. One of the most important type of cryptographic ZKPs is the zero-knowledge range proofs (ZKRPs). Such proofs have wide range of applications such as anonymous credentials, cryptocurrencies, e-cash schemes etc. In many ZKRPs the secret is represented in binary then committed via a suitable commitment scheme. Though there exist different base approaches on bilinear paring-based and RSA-like based constructions, to our knowledge there is no study on investigating the discrete logarithm-based constructions. In this study, we focus on a range proof construction produced by Mao in 1998. This protocol contains a bit commitment scheme with an OR-construction. We investigate the effect of different base approach on Mao's range proof and compare the efficiency of these basis approaches. To this end, we have extended Mao's range proof to base-3 with a modified OR-proof. We derive the number of computations in modulo exponentiations and the cost of the number of integers exchanged between parties. Then, we have generalized these costs for the base-u construction. Here, we mainly show that comparing with other base approaches, the base-3 approach consistently provides approximately 12% efficiency in computation cost and 10% efficiency in communication cost. We implemented the base-3 protocol and demonstrated that the results are consistent with our theoretical computations.
14th International Conference on Security of Information and Networks, SIN 2021


Pseudo-voter identity (PVID) scheme for e-voting protocols
Cetinkaya, Orhan; Doğanaksoy, Ali (2007-04-13)
Voter anonymity, also known as unlinkability, is the primary requirement to satisfy privacy in e-voting protocols. Up until now, e-voting protocols have tried to make communication channels anonymous in order to keep voter's identity hidden and many protocols have been proposed to construct anonymous communication channels. On the other hand, instead of making channel anonymous if we provide anonymous credentials to voter, we can easily hide voter's identity without any need of anonymous channels. This pap...
Particle filter based Conjoint Individual-Group Tracker (CIGT)
YİĞİT, Ahmet; Temizel, Alptekin (2015-08-28)
In this paper, we present a method for joint tracking of individuals and groups in surveillance scenarios. Groups are dynamic entities and they may grow or shrink with merge-split events. This dynamic nature makes it difficult to track groups using conventional trackers. In this paper, we propose a new tracking method named Conjoint Individual and Group Tracker (CIGT) based on particle filter with multi-observation model and particle advection. The proposed multi-observation model uses in-group and out-grou...
Advanced methods for diversification of results in general-purpose and specialized search engines
Yiğit Sert, Sevgi; Altıngövde, İsmail Sengör; Ulusoy, Özgür; Department of Computer Engineering (2020-12-28)
Diversifying search results is a common mechanism in information retrieval to satisfy more users by surfacing documents that address different possible intentions of users. It aims to generate a result list that is both relevant and diverse when ambiguous and/or broad queries appear. Such queries have different underlying subtopics (a.k.a., aspects or interpretations) that search result diversification algorithms should consider. In this thesis, we first address search result diversification as a useful met...
On Hiding a Plaintext Length by Preencryption
Tezcan, Cihangir (2011-01-01)
It is a well known fact that encryption schemes cannot hide a plaintext length when it is unbounded. We thus admit that an approximation of it may leak and we focus on hiding its precise value. Some standards such as TLS or SSH offer to do it by applying some pad-then-encrypt techniques. In this study, we investigate the information leakage when these techniques are used. We define the notion of padding scheme and its associated security. We show that when a padding length is uniformly distributed, the sche...
Keskinkurt Paksoy, İrem; Cenk, Murat; Department of Cryptography (2022-7-28)
One of the quantum-safe cryptography research areas is lattice-based cryptography. Most lattice-based schemes need efficient algorithms for multiplication in polynomial quotient rings. The fastest algorithm known for multiplication is the Number Theoretic Transform (NTT), which requires certain restrictions on the parameters of the ring, such as prime modulus. Direct NTT application is not an option for some schemes that do not comply with these restrictions, e.g., the two finalists of the PQC standardizati...
Citation Formats
E. Günsay, C. B. Onur, and M. Cenk, “An Improved Range Proof with Base-3 Construction,” presented at the 14th International Conference on Security of Information and Networks, SIN 2021, Virtual, Online, Birleşik Krallık, 2021, Accessed: 00, 2022. [Online]. Available: