HELP: Everlasting Privacy through Server-Aided Randomness

Yevgeniy Dodis; Jiaxin Guan; Peter Hall; Alison Lin

doi:10.62056/a3w7tr-10k

HELP: Everlasting Privacy through Server-Aided Randomness

Authors

Yevgeniy Dodis, Jiaxin Guan, Peter Hall, Alison Lin

Yevgeniy Dodis

New York University, New York, USA
dodis at cs dot nyu dot edu

Jiaxin Guan

New York University, New York, USA
jiaxin at guan dot io

Peter Hall

New York University, New York, USA
pf2184 at nyu dot edu

Alison Lin

Independent Contributor, USA
colorfly at gmail dot com

Abstract

Everlasting (EL) privacy offers an attractive solution to the Store-Now-Decrypt-Later (SNDL) problem, where future increases in the attacker's capability could break systems which are believed to be secure today. Instead of requiring full information-theoretic security, everlasting privacy allows computationally-secure transmissions of ephemeral secrets, which are only "effective" for a limited periods of time, after which their compromise is provably useless for the SNDL attacker.

In this work we revisit such everlasting privacy model of Dodis and Yeo (ITC'21), which we call Hypervisor EverLasting Privacy (HELP). HELP is a novel architecture for generating shared randomness using a network of semi-trusted servers (or "hypervisors"), trading the need to store/distribute large shared secrets with the assumptions that it is hard to: (a) simultaneously compromise too many publicly accessible ad-hoc servers; and (b) break a computationally-secure encryption scheme very quickly. While Dodis and Yeo presented good HELP solutions in the asymptotic sense, their solutions were concretely expensive and used heavy tools (like large finite fields or gigantic Toeplitz matrices).

We abstract and generalize the HELP architecture to allow for more efficient instantiations, and construct several concretely efficient HELP solutions. Our solutions use elementary cryptographic operations, such as hashing and message authentication. We also prove a very strong composition theorem showing that our EL architecture can use any message transmission method which is computationally-secure in the Universal Composability (UC) framework. This is the first positive composition result for everlasting privacy, which was otherwise known to suffer from many "non-composition" results (Müller-Quade and Unruh; J of Cryptology'10).

References

[ABB⁺14]

Romain Alléaume, Cyril Branciard, Jan Bouda, Thierry Debuisschert, Mehrdad Dianati, Nicolas Gisin, Mark Godfrey, Philippe Grangier, Thomas Länger, Norbert Lütkenhaus, and others. Using quantum key distribution for cryptographic purposes: a survey. Theoretical Computer Science, 560:62–81, 2014. DOI: 10.1016/j.tcs.2014.09.018

Google Scholar ePrint

[ADR02]

Y. Aumann, Yan Zong Ding, and M.O. Rabin. Everlasting security in the bounded storage model. IEEE Transactions on Information Theory, 48(6):1668-1680, 2002. DOI: 10.1109/TIT.2002.1003845

Google Scholar ePrint

[ARML06]

Romain Alléaume, François Roueff, Oliver Maurhart, and N Lutkenhaus. Architecture, Security and Topology of a global Quantum key distribution Network. In 2006 Digest of the LEOS Summer Topical Meetings, pages 38–39. 2006. IEEE. DOI: 10.1109/LEOSST.2006.1694006

Google Scholar ePrint

[BB14]

Charles H Bennett and Gilles Brassard. Quantum cryptography: Public key distribution and coin tossing. Theoretical computer science, 560:7–11, 2014. DOI: 10.1016/j.tcs.2014.05.025

Google Scholar ePrint

[BCEQ24]

Chris Brzuska, Geoffroy Couteau, Christoph Egger, and Willy Quach. On Bounded Storage Key Agreement and One-Way Functions. In Elette Boyle and Mohammad Mahmoody, editors, TCC 2024, Part I, volume 15364 of LNCS, pages 287–318. December 2024. Springer, Cham. DOI: 10.1007/978-3-031-78011-0_10

Google Scholar ePrint

[BGW88]

Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract). In 20th ACM STOC, pages 1–10. May 1988. ACM Press. DOI: 10.1145/62212.62213

Google Scholar ePrint

[BMV06]

Johannes Buchmann, Alexander May, and Ulrich Vollmer. Perspectives for cryptographic long-term security. Communications of the ACM, 49(9):50–55, 2006. DOI: 10.1145/1151030.1151055

Google Scholar ePrint

[BPP05]

H Bechmann-Pasquinucci and Andrea Pasquinucci. Quantum key distribution with trusted quantum relay. arXiv preprint quant-ph/0505089, 2005. DOI: 10.48550/arXiv.quant-ph/0505089

Google Scholar ePrint

[BZG⁺23]

Riccardo Bassi, Qiaolun Zhang, Alberto Gatto, Massimo Tornatore, and Giacomo Verticale. Quantum key distribution with trusted relay using an ETSI-compliant software-defined controller. In 2023 19th International Conference on the Design of Reliable Communication Networks (DRCN), pages 1–7. 2023. IEEE. DOI: 10.1109/DRCN57075.2023.10108347

Google Scholar ePrint

[Can01]

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

Google Scholar ePrint

[CCH⁺22]

Matthew Campagna, Craig Costello, Basil Hess, Aaron Hutchinson, Amir Jalali, Koray Karabina, Brian Koziel, Brian LaMacchia, Patrick Longa, Michael Naehrig, and others. Supersingular Isogeny Key Encapsulation. 2022.

Google Scholar ePrint

[CD23]

Wouter Castryck and Thomas Decru. An Efficient Key Recovery Attack on SIDH. In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part V, volume 14008 of LNCS, pages 423–447. April 2023. Springer, Cham. DOI: 10.1007/978-3-031-30589-4_15

Google Scholar ePrint

[CDH⁺00]

Ran Canetti, Yevgeniy Dodis, Shai Halevi, Eyal Kushilevitz, and Amit Sahai. Exposure-Resilient Functions and All-or-Nothing Transforms. In Bart Preneel, editor, EUROCRYPT 2000, volume 1807 of LNCS, pages 453–469. May 2000. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-45539-6_33

Google Scholar ePrint

[CF01]

Ran Canetti and Marc Fischlin. Universally Composable Commitments. In Joe Kilian, editor, CRYPTO 2001, volume 2139 of LNCS, pages 19–40. August 2001. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-44647-8_2

Google Scholar ePrint

[CGH⁺85]

Benny Chor, Oded Goldreich, Johan Hasted, Joel Freidmann, Steven Rudich, and Roman Smolensky. The bit extraction problem or t-resilient functions. In 26th Annual Symposium on Foundations of Computer Science (sfcs 1985), pages 396-407. 1985. DOI: 10.1109/SFCS.1985.55

Google Scholar ePrint

[Che24]

Yilei Chen. Quantum Algorithms for Lattice Problems. Cryptology ePrint Archive, Report 2024/555. 2024.

Google Scholar ePrint

[CZL⁺21]

Yuan Cao, Yongli Zhao, Jun Li, Rui Lin, Jie Zhang, and Jiajia Chen. Hybrid trusted/untrusted relay-based quantum key distribution over optical backbone networks. IEEE Journal on Selected Areas in Communications, 39(9):2701–2718, 2021. DOI: 10.1109/JSAC.2021.3064662

Google Scholar ePrint

[Dam89]

Ivan Damgård. A Design Principle for Hash Functions. In Advances in Cryptology - CRYPTO '89, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings, volume 435 of Lecture Notes in Computer Science, pages 416-427. 1989. Springer. DOI: 10.1007/0-387-34805-0_39

Google Scholar ePrint

[DDWY93]

Danny Dolev, Cynthia Dwork, Orli Waarts, and Moti Yung. Perfectly Secure Message Transmission. Journal of the ACM, 40(1):17–47, January 1993. DOI: 10.1145/138027.138036

Google Scholar ePrint

[DM04]

Stefan Dziembowski and Ueli M. Maurer. On Generating the Initial Key in the Bounded-Storage Model. In Christian Cachin and Jan Camenisch, editors, EUROCRYPT 2004, volume 3027 of LNCS, pages 126–137. May 2004. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-24676-3_8

Google Scholar ePrint

[Dod12]

Yevgeniy Dodis. Shannon Impossibility, Revisited. In Adam Smith, editor, ICITS 12, volume 7412 of LNCS, pages 100–110. August 2012. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-32284-6_6

Google Scholar ePrint

[DORS08]

Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, and Adam Smith. Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. In SIAM Journal of Computing. 2008. DOI: 10.1137/060651380

Google Scholar ePrint

[DP08]

Yevgeniy Dodis and Prashant Puniya. Getting the Best Out of Existing Hash Functions; or What if We Are Stuck with SHA?. In Applied Cryptography and Network Security. ACNS 2008, volume 5037. 2008. Springer. DOI: 10.1007/978-3-540-68914-0_10

Google Scholar ePrint

[DPP94]

Ivan Damgård, Torben P. Pedersen, and Birgit Pfitzmann. On the Existence of Statistically Hiding Bit Commitment Schemes and Fail-Stop Signatures. In Douglas R. Stinson, editor, CRYPTO'93, volume 773 of LNCS, pages 250–265. August 1994. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-48329-2_22

Google Scholar ePrint

[DQW23]

Yevgeniy Dodis, Willy Quach, and Daniel Wichs. Speak Much, Remember Little: Cryptography in the Bounded Storage Model, Revisited. In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part I, volume 14004 of LNCS, pages 86–116. April 2023. Springer, Cham. DOI: 10.1007/978-3-031-30545-0_4

Google Scholar ePrint

[DR02]

Yan Zong Ding and Michael O. Rabin. Hyper-Encryption and Everlasting Security. In Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, pages 1–26, Berlin, Heidelberg. 2002. Springer-Verlag. DOI: 10.1007/3-540-45841-7_1

Google Scholar ePrint

[DY21]

Yevgeniy Dodis and Kevin Yeo. Doubly-Affine Extractors, and Their Applications. In Stefano Tessaro, editor, ITC 2021, volume 199 of LIPIcs, pages 13:1–13:23. July 2021. Schloss Dagstuhl. DOI: 10.4230/LIPIcs.ITC.2021.13

Google Scholar ePrint

[Dzi06]

Stefan Dziembowski. On Forward-Secure Storage (Extended Abstract). In Cynthia Dwork, editor, CRYPTO 2006, volume 4117 of LNCS, pages 251–270. August 2006. Springer, Berlin, Heidelberg. DOI: 10.1007/11818175_15

Google Scholar ePrint

[Ell02]

Chip Elliott. Building the quantum network. New Journal of Physics, 4(1):46, 2002. DOI: 10.1088/1367-2630/4/1/346

Google Scholar ePrint

[FJP14]

Luca De Feo, David Jao, and Jérôme Plût. Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. J. Math. Cryptol., 8(3):209–247, 2014. DOI: 10.1515/jmc-2012-0015

Google Scholar ePrint

[FYLW⁺22]

Guan-Jie Fan-Yuan, Feng-Yu Lu, Shuang Wang, Zhen-Qiang Yin, De-Yong He, Wei Chen, Zheng Zhou, Ze-Hao Wang, Jun Teng, Guang-Can Guo, and others. Robust and adaptable quantum key distribution network without trusted nodes. Optica, 9(7):812–823, 2022. DOI: 10.1364/OPTICA.458937

Google Scholar ePrint

[GN94]

Peter Gemmell and Moni Naor. Codes for Interactive Authentication. In Douglas R. Stinson, editor, CRYPTO'93, volume 773 of LNCS, pages 355–367. August 1994. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-48329-2_30

Google Scholar ePrint

[Gro96]

Lov K. Grover. A Fast Quantum Mechanical Algorithm for Database Search. In 28th ACM STOC, pages 212–219. May 1996. ACM Press. DOI: 10.1145/237814.237866

Google Scholar ePrint

[GWZ22]

Jiaxin Guan, Daniel Wichs, and Mark Zhandry. Incompressible Cryptography. In Orr Dunkelman and Stefan Dziembowski, editors, EUROCRYPT 2022, Part I, volume 13275 of LNCS, pages 700–730. 2022. Springer, Cham. DOI: 10.1007/978-3-031-06944-4_24

Google Scholar ePrint

[GWZ23]

Jiaxin Guan, Daniel Wichs, and Mark Zhandry. Multi-instance Randomness Extraction and Security Against Bounded-Storage Mass Surveillance. In Guy N. Rothblum and Hoeteck Wee, editors, TCC 2023, Part III, volume 14371 of LNCS, pages 93–122. 2023. Springer, Cham. DOI: 10.1007/978-3-031-48621-0_4

Google Scholar ePrint

[GZ21]

Jiaxin Guan and Mark Zhandry. Disappearing Cryptography in the Bounded Storage Model. In Kobbi Nissim and Brent Waters, editors, TCC 2021, Part II, volume 13043 of LNCS, pages 365–396. November 2021. Springer, Cham. DOI: 10.1007/978-3-030-90453-1_13

Google Scholar ePrint

[HJR06]

K. Harmon, S. Johnson, and L. Reyzin. An Implementation of Syndrome Encoding and Decoding for Binary BCH Codes, Secure Sketches and Fuzzy Extractors. 2006.

Google Scholar ePrint

[HN06]

Danny Harnik and Moni Naor. On Everlasting Security in the Hybrid Bounded Storage Model. In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, editors, ICALP 2006, Part II, volume 4052 of LNCS, pages 192–203. July 2006. Springer, Berlin, Heidelberg. DOI: 10.1007/11787006_17

Google Scholar ePrint

[HNH13]

Stefan Heule, Marc Nunkesser, and Alexander Hall. Hyperloglog in practice: Algorithmic engineering of a state of the art cardinality estimation algorithm. In Proceedings of the 16th International Conference on Extending Database Technology, pages 683–692. 2013. DOI: 10.1145/2452376.2452456

Google Scholar ePrint

[ILL89]

Russell Impagliazzo, Leonid A. Levin, and Michael Luby. Pseudo-random Generation from one-way functions (Extended Abstracts). In 21st ACM STOC, pages 12–24. May 1989. ACM Press. DOI: 10.1145/73007.73009

Google Scholar ePrint

[JF11]

David Jao and Luca De Feo. Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies. In PQCrypto, volume 7071 of LNCS, pages 19–34. 2011. Springer. DOI: 10.1007/978-3-642-25405-5_2

Google Scholar ePrint

[LBD07a]

Quoc-Cuong Le, Patrick Bellot, and Akim Demaille. On the security of quantum networks: a proposal framework and its capacity. In New Technologies, Mobility and Security, pages 385–396. Springer 2007. DOI: 10.1007/978-1-4020-6270-4_32

Google Scholar ePrint

[LBD07b]

Quoc-Cuong Le, Patrick Bellot, and Akim Demaille. Stochastic routing in large grid-shaped quantum networks. In 2007 IEEE International Conference on Research, Innovation and Vision for the Future, pages 166–174. 2007. IEEE. DOI: 10.1109/RIVF.2007.369152

Google Scholar ePrint

[LBD08]

Quoc-Cuong Le, Patrick Bellot, and Akim Demaille. Towards the world-wide quantum network. In International Conference on Information Security Practice and Experience, pages 218–232. 2008. Springer. DOI: 10.1007/978-3-540-79104-1_16

Google Scholar ePrint

[Mau92]

Ueli M. Maurer. A Universal Statistical Test for Random Bit Generators. Journal of Cryptology, 5(2):89–105, January 1992. DOI: 10.1007/BF00193563

Google Scholar ePrint

[MMP⁺23]

Luciano Maino, Chloe Martindale, Lorenz Panny, Giacomo Pope, and Benjamin Wesolowski. A Direct Key Recovery Attack on SIDH. In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part V, volume 14008 of LNCS, pages 448–471. April 2023. Springer, Cham. DOI: 10.1007/978-3-031-30589-4_16

Google Scholar ePrint

[MU10]

Jörn Müller-Quade and Dominique Unruh. Long-Term Security and Universal Composability. Journal of Cryptology, 23(4):594–671, October 2010. DOI: 10.1007/s00145-010-9068-8

Google Scholar ePrint

[MVZJ18]

Vasileios Mavroeidis, Kamer Vishi, Mateusz D Zych, and Audun Jøsang. The impact of quantum computing on present cryptography. International Journal of Advanced Computer Science and Applications (IJACSA), 9(3):405–414, 2018. DOI: 10.14569/IJACSA.2018.090354

Google Scholar ePrint

[MW24]

Giulio Malavolta and Michael Walter. Robust Quantum Public-Key Encryption with Applications to Quantum Key Distribution. In Leonid Reyzin and Douglas Stebila, editors, CRYPTO 2024, Part VII, volume 14926 of LNCS, pages 126–151. August 2024. Springer, Cham. DOI: 10.1007/978-3-031-68394-7_5

Google Scholar ePrint

[NZ96]

Noam Nisan and David Zuckerman. Randomness is linear in space. Journal of Computer and System Sciences, 52(1):43–52, 1996. DOI: 10.1006/jcss.1996.0004

Google Scholar ePrint

[Rab05]

Michael O Rabin. Provably unbreakable hyper-encryption in the limited access model. In IEEE Information Theory Workshop on Theory and Practice in Information-Theoretic Security, 2005., pages 34–37. 2005. IEEE. DOI: 10.1109/ITWTPI.2005.1543953

Google Scholar ePrint

[Reg10]

Oded Regev. The learning with errors problem. In 25th Annual IEEE Conference on Computational Complexity, CCC 2010, pages 191–204. 2010. DOI: 10.1109/CCC.2010.26

Google Scholar ePrint

[Ren08]

Renato Renner. Security of quantum key distribution. International Journal of Quantum Information, 6(01):1–127, 2008. DOI: 10.1142/S0219749908003256

Google Scholar ePrint

[RS60]

Irving S. Reed and Gustave Solomon. Polynomial Codes Over Certain Finite Fields. Journal of the Society for Industrial and Applied Mathematics, 8:300–304, 1960. DOI: 10.1137/0108018

Google Scholar ePrint

[Sha49]

Claude E Shannon. Communication theory of secrecy systems. The Bell system technical journal, 28(4):656–715, 1949. DOI: 10.1002/j.1538-7305.1949.tb00928.x

Google Scholar ePrint

[Sho94]

Peter W. Shor. Algorithms for Quantum Computation: Discrete Logarithms and Factoring. In 35th FOCS, pages 124–134. November 1994. IEEE Computer Society Press. DOI: 10.1109/SFCS.1994.365700

Google Scholar ePrint

[VM24]

Nilesh Vyas and Paulo Mendes. Relaxing Trust Assumptions on Quantum Key Distribution Networks. arXiv preprint arXiv:2402.13136, 2024. DOI: 10.48550/arXiv.2402.13136

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/a3w7tr-10k

History

Submitted: 2024-07-09
Accepted: 2024-12-03
Published: 2025-01-13

How to cite

Yevgeniy Dodis, Jiaxin Guan, Peter Hall, and Alison Lin, HELP: Everlasting Privacy through Server-Aided Randomness. IACR Communications in Cryptology, vol. 1, no. 4, Jan 13, 2025, doi: 10.62056/a3w7tr-10k.

License

Copyright is held by the author(s)

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

@article{CiC-1-4-6,
    author = "Dodis, Yevgeniy and Guan, Jiaxin and Hall, Peter and Lin, Alison",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "{HELP}: Everlasting Privacy through Server-Aided Randomness",
    volume = "1",
    number = "4",
    date = "2025-01-13",
    year = "2025",
    issn = "3006-5496",
    doi = "10.62056/a3w7tr-10k"
}

TY - JOUR
AU - Dodis, Yevgeniy
AU - Guan, Jiaxin
AU - Hall, Peter
AU - Lin, Alison
PY  - 2025
TI  - HELP: Everlasting Privacy through Server-Aided Randomness
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 4
DO  - 10.62056/a3w7tr-10k
UR  - https://doi.org/10.62056/a3w7tr-10k
AB  - <p>  Everlasting (EL) privacy offers an attractive solution to the Store-Now-Decrypt-Later (SNDL) problem, where future increases in the attacker's capability could break systems which are believed to be secure today. Instead of requiring full information-theoretic security, everlasting privacy allows computationally-secure transmissions of ephemeral secrets, which are only "effective" for a limited periods of time, after which their compromise is provably useless for the SNDL attacker.</p><p>In this work we revisit such everlasting privacy model of Dodis and Yeo (ITC'21), which we call Hypervisor EverLasting Privacy (HELP). HELP is a novel architecture for generating shared randomness using a network of semi-trusted servers (or "hypervisors"), trading the need to store/distribute large shared secrets with the assumptions that it is hard to: (a) simultaneously compromise too many publicly accessible ad-hoc servers; and (b) break a computationally-secure encryption scheme very quickly. While Dodis and Yeo presented good HELP solutions in the asymptotic sense, their solutions were concretely expensive and used heavy tools (like large finite fields or gigantic Toeplitz matrices).</p><p>We abstract and generalize the HELP architecture to allow for more efficient instantiations, and construct several concretely efficient HELP solutions. Our solutions use elementary cryptographic operations, such as hashing and message authentication. We also prove a very strong composition theorem showing that our EL architecture can use any message transmission method which is computationally-secure in the Universal Composability (UC) framework. This is the first positive composition result for everlasting privacy, which was otherwise known to suffer from many "non-composition" results (Müller-Quade and Unruh; J of Cryptology'10). </p>
ER  -

Yevgeniy Dodis, Jiaxin Guan, Peter Hall, and Alison Lin, HELP: Everlasting Privacy through Server-Aided Randomness. IACR Communications in Cryptology, vol. 1, no. 4, Jan 13, 2025, doi: 10.62056/a3w7tr-10k.