Rational proofs, introduced by Azar and Micali (STOC 2012), are a variant of interactive proofs in which the prover is rational, and may deviate from the protocol for increasing his reward. Guo et al. (ITCS 2014) demonstrated that rational proofs are relevant to delegation of computation. By restricting the prover to be computationally bounded, they presented a one-round delegation scheme with sublinear verification for functions computable by log-space uniform circuits with logarithmic depth. In this work, we study rational proofs in which the verifier is also rational, and may deviate from the protocol for decreasing the prover's reward. We construct a three-message delegation scheme with sublinear verification for functions computable by log-space uniform circuits with polylogarithmic depth in the random oracle model.

Group signatures are a class of digital signatures with enhanced privacy. By using this type of signature, a user can sign a message on behalf of a specific group without revealing his identity, but in the case of a dispute, an authority can expose the identity of the signer. However, it is not always the case that we need to know the specific identity of a signature. In this paper, we propose the notion of deniable group signatures, where the authority can issue a proof showing that the specified user is NOT the signer of a signature, without revealing the actual signer. We point out that existing efficient non-interactive zero-knowledge proof systems cannot be straightforwardly applied to prove such a statement. We circumvent this problem by giving a fairly practical construction through extending the Groth group signature scheme (ASIACRYPT 2007). In particular, a denial proof in our scheme consists of 96 group elements, which is about twice the size of a signature in the Groth scheme. The proposed scheme is provably secure under the same assumptions as those of the Groth scheme.

Artificial lighting is responsible for a large portion of total energy consumption and has great potential for energy saving. This paper designs an LED light control algorithm based on users' localization using multiple battery-less binary human detection sensors. The proposed lighting control system focuses on reducing office lighting energy consumption and satisfying users' illumination requirement. Most current lighting control systems use infrared human detection sensors, but the poor detection probability, especially for a static user, makes it difficult to realize comfortable and effective lighting control. To improve the detection probability of each sensor, we proposed to locate sensors as close to each user as possible by using a battery-less wireless sensor network, in which all sensors can be placed freely in the space with high energy stability. We also proposed to use a multi-sensor-based user localization algorithm to capture user's position more accurately and realize fine lighting control which works even with static users. The system is actually implemented in an indoor office environment in a pilot project. A verification experiment is conducted by measuring the practical illumination and power consumption. The performance agrees with design expectations. It shows that the proposed LED lighting control system reduces the energy consumption significantly, 57% compared to the batch control scheme, and satisfies user's illumination requirement with 100% probability.

In this paper, we give a formalization of the behavior of the Content-Centric Networking (CCN) protocol with parameterizing content managements. CCN is a communications architecture that is based on the names of contents, rather than on addresses. In the protocol used in CCN, each node sends packets to the nodes that are connected to it, which communicate with further nodes that are connected to them. This kind of behaviors prevents formalizing the CCN protocol as end-to-end communications. In our previous work, we formalized the CCN protocol using the proof assistant Coq. However, in this model, each node in the network can store any number of contents. The storage for each node is usually limited and the node may drop some of the contents due to its filled storage. The model proposed in this paper permits a node to have its own content management method, and still keeps the temporal properties that are also valid in the previous model. To demonstrate difference between these models, we give a specification that is valid in the previous model but invalid in the proposed model, called orthogonality. Since it is generally invalid in CCN, the proposed model is more precise than the previous one.

Proof of Retrievability (POR) is a protocol by which a client can distribute his/her data to cloud servers and can check if the data stored in the servers is available and intact. After that, network coding-based POR has been applied to improve network throughput. Although many network coding-based PORs have been proposed, most of them have not achieved the following practical features: direct repair and dynamic operations. In this paper, we propose the D2-POR scheme (Direct repair and Dynamic operations in network coding-based POR) to address these shortcomings. When a server is corrupted, the D2-POR can support the direct repair in which the data stored in the corrupted server can be repaired using the data directly provided by healthy servers. The client is thus free from the burden of data repair. Furthermore, the D2-POR allows the client to efficiently perform dynamic operations, i.e., modification, insertion and deletion.

In the obnoxious facility game with a set of agents in a space, we wish to design a mechanism, a decision-making procedure that determines a location of an undesirable facility based on locations reported by the agents, where we do not know whether the location reported by an agent is where exactly the agent exists in the space. For a location of the facility, the benefit of each agent is defined to be the distance from the location of the facility to where the agent exists. Given a mechanism, all agents are informed of how the mechanism utilizes locations reported by the agents to determine a location of the facility before they report their locations. Some agent may try to manipulate the decision of the facility location by strategically misreporting her location. As a fair decision-making, mechanisms should be designed so that no particular group of agents can get a larger benefit by misreporting their locations. A mechanism is called group strategy-proof if no subset of agents can form a group such that every member of the group can increase her benefit by misreporting her location jointly with the rest of the group. For a given mechanism, a point in the space is called a candidate if it can be output as the location of the facility by the mechanism for some set of locations reported by agents. In this paper, we consider the case where a given space is a tree metric, and characterize the group strategy-proof mechanisms in terms of distribution of all candidates in the tree metric. We prove that there exists a group strategy-proof mechanism in the tree metric if and only if the tree has a point to which every candidate has the same distance.

A multisignature (MS) scheme enables a group of signers to produce a compact signature on a common message. In analyzing security of MS schemes, a key registration protocol with proof-of-possession (POP) is considered to prevent rogue key attacks. In this paper, we refine the POP-based security model by formalizing a new strengthened POP model and showing relations between the previous POP models and the new one. We next suggest a MS scheme that achieves: (1) non-interactive signing process, (2) O(1) pairing computations in verification, (3) tight security reduction under the co-CDH assumption, and (4) security under the new strengthened POP model. Compared to the tightly-secure BNN-MS scheme, the verification in ours can be at least 7 times faster at the 80-bit security level and 10 times faster at the 128-bit security level. To achieve our goal, we introduce a novel and simple POP generation method that can be viewed as a one-time signature without random oracles. Our POP technique can also be applied to the LOSSW-MS scheme (without random oracles), giving the security in the strengthened POP model.

The primitive called public key encryption with non-interactive opening (PKENO) is a class of public key encryption (PKE) with additional functionality. By using this, a receiver of a ciphertext can prove that the ciphertext is an encryption of a specified message in a publicly verifiable manner. In some situation that a receiver needs to claim that a ciphertext is NOT decrypted to a specified message, if he/she proves the fact by using PKENO straightforwardly, the real message of the ciphertext is revealed and a verifier checks that it is different from the specified message about which the receiver wants to prove. However, this naive solution is problematic in terms of privacy. Inspired by this problem, we propose the notion of disavowable public key encryption with non-interactive opening (disavowable PKENO) where, with respect to a ciphertext and a message, the receiver of the ciphertext can issue a proof that the plaintext of the ciphertext is NOT the message. Also, we give a concrete construction. Specifically, a disavowal proof in our scheme consists of 61 group elements. The proposed disavowable PKENO scheme is provably secure in the standard model under the decisional linear assumption and strong unforgeability of the underlying one-time signature scheme.

Code-based public-key encryption schemes (PKE) are the candidates for post-quantum cryptography, since they are believed to resist the attacks using quantum algorithms. The most famous such schemes are the McEliece encryption and the Niederreiter encryption. In this paper, we present the zero-knowledge (ZK) proof systems for proving statements about data encrypted using these schemes. Specifically, we present a proof of plaintext knowledge for both PKE's, and also a verifiable McEliece PKE. The main ingredients of our constructions are the ZK identification schemes by Stern from Crypto'93 and by Jain, Krenn, Pietrzak, and Tentes from Asiacrypt'12.

Nowadays, many individuals and organizations tend to outsource their data to a cloud storage for reducing the burden of data storage and maintenance. However, a cloud provider may be untrustworthy. The cloud thus leads to a numerous security challenges: data availability, data integrity, and data confidentiality. In this paper, we focus on data availability and data integrity because they are the prerequisites of the existence of a cloud system. The approach of this paper is the network coding-based Proof of Retrievability (POR) scheme which allows a client to check whether his/her data stored on the cloud servers are intact. Although many existing network coding-based PORs have been proposed, most of them still incur high costs in data check and data repair, and cannot prevent the small corruption attack which is a common attack in the POR scheme. This paper proposes a new network coding-based POR using the dispersal coding technique, named the ND-POR (Network coding - Dispersal coding POR) to improve the efficiency in data check and data repair and to protect against the small corruption attack.

The second edition of the international standard of IEC 61508, functional safety of electrical/electronic/programmable electronic safety-related system (SRS), was published in 2010. This international standard adopts a risk-based approach by which safety integrity requirements can be determined. It presents a formula to estimate the hazardous event rate taking account of non-perfect proof-tests. But it is not clear how to derive the formula. In the present paper, firstly, taking account of non-perfect proof-tests, the relationship between the dangerous undetected failure of SRS, the demand on the SRS and hazardous event is modeled by a fault tree and state-transition diagrams. Next, the hazardous event rate is formulated by use of the state-transition diagrams for the determination of the safety integrity requirements. Then, a comparison is made between the formulas obtained by this paper and given in the standard, and it is found that the latter does not always present rational formulation.

Recently, there have been many studies on constructing cryptographic primitives that are secure even if some secret information leaks. In this paper, we consider the problem of constructing public-key encryption schemes that are resilient to leaking the randomness used in the encryption algorithm. In particular, we consider the case in which public-key encryption schemes are constructed from the KEM/DEM framework, and the leakage of randomness in the encryption algorithms of KEM and DEM occurs independently. For this purpose, we define a new security notion for KEM. Then we provide a generic construction of a public-key encryption scheme that is resilient to randomness leakage from any KEM scheme satisfying this security. Also we construct a KEM scheme that satisfies the security from hash proof systems.

At Eurocrypt'03, Boneh, Gentry, Lynn and Shacham proposed a pairing based verifiably encrypted signature scheme (the BGLS-VES scheme). In 2004, Hess mounted an efficient rogue-key attack on the BGLS-VES scheme in the plain public-key model. In this letter, we show that the BGLS-VES scheme is not secure in the proof of possession (POP) model.

We consider the problem of constructing public-key encryption (PKE) schemes that are resilient to a-posteriori chosen-ciphertext and key-leakage attacks (LR-CCA2). In CTYPTO'09, Naor and Segev proved that the Naor-Yung generic construction of PKE which is secure against chosen-ciphertext attack (CCA2) is also secure against key-leakage attacks. They also presented a variant of the Cramer-Shoup cryptosystem, and showed that this PKE scheme is LR-CCA2-secure under the decisional Diffie-Hellman assumption. In this paper, we apply the generic construction of “Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption” (EUROCRYPT'02) to generalize the above work of Naor-Segev. In comparing to the first construction of Naor-Segev, ours is more efficient because of not using simulation-sound NIZK. We also extend it to stateful PKE schemes. Concretely, we present the notion of LR-CCA2 attack in the case of stateful PKE, and a generic construction of stateful PKE that is secure against this attack.

At Eurocrypt'2006, Lu et al. proposed a pairing based verifiably encrypted signature scheme (the LOSSW-VES scheme) without random oracles. In this letter, we show that the LOSSW-VES scheme does not have opacity against rogue-key attacks.

Key wrapping schemes are used to encrypt data of high entropy, such as cryptographic keys. There are two known security definitions for key wrapping schemes. One captures the security against chosen plaintext attacks (called DAE-security), and the other captures known plaintext attacks (called AKW-security). In this paper, we revisit the security of Hash-then-CBC key wrapping schemes. In [17], Osaki and Iwata showed that the UCC-then-CBC key wrapping scheme, a key wrapping scheme that uses the UCC hash function and CBC mode, has provable AKW-security. In this paper, we show that the scheme achieves the stronger notion of DAE-security. We also show our proof in the variable input length setting, where the adversary is allowed making queries of varying lengths. Furthermore, we consider the scheme that incorporates the use of headers. To handle such a setting, we generalize the previous definition of the UCC hash function to the variable input length setting and to take the header as its input, and show an efficient construction that meets the definition.

This paper proposes a new lightweight 256-bit hash function Lesamnta-LW. The security of Lesamnta-LW is reduced to that of the underlying AES-based block cipher and it is theoretically analyzed for an important application, namely the key-prefix mode. While most of recently proposed lightweight primitives are hardware-oriented with very small footprints, our main target with Lesamnta-LW is to achieve compact and fast hashing for lightweight application on a wider variety of environments ranging from inexpensive devices to high-end severs at the 2120 security level. As for performance, our primary target CPUs are 8-bit and it is shown that, for short message hashing, Lesamnta-LW offers better tradeoffs between speed and cost on an 8-bit CPU than SHA-256.

Constructing a secure and efficient key wrapping scheme is demanding, and the scheme based on a universal hash function and an elementary encryption mode like ECB and CBC modes is potential for a practical use. However, at SAC 2009, Gennaro and Halevi showed that a key wrapping scheme using a universal hash function and ECB mode (a HtECB scheme) is broken, and the security of a scheme based on a universal hash function and CBC mode (a HtCBC scheme) has been left as an open problem. In this paper, we first generalize classical notions of universal and uniform hash functions, and propose a total of four new notions of the keyed hash function. We then prove that HtECB and HtCBC schemes are secure key wrapping schemes if the universal hash function satisfies uniformity and our notions, where the result on the HtCBC scheme gives a partial answer to the open problem. Then we discuss a basic problem of identifying relations between various notions of a keyed hash function, and point out that a monic polynomial hash function satisfies all the new notions.

Traceable ring signatures, proposed at PKC'07, are a variant of ring signatures, which allow a signer to anonymously sign a message with a tag behind a ring, i.e., a group of users chosen by the signer, unless he signs two messages with the same tag. However, if a signer signs twice on the same tag, the two signatures will be linked and the identity of the signer will be revealed when the two signed messages are different. Traceable ring signatures can be applied to anonymous write-in voting without any special voting authority and electronic coupon services. The previous traceable ring signature scheme relies on random oracles at its security and the signature size is linear in the number of ring members. This paper proposes the first secure traceable ring signature schemes without random oracles in the common reference string model. In addition, the proposed schemes have a signature size of O(), where N is the number of users in the ring.

Establishment of a practical software protection method is a major issue in software distribution. There are several approaches to the issue; however, no practical, secure method for mobile phone applications has been proposed. In this paper, we propose a new software protection scheme combined with a tamper-proof device (TPD) in order to achieve computational security against illegal analysis and copying of the target program. Our scheme achieves a reasonable level of security for encoding the data and variables in a program. The program on a mobile phone deals only with encoded data that is difficult to compromise, and the TPD plays a role of decoding execution results. We implemented the proposed scheme on a 3G mobile phone and a user identification module (UIM). An analysis and copying of the protected program impose exponential computation complexities under our attack model.