ProvSec

 

 

 

 

ACCEPTED PAPERS CISC, HKU IE, CUHK

(Papers are sorted in their submission order. Abstracts come from submission version which may have been updated in the proceedings.)

FULL PAPERS

Yinghui Zhang, Dong Zheng, Xiaofeng Chen, Jin Li and Hui Li.
Computationally Efficient Ciphertext-Policy Attribute-Based Encryption with Constant-Size Ciphertexts

Abstract: Ciphertext-policy attribute-based encryption (CP-ABE) is extremely suitable for cloud computing environment in that it enables data owners to make and enforce access policies themselves. However, most of existing CP-ABE schemes suffer severe efficiency drawbacks due to large computation cost and ciphertext size, both of which linearly increase with the complexity of access policies. Aiming at tackling the challenge above, in this paper, we propose a CP-ABE scheme which features constant computation cost and constant-size ciphertexts. It is proven secure in the random oracle model under the decision n-Bilinear Diffie-Hellman Exponent (n-BDHE) assumption, where n represents the total number of attributes in universe. Furthermore, the proposed scheme can efficiently support AND-gate access policies with multiple values and wildcards. Performance comparisons indicate that the proposed CP-ABE scheme is promising in real-world applications, especially for the scenarios where computation and bandwidth issues are major concerns.


Jesper Buus Nielsen and Ivan Damgård.
Adaptive versus Static Security in the UC Model

Abstract: We show that for certain class of unconditionally secure protocols and target functionalities, static security implies adaptive in the UC model. Similar results were previously only known for models with weaker security and/or composition guarantees. The result is, for instance, applicable to a wide range of protocols based on secret sharing. It "explains'' why an often used proof technique for such protocols works, namely where the simulator runs in its head a copy of the honest players using dummy inputs and generates a protocol execution by letting the dummy players interact with the adversary. When a new player $P_i$ is corrupted, the simulator adjusts the state of its dummy copy of $P_i$ to be consistent with the real inputs and outputs of $P_i$ and gives the state to the adversary. Our result gives a characterization of the cases where this idea will work to prove adaptive security. As a special case, we use our framework to give the first proof of adaptive security of the seminal BGW protocol in the UC framework.


Shuichi Katsumata and Noboru Kunihiro.
Constructing Subspace Membership Encryption through Inner Product Encryption

Abstract: Subspace membership encryption is a generalization of inner product encryptions, which was recently formalized by Boneh, Raghunathan, and Segev in Asiacrypt 2013. The construction of this new predicate encryption was motivated by the fact that traditional predicate encryptions did not yield function privacy, a security notion introduced by Boneh et al. in Crypto 2013. This newly defined security notion requires that no information on the predicate associated to a given secret key is revealed, beyond the absolute minimum necessary. Boneh et al. gave a generic construction of the subspace membership encryption based on any inner product encryption. However, our research shows that their construction for subspace membership encryptions when the attribute space is small was incorrect, and that it does not yield the attribute hiding security, which is the baseline notion of security for predicate encryptions.

In this paper, we will first show why the construction does not possess the attribute hiding security, and see that this can not be altered through simple reconstruction. Then, we will formulate a generalized construction of subspace membership encryptions by introducing probability distributions over the attribute and predicate space, and prove that the attribute hiding security can not be satisfied even in the generalized setting. We will consider the requirements for subspace membership encryptions to yield the attribute hiding security, and evaluate them probabilistically.

Finally, we will present an extension of our generalized construction, and show that it holds the attribute hiding security even in small attribute spaces. However, in our extended generalized construction, function privacy was deprived, which was precisely the motivation of formalizing subspace member encryptions in the first place. Although, we did not succeed in constructing a subspace membership encryption which both yields the attribute hiding security and function privacy, we formalized a richer framework of construction of subspace membership encryptions, and discovered a trade-off like relationship between the two security notions, which presents possibility for a construction in-between ours and Boneh et al.'s. Furthermore, our extended generalized construction cut opens new perspectives in the construction of subspace membership encryptions and enables us to make various choices on the underlying inner product encryptions.


Rongxing Lu, Xiaodong Lin and Jun Shao.
RCCA-Secure Multi-use Bidirectional Proxy Re-Encryption with Master Secret Security

Abstract: Bidirectional proxy re-encryption allows ciphertext transformation between Alice and Bob via a semi-trusted proxy, who however cannot obtain the corresponding plaintext. Due to the special property, it becomes a flexible tool in many dynamic environments; such as publish subscribe systems, group communication, and cloud computing. Nonetheless, designing secure and efficient bidirectional proxy re-encryption is still challenging in bidirectional proxy re-encryption. In this paper, we propose a novel bidirectional proxy re-encryption scheme that holds the following nice properties: 1) constant ciphertext size no matter how many times the transformation performed; 2) master secret security in the random oracle model, i.e., Alice (resp. Bob) colluding with the proxy cannot obtain Bob's (resp. Alice's) private key; 3) RCCA security in the random oracle model. To the best of our knowledge, our proposal is the first bidirectional proxy re-encryption scheme holding the three properties simultaneously.


Yanjiang Yang, Haibing Lu, Jian Weng, Youcheng Zhang and Kouichi Sakurai.
Fine-grained Conditional Proxy Re-encryption and Application

Abstract: Conditional proxy re-encryption (CPRE) enables fine-grained delegation of decryption rights, and is useful in many applications. In this paper, we present a ciphertext-policy attribute based CPRE scheme, together with a formalization of the primitive and its security proof. We further propose applying the scheme for encryption of cloud data, to achieve fine-grained cryptographic access control. This application well implements the idea of cloud-enabled user revocation, offering an alternative yet more feasible solution to the user revocation issue in fine-grained encryption of cloud data. Features of the application include little cost in case of user revocation, and high user-side efficiency when users access cloud data.


Somindu C. Ramanna and Palash Sarkar.
Efficient (Anonymous) Compact HIBE From Standard Assumptions

Abstract: We present two hierarchical identity-based encryption (HIBE) schemes, denoted as $\ahibe$ and $\hibe$, from Type-3 pairings with constant sized ciphertexts. Scheme $\ahibe$ achieves anonymity while $\hibe$ is non-anonymous. The constructions are obtained by extending the IBE scheme recently proposed by Jutla and Roy (Asiacrypt 2013). Security is based on the standard decisional Symmetric eXternal Diffie-Hellman (SXDH) assumption. In terms of provable security properties, previous direct constructions of constant-size ciphertext HIBE had one or more of the following drawbacks: security in the weaker model of selective-identity attacks; exponential security degradation in the depth of the HIBE; and use of non-standard assumptions. The security arguments for $\ahibe$ and $\hibe$ avoid all of these drawbacks. These drawbacks can also be avoided by obtaining HIBE schemes by specialising schemes for hierarchical inner product encryption; the downside is that the resulting efficiencies are inferior to those of the schemes reported here. Currently, there is no known anonymous HIBE scheme having the security properties of $\ahibe$ and comparable efficiency. An independent work by Chen and Wee describes a non-anonymous HIBE scheme with security claims and efficiency similar to that of $\hibe$; we note though that in comparison to $\hibe$, the Chen-Wee HIBE scheme has larger ciphertexts and less efficient encryption and decryption algorithms. Based on the current state-of-the-art, $\ahibe$ and $\hibe$ are the schemes of choice for efficient implementation of (anonymous) HIBE constructions.


Shoichi Hirose and Hidenori Kuwakado.
Forward-Secure Sequential Aggregate Message Authentication Revisited: Formalization and a Provably Secure Scheme

Abstract: The notion of forward-secure sequential aggregate message authentication was introduced by Ma and Tsudik in 2007. It is suitable for applications such as audit logging systems and wireless sensor networks. Ma and Tsudik also constructed a scheme with a MAC function and a collision resistant hash function. However, the notion has not been fully formalized and the security of the scheme has not been confirmed. In this paper, forward-secure sequential aggregate message authentication schemes and their security are formalized. Then, a generic construction with a MAC function and a pseudorandom generator is presented. It is also shown that the construction is secure if the underlying primitives are secure.


Guangyao Zhao, Lei Cheng, Chao Li, Ruilin Li and Xuan Shen.
On the practical security bound of GF-NLFSR structure

Abstract: At ACISP 2009, Choy et al. proposed the generalised Feistel nonlinear feedback shift register structure (GF-NLFSR). The main feature of GF-NLFSR containing n sub-blocks is that it canbe parallelized up to n-round for implementation, and meanwhile the provable security bound against differential cryptanalysis (DC) and linear cryptanalysis (LC) can be provided for n+1 rounds. Thus, it maybe suit for the light-weight encryption environment, such as RFID tags, smart cards, and sensor nodes. The practical security bound of GF-NLFSR with SPN round function was further studied by Yap et al. at Africacrypt 2010, where a differential bound for 2nr-round was provided, while for the linear bound, only partial results for n=2,4 were presented. In this paper, we eliminate such discrepancy between the practical differential and linear bound of GF-NLFSR with SPN round function by demonstrating that a unified bound could be proved using the “divide and conquer” strategy. We further find a relationship between the truncated differential characteristics and linear characteristics of GF-NLFSR, which builds a nice link between the lower linear bound and differential bound of such construction, and demonstrates that proving the cipher’s resistence against either DC or LC is enough to show its existance against both DC and LC. We hope that the result in the current paper will be useful when designing ciphers based on GF-NLFSR structure with SPN round function.


Yuyu Wang and Keisuke Tanaka.
Generic Transformation to Strongly Existentially Unforgeable Signature Schemes with Leakage Resiliency

Abstract: This paper presents an efficient transformation method that converts fully leakage resilient signature schemes which are weakly existentially unforgeable into ones which are strongly existentially unforgeable. To achieve our goal, we give a definition of leakage resilient chameleon hash functions and present a construction based on the leakage resilient hard relation. Then we combine leakage resilient chameleon hash functions with the technique presented by Steinfeld, Pieprzyk, and Wang to obtain a generic transformation that works well in the bounded leakage model.


Tapas Pandit, Sumit Pandey and Rana Barua.
Attribute-Based Signcryption : Signer Privacy, Strong Unforgeability and IND-CCA2 Security in Adaptive-Predicates Attack

Abstract: The signcryption primitive was introduced by Zheng in 1997 for providing an efficient way of achieving message confidentiality and authentication simultaneously. “Commit then Encrypt and Sign” (CtE&S) paradigm has the advantage over the other two paradigms, “Encrypt then Sign” (EtS) and “Sign then Encrypt” (StE), as in the Signcrypt (resp. Unsigncrypt) algorithm both Encrypt and Sign (resp. Decrypt and Ver) can be executed in parallel. But in the generic conversion of An et al. in 2002, the CtE&S paradigm lacks the strong unforgeability and IND-CCA2 security even when the primitive signature scheme and encryption scheme have these properties. In “Combined Public-Key scheme”, the system has the same public parameters and key distribution for encryption and signature schemes, but the Encrypt and Decrypt (resp. Sign and Ver) of the encryption (resp. signature) scheme were kept unchanged in the combined scheme. An Attribute-Based Signcryption (ABSC) is a natural extension of Attribute-Based Encryption (ABE) and Attribute-Based Signature (ABS), where we have the message confidentiality and authenticity together. Since signer privacy is captured in security of ABS, it is quite natural to expect that signer privacy will be preserved in ABSC as well. In this paper, we first propose an ABSC scheme which is weak existential unforgeable, IND-CCA2 secure in adaptive-predicates attack and achieves signer privacy. Then, by using strong one-time signature, we extend this scheme to our second ABSC scheme to attain strong existential unforgeability in adaptive-predicates attack. Our systems support the combined public-key environment, viz, the common public parameters and key. Our first construction is almost in the flavor of CtE&S paradigm, except one extra component will be computed using both signature components and ciphertext components. The second proposed construction follows a new paradigm (extension of CtE&S), we name it “Commit then Encrypt and Sign then Sign” (CtE&StS). The last signature is done using a strong one-time signature scheme. Since the non-repudiation (publicly verifiability) is achieved in CtE&S paradigm, therefore our systems also achieve non-repudiation.


Peeter Laud and Alisa Pankova.
Verifiable Computation in Multiparty Protocols with Honest Majority

Abstract: We present a generic method for turning passively secure protocols into protocols secure against covert attacks. The method adds a post-execution verification phase to the protocol that allows a misbehaving party to escape detection only with negligible probability. The execution phase, after which the computed protocol result is already available for parties, has only negligible overhead added by our method. The checks, based on linear probabilistically checkable proofs, are done in zero-knowledge, thereby preserving the privacy guarantees of the original protocol. Our method is inspired by recent results in verifiable computation, adapting them to multiparty setting and significantly lowering their computational costs for the provers.


Reza Reyhanitabar, Serge Vaudenay and Damian Vizár.
Misuse-Resistant Variants of the OMD Authenticated Encryption Mode

Abstract: We present two variants of OMD which are robust against nonce misuse. Security of OMD---a CAESAR candidate---relies on the assumption that implementations always ensure correct use of nonce (a.k.a. message number); namely that, the nonce never gets repeated. However, in some application environments, this non-repetitiveness requirement on nonce might be compromised or ignored, yielding to full collapse of the security guaranty in such nonce-misusing implementations. We aim to reach maximal possible level of robustness against repeated nonces, as defined by Rogaway and Shrimpton (FSE 2006) under the name misuse-resistant AE (MRAE). Our first scheme, called misuse-resistant OMD (MR-OMD), is designed to be substantially similar to OMD while achieving stronger security goals; hence, being able to reuse any existing common code/hardware. Our second scheme, called parallelizable misuse-resistant OMD (PMR-OMD), further deviates from the original OMD design in its encryption process, providing a parallelizable algorithm in contrast with OMD and MR-OMD which have serial encryption/decryption processes. Both MR-OMD and PMR-OMD are single-key mode of operation. It is known that maximally robust MRAE schemes are necessarily two-pass, a price paid compared to a one-pass scheme such as OMD. Nevertheless, in MR-OMD and PMR-OMD, we combine the two passes in a way that minimizes the additional cost: the overhead incurred by the second pass in our two-pass variants is about 50% of the encryption time for OMD.


Xue Haiyang, Lu Xianhui, Li Bao and Liu Yamin.
Lossy Relation and Its Application to Lossy Encryption and Adaptive Trapdoor Relation

Abstract: Peikert and Waters proposed the notion of lossy trapdoor function in STOC 2008. In this paper, we propose a relaxation of lossy trapdoor function, called lossy relation. Unlike the lossy trapdoor function, lossy relation does not require completely recovering the input but a public computable injective map of it. Interestingly, the lossy relation maintains the application of lossy trapdoor function on the lossy encryption. Moreover, motivated by the construction of adaptive trapdoor relation proposed by Wee (Crypto 2010), we introduce all-but-one verifiable lossy relation which is in fact a relaxation of all-but-one lossy trapdoor function.

  • The lossy relation can be constructed from discrete logarithm related assumptions and subgroup membership assumptions efficiently. We also give an efficient construction of all-but-one verifiable lossy relation from DLDH assumption over pairing group. As a byproduct, we propose the first all-but-one lossy trapdoor function based on DLDH assumption which partially solve the open problem of Freeman \emph{et al.} (PKC 2010).
  • The lossy relation has a direct application to the lossy encryption and we propose new lossy encryptions based on three subgroup membership assumptions. The all-but-one verifiable lossy relation can be used to construct adaptive trapdoor relation, which derives chosen ciphertext secure encryption.

Mehdi Tibouchi.
Impossibility of Surjective Icart-Like Encodings

Abstract: Many cryptographic protocols based on elliptic curves rely on the possibility of representing integer values or bit strings as elliptic curve points, or vice versa, in an invertible way. The most practical approach proposed to achieve this for an elliptic curve E/F_q has been the use of (piecewise) algebraic maps f: F_q → E(F_q) called (deterministic, constant-time) ``encoding functions'', for which numerous constructions have been proposed in recent years, starting with the very simple encoding of Boneh and Franklin, which maps a value u\in F_q to ((u^2-b)^{1/3}, u) on the elliptic curve y^2 = x^3 + b over F_q.

The Boneh-Franklin encoding (CRYPTO 2001) is almost a bijection between F_q and E(F_q) (except for the point at infinity), which makes it very convenient for security proofs, as well as for applications like covertness. Unfortunately, however, it is only well-defined for a very limited class of elliptic curves, all of them supersingular, and hence with poor performance characteristics.

Since then, many other encoding functions have been proposed, and constructions are known for all elliptic curves. As observed by Farashahi et al. (Math. Comp. 2013), they fit in two broad families: Icart-like encodings, which are generalizations of the original Boneh-Franklin encoding starting with a construction due to Icart (CRYTPO 2009), and SWU-like encodings, based on works by Schinzel, Skałba, Shallue and van de Woestijne. So far, however, almost none of these numerous encodings has replicated the very useful bijectivity property of the Boneh-Franklin encoding.

In this paper, we focus on Icart-like encodings, and investigate the possibility of constructing such encodings f: F_q → E(F_q) that are almost bijective like Boneh and Franklin's, or achieve a weaker property like ``almost surjectivity'' (in the sense that #f(F_q) = q - o(q). And we show that the lack of such constructions is no wonder: almost surjective Icart-like encoding cannot exist to non-supersingular elliptic curves.


Shoichi Hirose and Hidenori Kuwakado.
A Block-Cipher-Based Hash Function Using an MMO-Type Double-Block Compression Function

Abstract: Methods to construct a hash function using an existing block cipher recently attract some interests as an approach to implement a hash function on constrained devices. It is often required to construct a hash function whose output length is larger than that of the underlying block cipher to provide sufficient level of collision resistance with the use of an existing block cipher. This article presents a new mode of double-block compression function, which is based on the mode proposed by Jonsson and Robshaw at PKC 2005. The mode can be instantiated with a block cipher whose key-length is larger than its block-length such as AES-192/256, PRESENT-128, etc. This article also provides provable security analyses to an iterated hash function using the proposed mode and the MDP domain extension. The security properties discussed are collision resistance, preimage resistance, pseudorandom-function property of the keyed-via-IV mode, and the indifferentiability from a random oracle. It is shown, for instance, that the query complexity to differentiate the iterated hash function from a random oracle is optimal up to a constant factor in the ideal cipher model.


Jiageng Chen, Atsuko Miyaji and Chunhua Su.
A Provable Secure Batch Authentication Scheme for EPCGen2 Tags

Abstract: EPC Class1 Gen2 (EPCGen2)is an international industrial standards for low cost RFID system used in many applications such as supply chain. While RFID technology offers convenience and being employed in various applications in our society, security and privacy issues are still the number one concern of-most RFID applications today. In this paper, we study the problems occurring where a reader wants to authenticate and identify legitimate RFID EPCGen2 tags in a batch to guarantee the integrity of the products. Most of the EPCGen2 tags are passive and have limited computational ability to compute cryptographic functions. For this reason, to design a mechanism to protect the tags from the security and privacy risks for EPCGen2 is a challenging task. We propose a provable secure batch authentication scheme for EPCGen2 Tags using the pseudo-random number generator (PRNG) and cyclic redundancy check (CRC) code. Our ultra-lightweight scheme which integrates the operation of EPCGen2 build-in CRC-16 and PRNG function with secret key inside the tags. We formally analyze the security and privacy functionality of the proposed scheme by using mathematical modelling. Our analysis shows that our scheme provides strong ability to prevent existing possible attacks.


Kazuki Yoneyama and Goichiro Hanaoka.
Compact Public Key Encryption with Minimum Ideal Property of Hash Functions

Abstract: Achieving shorter ciphertext length under weaker assumptions in chosen-ciphertext (CCA) secure public-key encryption (PKE) is one of the most important research topics in cryptography. However, it is also known that it is hard to construct a CCA-secure PKE whose ciphertext overhead is less than two group elements in the underlying prime-order group under non-interactive assumption. A naive approach for achieving more compactness than the above bound is to use random oracles (ROs), but the full RO has various ideal properties like programmability. In this paper, we pursue how to achieve compact PKE only with a minimum ideal property of ROs. Specifically, only with observability, we can give three novel CCA-secure PKE schemes whose ciphertext overhead is less than two group elements. Our schemes are provably secure under standard assumptions such as the CDH and DDH assumptions. This study shows that ideal properties other than observability are not necessary to construct compact PKE beyond the bound.


Ahto Buldas, Risto Laanoja, Ahto Truu and Peeter Laud.
Bounded Pre-Image Awareness and the Security of Hash-Tree Keyless Signatures

Abstract: We present a new tighter security proof for unbounded hash tree keyless signature (time-stamping) schemes that use Merkle-Damg\aa rd (MD) hash functions with Preimage Aware (PrA) compression functions. It is known that the PrA assumption alone is insufficient for proving the security of unbounded hash tree schemes against back-dating attacks. We show that many known PrA constructions satisfy a stronger \emph{Bounded Pre-Image Awareness (BPrA)} condition that assumes the existence of an extractor $\EXT$ that is bounded in the sense that for any efficiently computable query string $\alpha$, the number of outputs $y$ for which $\EXT(y,\alpha)$ succeeds does not exceed the number of queries in $\alpha$. We show that blockcipher based MD-hash functions with rank-1 compression functions (such as Davies-Meyer and Miaguchi-Preneel) of both type I and type II are BPrA. We also show that the compression function of Shrimpton-Stam that uses non-compressing components is BPrA. The security proof for unbounded hash-tree schemes is very tight under the BPrA assumption. In order to have $2^s$-security against back-dating, the hash function must have $n=2s + 4$ output bits, assuming that the security of the hash function is close to the birthday barrier, i.e. that there are no structural weaknesses in the hash function itself. Note that the previous proofs that assume PrA gave the estimation $n=2s + 2 \log_2 C + 2$, where $C$ is the maximum allowed size of the hash tree. For example, if $s=100$ ($2^{100}$-security) and $C = 260$, the previous proofs require $n = 322$ output bits, while the new proof requires $n = 204$ output bits.

SHORT PAPERS

Koji Nuida.
How to Use Pseudorandom Generators in Unconditional Security Settings

Abstract: Cryptographic pseudorandom generators (PRGs) can universally reduce the randomness complexity of computationally secure schemes. To extend it to unconditional security, Nuida and Hanaoka (IEEE Trans. IT 2013) developed a security proof technique under the use of cryptographic PRGs against computationally unbounded adversaries. However, their proof is not yet unconditional since it assumed unproven hardness of the underlying problem for the cryptographic PRG; i.e., the proof becomes ineffective if an efficient algorithm for the problem is found. In the paper, we extend the previous result to "non-cryptographic" PRGs, especially the one proposed by Impagliazzo, Nisan and Wigderson (STOC 1994). Since their PRG uses expander graphs (rather than one-way functions for cryptographic PRGs) to stretch and scramble the random seeds information-theoretically against a special class of distinguishers, our result does not require the unproven hardness assumptions any longer and provides unconditional security proof under the use of PRGs, which was not achieved by the previous work. Although the use of "non-cryptographic" PRGs might narrow the class of schemes to which our proof is applicable, the class still involves some existing information-theoretically secure schemes such as fingerprint codes. Moreover, we propose a "dual-mode" modification of the PRG above to provide the following hybrid security; besides the unconditional security for schemes in the class above, we can still prove computational security even if the scheme is outside the class.


Hui Cui, Yi Mu and Man Ho Au.
Complete Robustness in Identity-Based Encryption

Abstract: Complete robustness (CROB) was proposed to guarantee that for a public key encryption scheme, decryption attempts will fail with high probability if the wrong decryption key is used to decrypt a ciphertext, even if the keys are maliciously generated by the adversary. In this paper, we extend the notion of complete robustness to the identity-based setting. We firstly formalize the CROB for identity-based encryption, and present a generic construction achieving CROB from an arbitrary identity-based encryption scheme. After that, motivated by the fact that complete robustness implies security against related-key attack (RKA) in public key encryption, we investigate whether such implication is still true for the case of identity-based encryption. We conclude that these two notions (CROB and RKA security) are separable for identity-based encryption. However, we note that with a slight modification to our generic construction, an identity-based encryption scheme offering complete robustness with security against related-key attacks can be constructed from any identity-based encryption scheme.



Mridul Nandi and Nilanjan Datta.
Equivalence between MAC and PRF for Blockcipher based Constructions

Abstract: In FSE 2010, Nandi proved a sufficient condition of pseudo random function (PRF) for affine domain extensions (ADE), wide class of block cipher based domain extensions. This sufficient condition is satisfied by all known blockcipher based ADE constructions, however, it is not a characterization of PRF. In this paper we completely characterize the ADE and show that {\em message authentication code (MAC) and weakly collision resistant (WCR) are indeed equivalent to PRF}. Note that a PRF is trivially a MAC and WCR, however, the converse need not be true in general. So our result suggests that it would be sufficient to ensure resisting against weakly collision attack or the forging attack to construct a pseudo random function ADE. Unlike FSE 2010 paper, here we consider the {\em forced collisions of inputs of underlying blockciphers by incorporating the final outputs of a domain extension queried by an adaptive adversary}. This is the main reason why we are able to obtain a characterization of PRF. Our approach is a more general and hence might have other theoretical interest.


Kazuki Yoneyama.
Computational Soundness of Asymmetric Bilinear Pairing-based Protocols

Abstract: Asymmetric bilinear maps using Type-3 pairings are known to be advantageous in several points (e.g., the speed and the size of a group element) to symmetric bilinear maps using Type-1 pairings. Kremer and Mazar\'{e} introduce a symbolic model to analyze protocols based on bilinear maps, and show that the symbolic model is computationally sound. However, their model only covers symmetric bilinear maps. In this paper, we propose a new symbolic model to capture asymmetric bilinear maps. Our model allows analyzing many protocols based on asymmetric bilinear maps (e.g., Joux's tripartite key exchange, and Scott's client-server ID-based key exchange). Also, we show computational soundness of our symbolic model under the decisional bilinear Diffie-Hellman assumption.


Takashi Yamakawa, Nobuaki Kitajima, Takashi Nishide, Goichiro Hanaoka and Eiji Okamoto.
A Short Fail-Stop Signature Scheme from Factoring

Abstract: Fail-stop signature (FSS) is information theoretically secure digital signature in the sense that even if a signature is forged, the signer can prove the forgery with overwhelming probability. There are many known constructions of FSS schemes based on various assumptions. Among them, factoring-based schemes are important due to their high reliability. However, known factoring-based FSS schemes generally suffer from their large signature sizes, which are larger than $|N|$, where $|N|$ is the length of an underlying composite number. In this paper, we propose a new factoring-based FSS scheme. For this purpose, we propose a variant of the generic construction of FSS schemes based on a bundling homomorphism. Specifically, we introduce a notion of a {\it collision resistant group generator}, which can be seen as a variant of a bundling homomorphism, and propose a generic construction of FSS schemes based on it. Then we propose a construction of a collision resistant group generator based on the factoring assumption. This yields the first factoring-based FSS scheme whose signature size is smaller than $|N|$.


Yohei Watanabe and Junji Shikata.
Timed-Release Computational Secret Sharing Scheme and Its Applications

Abstract: In modern cryptography, a secret sharing scheme is an important cryptographic primitive. In particular, Krawczyk proposed a computational secret sharing (CSS) scheme, which is a practical, simple secret sharing scheme. In this paper, we focus on a CSS scheme with timed-release functionality, which we call a timed-release computational secret sharing (TR-CSS) scheme. In TR-CSS, participants more than or equal to a threshold number can reconstruct a secret by using their shares only when the time specified by a dealer has come. Our main purpose is to realize a TR-CSS scheme in a generic and efficient way in terms of the share size. Specifically, we first introduce a model and formalization of security of TR-CSS. In addition, we propose two kinds of constructions of TR-CSS: the first one is a simple and generic construction starting from identity-based encryption (IBE); the second one is a more efficient construction, by using Waters' IBE as an building block of IBE, than the first one. As a result, we can regard TR-CSS as a natural extension of Krawczyk's CSS in terms of both a model and constructions, and we finally succeed to add timed-release functionality to Krawczyk's CSS with small overhead, which seems to be almost optimal. Moreover, Our proposal of TR-CSS is important for constructing threshold encryption and multiple encryption with timed-release functionality in a generic and efficient way. Dodis and Katz showed (i) a simple and generic construction of threshold encryption from multiple encryption; and (ii) a simple, elegant and generic construction of multiple encryption. By using TR-CSS, we can effectively apply the Dodis--Katz paradigm even in the context of timed-release security.

Lukasz Krzywiecki.
Deniable Version of SIGMA Key Exchange Protocol Resilient to Ephemeral Key Leakage

Abstract: We propose modifications of SIGMA key exchange protocol that provide the deniability property, and strengthen the security of the resulting session keys. Contrary to the intuition that transcripts of protocols based on the ’SIGn-and-MAc’ paradigm, that includes signed messages, are undeniable proofs of interaction, our proposition, based on ring signatures, provide the possibility that a single party alone can produce a simulated transcripts of protocol run without the peer participation. Moreover we propose straightening of the SIGMA resulting session keys by additional using of long-term keys in the Diffie-Hellman key exchange phase of the protocol. Our proposition preserves the modular construction of the protocol, does not change the number of the protocol rounds, and can be done optionally by the communicating parties – provides compatibility with original construction.