1,720,983 research outputs found
Leakage-resilient coin tossing
Get PDFProceedings 25th International Symposium, DISC 2011, Rome, Italy, September 20-22, 2011.The ability to collectively toss a common coin among n parties
in the presence of faults is an important primitive in the arsenal of
randomized distributed protocols. In the case of dishonest majority, it
was shown to be impossible to achieve less than 1
r bias in O(r) rounds
(Cleve STOC ’86). In the case of honest majority, in contrast, unconditionally
secure O(1)-round protocols for generating common unbiased
coins follow from general completeness theorems on multi-party secure
protocols in the secure channels model (e.g., BGW, CCD STOC ’88).
However, in the O(1)-round protocols with honest majority, parties
generate and hold secret values which are assumed to be perfectly hidden
from malicious parties: an assumption which is crucial to proving the
resulting common coin is unbiased. This assumption unfortunately does
not seem to hold in practice, as attackers can launch side-channel attacks
on the local state of honest parties and leak information on their secrets.
In this work, we present an O(1)-round protocol for collectively generating
an unbiased common coin, in the presence of leakage on the local
state of the honest parties. We tolerate t ≤ ( 1
3
− )n computationallyunbounded
Byzantine faults and in addition a Ω(1)-fraction leakage on
each (honest) party’s secret state. Our results hold in the memory leakage
model (of Akavia, Goldwasser, Vaikuntanathan ’08) adapted to the
distributed setting.
Additional contributions of our work are the tools we introduce to
achieve the collective coin toss: a procedure for disjoint committee election,
and leakage-resilient verifiable secret sharing.National Defense Science and Engineering Graduate FellowshipNational Science Foundation (U.S.) (CCF-1018064
Untangling the Security of Kilian’s Protocol: Upper and Lower Bounds
No full textSigma protocols are elegant cryptographic proofs that have become a cornerstone of modern cryptography. A notable example is Schnorr’s protocol, a zero-knowledge proof-of-knowledge of a discrete logarithm. Despite extensive research, the security of Schnorr’s protocol in the standard model is not fully understood. In this paper we study Kilian’s protocol, an influential public-coin interactive protocol that, while not a sigma protocol, shares striking similarities with sigma protocols. The first example of a succinct argument, Kilian’s protocol is proved secure via rewinding, the same idea used to prove sigma protocols secure. In this paper we show how, similar to Schnorr’s protocol, a precise understanding of the security of Kilian’s protocol remains elusive. We contribute new insights via upper bounds and lower bounds. Upper bounds. We establish the tightest known bounds on the security of Kilian’s protocol in the standard model, via strict-time reductions and via expected-time reductions. Prior analyses are strict-time reductions that incur large overheads or assume restrictive properties of the PCP underlying Kilian’s protocol.Lower bounds. We prove that significantly improving on the bounds that we establish for Kilian’s protocol would imply improving the security analysis of Schnorr’s protocol beyond the current state-of-the-art (an open problem). This partly explains the difficulties in obtaining tight bounds for Kilian’s protocol. Upper bounds. We establish the tightest known bounds on the security of Kilian’s protocol in the standard model, via strict-time reductions and via expected-time reductions. Prior analyses are strict-time reductions that incur large overheads or assume restrictive properties of the PCP underlying Kilian’s protocol. Lower bounds. We prove that significantly improving on the bounds that we establish for Kilian’s protocol would imply improving the security analysis of Schnorr’s protocol beyond the current state-of-the-art (an open problem). This partly explains the difficulties in obtaining tight bounds for Kilian’s protocol.COMPSE
zkSNARKs in the ROM with Unconditional UC-Security
No full textThe universal composability (UC) framework is a “gold standard” for security in cryptography. UC-secure protocols achieve strong security guarantees against powerful adaptive adversaries, and retain these guarantees when used as part of larger protocols. Zero knowledge succinct non-interactive arguments of knowledge (zkSNARKs) are a popular cryptographic primitive that are often used within larger protocols deployed in dynamic environments, and so UC-security is a highly desirable, if not necessary, goal. In this paper we prove that there exist zkSNARKs in the random oracle model (ROM) that unconditionally achieve UC-security. Here, “unconditionally” means that security holds against adversaries that make a bounded number of queries to the random oracle, but are otherwise computationally unbounded. Prior work studying UC-security for zkSNARKs obtains transformations that rely on computational assumptions and, in many cases, lose most of the succinctness property of the zkSNARK. Moreover, these transformations make the resulting zkSNARK more expensive and complicated. In contrast, we prove that widely used zkSNARKs in the ROM are UC-secure without modifications. We prove that the Micali construction, which is the canonical construction of a zkSNARK, is UC-secure. Moreover, we prove that the BCS construction, which many zkSNARKs deployed in practice are based on, is UC-secure. Our results confirm the intuition that these natural zkSNARKs do not need to be augmented to achieve UC-security, and give confidence that their use in larger real-world systems is secure.COMPSE
Security Bounds for Proof-Carrying Data from Straightline Extractors
No full textProof-carrying data (PCD) is a powerful cryptographic primitive that allows mutually distrustful parties to perform distributed computation in an efficiently verifiable manner. Real-world deployments of PCD have sparked keen interest within the applied community and industry. Known constructions of PCD are obtained by recursively-composing SNARKs or related primitives. Unfortunately, known security analyses incur expensive blowups, which practitioners have disregarded as the analyses would lead to setting parameters that are prohibitively expensive. In this work we study the concrete security of recursive composition, with the goal of better understanding how to reasonably set parameters for certain PCD constructions of practical interest. Our main result is that PCD obtained from SNARKs with straightline knowledge soundness has essentially the same security as the underlying SNARK (i.e., recursive composition incurs essentially no security loss). We describe how straightline knowledge soundness is achieved by SNARKs in several oracle models, which results in a highly efficient security analysis of PCD that makes black-box use of the SNARK’s oracle (there is no need to instantiated the oracle to carry out the security reduction). As a notable application, our work offers an idealized model that provides new, albeit heuristic, insights for the concrete security of recursive STARKs used in blockchain systems. Our work could be viewed as partial evidence justifying the parameter choices for recursive STARKs made by practitioners.COMPSE
Quantum Key-Revocable Dual-Regev Encryption, Revisited
No full textQuantum information can be used to achieve novel cryptographic primitives that are impossible to achieve classically. A recent work by Ananth, Poremba, Vaikuntanathan (TCC 2023) focuses on equipping the dual-Regev encryption scheme, introduced by Gentry, Peikert, Vaikuntanathan (STOC 2008), with key revocation capabilities using quantum information. They further showed that the key-revocable dual-Regev scheme implies the existence of fully homomorphic encryption and pseudorandom functions, with both of them also equipped with key revocation capabilities. Unfortunately, they were only able to prove the security of their schemes based on new conjectures and left open the problem of basing the security of key revocable dual-Regev encryption on well-studied assumptions. In this work, we resolve this open problem. Assuming polynomial hardness of learning with errors (over sub-exponential modulus), we show that key-revocable dual-Regev encryption is secure. As a consequence, for the first time, we achieve the following results:Key-revocable public-key encryption and key-revocable fully-homomorphic encryption satisfying classical revocation security and based on polynomial hardness of learning with errors. Prior works either did not achieve classical revocation or were based on sub-exponential hardness of learning with errors.Key-revocable pseudorandom functions satisfying classical revocation from the polynomial hardness of learning with errors. Prior works relied upon unproven conjectures. Key-revocable public-key encryption and key-revocable fully-homomorphic encryption satisfying classical revocation security and based on polynomial hardness of learning with errors. Prior works either did not achieve classical revocation or were based on sub-exponential hardness of learning with errors. Key-revocable pseudorandom functions satisfying classical revocation from the polynomial hardness of learning with errors. Prior works relied upon unproven conjectures.COMPSE
Calcul multipartite sécurisé avec communication sous-linéaire
No full textLe calcul multipartite sécurisé (en anglais, MPC) [Yao82,GMW87a] permet à des agents d'un réseau de communication de calculer conjointement une fonction de leurs entrées sans avoir à n'en rien révéler de plus que le résultat du calcul lui-même. Une question primordiale est de savoir dans quelle mesure le coût en communication entre les agents dépend de la complexité calculatoire de la fonction en question. Un point de départ est l'étude d'une hypothétique barrière de la taille du circuit. L'existence d'une telle barrière est suggérée par le fait que tous les protocoles MPC fondateurs, des années 80 et 90, emploient une approche "porte-logique-par-porte-logique" au calcul sécurisé: la communication d'un tel protocole sera nécessairement au moins linéaire en le nombre de portes, c'est-à-dire en la taille du circuit. De plus ceux-ci représentent moralement l'état de l'art encore de nos jours en ce qui concerne la sécurité dite "par théorie de l'information". La barrière de la taille du circuit a été franchie pour le MPC avec sécurité calculatoire, mais sous des hypothèses structurées impliquant l'existence de chiffrement totalement homomorphe (en anglais, FHE) [Gen09] ou de partage de secret homomorphe (en anglais, HSS) [BGI16a]. De plus, il existe des protocoles avec sécurité par théorie de l'information dont la communication en-ligne (mais pas la communication totale) est sous-linéaire en la taille du circuit [IKM + 13, DNNR17, Cou19]. Notre méthodologie de recherche consiste à s'inspirer des techniques developpées dans le modèle de l'aléa corrélée dans lequel tout résultat pourra être considéré comme plus "fondamental" que le modèle calculatoire (de par le type de sécurité obtenue) mais qui est néanmoins un modèle inadapté à comprendre la complexité de communication du MPC (puisque que l'on s'autorise à ne pas compter toute quantité de communication qui peut être reléguée à une phase "hors-ligne", c'est-à-dire avant que les participants au calcul ne prennent connaissance de leurs entrées) pour développer de nouvelles méthodes dans le modèle calculatoire. Avec cette approche, nous obtenons des protocoles franchissant la barrière de la taille du circuit sous l'hypothèse de la sécurité quasipolynomiale de LPN [CM21] ou sous l'hypothèse QR+LPN [BCM22]. Ces hypothèses calculatoires n'étant pas précédement réputées impliquer l'existence de MPC sous-linéaire, la pertinence de notre méthodologie est, dans une certaine mesure, validée a posteriori. Plus fondamentalement cependant, nos travaux empruntent un nouveau paradigme pour construire du MPC sous-linéaire, sans utiliser les outils "avec de fortes propriétés homomorphiques" que sont le FHE ou du HSS. En combinant toutes nos techniques héritées de notre étude du modèle de l'aléa corrélé, nous parvenons à briser la barrière des deux joueurs pour le calcul sécurisé avec communication sous-linéaire, sans FHE [BCM23]. Spécifiquement, nous présentons le premier protocole à plus de deux participants dont la communication est sous-linéaire en la taille du circuit et qui ne soit pas fondé sur des hypothèses sous lesquelles on sait déjà faire du FHE. Parallèlement à ces travaux centrés sur la sécurité calculatoire, nous montrons [CMPR23] comment adapter les approches à deux joueurs utilisant du HSS, à la [BGI16a], pour gurantir une sécurité "théorie de l'information" à l'un des deux joueurs et une sécurité calculatoire à l'autre. Ceci est, de façon prouvable, la notion de sécurité la plus forte que l'on puisse espérer en présence de seulement deux joueurs (sans aléa corrélé). Nous obtenons le premier protocole de ce type avec communication sous-linéaire, qui ne soit pas fondé sur des hypothèses sous lesquelles on sait déjà faire du FHE.Secure Multi-Party Computation (MPC) [Yao82, GMW87a] allows a set of mutually distrusting parties to perform some joint computation on their private inputs without having to reveal anything beyond the output. A major open question is to understand how strongly the communication complexity of MPC and the computational complexity of the function being computed are correlated. An intriguing starting point is the study of the circuit-size barrier. The relevance of this barrier is a historical, and potentially absolute, one: all seminal protocols from the 1980s and 1990s use a "gate-by-gate" approach, requiring interaction between the parties for each (multiplicative) gate of the circuit to be computed, and this remains the state of the art if we wish to provide the strongest security guarantees. The circuit-size barrier has been broken in the computational setting from specific, structured, computational assumption, via Fully Homomorphic Encryption (FHE) [Gen09] and later Homomorphic Secret Sharing [BGI16a]. Additionally, the circuit-size barrier for online communication has been broken (in the correlated randomness model) information-theoretically [IKM + 13, DNNR17, Cou19], but no such result is known for the total communication complexity (in the plain model). Our methodology is to draw inspiration from known approaches in the correlated randomness model, which we view simultaneously as fundamental (because it provides information-theoretic security guarantees) and inherently limited (because the best we can hope for in this model is to understand the online communication complexity of secure computation), in order to devise new ways to break the circuit-size barrier in the computational setting. In the absence of a better way to decide when concrete progress has been made, we take extending the set of assumptions known to imply sublinear-communication secure computation as "proof of conceptual novelty". This approach has allowed us to break the circuit-size barrier under quasipolynomial LPN [CM21] or QR and LPN [BCM22]. More fundamentally, these works constituted a paradigm shift, away from the "homomorphism-based" approaches of FHE and HSS, which ultimately allowed us to break the two-party barrier for sublinear-communication secure computation and provide in [BCM23] the first sublinear-communication protocol with more than two parties, without FHE. Orthogonally to this line of work, purely focusing on computational security, we showed in [CMPR23] that [BGI16a] could be adapted to provide information-theoretic security for one of the two parties, and computational security for the other: these are provably the strongest security guarantees one can hope to achieve in the two-party setting (without setup), and ours is the first sublinear-communication protocol in this setting which does not use FHE
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Get PDF“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Get PDFWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
- …
