414 research outputs found
On the Computational Hardness Needed for Quantum Cryptography
No full textIn the classical model of computation, it is well established that one-way functions (OWF) are minimal for computational cryptography: They are essential for almost any cryptographic application that cannot be realized with respect to computationally unbounded adversaries. In the quantum setting, however, OWFs appear not to be essential (Kretschmer 2021; Ananth et al., Morimae and Yamakawa 2022), and the question of whether such a minimal primitive exists remains open.
We consider EFI pairs - efficiently samplable, statistically far but computationally indistinguishable pairs of (mixed) quantum states. Building on the work of Yan (2022), which shows equivalence between EFI pairs and statistical commitment schemes, we show that EFI pairs are necessary for a large class of quantum-cryptographic applications. Specifically, we construct EFI pairs from minimalistic versions of commitments schemes, oblivious transfer, and general secure multiparty computation, as well as from QCZK proofs from essentially any non-trivial language. We also construct quantum computational zero knowledge (QCZK) proofs for all of QIP from any EFI pair.
This suggests that, for much of quantum cryptography, EFI pairs play a similar role to that played by OWFs in the classical setting: they are simple to describe, essential, and also serve as a linchpin for demonstrating equivalence between primitives
Black-Box Concurrent Zero-Knowledge Requires (Almost) Logarithmically Many Rounds
No full textWe show that any concurrent zero-knowledge protocol for a non-trivial language, whose security is
proven via black-box simulation, must use at least logarithmically rounds of interaction. This result achieves a substantial improvement over previous lower bounds, and is the first bound to rule out the possibility of constant-round concurrent zero-knowledge when proven via black-box simulation. Furthermore, the bound is polynomially related to the number of rounds in the best known concurrent zero-knowledge protocol for languages in NP
On the Existence of Extractable One-Way Functions
No full textA function f is extractable if it is possible to algorithmically “extract,” from any adversarial program
that outputs a value y in the image of f, a preimage of y. When combined with hardness properties
such as one-wayness or collision-resistance, extractability has proven to be a powerful tool. However, so far, extractability has not been explicitly shown. Instead, it has only been considered as a non-standard knowledge assumption on certain functions.
We make two headways in the study of the existence of extractable one-way functions (EOWFs). On
the negative side, we show that if there exist indistinguishability obfuscators for a certain class of circuits then there do not exist EOWFs where extraction works for any adversarial program with auxiliary-input of unbounded polynomial length.
On the positive side, for adversarial programs with bounded auxiliary-input (and unbounded polynomial running time), we give the first construction of EOWFs with an explicit extraction procedure, based on relatively standard assumptions (e.g., sub-exponential hardness of Learning with Errors). We then use these functions to construct the first 2-message zero-knowledge arguments and 3-message zeroknowledge arguments of knowledge, against the same class of adversarial verifiers, from essentially the same assumptions
08491 Abstracts Collection – Theoretical Foundations of Practical Information Security
No full textFrom 30.11. to 05.12.2008, the Dagstuhl Seminar 08491 ``Theoretical Foundations of Practical Information Security '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics.
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
08491 Executive Summary – Theoretical Foundations of Practical Information Security
No full textDesigning, building, and operating secure information processing
systems is a complex task, and the only scientific way to address the
diverse challenges arising throughout the life-cycle of security
criticial systems is to consolidate and increase the knowledge of the
theoretical foundations of practical security problems. To this aim,
the mutual exchange of ideas across individual security research
communities can be extraordinary beneficial. Accordingly, the
motivation of this Dagstuhl seminar was the integration of different
research areas with the common goal of providing an integral
theoretical basis that is needed for the design of secure information
processing systems
Om Elias Canetti
No full textElias Canetti (1905–1994) was a Jewish author, born in Bulgaria and later living in Great Britain, who wrote mainly in German language. Although Canetti did not express Jewish belief or religiosity, being a Jew was still important to him. His Jewish identity was closely connected to the German language. He published memoirs, novels, philosophical works and drama which all entail some biblical themes or other themes that express his Jewish heritage
Quevedo\u27s presence in the works by Elias Canetti
No full textElias Canetti points out in his autobiography that after Swift and Aristophanes, Quevedo became his literary ancestor. In this article the author tries to explain the reasons of this election. First, it is important to know how Canetti became interested in Spanish culture and literature. Then, it is explained the meaning of literaiy ancestor in the formation of the writer. Finally, the author analyses Quevedo\u27s presence in Canetti\u27s works, and pays special attention to satire and the affinities between Ouevedo and Canetti
Secure Computation with Honest-Looking Parties: What if nobody is truly honest? (Extended Abstract)
No full text) Ran Canetti Rafail Ostrovsky y April 28, 1999 Abstract In a secure multi-party computation a set of mutually distrustful parties interact in order to evaluate a pre-defined function of their inputs, without revealing the inputs to each other. In this scenario, the trust in other parties should be minimal. In the classic formulation of this problem, most of the parties are trusted to exactly follow the prescribed protocol, except for a limited number of parties that are corrupted by a centralized adversary and are allowed to deviate from the protocol in an arbitrary way. However, an assumption of a totally honest behavior of most parties can not be verified. In particular, if an "honest-looking" party diverges from its protocol in a way that is indistinguishable from a totally honest player, it can do so with "impunity". In this paper, we consider the situation where all parties (even uncorrupted ones) may deviate from their protocol in arbitrary ways, under the sole restriction ..
Secure Database Commitments and Universal Arguments of Quasi Knowledge
No full textIn this work we focus on a simple database commitment functionality where besides the standard security properties, one would like to hide the size of the input of the sender. Hiding the size of the input of a player is a critical requirement in some applications, and relatively few works have considered it. Notable exceptions are the work on zero-knowledge sets introduced in~\cite{MRK03}, and recent work on size-hiding private set intersection~\cite{ADT11}. However, neither of these achieves a secure computation (i.e., a reduction of a real-world attack of a malicious adversary into an ideal-world attack) of the proposed functionality.
The first result of this submission consists in defining ``secure\u27\u27 database commitment and in observing that previous constructions do not satisfy this definition. This leaves open the question of whether there is any way this functionality can be achieved.
We then provide an affirmative answer to this question by using new techniques that combined together achieve ``secure\u27\u27 database commitment. Our construction is in particular optimized to require only a constant number of rounds, to provide non-interactive proofs on the content of the database, and to rely only on the existence of a family of CRHFs. This is the first result where input-size hiding secure computation is achieved for an interesting functionality and moreover we obtain this result with standard security (i.e., simulation in expected polynomial time against fully malicious adversaries, without random oracles, non-black-box extraction assumptions, hardness assumptions against super-polynomial time adversaries, or other controversial/strong assumptions).
A key building block in our construction is a universal argument enjoying an improved proof of knowledge property, that we call quasi-knowledge. This property is significantly closer to the standard proof of knowledge property than the weak proof of knowledge property satisfied by previous constructions
On the existence of extractable one-way functions
No full textA function f is extractable if it is possible to algorithmically “extract,” from any adversarial program that outputs a value y in the image of f, a preimage of y. When combined with hardness properties such as one-wayness or collision-resistance, extractability has proven to be a powerful tool. However, so far, extractability has not been explicitly shown. Instead, it has only been considered as a non-standard knowledge assumption on certain functions. We make two headways in the study of the existence of extractable one-way functions (EOWFs). On the negative side, we show that if there exist indistinguishability obfuscators for a certain class of circuits then there do not exist EOWFs where extraction works for any adversarial program with auxiliary-input of unbounded polynomial length. On the positive side, for adversarial programs with bounded auxiliary-input (and unbounded polynomial running time), we give the first construction of EOWFs with an explicit extraction procedure, based on relatively standard assumptions (e.g., sub-exponential hardness of Learning with Errors). We then use these functions to construct the first 2-message zero-knowledge arguments and 3-message zeroknowledge arguments of knowledge, against the same class of adversarial verifiers, from essentially th
- …
