9 Search Results for "Ryan, Mark D."


Document
Smaller ACC0 Circuits for Symmetric Functions

Authors: Brynmor Chapman and R. Ryan Williams

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)


Abstract
What is the power of constant-depth circuits with MOD_m gates, that can count modulo m? Can they efficiently compute MAJORITY and other symmetric functions? When m is a constant prime power, the answer is well understood. In this regime, Razborov and Smolensky proved in the 1980s that MAJORITY and MOD_m require super-polynomial-size MOD_q circuits, where q is any prime power not dividing m. However, relatively little is known about the power of MOD_m gates when m is not a prime power. For example, it is still open whether every problem decidable in exponential time can be computed by depth-3 circuits of polynomial-size and only MOD_6 gates. In this paper, we shed some light on the difficulty of proving lower bounds for MOD_m circuits, by giving new upper bounds. We show how to construct MOD_m circuits computing symmetric functions with non-prime power m, with size-depth tradeoffs that beat the longstanding lower bounds for AC^0[m] circuits when m is a prime power. Furthermore, we observe that our size-depth tradeoff circuits have essentially optimal dependence on m and d in the exponent, under a natural circuit complexity hypothesis. For example, we show that for every ε > 0, every symmetric function can be computed using MOD_m circuits of depth 3 and 2^{n^ε} size, for a constant m depending only on ε > 0. In other words, depth-3 CC^0 circuits can compute any symmetric function in subexponential size. This demonstrates a significant difference in the power of depth-3 CC^0 circuits, compared to other models: for certain symmetric functions, depth-3 AC^0 circuits require 2^{Ω(√n)} size [Håstad 1986], and depth-3 AC^0[p^k] circuits (for fixed prime power p^k) require 2^{Ω(n^{1/6})} size [Smolensky 1987]. Even for depth-2 MOD_p ∘ MOD_m circuits, 2^{Ω(n)} lower bounds were known [Barrington Straubing Thérien 1990].

Cite as

Brynmor Chapman and R. Ryan Williams. Smaller ACC0 Circuits for Symmetric Functions. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 38:1-38:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{chapman_et_al:LIPIcs.ITCS.2022.38,
  author =	{Chapman, Brynmor and Williams, R. Ryan},
  title =	{{Smaller ACC0 Circuits for Symmetric Functions}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{38:1--38:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.38},
  URN =		{urn:nbn:de:0030-drops-156342},
  doi =		{10.4230/LIPIcs.ITCS.2022.38},
  annote =	{Keywords: ACC, CC, circuit complexity, symmetric functions, Chinese Remainder Theorem}
}
Document
Explicit Abelian Lifts and Quantum LDPC Codes

Authors: Fernando Granha Jeronimo, Tushant Mittal, Ryan O'Donnell, Pedro Paredes, and Madhur Tulsiani

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)


Abstract
For an abelian group H acting on the set [𝓁], an (H,𝓁)-lift of a graph G₀ is a graph obtained by replacing each vertex by 𝓁 copies, and each edge by a matching corresponding to the action of an element of H. Expanding graphs obtained via abelian lifts, form a key ingredient in the recent breakthrough constructions of quantum LDPC codes, (implicitly) in the fiber bundle codes by Hastings, Haah and O'Donnell [STOC 2021] achieving distance Ω̃(N^{3/5}), and in those by Panteleev and Kalachev [IEEE Trans. Inf. Theory 2021] of distance Ω(N/log(N)). However, both these constructions are non-explicit. In particular, the latter relies on a randomized construction of expander graphs via abelian lifts by Agarwal et al. [SIAM J. Discrete Math 2019]. In this work, we show the following explicit constructions of expanders obtained via abelian lifts. For every (transitive) abelian group H ⩽ Sym(𝓁), constant degree d ≥ 3 and ε > 0, we construct explicit d-regular expander graphs G obtained from an (H,𝓁)-lift of a (suitable) base n-vertex expander G₀ with the following parameters: ii) λ(G) ≤ 2√{d-1} + ε, for any lift size 𝓁 ≤ 2^{n^{δ}} where δ = δ(d,ε), iii) λ(G) ≤ ε ⋅ d, for any lift size 𝓁 ≤ 2^{n^{δ₀}} for a fixed δ₀ > 0, when d ≥ d₀(ε), or iv) λ(G) ≤ Õ(√d), for lift size "exactly" 𝓁 = 2^{Θ(n)}. As corollaries, we obtain explicit quantum lifted product codes of Panteleev and Kalachev of almost linear distance (and also in a wide range of parameters) and explicit classical quasi-cyclic LDPC codes with wide range of circulant sizes. Items (i) and (ii) above are obtained by extending the techniques of Mohanty, O'Donnell and Paredes [STOC 2020] for 2-lifts to much larger abelian lift sizes (as a byproduct simplifying their construction). This is done by providing a new encoding of special walks arising in the trace power method, carefully "compressing" depth-first search traversals. Result (iii) is via a simpler proof of Agarwal et al. [SIAM J. Discrete Math 2019] at the expense of polylog factors in the expansion.

Cite as

Fernando Granha Jeronimo, Tushant Mittal, Ryan O'Donnell, Pedro Paredes, and Madhur Tulsiani. Explicit Abelian Lifts and Quantum LDPC Codes. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 88:1-88:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{jeronimo_et_al:LIPIcs.ITCS.2022.88,
  author =	{Jeronimo, Fernando Granha and Mittal, Tushant and O'Donnell, Ryan and Paredes, Pedro and Tulsiani, Madhur},
  title =	{{Explicit Abelian Lifts and Quantum LDPC Codes}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{88:1--88:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.88},
  URN =		{urn:nbn:de:0030-drops-156846},
  doi =		{10.4230/LIPIcs.ITCS.2022.88},
  annote =	{Keywords: Graph lifts, expander graphs, quasi-cyclic LDPC codes, quantum LDPC codes}
}
Document
Privacy and Security in an Age of Surveillance (Dagstuhl Perspectives Workshop 14401)

Authors: Bart Preneel, Philipp Rogaway, Mark D. Ryan, and Peter Y. A. Ryan

Published in: Dagstuhl Manifestos, Volume 5, Issue 1 (2015)


Abstract
Before the Snowden revelations about the scope of surveillance by the NSA and its partner agencies, most people assumed that surveillance was limited to what is necessary and proportionate for these agencies to fulfil their prescribed role. People assumed that oversight mechanisms were in place to ensure that surveillance was appropriately constrained. But the Snowden revelations undermine these beliefs. We now know that nations are amassing personal data about people's lives at an unprecedented scale, far beyond most people's wildest expectations. The scope of state surveillance must be limited by an understanding of its costs as well as benefits. The costs are not limited to financial ones but also include eroding personal rights and the degradation to the integrity, vibrancy, or fundamental character of civil society. This manifesto stems from a Dagstuhl Perspectives Workshop held in late 2014. The meeting was a four-day gathering of experts from multiple disciplines connected with privacy and security. The aim was to explore how society as a whole, and the computing science community in particular, should respond to the Snowden revelations. More precisely, the meeting discussed the scope and nature of the practice of mass-surveillance, basic principles that should underlie reforms, and the potential for technical, legal, and other means to help stem or restore human rights threatened by ubiquitous electronic surveillance.

Cite as

Bart Preneel, Philipp Rogaway, Mark D. Ryan, and Peter Y. A. Ryan. Privacy and Security in an Age of Surveillance (Dagstuhl Perspectives Workshop 14401). In Dagstuhl Manifestos, Volume 5, Issue 1, pp. 25-37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@Article{preneel_et_al:DagMan.5.1.25,
  author =	{Preneel, Bart and Rogaway, Philipp and Ryan, Mark D. and Ryan, Peter Y. A.},
  title =	{{Privacy and Security in an Age of Surveillance (Dagstuhl Perspectives Workshop 14401)}},
  pages =	{25--37},
  journal =	{Dagstuhl Manifestos},
  ISSN =	{2193-2433},
  year =	{2015},
  volume =	{5},
  number =	{1},
  editor =	{Preneel, Bart and Rogaway, Philipp and Ryan, Mark D. and Ryan, Peter Y. A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagMan.5.1.25},
  URN =		{urn:nbn:de:0030-drops-55653},
  doi =		{10.4230/DagMan.5.1.25},
  annote =	{Keywords: Big data, encryption, mass surveillance, privacy}
}
Document
Privacy and Security in an Age of Surveillance (Dagstuhl Perspectives Workshop 14401)

Authors: Bart Preneel, Phillip Rogaway, Mark D. Ryan, and Peter Y. A. Ryan

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


Abstract
The Snowden revelations have demonstrated that the US and other nations are amassing data about people's lives at an unprecedented scale. Furthermore, these revelations have shown that intelligence agencies are not only pursuing passive surveillance over the world's communication systems, but are also seeking to facilitate such surveillance by undermining the security of the internet and communications technologies. Thus the activities of these agencies threatens not only the rights of individual citizens but also the fabric of democratic society. Intelligence services do have a useful role to play in protecting society and for this need the capabilities and authority to perform targeted surveillance. But the scope of such surveillance must be strictly limited by an understanding of its costs as well as benefits, and it should not impinge on the privacy rights of citizens any more than necessary. Here we report on a recent Dagstuhl Perspectives Workshop addressing these issues - a four-day gathering of experts from multiple disciplines connected with privacy and security. The meeting explored the scope of mass-surveillance and the deliberate undermining of the security of the internet, defined basic principles that should underlie needed reforms, and discussed the potential for technical, legal and regulatory means to help restore the security of the internet and stem infringement of human-rights by ubiquitous electronic surveillance.

Cite as

Bart Preneel, Phillip Rogaway, Mark D. Ryan, and Peter Y. A. Ryan. Privacy and Security in an Age of Surveillance (Dagstuhl Perspectives Workshop 14401). In Dagstuhl Reports, Volume 4, Issue 9, pp. 106-123, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@Article{preneel_et_al:DagRep.4.9.106,
  author =	{Preneel, Bart and Rogaway, Phillip and Ryan, Mark D. and Ryan, Peter Y. A.},
  title =	{{Privacy and Security in an Age of Surveillance (Dagstuhl Perspectives Workshop 14401)}},
  pages =	{106--123},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{4},
  number =	{9},
  editor =	{Preneel, Bart and Rogaway, Phillip and Ryan, Mark D. and Ryan, Peter Y. A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.4.9.106},
  URN =		{urn:nbn:de:0030-drops-48882},
  doi =		{10.4230/DagRep.4.9.106},
  annote =	{Keywords: Big data, encryption, mass surveillance, privacy}
}
Document
07421 Abstracts Collection – Formal Protocol Verification Applied

Authors: Liqun Chen, Steve Kremer, and Mark D. Ryan

Published in: Dagstuhl Seminar Proceedings, Volume 7421, Formal Protocol Verification Applied (2008)


Abstract
From 14/10/2007 to 19/10/2007, the Dagstuhl Seminar 07421 ``Formal Protocol Verification Applied'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Liqun Chen, Steve Kremer, and Mark D. Ryan. 07421 Abstracts Collection – Formal Protocol Verification Applied. In Formal Protocol Verification Applied. Dagstuhl Seminar Proceedings, Volume 7421, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{chen_et_al:DagSemProc.07421.1,
  author =	{Chen, Liqun and Kremer, Steve and Ryan, Mark D.},
  title =	{{07421 Abstracts Collection – Formal Protocol Verification Applied}},
  booktitle =	{Formal Protocol Verification Applied},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7421},
  editor =	{Liqun Chen and Steve Kremer and Mark D. Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07421.1},
  URN =		{urn:nbn:de:0030-drops-14196},
  doi =		{10.4230/DagSemProc.07421.1},
  annote =	{Keywords: Security protocols, formal verification, trusted computing, biometrics, security of mobile computing, electronic voting, payment systems}
}
Document
07421 Executive Summary – Formal Protocol Verification Applied

Authors: Liqun Chen, Steve Kremer, and Mark D. Ryan

Published in: Dagstuhl Seminar Proceedings, Volume 7421, Formal Protocol Verification Applied (2008)


Abstract
Security protocols are a core part of distributed computing systems, and are part of our everyday life since they are used in web servers, email, mobile phones, bank transactions, etc. However, security protocols are notoriously difficult to get right. There are many cases of protocols which are proposed and considered secure for many years, but later found to have security flaws. Formal methods offer a promising way for automated security analysis of protocols. While there have been considerable advances in this area, most techniques have only been applied to academic case studies and security properties such as secrecy and authentication. The seminar brought together researchers deploying security protocols in new application areas, cryptographers, and researchers from formal methods who analyse security protocols. The interaction between researchers from these different communities aims to open new research topics, e.g., identify new security properties that need verification and refine abstractions of the abstract models of crytpographic primitives.

Cite as

Liqun Chen, Steve Kremer, and Mark D. Ryan. 07421 Executive Summary – Formal Protocol Verification Applied. In Formal Protocol Verification Applied. Dagstuhl Seminar Proceedings, Volume 7421, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{chen_et_al:DagSemProc.07421.2,
  author =	{Chen, Liqun and Kremer, Steve and Ryan, Mark D.},
  title =	{{07421 Executive Summary – Formal Protocol Verification Applied}},
  booktitle =	{Formal Protocol Verification Applied},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7421},
  editor =	{Liqun Chen and Steve Kremer and Mark D. Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07421.2},
  URN =		{urn:nbn:de:0030-drops-14186},
  doi =		{10.4230/DagSemProc.07421.2},
  annote =	{Keywords: Security protocols, formal verification, trusted computing, biometrics, security of mobile computing, electronic voting, payment systems}
}
Document
Complete Characterization of Security Protocols by Pattern Refinement

Authors: Cas Cremers

Published in: Dagstuhl Seminar Proceedings, Volume 7421, Formal Protocol Verification Applied (2008)


Abstract
Recently, the notion of complete characterizations of security protocols was introduced by Guttman and Thayer. We provide an alternative definition of this concept, and extend an existing protocol verification tool (Scyther) to compute our notion of complete characterization. We present both notions of complete characterization, discuss their relative merits, and provide preliminary empirical results using an extended version of the Scyther tool.

Cite as

Cas Cremers. Complete Characterization of Security Protocols by Pattern Refinement. In Formal Protocol Verification Applied. Dagstuhl Seminar Proceedings, Volume 7421, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{cremers:DagSemProc.07421.3,
  author =	{Cremers, Cas},
  title =	{{Complete Characterization of Security Protocols by Pattern Refinement}},
  booktitle =	{Formal Protocol Verification Applied},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7421},
  editor =	{Liqun Chen and Steve Kremer and Mark D. Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07421.3},
  URN =		{urn:nbn:de:0030-drops-14173},
  doi =		{10.4230/DagSemProc.07421.3},
  annote =	{Keywords: Security protocols, Formal analysis, Verification, Tools}
}
Document
Zero-Knowledge in the Applied Pi-calculus and Automated Verification of the Direct Anonymous Attestation Protocol

Authors: Michael Backes, Matteo Maffei, and Dominique Unruh

Published in: Dagstuhl Seminar Proceedings, Volume 7421, Formal Protocol Verification Applied (2008)


Abstract
We devise an abstraction of zero-knowledge protocols that is accessible to a fully mechanized analysis. The abstraction is formalized within the applied pi-calculus using a novel equational theory that abstractly characterizes the cryptographic semantics of zero-knowledge proofs. We present an encoding from the equational theory into a convergent rewriting system that is suitable for the automated protocol verifier ProVerif. The encoding is sound and fully automated. We successfully used ProVerif to obtain the first mechanized analysis of the Direct Anonymous Attestation (DAA) protocol. The analysis in particular required us to devise novel abstractions of sophisticated cryptographic security definitions based on interactive games.

Cite as

Michael Backes, Matteo Maffei, and Dominique Unruh. Zero-Knowledge in the Applied Pi-calculus and Automated Verification of the Direct Anonymous Attestation Protocol. In Formal Protocol Verification Applied. Dagstuhl Seminar Proceedings, Volume 7421, pp. 1-43, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{backes_et_al:DagSemProc.07421.4,
  author =	{Backes, Michael and Maffei, Matteo and Unruh, Dominique},
  title =	{{Zero-Knowledge in the Applied Pi-calculus and Automated Verification of the Direct Anonymous Attestation Protocol}},
  booktitle =	{Formal Protocol Verification Applied},
  pages =	{1--43},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7421},
  editor =	{Liqun Chen and Steve Kremer and Mark D. Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07421.4},
  URN =		{urn:nbn:de:0030-drops-14153},
  doi =		{10.4230/DagSemProc.07421.4},
  annote =	{Keywords: Language-based security, zero-knowledge proofs, applied pi-calculus, direct anonymous attestation}
}
Document
Objects, Agents and Features (Dagstuhl Seminar 03081)

Authors: Hans-Dieter Ehrich, John-Jules Ch. Meyer, and Mark D. Ryan

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)


Abstract

Cite as

Hans-Dieter Ehrich, John-Jules Ch. Meyer, and Mark D. Ryan. Objects, Agents and Features (Dagstuhl Seminar 03081). Dagstuhl Seminar Report 367, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)


Copy BibTex To Clipboard

@TechReport{ehrich_et_al:DagSemRep.367,
  author =	{Ehrich, Hans-Dieter and Meyer, John-Jules Ch. and Ryan, Mark D.},
  title =	{{Objects, Agents and Features (Dagstuhl Seminar 03081)}},
  pages =	{1--6},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{367},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.367},
  URN =		{urn:nbn:de:0030-drops-152472},
  doi =		{10.4230/DagSemRep.367},
}
  • Refine by Author
  • 5 Ryan, Mark D.
  • 2 Chen, Liqun
  • 2 Kremer, Steve
  • 2 Preneel, Bart
  • 2 Ryan, Peter Y. A.
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Circuit complexity
  • 1 Theory of computation → Expander graphs and randomness extractors
  • 1 Theory of computation → Pseudorandomness and derandomization

  • Refine by Keyword
  • 3 Security protocols
  • 2 Big data
  • 2 biometrics
  • 2 electronic voting
  • 2 encryption
  • Show More...

  • Refine by Type
  • 9 document

  • Refine by Publication Year
  • 4 2008
  • 2 2015
  • 2 2022
  • 1 2003

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail