International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Colin Boyd

Affiliation: NTNU, Norway

Publications

Year
Venue
Title
2015
EPRINT
2015
EPRINT
2014
EPRINT
2014
EPRINT
2010
EPRINT
Delaying Mismatched Field Multiplications in Pairing Computations
Miller's algorithm for computing pairings involves performing multiplications between elements that belong to different finite fields. Namely, elements in the full extension field $\mathbb{F}_{p^k}$ are multiplied by elements contained in proper subfields $\mathbb{F}_{p^{k/d}}$, and by elements in the base field $\mathbb{F}_{p}$. We show that significant speedups in pairing computations can be achieved by delaying these ``mismatched'' multiplications for an optimal number of iterations. Importantly, we show that our technique can be easily integrated into traditional pairing algorithms; implementers can exploit the computational savings herein by applying only minor changes to existing pairing code.
2010
EPRINT
One Round Group Key Exchange with Forward Security in the Standard Model
Constructing a one round group key exchange (GKE) protocol that provides forward secrecy is an open problem in the literature. In this paper, we investigate whether or not the security of one round GKE protocols can be enhanced with any form of forward secrecy without increasing the number of rounds. We apply the {\em key evolving} approach used for forward secure encryption/signature schemes and then model the notion of forward security for the first time for key exchange protocols. This notion is slightly weaker than forward secrecy, considered traditionally for key exchange protocols. We then revise an existing one round GKE protocol to propose a GKE protocol with forward security. In the security proof of the revised protocol we completely avoid reliance on the random oracle assumption that was needed for the proof of the base protocol. Our security proof can be directly applied to the base protocol, making it the most efficient one round GKE protocol secure in the standard model. Our one round GKE protocol is generically constructed from the primitive of forward secure encryption. We also propose a concrete forward secure encryption scheme with constant size ciphertext that can be used to efficiently instantiate our protocol.
2010
EPRINT
Attribute-based Authenticated Key Exchange
We introduce the concept of attribute-based authenticated key exchange (AB-AKE) within the framework of ciphertext policy attribute-based systems. A notion of AKE-security for AB-AKE is presented based on the security models for group key exchange protocols and also taking into account the security requirements generally considered in the ciphertext policy attribute-based setting. We also extend the paradigm of hybrid encryption to the ciphertext policy attribute-based encryption schemes. A new primitive called encapsulation policy attribute-based key encapsulation mechanism (EP-AB-KEM) is introduced and a notion of chosen ciphertext security is defined for EP-AB-KEMs. We propose an EP-AB-KEM from an existing attribute-based encryption scheme and show that it achieves chosen ciphertext security in the generic group and random oracle models. We present a generic one-round AB-AKE protocol that satisfies our AKE-security notion. The protocol is generically constructed from any EP-AB-KEM that satisfies chosen ciphertext security. Instantiating the generic AB-AKE protocol with our EP-AB-KEM will result in a concrete one-round AB-AKE protocol also secure in the generic group and random oracle models.
2010
EPRINT
Avoiding Full Extension Field Arithmetic in Pairing Computations
The most costly operations encountered in pairing computations are those that take place in the full extension field $\mathbb{F}_{p^k}$. At high levels of security, the complexity of operations in $\mathbb{F}_{p^k}$ dominates the complexity of the operations that occur in the lower degree subfields. Consequently, full extension field operations have the greatest effect on the runtime of Miller's algorithm. Many recent optimizations in the literature have focussed on improving the overall operation count by presenting new explicit formulas that reduce the number of subfield operations encountered throughout an iteration of Miller's algorithm. Unfortunately, almost all of these operations far outweigh the operations in the smaller subfields. In this paper, we propose a new way of carrying out Miller's algorithm that involves new explicit formulas which reduce the number of full extension field operations that occur in an iteration of the Miller loop, resulting in significant speed ups in most practical situations of between 5 and 30 percent.
2009
PKC
2008
EPRINT
Efficient One-round Key Exchange in the Standard Model
We consider one-round identity-based key exchange protocols secure in the standard model. The security analysis uses the powerful security model of Canetti and Krawczyk and a natural extension of it to the ID-based setting. It is shown how KEMs can be used in a generic way to obtain two different protocol designs with progressively stronger security guarantees. A detailed analysis of the performance of the protocols is included; surprisingly, when instantiated with specific KEM constructions, the resulting protocols are competitive with the best previous schemes that have proofs only in the random oracle model.
2006
PKC
2005
ASIACRYPT
2005
ASIACRYPT
2005
CRYPTO
2005
EPRINT
Examining Indistinguishability-Based Proof Models for Key Establishment Protocols
We examine various indistinguishability-based proof models for key establishment protocols, namely the Bellare & Rogaway (1993, 1995), the Bellare, Pointcheval, & Rogaway (2000), and the Canetti & Krawczyk (2001) proof models. We then consider several variants of these proof models, identify several subtle differences between these variants and models, and compare the relative strengths of the notions of security between the models. For each of the pair of relations between the models (either an implication or a non-implication), we provide proofs or counter-examples to support the observed relations. We also reveal a drawback with the original formulation of the Bellare, Pointcheval, & Rogaway (2000) model, whereby the Corrupt query is not allowed. As a case study, we use the Abdalla & Pointcheval (2005) three-party password-based key exchange protocol (3PAKE), which carries a proof of security in the Bellare, Pointcheval, & Rogaway (2000) model. We reveal a previously unpublished flaw in the protocol, and demonstrate that this attack would not be captured in the model due to the omission of the Corrupt query.
2005
EPRINT
Batch Verification of Validity of Bids in Homomorphic E-auction
Kun Peng Colin Boyd Ed Dawson
Bid opening in e-auction is efficient when a homomorphic secret sharing function is employed to seal the bids and homomorphic secret reconstruction is employed to open the bids. However, this high efficiency is based on an assumption: the bids are valid (e.g. within a special range). An undetected invalid bid can compromise correctness and fairness of the auction. Unfortunately, validity verification of the bids is ignored in the auction schemes employing homomorphic secret sharing (called homomorphic auction in this paper). In this paper, an attack against the homomorphic auction in the absence of bid validity check is presented and a necessary bid validity check mechanism is proposed. Then a batch cryptographic technique is introduced and applied to improve the efficiency of bid validity check.
2005
EPRINT
Errors in Computational Complexity Proofs for Protocols
Proofs are invaluable tools in assuring protocol implementers about the security properties of protocols. However, several instances of undetected flaws in the proofs of protocols (resulting in flawed protocols) undermine the credibility of provably-secure protocols. In this work, we examine several protocols with claimed proofs of security by Boyd & Gonzalez Nieto (2003), Jakobsson & Pointcheval (2001), and Wong & Chan (2001), and an authenticator by Bellare, Canetti, & Krawczyk (1998). Using these protocols as case studies, we reveal previously unpublished flaws in these protocols and their proofs. We hope our analysis will enable similar mistakes to be avoided in the future.
2004
PKC
2003
PKC
2002
PKC
2000
ASIACRYPT
2000
PKC
2000
PKC
1998
ASIACRYPT
1994
ASIACRYPT
1993
EUROCRYPT
1991
EUROCRYPT
1989
EUROCRYPT
1988
EUROCRYPT

Program Committees

Asiacrypt 2019
Crypto 2015
PKC 2014
Asiacrypt 2013
Crypto 2012
PKC 2012
PKC 2011
Eurocrypt 2009
Asiacrypt 2008
Eurocrypt 2006
Asiacrypt 2005
PKC 2004
Asiacrypt 2004
Asiacrypt 2003
Asiacrypt 2001 (Program chair)
Asiacrypt 1999
Asiacrypt 1998
Eurocrypt 1991