Sponsor
Publisher

ACCEPTED PAPERS 

(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 CiphertextPolicy AttributeBased Encryption with ConstantSize Ciphertexts
Abstract: Ciphertextpolicy attributebased encryption (CPABE) is extremely suitable for cloud computing environment in that it enables data owners to make and enforce access policies themselves. However, most of existing CPABE 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 CPABE scheme which features constant computation cost and constantsize ciphertexts. It is proven secure in the random oracle model under the decision nBilinear DiffieHellman Exponent (nBDHE) assumption, where n represents the total number of attributes in universe. Furthermore, the proposed scheme can efficiently support ANDgate access policies with multiple values and wildcards. Performance comparisons indicate that the proposed CPABE scheme is promising in realworld 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 tradeoff like relationship between the
two security notions, which presents possibility for a construction
inbetween 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. RCCASecure Multiuse Bidirectional Proxy ReEncryption with Master Secret Security
Abstract: Bidirectional proxy reencryption allows ciphertext transformation between Alice and Bob via a semitrusted 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 reencryption is still challenging in bidirectional proxy reencryption. In this paper, we propose a novel bidirectional proxy reencryption 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 reencryption scheme holding the three properties simultaneously.
Yanjiang Yang, Haibing Lu, Jian Weng, Youcheng Zhang and Kouichi Sakurai. Finegrained Conditional Proxy Reencryption and Application
Abstract: Conditional proxy reencryption (CPRE) enables finegrained delegation of decryption rights, and is useful in many applications. In this paper, we present a ciphertextpolicy 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 finegrained cryptographic access control. This
application well implements the idea of cloudenabled user revocation, offering an alternative yet more feasible solution to the user revocation issue in finegrained encryption of cloud data. Features of the application include little cost in case of user revocation, and high userside efficiency when users access cloud data.
Somindu C. Ramanna and Palash Sarkar. Efficient (Anonymous) Compact HIBE From Standard Assumptions
Abstract: We present two hierarchical identitybased encryption (HIBE) schemes, denoted as $\ahibe$ and $\hibe$,
from Type3 pairings with constant sized ciphertexts. Scheme $\ahibe$ achieves anonymity while $\hibe$ is nonanonymous.
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 DiffieHellman (SXDH) assumption. In terms of provable
security properties, previous direct
constructions of constantsize ciphertext HIBE had one or more of the following drawbacks: security in the weaker model of
selectiveidentity attacks; exponential security degradation in the depth of the HIBE; and use of nonstandard 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 nonanonymous HIBE scheme with security claims and efficiency similar to that of
$\hibe$; we note though that in comparison to $\hibe$, the ChenWee HIBE scheme has larger ciphertexts and less efficient
encryption and decryption algorithms. Based on the current stateoftheart, $\ahibe$ and $\hibe$ are the schemes of choice
for efficient implementation of (anonymous) HIBE constructions.
Shoichi Hirose and Hidenori Kuwakado. ForwardSecure Sequential Aggregate Message Authentication Revisited: Formalization and a Provably Secure Scheme
Abstract: The notion of forwardsecure 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, forwardsecure 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 GFNLFSR structure
Abstract: At ACISP 2009, Choy et al. proposed the generalised Feistel nonlinear feedback shift register structure (GFNLFSR). The main feature of GFNLFSR containing n subblocks is that it canbe parallelized up to nround 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 lightweight encryption environment, such as RFID tags, smart cards, and sensor nodes. The practical security bound of GFNLFSR with SPN round function was further studied by Yap et al. at Africacrypt 2010, where a differential bound for 2nrround 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 GFNLFSR 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 GFNLFSR, 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 GFNLFSR 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. AttributeBased Signcryption : Signer Privacy, Strong Unforgeability and INDCCA2 Security in AdaptivePredicates 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 INDCCA2 security even when the primitive signature scheme and encryption scheme have these properties. In “Combined PublicKey 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 AttributeBased Signcryption (ABSC) is a natural extension of AttributeBased Encryption (ABE) and AttributeBased 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, INDCCA2 secure in adaptivepredicates attack and achieves signer privacy. Then, by using strong onetime signature, we extend this scheme to our second ABSC scheme to attain strong existential unforgeability in adaptivepredicates attack. Our systems support the combined publickey 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 onetime signature scheme. Since the nonrepudiation (publicly verifiability) is achieved in CtE&S paradigm, therefore our systems also achieve nonrepudiation.
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 postexecution 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 zeroknowledge, 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. MisuseResistant Variants of the OMD Authenticated Encryption Mode
Abstract: We present two variants of OMD which are robust against nonce misuse. Security of OMDa CAESAR candidaterelies 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 nonrepetitiveness requirement on nonce might be compromised or ignored, yielding to full collapse of the security guaranty in such noncemisusing implementations. We aim to reach maximal possible level of robustness against repeated nonces, as defined by Rogaway and Shrimpton (FSE 2006) under the name misuseresistant AE (MRAE). Our first scheme, called misuseresistant OMD (MROMD), 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 misuseresistant OMD (PMROMD), further deviates from the original OMD design in its encryption process, providing a parallelizable algorithm in contrast with OMD and MROMD which have serial encryption/decryption processes. Both MROMD and PMROMD are singlekey mode of operation. It is known that maximally robust MRAE schemes are necessarily twopass, a price paid compared to a onepass scheme such as OMD. Nevertheless, in MROMD and PMROMD, we combine the two passes in a way that minimizes the additional cost: the overhead incurred by the second pass in our twopass 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 allbutone verifiable lossy relation which is in fact a relaxation of allbutone 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 allbutone verifiable lossy relation from DLDH assumption over pairing group. As a byproduct, we propose the first allbutone 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 allbutone verifiable lossy relation can be used to construct adaptive trapdoor relation, which derives chosen ciphertext secure encryption.
Mehdi Tibouchi. Impossibility of Surjective IcartLike 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, constanttime) ``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^2b)^{1/3}, u) on the elliptic curve y^2 = x^3 + b over F_q.
The BonehFranklin 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 welldefined 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:
Icartlike encodings, which are generalizations of the original
BonehFranklin encoding starting with a construction due to Icart
(CRYTPO 2009), and SWUlike 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 BonehFranklin encoding.
In this paper, we focus on Icartlike 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 Icartlike encoding cannot exist to nonsupersingular
elliptic curves.
Shoichi Hirose and Hidenori Kuwakado. A BlockCipherBased Hash Function Using an MMOType DoubleBlock 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 doubleblock 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 keylength is
larger than its blocklength such as AES192/256, PRESENT128, 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, pseudorandomfunction property of the keyedviaIV 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 ofmost 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 pseudorandom number generator (PRNG) and cyclic redundancy check (CRC) code. Our ultralightweight scheme which integrates the operation of EPCGen2 buildin CRC16 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 chosenciphertext (CCA) secure publickey encryption (PKE) is one of the most important research topics in cryptography. However, it is also known that it is hard to construct a CCAsecure PKE whose ciphertext overhead is less than two group elements in the underlying primeorder group under noninteractive 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 CCAsecure 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 PreImage Awareness and the Security of HashTree Keyless Signatures
Abstract: We present a new tighter security proof for unbounded hash tree keyless signature (timestamping) schemes that
use MerkleDamg\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 backdating attacks. We show that many known PrA constructions satisfy a stronger \emph{Bounded PreImage 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 MDhash functions with rank1 compression functions (such as DaviesMeyer and MiaguchiPreneel) of both type I and type II are BPrA.
We also show that the compression function of ShrimptonStam that uses noncompressing components is BPrA.
The security proof for unbounded hashtree schemes is very tight under the BPrA assumption.
In order to have $2^s$security against backdating, 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 "noncryptographic" PRGs, especially the one proposed by Impagliazzo, Nisan and Wigderson (STOC 1994). Since their PRG uses expander graphs (rather than oneway functions for cryptographic PRGs) to stretch and scramble the random seeds informationtheoretically 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 "noncryptographic" PRGs might narrow the class of schemes to which our proof is applicable, the class still involves some existing informationtheoretically secure schemes such as fingerprint codes. Moreover, we propose a "dualmode" 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 IdentityBased 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 identitybased setting. We firstly formalize the CROB for identitybased encryption, and present a generic construction achieving CROB from an arbitrary identitybased encryption scheme. After that, motivated by the fact that complete robustness implies security against relatedkey attack (RKA) in public key encryption, we investigate whether such implication is still true for the case of identitybased encryption.
We conclude that these two notions (CROB and RKA security) are separable for identitybased encryption. However, we note that with a slight modification to our generic construction, an identitybased encryption scheme offering complete robustness with security against relatedkey attacks can be constructed from any identitybased 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 Pairingbased Protocols
Abstract: Asymmetric bilinear maps using Type3 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 Type1 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 clientserver IDbased key exchange). Also, we show computational soundness of our symbolic model under the decisional bilinear DiffieHellman assumption.
Takashi Yamakawa, Nobuaki Kitajima, Takashi Nishide, Goichiro Hanaoka and Eiji Okamoto. A Short FailStop Signature Scheme from Factoring
Abstract: Failstop 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, factoringbased schemes are important due to their high reliability. However, known factoringbased 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 factoringbased 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 factoringbased FSS scheme whose signature size is smaller than $N$.
Yohei Watanabe and Junji Shikata.
TimedRelease 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 timedrelease functionality, which we call a timedrelease computational secret sharing (TRCSS) scheme. In TRCSS, 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 TRCSS scheme in a generic and efficient way in terms of the share size. Specifically, we first introduce a model and formalization of security of TRCSS. In addition, we propose two kinds of constructions of TRCSS: the first one is a simple and generic construction starting from identitybased 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 TRCSS as a natural extension of Krawczyk's CSS in terms of both a model and constructions, and we finally succeed to add timedrelease functionality to Krawczyk's CSS with small overhead, which seems to be almost optimal. Moreover, Our proposal of TRCSS is important for constructing threshold encryption and multiple encryption with timedrelease 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 TRCSS, we can effectively apply the DodisKatz paradigm even in the context of timedrelease 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 ’SIGnandMAc’ 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 longterm keys in the DiffieHellman 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.
