26 research outputs found
Towards Bringing Cryptographic Idealized Models Closer to Reality
No full textReal-world cryptosystems are complex objects involving a number of components that have to work in unison for their combination to run as intended. This makes assessing their security a challenging task, so much so that a complete analysis of a system as it stands is often out of reach. As a result, to gain confidence in the soundness of an application, it is essential to make abstractions about certain parts of the scheme while studying its security, and leave some of its specifics outside the model.
Idealized and restricted models of computation, like the random-oracle (ROM), the generic-group (GGM), and the algebraic-group (AGM) models, are three examples of such abstractions: They simplify what real-world hash functions and cryptographic groups are and how algorithms can interact with them. As abstractions, they have been exceptionally successful in justifying the security of many classical and modern cryptosystems that otherwise resist analysis under well-known and widely accepted assumptions. However, these models also come with standard-model uninstantiability results, raising the question of whether the schemes analyzed under them can be based on firmer standard-model footing. In this work, we tackle this question from two different angles.
In the first part of this thesis, we study a cryptographic scheme whose security is justified in the ROM yet whose security proof uses a distinctive feature of random oracles (programmability) that no real-world hash function provides. This, in turn, puts the meaning of the proof itself into question, as it cannot be replicated once the abstraction provided by the ROM is dispensed with. To make matters worse, we prove that this state of affairs is inherent, i.e., that a ROM-proof for the scheme that does not rely on this artificial property is unlikely to exist. We then go on to show that one can modify the scheme in such a way that a reduction that does not require programming the random oracle becomes possible. This serves as an example of how one can sometimes tweak schemes so that they are backed by "better" heuristic evidence of security and should, therefore, be preferred as they are arguably "closer to reality."
In the second and third parts of this thesis, we propose new standard-model assumptions for cryptographic groups. We validate these assumptions in appropriate idealized models and then show how they can be used to instantiate a range of existing, practical schemes previously proven secure only in the GGM or the AGM. These results facilitate a modular approach to security in the GGM and AGM since our definitions form an intermediate "layer" between the models themselves and the final applications. Our novel assumptions combine standard-model analyses with the ease of use offered by the corresponding idealized model and, in some cases, even allow reusing existing proofs. Importantly, our assumptions enable basing the security of our target applications in the standard model, thus placing them outside the class of uninstantiable schemes
Invisible Sanitizable Signatures and Public-Key Encryption are Equivalent
No full textSanitizable signature schemes are signature schemes which support the delegation of modification rights. The signer can allow a sanitizer to perform a set of admissible operations on the original message and then to update the signature, in such a way that basic security properties like unforgeability or accountability are preserved. Recently, Camenisch et al. (PKC 2017) devised new schemes with the previously unattained invisibility property. This property says that the set of admissible operations for the sanitizer remains hidden from outsiders. Subsequently, Beck et al. (ACISP 2017) gave an even stronger version of this notion and constructions achieving it. Here we characterize the invisibility property in both forms by showing that invisible sanitizable signatures are equivalent to IND−CPA-secure encryption schemes, and strongly invisible signatures are equivalent to IND−CCA2-secure encryption schemes. The equivalence is established by proving that invisible (resp. strongly invisible) sanitizable signature schemes yield IND−CPA-secure (resp. IND−CCA2-secure) public-key encryption schemes and that, vice versa, we can build (strongly) invisible sanitizable signatures given a corresponding public-key encryption scheme
The relationship between homonegativity, sexual harassment myth acceptance, harasser and target sex, and perceptions of sexual harassment
No full textThe current purpose was to determine the relationship between participant homonegativity, sexual harassment myth acceptance, and perceptions of sexual harassment where the gender of the target and harasser varied. Contrary to the hypothesis, higher and lower homonegativity participants did not differ in their perceptions of harassment severity, realism, or consequence and higher homonegativity participants did not report any differences in perceptions between the different-sex and same-sex scenarios. However as hypothesized, participant homonegativity was positively correlated with sexual harassment myth acceptance. Interestingly, participants higher in homonegativity or sexual harassment myth acceptance were more likely to rate the harassment as less severe and had less of an emotional reaction. The current results imply that regardless of the type sexual harassment (different or same-sex), higher homonegativitly participants may not react in institutionally appropriate ways regarding sexual harassment in the workplace
The Uber-Knowledge Assumption: A Bridge to the AGM
No full textThe generic-group model (GGM) and the algebraic-group model (AGM) have been exceptionally successful in proving the security of many classical and modern cryptosystems. These models, however, come with standard-model uninstantiability results, raising the question whether the schemes analyzed under them can be based on firmer standard-model footing.
We formulate the uber-knowledge (UK) assumption, a standard-model assumption that naturally extends the uber-assumption family to knowledge-type problems. We justify the soundness of the UK assumption in both the bilinear GGM and the bilinear AGM. Along the way we extend these models to account for hashing into groups, an adversarial capability that is available in many concrete groups---In contrast to standard assumptions, hashing may affect the validity of knowledge assumptions. These results, in turn, enable a modular approach to security in the GGM and the AGM.
As example applications, we use the UK assumption to prove knowledge soundness of Groth16 and of KZG polynomial commitments in the standard model, where for the former we reuse the existing proof in the AGM without hashing.
Note: Corrected claims that the uber-knowledge assumption implies several other knowledge assumptions, and provided formal proofs
Signatures from Sequential-OR Proofs
No full textOR-proofs enable a prover to show that it knows the witness for one of many statements, or that one out of many statements is true. OR-proofs are a remarkably versatile tool, used to strengthen security properties, design group and ring signature schemes, and achieve tight security. The common technique to build OR-proofs is based on an approach introduced by Cramer, Damgård, and Schoenmakers (CRYPTO’94), where the prover splits the verifier’s challenge into random shares and computes proofs for each statement in parallel.
In this work we study a different, less investigated OR-proof technique, put forward by Abe, Ohkubo, and Suzuki (ASIACRYPT’02). The difference is that the prover now computes the individual proofs sequentially. We show that such sequential OR-proofs yield signature schemes which can be proved secure in the non-programmable random oracle model. We complement this positive result with a black-box impossibility proof, showing that the same is unlikely to be the case for signatures derived from traditional OR-proofs. We finally argue that sequential-OR signature schemes can be proved secure in the quantum random oracle model, albeit with very loose bounds and by programming the random oracle
Block Ciphers in Idealized Models: Automated Proofs and New Security Results
No full textWe develop and implement AlgoROM, a tool to systematically analyze the security of a wide class of symmetric primitives in idealized models of computation. The schemes that we consider are those that can be expressed over an alphabet consisting of XOR and function symbols for hash functions, permutations, or block ciphers.
We implement our framework in OCaml and apply it to a number of prominent constructions, which include the Luby–Rackoff (LR), key-alternating Feistel (KAF), and iterated Even–Mansour (EM) ciphers, as well as substitution-permutation networks (SPN). The security models we consider are (S)PRP, and strengthenings thereof under related-key (RK), key-dependent message (KD), and more generally key-correlated (KC) attacks.
Using AlgoROM, we are able to reconfirm a number of classical and previously established security theorems, and in one case we identify a gap in a proof from the literature (Connolly et al., ToSC\u2719). However, most results that we prove with AlgoROM are new. In particular, we obtain new positive results for LR, KAF, EM, and SPN in the above models. Our results better reflect the configurations actually implemented in practice, as they use a single idealized primitive. In contrast to many existing tools, our automated proofs do not operate in symbolic models, but rather in the standard probabilistic model for cryptography
BlindOR: An Efficient Lattice-Based Blind Signature Scheme from OR-Proofs
No full textAn OR-proof is a protocol that enables a user to prove the possession of a witness for one of two (or more) statements, without revealing which one. Abe and Okamoto (CRYPTO 2000) used this technique to build a partially blind signature scheme whose security is based on the hardness of the discrete logarithm problem. Inspired by their approach, we present BlindOR, an efficient blind signature scheme from OR-proofs based on lattices over modules. Using OR-proofs allows us to reduce the security of our scheme from the MLWE and MSIS problems, yielding a much more efficient solution compared to previous works
Block Ciphers in Idealized Models: Automated Proofs and New Security Results
No full textWe develop and implement AlgoROM, a tool to systematically analyze the security of a wide class of symmetric primitives in idealized models of computation. The schemes that we consider are those that can be expressed over an alphabet consisting of XOR and function symbols for hash functions, permutations, or block ciphers.
We implement our framework in OCaml and apply it to a number of prominent constructions, which include the Luby–Rackoff (LR), key-alternating Feistel (KAF), and iterated Even–Mansour (EM) ciphers, as well as substitution-permutation networks (SPN). The security models we consider are (S)PRP, and strengthenings thereof under related-key (RK), key-dependent message (KD), and more generally key-correlated (KC) attacks.
Using AlgoROM, we are able to reconfirm a number of classical and previously established security theorems, and in one case we identify a gap in a proof from the literature (Connolly et al., ToSC'19). However, most results that we prove with AlgoROM are new. In particular, we obtain new positive results for LR, KAF, EM, and SPN in the above models. Our results better reflect the configurations actually implemented in practice, as they use a single idealized primitive. In contrast to many existing tools, our automated proofs do not operate in symbolic models, but rather in the standard probabilistic model for cryptography
Block Ciphers in Idealized Models: Automated Proofs and New Security Results
No full textWe develop and implement AlgoROM, a tool to systematically analyze the security of a wide class of symmetric primitives in idealized models of computation. The schemes that we consider are those that can be expressed over an alphabet consisting of XOR and function symbols for hash functions, permutations, or block ciphers. We implement our framework in OCaml and apply it to a number of prominent constructions, which include the Luby-Rackoff (LR), key-alternating Feistel (KAF), and iterated Even-Mansour (EM) ciphers, as well as substitution-permutation networks (SPN). The security models we consider are (S)PRP, and strengthenings thereof under related-key (RK), key-dependent message (KD), and more generally key-correlated (KC) attacks. Using AlgoROM, we are able to reconfirm a number of classical and previously established security theorems, and in one case we identify a gap in a proof from the literature (Connolly et al., ToSC'19). However, most results that we prove with AlgoROM are new. In particular, we obtain new positive results for LR, KAF, EM, and SPN in the above models. Our results better reflect the configurations actually implemented in practice, as they use a single idealized primitive. In contrast to many existing tools, our automated proofs do not operate in symbolic models, but rather in the standard probabilistic model for cryptography
