Efficient Maliciously Secure Oblivious Exponentiations

Communications in Cryptology IACR CiC

Efficient Maliciously Secure Oblivious Exponentiations

Authors

Carsten Baum, Jens Berlips, Walther Chen, Ivan B. Damgård, Kevin M. Esvelt, Leonard Foner, Dana Gretton, Martin Kysel, Ronald L. Rivest, Lawrence Roy, Francesca Sage-Ling, Adi Shamir, Vinod Vaikuntanathan, Lynn Van Hauwe, Theia Vogel, Benjamin Weinstein-Raun, Daniel Wichs, Stephen Wooster, Andrew C. Yao, Yu Yu

Carsten Baum

Technical University of Denmark, Kgs. Lyngby, Denmark
cabau at dtu dot dk

Jens Berlips

SecureDNA Foundation, Zug, Switzerland

Walther Chen

SecureDNA Foundation, Zug, Switzerland

Ivan B. Damgård

Aarhus University, Aarhus, Denmark
ivan at cs dot au dot dk

Kevin M. Esvelt

MIT, Cambridge, USA

Leonard Foner

SecureDNA Foundation, Zug, Switzerland

Dana Gretton

MIT, Cambridge, USA

Martin Kysel

SecureDNA Foundation, Zug, Switzerland

Ronald L. Rivest

MIT, Cambridge, USA

Lawrence Roy

Aarhus University, Aarhus, Denmark
ldr709 at gmail dot com

Francesca Sage-Ling

SecureDNA Foundation, Zug, Switzerland

Adi Shamir

Weizmann Institute, Rehovot, Israel

Vinod Vaikuntanathan

MIT, Cambridge, USA

Lynn Van Hauwe

SecureDNA Foundation, Zug, Switzerland

Theia Vogel

SecureDNA Foundation, Zug, Switzerland

Benjamin Weinstein-Raun

SecureDNA Foundation, Zug, Switzerland

Daniel Wichs

Northeastern University, Boston, USA
NTT Research, Sunnyvale, USA

Stephen Wooster

SecureDNA Foundation, Zug, Switzerland

Andrew C. Yao

Tsinghua University, Beijing, China

Yu Yu

Shanghai Jiao Tong University, Shanghai, China

Abstract

Oblivious Pseudorandom Functions (OPRFs) allow a client to evaluate a pseudorandom function (PRF) on her secret input based on a key that is held by a server. In the process, the client only learns the PRF output but not the key, while the server neither learns the input nor the output of the client. The arguably most popular OPRF is due to Naor, Pinkas and Reingold (Eurocrypt 2009). It is based on an Oblivious Exponentiation by the server, with passive security under the Decisional Diffie-Hellman assumption. In this work, we strengthen the security guarantees of the NPR OPRF by protecting it against active attacks of the server. We have implemented our solution and report on the performance. Our main result is a new batch OPRF protocol which is secure against maliciously corrupted servers, but is essentially as efficient as the semi-honest solution. More precisely, the computation (and communication) overhead is a multiplicative factor $o(1)$ as the batch size increases. The obvious solution using zero-knowledge proofs would have a constant factor overhead at best, which can be too expensive for certain deployments. Our protocol relies on a novel version of the DDH problem, which we call the Oblivious Exponentiation Problem (OEP), and we give evidence for its hardness in the Generic Group model. We also present a variant of our maliciously secure protocol that does not rely on the OEP but nevertheless only has overhead $o(1)$ over the known semi-honest protocol. Moreover, we show that our techniques can also be used to efficiently protect threshold blind BLS signing and threshold ElGamal decryption against malicious attackers.

References

[AC20]

Thomas Attema and Ronald Cramer. Compressed $\varSigma$-Protocol Theory and Practical Application to Plug & Play Secure Algorithmics. In Daniele Micciancio and Thomas Ristenpart, editors, Advances in Cryptology – CRYPTO 2020, Part III, volume 12172 of Lecture Notes in Computer Science, pages 513–543. August 2020. Springer, Cham. DOI: 10.1007/978-3-030-56877-1_18

Google Scholar ePrint

[AMMM18]

Shashank Agrawal, Peihan Miao, Payman Mohassel, and Pratyay Mukherjee. PASTA: PASsword-based Threshold Authentication. In David Lie, Mohammad Mannan, Michael Backes, and XiaoFeng Wang, editors, ACM CCS 2018: 25th Conference on Computer and Communications Security, pages 2042–2059. October 2018. ACM Press. DOI: 10.1145/3243734.3243839

Google Scholar ePrint

[AP05]

Michel Abdalla and David Pointcheval. Simple Password-Based Encrypted Key Exchange Protocols. In Alfred Menezes, editor, Topics in Cryptology – CT-RSA 2005, volume 3376 of Lecture Notes in Computer Science, pages 191–208. February 2005. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-30574-3_14

Google Scholar ePrint

[BBB⁺18]

Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Greg Maxwell. Bulletproofs: Short Proofs for Confidential Transactions and More. In 2018 IEEE Symposium on Security and Privacy, pages 315–334. May 2018. IEEE Computer Society Press. DOI: 10.1109/SP.2018.00020

Google Scholar ePrint

[BBC⁺24]

Carsten Baum, Jens Berlips, Walther Chen, Hongrui Cui, Ivan Damgard, Jiangbin Dong, Kevin M. Esvelt, Leonard Foner, Mingyu Gao, Dana Gretton, Martin Kysel, Juanru Li, Xiang Li, Omer Paneth, Ronald L. Rivest, Francesca Sage-Ling, Adi Shamir, Yue Shen, Meicen Sun, Vinod Vaikuntanathan, Lynn Van Hauwe, Theia Vogel, Benjamin Weinstein-Raun, Yun Wang, Daniel Wichs, Stephen Wooster, Andrew C. Yao, Yu Yu, Haoling Zhang, and Kaiyi Zhang. A system capable of verifiably and privately screening global DNA synthesis. 2024.

Google Scholar ePrint

[BFF⁺19]

Gilles Barthe, Edvard Fagerholm, Dario Fiore, John C. Mitchell, Andre Scedrov, and Benedikt Schmidt. Automated Analysis of Cryptographic Assumptions in Generic Group Models. Journal of Cryptology, 32(2):324–360, April 2019. DOI: 10.1007/s00145-018-9302-3

Google Scholar ePrint

[BFH⁺20]

Carsten Baum, Tore Frederiksen, Julia Hesse, Anja Lehmann, and Avishay Yanai. PESTO: proactively secure distributed single sign-on, or how to trust a hacked server. In 2020 IEEE European Symposium on Security and Privacy (EuroS&P), pages 587–606. 2020. IEEE. DOI: https://doi.org/10.1109/EuroSP48549.2020.00044

Google Scholar ePrint

[BGR98]

Mihir Bellare, Juan A. Garay, and Tal Rabin. Fast Batch Verification for Modular Exponentiation and Digital Signatures. In Kaisa Nyberg, editor, Advances in Cryptology – EUROCRYPT'98, volume 1403 of Lecture Notes in Computer Science, pages 236–250. 1998. Springer, Berlin, Heidelberg. DOI: 10.1007/BFb0054130

Google Scholar ePrint

[BLS04]

Dan Boneh, Ben Lynn, and Hovav Shacham. Short Signatures from the Weil Pairing. Journal of Cryptology, 17(4):297–319, September 2004. DOI: 10.1007/s00145-004-0314-9

Google Scholar ePrint

[Can01]

Ran Canetti. Universally Composable Security: A New Paradigm for Cryptographic Protocols. In 42nd Annual Symposium on Foundations of Computer Science, pages 136–145. October 2001. IEEE Computer Society Press. DOI: 10.1109/SFCS.2001.959888

Google Scholar ePrint

[CDG⁺18]

Jan Camenisch, Manu Drijvers, Tommaso Gagliardoni, Anja Lehmann, and Gregory Neven. The Wonderful World of Global Random Oracles. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2018, Part I, volume 10820 of Lecture Notes in Computer Science, pages 280–312. 2018. Springer, Cham. DOI: 10.1007/978-3-319-78381-9_11

Google Scholar ePrint

[Cha91]

David Chaum. Zero-Knowledge Undeniable Signatures. In Ivan Damgård, editor, Advances in Cryptology – EUROCRYPT'90, volume 473 of Lecture Notes in Computer Science, pages 458–464. May 1991. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-46877-3_41

Google Scholar ePrint

[CHL22]

Sílvia Casacuberta, Julia Hesse, and Anja Lehmann. SoK: Oblivious Pseudorandom Functions. In 2022 IEEE 7th European Symposium on Security and Privacy (EuroS&P), pages 625–646. 2022. IEEE. DOI: https://doi.org/10.1109/EuroSP53844.2022.00045

Google Scholar ePrint

[CLN15]

Jan Camenisch, Anja Lehmann, and Gregory Neven. Optimal Distributed Password Verification. In Indrajit Ray, Ninghui Li, and Christopher Kruegel, editors, ACM CCS 2015: 22nd Conference on Computer and Communications Security, pages 182–194. October 2015. ACM Press. DOI: 10.1145/2810103.2813722

Google Scholar ePrint

[DGS⁺18]

Alex Davidson, Ian Goldberg, Nick Sullivan, George Tankersley, and Filippo Valsorda. Privacy Pass: Bypassing Internet Challenges Anonymously. Proceedings on Privacy Enhancing Technologies, 2018(3):164–180, July 2018. DOI: 10.1515/popets-2018-0026

Google Scholar ePrint

[DY05]

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. January 2005. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-30580-4_28

Google Scholar ePrint

[ECS⁺15]

Adam Everspaugh, Rahul Chatterjee, Samuel Scott, Ari Juels, and Thomas Ristenpart. The Pythia PRF Service. In Jaeyeon Jung and Thorsten Holz, editors, USENIX Security 2015: 24th USENIX Security Symposium, pages 547–562. August 2015. USENIX Association.

Google Scholar ePrint

[ElG85]

Taher ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE transactions on information theory, 31(4):469–472, 1985. DOI: https://doi.org/10.1109/TIT.1985.1057074

Google Scholar ePrint

[GLSY04]

Rosario Gennaro, Darren Leigh, R. Sundaram, and William S. Yerazunis. Batching Schnorr Identification Scheme with Applications to Privacy-Preserving Authorization and Low-Bandwidth Communication Devices. In Pil Joong Lee, editor, Advances in Cryptology – ASIACRYPT 2004, volume 3329 of Lecture Notes in Computer Science, pages 276–292. December 2004. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-30539-2_20

Google Scholar ePrint

[GWE⁺24]

Dana Gretton, Brian Wang, Rey Edison, Leonard Foner, Jens Berlips, Theia Vogel, Martin Kysel, Walther Chen, Francesca Sage-Ling, Lynn Van Hauwe, Stephen Wooster, Benjamin Weinstein-Raun, Erika A. DeBenedictis, Andrew B. Liu, Emma Chory, Hongrui Cui, Xiang Li, Jiangbin Dong, Andres Fabrega, Christianne Dennison, Otilia Don, Cassandra Tong Ye, Kaveri Uberoy, Ronald L. Rivest, Mingyu Gao, Yu Yu, Carsten Baum, Ivan Damgard, Andrew C. Yao, and Kevin M. Esvelt. Random adversarial threshold search enables automated DNA screening. 2024.

Google Scholar ePrint

[HL08]

Carmit Hazay and Yehuda Lindell. Efficient Protocols for Set Intersection and Pattern Matching with Security Against Malicious and Covert Adversaries. In Ran Canetti, editor, TCC 2008: 5th Theory of Cryptography Conference, volume 4948 of Lecture Notes in Computer Science, pages 155–175. March 2008. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-78524-8_10

Google Scholar ePrint

[IKNP03]

Yuval Ishai, Joe Kilian, Kobbi Nissim, and Erez Petrank. Extending Oblivious Transfers Efficiently. In Dan Boneh, editor, Advances in Cryptology – CRYPTO 2003, volume 2729 of Lecture Notes in Computer Science, pages 145–161. August 2003. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-45146-4_9

Google Scholar ePrint

[JKK14]

Stanislaw Jarecki, Aggelos Kiayias, and Hugo Krawczyk. Round-Optimal Password-Protected Secret Sharing and T-PAKE in the Password-Only Model. In Palash Sarkar and Tetsu Iwata, editors, Advances in Cryptology – ASIACRYPT 2014, Part II, volume 8874 of Lecture Notes in Computer Science, pages 233–253. December 2014. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-45608-8_13

Google Scholar ePrint

[JKKX17]

Stanislaw Jarecki, Aggelos Kiayias, Hugo Krawczyk, and Jiayu Xu. TOPPSS: Cost-Minimal Password-Protected Secret Sharing Based on Threshold OPRF. In Dieter Gollmann, Atsuko Miyaji, and Hiroaki Kikuchi, editors, ACNS 17: 15th International Conference on Applied Cryptography and Network Security, volume 10355 of Lecture Notes in Computer Science, pages 39–58. July 2017. Springer, Cham. DOI: 10.1007/978-3-319-61204-1_3

Google Scholar ePrint

[KKRT16]

Vladimir Kolesnikov, Ranjit Kumaresan, Mike Rosulek, and Ni Trieu. Efficient Batched Oblivious PRF with Applications to Private Set Intersection. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, ACM CCS 2016: 23rd Conference on Computer and Communications Security, pages 818–829. October 2016. ACM Press. DOI: 10.1145/2976749.2978381

Google Scholar ePrint

[MPR⁺20]

Peihan Miao, Sarvar Patel, Mariana Raykova, Karn Seth, and Moti Yung. Two-Sided Malicious Security for Private Intersection-Sum with Cardinality. In Daniele Micciancio and Thomas Ristenpart, editors, Advances in Cryptology – CRYPTO 2020, Part III, volume 12172 of Lecture Notes in Computer Science, pages 3–33. August 2020. Springer, Cham. DOI: 10.1007/978-3-030-56877-1_1

Google Scholar ePrint

[NPR99]

Moni Naor, Benny Pinkas, and Omer Reingold. Distributed Pseudo-random Functions and KDCs. In Jacques Stern, editor, Advances in Cryptology – EUROCRYPT'99, volume 1592 of Lecture Notes in Computer Science, pages 327–346. May 1999. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-48910-X_23

Google Scholar ePrint

[NR04]

Moni Naor and Omer Reingold. Number-theoretic constructions of efficient pseudo-random functions. Journal of the ACM (JACM), 51(2):231–262, 2004. DOI: https://doi.org/10.1145/972639.972643

Google Scholar ePrint

[Pei06]

Chris Peikert. On Error Correction in the Exponent. In Shai Halevi and Tal Rabin, editors, TCC 2006: 3rd Theory of Cryptography Conference, volume 3876 of Lecture Notes in Computer Science, pages 167–183. March 2006. Springer, Berlin, Heidelberg. DOI: 10.1007/11681878_9

Google Scholar ePrint

[Szy06]

Michael Szydlo. A Note on Chosen-Basis Decisional Diffie-Hellman Assumptions. In Giovanni Di Crescenzo and Avi Rubin, editors, FC 2006: 10th International Conference on Financial Cryptography and Data Security, volume 4107 of Lecture Notes in Computer Science, pages 166–170. 2006. Springer, Berlin, Heidelberg. DOI: 10.1007/11889663_14

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/a66cy7qiu

History

Submitted: 2024-07-02
Accepted: 2024-09-02
Published: 2024-10-07

How to cite

Carsten Baum, Jens Berlips, Walther Chen, Ivan B. Damgård, Kevin M. Esvelt, Leonard Foner, Dana Gretton, Martin Kysel, Ronald L. Rivest, Lawrence Roy, Francesca Sage-Ling, Adi Shamir, Vinod Vaikuntanathan, Lynn Van Hauwe, Theia Vogel, Benjamin Weinstein-Raun, Daniel Wichs, Stephen Wooster, Andrew C. Yao, and Yu Yu, Efficient Maliciously Secure Oblivious Exponentiations. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/a66cy7qiu.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{CiC-1-3-10,
    author = "Baum, Carsten and Berlips, Jens and Chen, Walther and Damgård, Ivan B. and Esvelt, Kevin M. and Foner, Leonard and Gretton, Dana and Kysel, Martin and Rivest, Ronald L. and Roy, Lawrence and Sage-Ling, Francesca and Shamir, Adi and Vaikuntanathan, Vinod and Hauwe, Lynn Van and Vogel, Theia and Weinstein-Raun, Benjamin and Wichs, Daniel and Wooster, Stephen and Yao, Andrew C. and Yu, Yu",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "Efficient Maliciously Secure   Oblivious Exponentiations",
    volume = "1",
    number = "3",
    date = "2024-10-07",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/a66cy7qiu"
}

TY - JOUR
AU - Baum, Carsten
AU - Berlips, Jens
AU - Chen, Walther
AU - Damgård, Ivan
AU - Esvelt, Kevin
AU - Foner, Leonard
AU - Gretton, Dana
AU - Kysel, Martin
AU - Rivest, Ronald
AU - Roy, Lawrence
AU - Sage-Ling, Francesca
AU - Shamir, Adi
AU - Vaikuntanathan, Vinod
AU - Van Hauwe, Lynn
AU - Vogel, Theia
AU - Weinstein-Raun, Benjamin
AU - Wichs, Daniel
AU - Wooster, Stephen
AU - Yao, Andrew
AU - Yu, Yu
PY - 2024
TI - Efficient Maliciously Secure Oblivious Exponentiations
JF - IACR Communications in Cryptology
JA - CIC
VL - 1
IS - 3
DO - 10.62056/a66cy7qiu
UR - https://doi.org/10.62056/a66cy7qiu
AB - <p> Oblivious Pseudorandom Functions (OPRFs) allow a client to evaluate a pseudorandom function (PRF) on her secret input based on a key that is held by a server. In the process, the client only learns the PRF output but not the key, while the server neither learns the input nor the output of the client. The arguably most popular OPRF is due to Naor, Pinkas and Reingold (Eurocrypt 2009). It is based on an Oblivious Exponentiation by the server, with passive security under the Decisional Diffie-Hellman assumption. In this work, we strengthen the security guarantees of the NPR OPRF by protecting it against active attacks of the server. We have implemented our solution and report on the performance. Our main result is a new batch OPRF protocol which is secure against maliciously corrupted servers, but is essentially as efficient as the semi-honest solution. More precisely, the computation (and communication) overhead is a multiplicative factor $o(1)$ as the batch size increases. The obvious solution using zero-knowledge proofs would have a constant factor overhead at best, which can be too expensive for certain deployments. Our protocol relies on a novel version of the DDH problem, which we call the Oblivious Exponentiation Problem (OEP), and we give evidence for its hardness in the Generic Group model. We also present a variant of our maliciously secure protocol that does not rely on the OEP but nevertheless only has overhead $o(1)$ over the known semi-honest protocol. Moreover, we show that our techniques can also be used to efficiently protect threshold blind BLS signing and threshold ElGamal decryption against malicious attackers. </p>
ER -

Carsten Baum, Jens Berlips, Walther Chen, Ivan B. Damgård, Kevin M. Esvelt, Leonard Foner, Dana Gretton, Martin Kysel, Ronald L. Rivest, Lawrence Roy, Francesca Sage-Ling, Adi Shamir, Vinod Vaikuntanathan, Lynn Van Hauwe, Theia Vogel, Benjamin Weinstein-Raun, Daniel Wichs, Stephen Wooster, Andrew C. Yao, and Yu Yu, Efficient Maliciously Secure Oblivious Exponentiations. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/a66cy7qiu.