4 Search Results for "Kerschbaum, Florian"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.61
Random Unitaries in Constant (Quantum) Time

Authors: Ben Foxman, Natalie Parham, Francisca Vasconcelos, and Henry Yuen

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Random unitaries are a central object of study in quantum information, with applications to quantum computation, quantum many-body physics, and quantum cryptography. Recent work has constructed unitary designs and pseudorandom unitaries (PRUs) using Θ(log log n)-depth unitary circuits with two-qubit gates. In this work, we show that unitary designs and PRUs can be efficiently constructed in several well-studied models of constant-time quantum computation (i.e., the time complexity on the quantum computer is independent of the system size). These models are constant-depth circuits augmented with certain nonlocal operations, such as (a) many-qubit TOFFOLI gates, (b) many-qubit FANOUT gates, or (c) mid-circuit measurements with classical feedforward control. Recent advances in quantum computing hardware suggest experimental feasibility of these models in the near future. Our results demonstrate that unitary designs and PRUs can be constructed in much weaker circuit models than previously thought. Furthermore, our construction of PRUs in constant-depth with many-qubit TOFFOLI gates shows that, under cryptographic assumptions, there is no polynomial-time learning algorithm for the circuit class QAC⁰. Finally, our results suggest a new approach towards proving that PARITY is not computable in QAC⁰, a long-standing question in quantum complexity theory.
Cite as

Ben Foxman, Natalie Parham, Francisca Vasconcelos, and Henry Yuen. Random Unitaries in Constant (Quantum) Time. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 61:1-61:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{foxman_et_al:LIPIcs.ITCS.2026.61,
  author =	{Foxman, Ben and Parham, Natalie and Vasconcelos, Francisca and Yuen, Henry},
  title =	{{Random Unitaries in Constant (Quantum) Time}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{61:1--61:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.61},
  URN =		{urn:nbn:de:0030-drops-253481},
  doi =		{10.4230/LIPIcs.ITCS.2026.61},
  annote =	{Keywords: Quantum Information, Pseudorandomness, Circuit Complexity}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2025.25
Optimal Oblivious Algorithms for Multi-Way Joins

Authors: Xiao Hu and Zhiang Wu

Published in: LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025)

Abstract
In cloud databases, cloud computation over sensitive data uploaded by clients inevitably causes concern about data security and privacy. Even if cryptographic primitives and trusted computing environments are integrated into query processing to safeguard the actual contents of the data, access patterns of algorithms can still leak private information about data. Oblivious RAM (ORAM) and circuits are two generic approaches to address this issue, ensuring that access patterns of algorithms remain oblivious to the data. However, deploying these methods on insecure algorithms, particularly for multi-way join processing, is computationally expensive and inherently challenging. In this paper, we propose a novel sorting-based algorithm for multi-way join processing that operates without relying on ORAM simulations or other security assumptions. Our algorithm is a non-trivial, provably oblivious composition of basic primitives, with time complexity matching the insecure worst-case optimal join algorithm, up to a logarithmic factor. Furthermore, it is cache-agnostic, with cache complexity matching the insecure lower bound, also up to a logarithmic factor. This clean and straightforward approach has the potential to be extended to other security settings and implemented in practical database systems.
Cite as

Xiao Hu and Zhiang Wu. Optimal Oblivious Algorithms for Multi-Way Joins. In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 25:1-25:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hu_et_al:LIPIcs.ICDT.2025.25,
  author =	{Hu, Xiao and Wu, Zhiang},
  title =	{{Optimal Oblivious Algorithms for Multi-Way Joins}},
  booktitle =	{28th International Conference on Database Theory (ICDT 2025)},
  pages =	{25:1--25:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-364-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{328},
  editor =	{Roy, Sudeepa and Kara, Ahmet},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.25},
  URN =		{urn:nbn:de:0030-drops-229662},
  doi =		{10.4230/LIPIcs.ICDT.2025.25},
  annote =	{Keywords: oblivious algorithms, multi-way joins, worst-case optimality}
}
Document
DOI: 10.4230/DagRep.4.12.29
The Synergy Between Programming Languages and Cryptography (Dagstuhl Seminar 14492)

Authors: Gilles Barthe, Michael Hicks, Florian Kerschbaum, and Dominique Unruh

Published in: Dagstuhl Reports, Volume 4, Issue 12 (2015)

Abstract
Increasingly, modern cryptography (crypto) has moved beyond the problem of secure communication to a broader consideration of securing computation. The past thirty years have seen a steady progression of both theoretical and practical advances in designing cryptographic protocols for problems such as secure multiparty computation, searching and computing on encrypted data, verifiable storage and computation, statistical data privacy, and more. More recently, the programming-languages (PL) community has begun to tackle the same set of problems, but from a different perspective, focusing on issues such as language design (e.g., new features or type systems), formal methods (e.g., model checking, deductive verification, static and dynamic analysis), compiler optimizations, and analyses of side-channel attacks and information leakage. This seminar helped to cross-fertilize ideas between the PL and crypto communities, exploiting the synergies for advancing the development of secure computing, broadly speaking, and fostering new research directions in and across both communities.
Cite as

Gilles Barthe, Michael Hicks, Florian Kerschbaum, and Dominique Unruh. The Synergy Between Programming Languages and Cryptography (Dagstuhl Seminar 14492). In Dagstuhl Reports, Volume 4, Issue 12, pp. 29-47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{barthe_et_al:DagRep.4.12.29,
  author =	{Barthe, Gilles and Hicks, Michael and Kerschbaum, Florian and Unruh, Dominique},
  title =	{{The Synergy Between Programming Languages and Cryptography (Dagstuhl Seminar 14492)}},
  pages =	{29--47},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{4},
  number =	{12},
  editor =	{Barthe, Gilles and Hicks, Michael and Kerschbaum, Florian and Unruh, Dominique},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.12.29},
  URN =		{urn:nbn:de:0030-drops-50045},
  doi =		{10.4230/DagRep.4.12.29},
  annote =	{Keywords: Security, Theory, Languages}
}
Document
DOI: 10.4230/DagSemProc.08302.3
Collaborative Fraud Detection in Outsourcing Scenarios: Issues of and Solutions for Privacy and Confidentiality

Authors: Ulrich Flegel, Florian Kerschbaum, and Richard Wacker

Published in: Dagstuhl Seminar Proceedings, Volume 8302, Countering Insider Threats (2008)

Abstract
In this paper we investigate the privacy dimension of collaborative fraud detection envisioned for outsourcing scenarios. Firstly, we investigate the privacy requirements derived from privacy law and present the resulting judicial argument for pseudonymizing audit data generated for the purpose of fraud detection. Second, we summarize the requirements for such pseudonymization derived from the requirements of the misuse detection approach for fraud detection. Third, we describe our approach for pseudonymization of audit data and two approaches for hiding timestamps in audit data.
Cite as

Ulrich Flegel, Florian Kerschbaum, and Richard Wacker. Collaborative Fraud Detection in Outsourcing Scenarios: Issues of and Solutions for Privacy and Confidentiality. In Countering Insider Threats. Dagstuhl Seminar Proceedings, Volume 8302, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{flegel_et_al:DagSemProc.08302.3,
  author =	{Flegel, Ulrich and Kerschbaum, Florian and Wacker, Richard},
  title =	{{Collaborative Fraud Detection in Outsourcing Scenarios: Issues of and Solutions for Privacy and Confidentiality}},
  booktitle =	{Countering Insider Threats},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8302},
  editor =	{Matt Bishop and Dieter Gollmann and Jeffrey Hunke and Christian W. Probst},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08302.3},
  URN =		{urn:nbn:de:0030-drops-17947},
  doi =		{10.4230/DagSemProc.08302.3},
  annote =	{Keywords: Insider threat; occupational fraud; privacy law; PET; logical clocks, pseudonyms,}
}
  • Refine by Type
  • 4 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2025
  • 1 2015
  • 1 2008

  • Refine by Author
  • 2 Kerschbaum, Florian
  • 1 Barthe, Gilles
  • 1 Flegel, Ulrich
  • 1 Foxman, Ben
  • 1 Hicks, Michael
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs
  • 1 DagRep
  • 1 DagSemProc

  • Refine by Classification
  • 1 Information systems → Join algorithms
  • 1 Security and privacy → Management and querying of encrypted data
  • 1 Theory of computation → Quantum complexity theory

  • Refine by Keyword
  • 1 Circuit Complexity
  • 1 Insider threat; occupational fraud; privacy law; PET; logical clocks
  • 1 Languages
  • 1 Pseudorandomness
  • 1 Quantum Information
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact