On Several Verifiable Random Functions and the q-decisional Bilinear Diffie-Hellman Inversion Assumption
Pages 45 - 51
Abstract
In 1999, Micali, Rabin and Vadhan introduced the notion of Verifiable Random Functions (VRF)\citeFOCS:MicRabVad99. VRFs compute for a given input x and a secret key $sk$ a unique function value $y=V_sk (x)$, and additionally a publicly verifiable proof π. Each owner of the corresponding public key $pk$ can use the proof to non-interactivly verify that the function value was computed correctly. Furthermore, the function value provides the property of pseudorandomness. Most constructions in the past are based on q-type assumptions. Since these assumptions get stronger for a larger factor q, it is desirable to show the existence of VRFs under static or general assumptions. In this work we will show for the constructions presented in \citePKC:DodYam05 \citeCCS:BonMonRag10 the equivalence of breaking the VRF and solving the underlying q-type assumption.
References
[1]
Michel Abdalla, Dario Catalano, and Dario Fiore. Verifiable random functions: Relations to identity-based key encapsulation and new constructions. Journal of Cryptology, 27(3):544--593, July 2014.
[2]
Man Ho Au, Willy Susilo, and Yi Mu. Practical compact e-cash. In Josef Pieprzyk, Hossein Ghodosi, and Ed Dawson, editors, ACISP 07: 12th Australasian Conference on Information Security and Privacy, volume 4586 of Lecture Notes in Computer Science, pages 431--445, Townsville, Australia, July 2--4, 2007. Springer, Heidelberg, Germany.
[3]
Nir Bitansky. Verifiable random functions from non-interactive witness-indistinguishable proofs. In Yael Kalai and Leonid Reyzin, editors, TCC 2017: 15th Theory of Cryptography Conference, Part II, volume 10678 of Lecture Notes in Computer Science, pages 567--594, Baltimore, MD, USA, November 12--15, 2017. Springer, Heidelberg, Germany.
[4]
Dan Boneh and Xavier Boyen. Efficient selective-ID secure identity based encryption without random oracles. In Christian Cachin and Jan Camenisch, editors, Advances in Cryptology -- EUROCRYPT 2004, volume 3027 of Lecture Notes in Computer Science, pages 223--238, Interlaken, Switzerland, May 2--6, 2004. Springer, Heidelberg, Germany.
[5]
Dan Boneh and Xavier Boyen. Short signatures without random oracles. In Christian Cachin and Jan Camenisch, editors, Advances in Cryptology -- EUROCRYPT 2004, volume 3027 of Lecture Notes in Computer Science, pages 56--73, Interlaken, Switzerland, May 2--6, 2004. Springer, Heidelberg, Germany.
[6]
Dan Boneh, Hart William Montgomery, and Ananth Raghunathan. Algebraic pseudorandom functions with improved efficiency from the augmented cascade. In Ehab Al-Shaer, Angelos D. Keromytis, and Vitaly Shmatikov, editors, ACM CCS 10: 17th Conference on Computer and Communications Security, pages 131--140, Chicago, Illinois, USA, October 4--8, 2010. ACM Press.
[7]
Zvika Brakerski, Shafi Goldwasser, Guy N. Rothblum, and Vinod Vaikuntanathan. Weak verifiable random functions. In Omer Reingold, editor, TCC 2009: 6th Theory of Cryptography Conference, volume 5444 of Lecture Notes in Computer Science, pages 558--576. Springer, Heidelberg, Germany, March 15--17, 2009.
[8]
Jan Camenisch, Susan Hohenberger, and Anna Lysyanskaya. Compact e-cash. In Ronald Cramer, editor, Advances in Cryptology -- EUROCRYPT 2005, volume 3494 of Lecture Notes in Computer Science, pages 302--321, Aarhus, Denmark, May 22--26, 2005. Springer, Heidelberg, Germany.
[9]
Melissa Chase and Sarah Meiklejohn. Déjà Q: Using dual systems to revisit q-type assumptions. In Phong Q. Nguyen and Elisabeth Oswald, editors, Advances in Cryptology -- EUROCRYPT 2014, volume 8441 of Lecture Notes in Computer Science, pages 622--639, Copenhagen, Denmark, May 11--15, 2014. Springer, Heidelberg, Germany.
[10]
Jung Hee Cheon. Security analysis of the strong Diffie-Hellman problem. In Serge Vaudenay, editor, Advances in Cryptology -- EUROCRYPT 2006, volume 4004 of Lecture Notes in Computer Science, pages 1--11, St. Petersburg, Russia, May 28 -- June 1, 2006. Springer, Heidelberg, Germany.
[11]
Sherman S. M. Chow, Lucas C. K. Hui, S. M. Yiu, and K. P. Chow. An e-lottery scheme using verifiable random function. In Proceedings of the 2005 International Conference on Computational Science and Its Applications - Volume Part III, ICCSA'05, pages 651--660, Berlin, Heidelberg, 2005. Springer-Verlag.
[12]
Yevgeniy Dodis. Efficient construction of (distributed) verifiable random functions. In Yvo Desmedt, editor, PKC 2003: 6th International Workshop on Theory and Practice in Public Key Cryptography, volume 2567 of Lecture Notes in Computer Science, pages 1--17, Miami, FL, USA, January 6--8, 2003. Springer, Heidelberg, Germany.
[13]
Yevgeniy Dodis and Aleksandr Yampolskiy. A verifiable random function with short proofs and keys. In Serge Vaudenay, editor, PKC 2005: 8th International Workshop on Theory and Practice in Public Key Cryptography, volume 3386 of Lecture Notes in Computer Science, pages 416--431, Les Diablerets, Switzerland, January 23--26, 2005. Springer, Heidelberg, Germany.
[14]
Dario Fiore and Dominique Schröder. Uniqueness is a different story: Impossibility of verifiable random functions from trapdoor permutations. In Ronald Cramer, editor, TCC 2012: 9th Theory of Cryptography Conference, volume 7194 of Lecture Notes in Computer Science, pages 636--653, Taormina, Sicily, Italy, March 19--21, 2012. Springer, Heidelberg, Germany.
[15]
Rishab Goyal, Susan Hohenberger, Venkata Koppula, and Brent Waters. A generic approach to constructing and proving verifiable random functions. In Yael Kalai and Leonid Reyzin, editors, TCC 2017: 15th Theory of Cryptography Conference, Part II, volume 10678 of Lecture Notes in Computer Science, pages 537--566, Baltimore, MD, USA, November 12--15, 2017. Springer, Heidelberg, Germany.
[16]
Dennis Hofheinz and Tibor Jager. Verifiable random functions from standard assumptions. In Eyal Kushilevitz and Tal Malkin, editors, TCC 2016-A: 13th Theory of Cryptography Conference, Part I, volume 9562 of Lecture Notes in Computer Science, pages 336--362, Tel Aviv, Israel, January 10--13, 2016. Springer, Heidelberg, Germany.
[17]
Susan Hohenberger and Brent Waters. Constructing verifiable random functions with large input spaces. In Henri Gilbert, editor, Advances in Cryptology -- EUROCRYPT 2010, volume 6110 of Lecture Notes in Computer Science, pages 656--672, French Riviera, May 30 -- June 3, 2010. Springer, Heidelberg, Germany.
[18]
Tibor Jager. Verifiable random functions from weaker assumptions. In Yevgeniy Dodis and Jesper Buus Nielsen, editors, TCC 2015: 12th Theory of Cryptography Conference, Part II, volume 9015 of Lecture Notes in Computer Science, pages 121--143, Warsaw, Poland, March 23--25, 2015. Springer, Heidelberg, Germany.
[19]
David Jao and Kayo Yoshida. Boneh-Boyen signatures and the strong Diffie-Hellman problem. In Hovav Shacham and Brent Waters, editors, PAIRING 2009: 3rd International Conference on Pairing-based Cryptography, volume 5671 of Lecture Notes in Computer Science, pages 1--16, Palo Alto, CA, USA, August 12--14, 2009. Springer, Heidelberg, Germany.
[20]
Stanislaw Jarecki and Vitaly Shmatikov. Handcuffing big brother: an abuse-resilient transaction escrow scheme. In Christian Cachin and Jan Camenisch, editors, Advances in Cryptology -- EUROCRYPT 2004, volume 3027 of Lecture Notes in Computer Science, pages 590--608, Interlaken, Switzerland, May 2--6, 2004. Springer, Heidelberg, Germany.
[21]
Shuichi Katsumata. On the untapped potential of encoding predicates by arithmetic circuits and their applications. In Tsuyoshi Takagi and Thomas Peyrin, editors, Advances in Cryptology -- ASIACRYPT 2017, Part III, volume 10626 of Lecture Notes in Computer Science, pages 95--125, Hong Kong, China, December 3--7, 2017. Springer, Heidelberg, Germany.
[22]
Bei Liang, Hongda Li, and Jinyong Chang. Constrained verifiable random functions from indistinguishability obfuscation. In Man Ho Au and Atsuko Miyaji, editors, ProvSec 2015: 9th International Conference on Provable Security, volume 9451 of Lecture Notes in Computer Science, pages 43--60, Kanazawa, Japan, November 24--26, 2015. Springer, Heidelberg, Germany.
[23]
Anna Lysyanskaya. Unique signatures and verifiable random functions from the DH-DDH separation. In Moti Yung, editor, Advances in Cryptology -- CRYPTO 2002, volume 2442 of Lecture Notes in Computer Science, pages 597--612, Santa Barbara, CA, USA, August 18--22, 2002. Springer, Heidelberg, Germany.
[24]
Silvio Micali, Michael O. Rabin, and Salil P. Vadhan. Verifiable random functions. In 40th Annual Symposium on Foundations of Computer Science, pages 120--130, New York, NY, USA, October 17--19, 1999. IEEE Computer Society Press.
[25]
Silvio Micali and Leonid Reyzin. Soundness in the public-key model. In Joe Kilian, editor, Advances in Cryptology -- CRYPTO 2001, volume 2139 of Lecture Notes in Computer Science, pages 542--565, Santa Barbara, CA, USA, August 19--23, 2001. Springer, Heidelberg, Germany.
[26]
Silvio Micali and Ronald L. Rivest. Micropayments revisited. In Bart Preneel, editor, Topics in Cryptology -- CT-RSA 2002, volume 2271 of Lecture Notes in Computer Science, pages 149--163, San Jose, CA, USA, February 18--22, 2002. Springer, Heidelberg, Germany.
[27]
Shigeo Mitsunari, Ryuichi Saka, and Masao Kasahara. A new traitor tracing. IEICE Transactions, E85-A(2):481--484, February 2002.
[28]
Shota Yamada. Asymptotically compact adaptively secure lattice IBEs and verifiable random functions via generalized partitioning techniques. In Jonathan Katz and Hovav Shacham, editors, Advances in Cryptology -- CRYPTO 2017, Part III, volume 10403 of Lecture Notes in Computer Science, pages 161--193, Santa Barbara, CA, USA, August 20--24, 2017. Springer, Heidelberg, Germany.
Index Terms
- On Several Verifiable Random Functions and the q-decisional Bilinear Diffie-Hellman Inversion Assumption
Recommendations
Efficient Threshold Public Key Encryption from the Computational Bilinear Diffie-Hellman Assumption
APKC '21: Proceedings of the 8th ACM on ASIA Public-Key Cryptography WorkshopIn this paper, we show the first efficient threshold public-key encryption (TPKE) scheme under the difficulty of search problems. More specifically, our TPKE scheme simultaneously achieves: (1) chosen ciphertext security (CCA security) under the ...
Public-key encryption scheme with selective opening chosen-ciphertext security based on the Decisional Diffie-Hellman assumption
Chosen-ciphertext security has been well-accepted as a standard security notion for public-key encryption. But in a multi-user surrounding, it may not be sufficient, because the adversary may corrupt some users to obtain the random coins as well as the ...
Practical hybrid hierarchical identity-based encryption schemes based on the decisional bilinear Diffie-Hellman assumption
The paper proposes a HIBE scheme, which improves upon Waters' scheme from Eurocrypt 2005 by significantly reducing the size of the public parameters. The improvement is based on two ideas: 1 partitioning the identities in smaller blocks; 2 reusing ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
May 2018
66 pages
Copyright © 2018 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 23 May 2018
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
ASIA CCS '18
Sponsor:
ASIA CCS '18: ACM Asia Conference on Computer and Communications Security
June 4, 2018
Incheon, Republic of Korea
Acceptance Rates
APKC '18 Paper Acceptance Rate 7 of 20 submissions, 35%;
Overall Acceptance Rate 36 of 103 submissions, 35%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 168Total Downloads
- Downloads (Last 12 months)21
- Downloads (Last 6 weeks)2
Reflects downloads up to 16 Feb 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in