Chu et al. (ASIACCS 2012) proposed group signature with time-bound keys (GS-TBK) where each signing key is associated to an expiry time $\tau$. In addition to prove the membership of the group, a signer needs to prove that the expiry time has not passed, i.e., $t<\tau$ where $t$ is the current time. A signer whose expiry time has passed is automatically revoked, and this revocation is called natural revocation. Simultaneously, signers can be revoked before their expiry times have passed due to the compromise of the credential. This revocation is called premature revocation. A nice property of the Chu et al. proposal is that the size of revocation lists can be reduced compared to those of Verifier-Local Revocation (VLR) group signature schemes, by assuming that natural revocation accounts for most of signer revocations in practice, and prematurely revoked signers are only a small fraction. In this paper, we point out that the definition of traceability of Chu et al. did not capture unforgeability of expiry time of signing keys which guarantees that no adversary who has a signing key associated to an expiry time $\tau$ can compute a valid signature after $\tau$ has passed. We introduce a security model that captures unforgeability, and propose a GS-TBK scheme secure in the new model. Our scheme also provides the constant signing costs whereas those of the previous schemes depend on the bit-length of the time representation. Finally, we give implementation results, and show that our scheme is feasible in practical settings.

The COPA authenticated encryption mode was proved to have a birthday-bound security on integrity, and its instantiation AES-COPA (v1/2) was claimed or conjectured to have a full security on tag guessing. The Marble (v1.0/1.1/1.2) authenticated encryption algorithm was claimed to have a full security on authenticity. Both AES-COPA (v1) and Marble (v1.0) were submitted to the Competition for Authenticated Encryption: Security, Applicability, and Robustness (CAESAR) in 2014, and Marble was revised twice (v1.1/1.2) in the first round of CAESAR, and AES-COPA (v1) was tweaked (v2) for the second round of CAESAR. In this paper, we cryptanalyse the basic cases of COPA, AES-COPA and Marble, that process messages of a multiple of the block size long; we present collision-based almost universal forgery attacks on the basic cases of COPA, AES-COPA (v1/2) and Marble (v1.0/1.1/1.2), and show that the basic cases of COPA and AES-COPA have roughly at most a birthday-bound security on tag guessing and the basic case of Marble has roughly at most a birthday-bound security on authenticity. The attacks on COPA and AES-COPA do not violate their birthday-bound security proof on integrity, but the attack on AES-COPA violates its full security claim or conjecture on tag guessing. Therefore, the full security claim or conjecture on tag guessing of AES-COPA and the full security claim on authenticity of Marble are incorrectly far overestimated in the sense of a general understanding of full security of these security notions. Designers should pay attention to these attacks when designing authenticated encryption algorithms with similar structures in the future, and should be careful when claiming the security of an advanced form of a security notion without making a corresponding proof after proving the security of the security notion only under its most fundamental form.

Distance-bounding protocols have been introduced to thwart relay attacks against contactless authentication protocols. In this context, verifiers have to authenticate the credentials of untrusted provers. Unfortunately, these protocols are themselves subject to complex threats such as terrorist-fraud attacks, in which a malicious prover helps an accomplice to authenticate. Provably guaranteeing the resistance of distance-bounding protocols to these attacks is complex. The classical solutions assume that rational provers want to protect their long-term authentication credentials, even with respect to their accomplices. Thus, terrorist-fraud resistant protocols generally rely on artificial extraction mechanisms, ensuring that an accomplice can retrieve the credential of his partnering prover, if he is able to authenticate. We propose a novel approach to obtain provable terrorist-fraud resistant protocols that does not rely on an accomplice being able to extract any long-term key. Instead, we simply assume that he can replay the information received from the prover. Thus, rational provers should refuse to cooperate with third parties if they can impersonate them freely afterwards. We introduce a generic construction for provably secure distance-bounding protocols, and give three instances of this construction: (1) an efficient symmetric-key protocol, (2) a public-key protocol protecting the identities of provers against external eavesdroppers, and finally (3) a fully anonymous protocol protecting the identities of provers even against malicious verifiers that try to profile them.

Cryptanalytic time-memory trade-offs are techniques introduced by Hellman in 1980 to speed up exhaustive searches. Oechslin improved the original version with the introduction of rainbow tables in 2003. It is worth noting that this variant is nowadays used world-wide by security experts, notably to break passwords, and a key assumption is that rainbow tables are of equal width. We demonstrate in this paper that rainbow tables are underexploited due to this assumption never being challenged. We stress that the optimal width of each rainbow table should be individually — although not independently — calculated. So it goes for the memory allocated to each table. We also stress that visiting sequentially the rainbow tables is no longer optimal when considering tables with heterogeneous widths. We provide an algorithm to calculate the optimal configuration and a decision function to visit the tables. Our technique performs very well: it makes any TMTO based on rainbow tables 40% faster than its classical version.

We introduce an ecient Key-Policy Attribute-Based Encryption (KP-ABE) scheme in prime order groups. Our scheme is semi-adaptively secure under the decisional linear assumption and supports a large universe of attributes and multi-use of attributes. Those properties are critical for real applications of KP-ABE schemes since they enable an ecient and exible access control. Prior to our work, existing KP-ABE schemes with short ciphertexts were in composite order groups or utilized either Dual Pairing Vector Spaces (DPVS) or Dual System Groups (DSG) in prime order groups. However, those techniques brought an eciency loss. In this work, we utilize a nested dual system encryp- tion which is a variant of Waters’ dual system encryption (Crypto’ 09) to achieve semi-adaptively secure KP-ABE. As a result, we obtain a new scheme having better eciency compared to existing schemes while it keeps a semi-adaptive security under the standard assumption. We implement our scheme and compare its eciency with the previous best work.