*09:17* [Pub][ePrint]
Subgroup security in pairing-based cryptography, by Paulo S. L. M. Barreto and Craig Costello and Rafael Misoczki and Michael Naehrig and Geovandro C. C. F. Pereira and Gustavo Zanon
Pairings are typically implemented using ordinary pairing-friendly elliptic curves. The two input groups of the pairing function are groups of elliptic curve points, while the target group lies in the multiplicative group of a large finite field. At moderate levels of security, at least two of the three pairing groups are necessarily proper subgroups of a much larger composite-order group, which makes pairing implementations potentially susceptible to small-subgroup attacks.To minimize the chances of such attacks, or the effort required to thwart them, we put forward a property for ordinary pairing-friendly curves called subgroup security. We point out that existing curves in the literature and in publicly available pairing libraries fail to achieve this notion, and propose a list of replacement curves that do offer subgroup security. These curves were chosen to drop into existing libraries with minimal code change, and to sustain state-of-the-art performance numbers. In fact, there are scenarios in which the replacement curves could facilitate faster implementations of protocols because they can remove the need for expensive group exponentiations that test subgroup membership.

*09:17* [Pub][ePrint]
Verifiably Encrypted Signatures with Short Keys based on the Decisional Linear Problem and Obfuscation for Encrypted VES, by Ryo Nishimaki and Keita Xagawa
Verifiably encrypted signatures (VES) are signatures encrypted by a public key of a trusted third party and we can verify their validity without decryption. This paper proposes a new VES scheme which is secure under the decisional linear (DLIN) assumption in the standard model. We also propose new obfuscators for encrypted signatures (ES) and encrypted VES (EVES) which are secure under the DLIN assumption. All previous efficient VES schemes in the standard model are either secure under standard assumptions (such as the computational Diffie-Hellman assumption) with large verification (or secret) keys or secure under \\emph{(non-standard) dynamic $q$-type assumptions} (such as the $q$-strong Diffie-Hellman extraction assumption) with short verification keys. Our construction is the first efficient VES scheme with short verification (and secret) keys secure under \\emph{a standard assumption (DLIN)}.

As by-products of our VES scheme, we construct new obfuscators for ES/EVES based on our new VES scheme. They are more efficient than previous obfuscators with respect to the public key size. Previous obfuscators for EVES are secure under non-standard assumption and use zero-knowledge (ZK) proof systems and Fiat-Shamir heuristics to obtain non-interactive ZK, i.e., its security is considered in the random oracle model. Thus, our construction also has an advantage with respect to assumptions and security models. Our new obfuscator for ES is obtained from our new obfuscator for EVES.

*09:17* [Pub][ePrint]
Improved (Hierarchical) Inner-Product Encryption from Lattices, by Keita Xagawa
Inner-product encryption (IPE) provides fine-grained access control and has attractive applications. Agrawal, Freeman, and Vaikuntanathan~(Asiacrypt 2011) proposed the first IPE scheme from lattices by twisting the identity-based encryption (IBE) scheme by Agrawal, Boneh, and Boyen~(Eurocrypt 2010). Their IPE scheme supports inner-product predicates over $R^{\\mu}$, where the ring is $R = \\mathbb{Z}_q$. Several applications require the ring $R$ to be exponentially large and, thus, they set $q = 2^{O(n)}$ to implement such applications. This choice results in the AFV IPE scheme with public parameters of size $O(\\mu n^2 \\lg^3{q}) = O(\\mu n^5)$ and ciphertexts of size $O(\\mu n \\lg^3{q}) = O(\\mu n^4)$, where $n$ is the security parameter. Hence, this makes the scheme impractical, as they noted.We address this efficiency issue by ``untwisting\'\' their twist and providing another twist. Our scheme supports inner-product predicates over $R^\\mu$ where $R = \\mathrm{GF}(q^n)$ instead of $\\mathbb{Z}_q$. Our scheme has public parameters of size $O(\\mu n^2 \\lg^2{q})$ and ciphertexts of size $O(\\mu n \\lg^2{q})$. Since the cardinality of $\\mathrm{GF}(q^n)$ is inherently exponential in $n$, we have no need to set $q$ as the exponential size for applications.

As side contributions, we extend our IPE scheme to a hierarchical IPE (HIPE) scheme and propose a fuzzy IBE scheme from IPE. Our HIPE scheme is more efficient than that developed by Abdalla, De Caro, and Mochetti (Latincrypt 2012). Our fuzzy IBE is secure under a much weaker assumption than that employed by Agrawal et al.~(PKC 2012), who constructed the first lattice-based fuzzy IBE scheme.

*09:17* [Pub][ePrint]
Design and Analysis of Information-Theoretically Secure Authentication Codes with Non-Uniformly Random Keys, by Junji Shikata
The authentication code (A-code) is the one of the most fundamental cryptographic protocols in information-theoretic cryptography, and it provides information-theoretic integrity or authenticity, i.e., preventing information from being altered or substituted by the adversary having unbounded computational powers. In addition, it has a wide range of applications such as multiparty computations and quantum key distribution protocols. The traditional A-code theory states that a good A-code is characterized as an A-code which satisfies equality of a lower bound on size of secret-keys, i.e., an A-code satisfying |K|=\\epsilon^{-2}, where |K}| is cardinality of the set of secret-keys and \\epsilon is the success probability of attacks of the adversary. However, good A-codes imply that secret-keys must be uniformly distributed. Therefore, if a non-uniformly random key is given, we cannot realize a good A-code by using it as a secret-key. Then, a natural question about this is: what is a good A-code having non-uniformly random keys? And, how can we design such a good A-code having non-uniformly random keys? To answer the questions, in this paper, we perform analysis of A-codes having non-uniformly random keys, and show the principle that guides the design for such good A-codes.

Specifically, the contribution of this paper is as follows. We first derive a new lower bound on entropy of secret-keys, and it is described in terms of \\R entropy. Next, we define that a good A-code having non-uniformly random keys is the one satisfying equality of the bound, and it is characterized by the min-entropy (a special case of \\R entropy). Furthermore, we introduce the classification methodology for A-codes which are realizable from a biased key-source. This classification is performed by using a mathematical tool, i.e., a group action on the set of authentication matrices. By this analysis, we can understand what kind of A-codes is actually constructable.

Finally, we design how to construct good A-codes having 1-bit messages from von Neumann sources. We also show that our construction methodology is superior to the one by applying von Neumann extractors and the traditional optimal A-code constructions. Although the case of 1-bit messages may be restricted, however, this case is simple and we believe that a general case will develop from this simple case.

*09:17* [Pub][ePrint]
How to Construct UC-Secure Searchable Symmetric Encryption Scheme, by Kaoru Kurosawa and Yasuhiro Ohtaki
A searchable symmetric encryption (SSE) scheme allows a client to store a set of encrypted files on an untrusted server in such a way that he can efficiently retrieve some of the encrypted files containing (or indexed by) specific keywords keeping the keywords and the files secret.In this paper, we first extend the model of SSE schemes to that of verifiable SSE schemes, and formulate the UC security. We then prove its weak equivalence with privacy and reliability. Finally we show an efficient verifiable SSE scheme which is UC-secure.

*09:17* [Pub][ePrint]
Linearization of Multi-valued Nonlinear Feedback Shift Registers, by Haiyan Wang, Jianghua Zhong, Dongdai Lin
The Linearization of Nonlinear feedback shift registers (NFSRs) is to find their state transition matrices. In this paper,we investigate the linearization multi-valued NFSRs by considering it as a logical network via a semi-tensor product approach.

A new state transition matrix is found for an multi-valued NFSR, which can be simply computed from the truth table of its

feedback function, and the new state transition matrix is easier to compute and is more explicit. First, a linear representation of a

multi-valued NFSR is given, based on which several necessary and sufficient conditions for the nonsingularity are given. Then,

some properties of the state transition matrice are provided, which are helpful to theoretically analyze NFSRs. Finally, we give

properties of a maximum length multi-valued NFSR and the linear representation of the general structure of an n-bit shift register

with updating functions.

*09:17* [Pub][ePrint]
Stability and Linearization of Multi-valued Nonlinear Feedback Shift Registers, by Haiyan Wang , Dongdai Lin
In this paper, we study stability and linearization of multi-valued nonlinear feedback shift registers which are considered as logic

networks. First, the linearization of multi-valued nonlinear feedback shift

registers (NFSRs) is discussed, which is to nd their state transition ma-

trices by considering it as a logical network via a semi-tensor product ap-

proach. For a multi-valued NFSR, the new state transition matrix which

can be simply computed from the truth table of its feedback function is

more explicit. Second, based on the linearization theory of multi-valued

NFSRs, we investigate the stability of multi-valued NFSRs, and some suf-

cient and necessary conditions are provided for globally (locally) stable

multi-valued NFSRs. Finally, some examples are presented to show the

eectiveness of the proposed results.

*09:17* [Pub][ePrint]
A comprehensive analysis of game-based ballot privacy definitions, by David Bernhard and Veronique Cortier and David Galindo and Olivier Pereira and Bogdan Warinschi
We critically survey game-based security definitions for the privacy of voting schemes. In addition to known limitations, we unveil several previously unnoticed shortcomings. Surprisingly, the conclusion of our study is that none of the existing definitions is satisfactory: they either provide only weak guarantees, or can be applied only to a limited class of schemes, or both. Based on our findings, we propose a new game-based definition of privacy which we call BPRIV. We also identify a new property which we call {\\em strong consistency}, needed to express that tallying does not leak sensitive information. We validate our security notions by showing that BPRIV, strong consistency and strong correctness for a voting scheme imply its security in a simulation-based sense. This result also yields a proof technique for proving entropy-based notions of privacy which offer the strongest security guarantees but are hard

to prove directly: first prove your scheme BPRIV, strongly consistent and strongly correct,

then study the entropy-based privacy of the result function of the election, which is a much easier task.