So far, in almost all of the practical public key encryption schemes, hash functions which are dependent on underlying cyclic groups are necessary, e.g., H:{0,1}* → Zp where p is the order of the underlying cyclic group, and it could be required to construct a dedicated hash function for each public key. The motivation of this note is derived from the following two facts: 1). there is an important technical gap between hashing to a specific prime-order group and hashing to a certain length bit sequence, and this could cause a security hole; 2). surprisingly, to our best knowledge, there is no explicit induction that one could use the simple construction, instead of tailor-made hash functions. In this note, we investigate this issue and provide the first rigorous discussion that in many existing schemes, it is possible to replace such hash functions with a target collision resistant hash function H:{0,1}* → {0,1}k, where k is the security parameter. We think that it is very useful and could drastically save the cost for the hash function implementation in many practical cryptographic schemes.

In a large-scale information-sharing platform, such as a cloud storage, it is often required to not only securely protect sensitive information but also recover it in a reliable manner. Public-key encryption with non-interactive opening (PKENO) is considered as a suitable cryptographic tool for this requirement. This primitive is an extension of public-key encryption which enables a receiver to provide a non-interactive proof which confirms that a given ciphertext is decrypted to some public plaintext. In this paper, we present a Tag-KEM/DEM framework for PKENO. In particular, we define a new cryptographic primitive called a Tag-KEM with non-interactive opening (Tag-KEMNO), and prove the KEM/DEM composition theorem for this primitives, which ensures a key encapsulation mechanism (KEM) and a data encapsulation mechanism (DEM) can be, under certain conditions, combined to form a secure PKENO scheme. This theorem provides a secure way of combining a Tag-KEMNO scheme with a DEM scheme to construct a secure PKENO scheme. Using this framework, we explain the essence of existing constructions of PKENO. Furthermore, we present four constructions of Tag-KEMNO, which yields four PKENO constructions. These PKENO constructions coincide with the existing constructions, thereby we explain the essence of these existing constructions. In addition, our Tag-KEMNO framework enables us to expand the plaintext space of a PKENO scheme. Some of the previous PKENO schemes are only able to encrypt a plaintext of restricted length, and there has been no known way to expand this restricted plaintext space to the space of arbitrary-length plaintexts. Using our framework, we can obtain a PKENO scheme with the unbounded-length plaintext space by modifying and adapting such a PKENO scheme with a bounded-length plaintext space.

It is known that, using just a deck of cards, an arbitrary number of parties with private inputs can securely compute the output of any function of their inputs. In 2009, Mizuki and Sone constructed a six-card COPY protocol, a four-card XOR protocol, and a six-card AND protocol, based on a commonly used encoding scheme in which each input bit is encoded using two cards. However, up until now, there are no known results to construct a set of COPY, XOR, and AND protocols based on a two-card-per-bit encoding scheme, which all can be implemented using only four cards. In this paper, we show that it is possible to construct four-card COPY, XOR, and AND protocols using polarizing plates as cards and a corresponding two-card-per-bit encoding scheme. Our protocols use a minimum number of cards in the setting of two-card-per-bit encoding schemes since four cards are always required to encode the inputs. Moreover, we show that it is possible to construct two-card COPY, two-card XOR, and three-card AND protocols based on a one-card-per-bit encoding scheme using a common reference polarizer which is a polarizing material accessible to all parties.

Unforgeability of digital signatures is closely related to the security of hash functions since hashing messages, such as hash-and-sign paradigm, is necessary in order to sign (arbitrarily) long messages. Recent successful collision finding attacks against practical hash functions would indicate that constructing practical collision resistant hash functions is difficult to achieve. Thus, it is worth considering to relax the requirement of collision resistance for hash functions that is used to hash messages in signature schemes. Currently, the most efficient strongly unforgeable signature scheme in the standard model which is based on the CDH assumption (in bilinear groups) is the Boneh-Shen-Waters (BSW) signature proposed in 2006. In their scheme, however, a collision resistant hash function is necessary to prove its security. In this paper, we construct a signature scheme which has the same properties as the BSW scheme but does not rely on collision resistant hash functions. Instead, we use a target collision resistant hash function, which is a strictly weaker primitive than a collision resistant hash function. Our scheme is, in terms of the signature size and the computational cost, as efficient as the BSW scheme.

This paper presents a non-interactive verifiable secret sharing scheme (VSS) tolerating a dishonest majority based on data pre-distributed by a trusted authority. As an application of this VSS scheme we present very efficient unconditionally secure protocols for performing multiplication of shares based on pre-distributed data which generalize two-party computations based on linear pre-distributed bit commitments. The main results of this paper are a non-interactive VSS, a simplified multiplication protocol for shared values based on pre-distributed random products, and non-interactive zero knowledge proofs for arbitrary polynomial relations. The security of the schemes is proved using the UC framework.

We have introduced the first electronic cash scheme with unconditional security. That is, even malicious users with unlimited computational ability cannot forge a coin and cannot change user's identity secretly embedded in each coin. While, the spender's anonymity is preserved by our new blind signature scheme based on unconditionally secure signature proposed in [7]. But the anonymity is preserved only computationally under the assumption that Decisional Diffie-Hellman Problem is intractable.

In this paper, we propose a new generic construction of signatures from trapdoor commitments with strong openings in the random oracle model. Our construction is very efficient in the sense that signatures consist of just a single decommitment of the underlying commitment scheme, and verification corresponds to verifying this decommitment against a commitment derived via a hash function. Furthermore, assuming the commitment scheme provides sufficiently strong statistical hiding and trapdoor opening properties, the reduction of the security of the signature scheme to the binding property of the commitment scheme is tight. To instantiate our construction, we propose two new commitment schemes with strong openings. Both of these are statistically hiding, and have binding properties based on a Diffie-Hellman inversion problem and factoring, respectively. The signature schemes obtained from these are very efficient; the first matches the performance of BLS signatures, which currently provides the shortest signatures, and the second provides signatures of similar length to the shortest version of Rabin-Williams signatures while still being tightly related to factoring.

A lot of encryption and watermarking schemes have been developed as countermeasures to protect copyrights of broadcast or multicast content from malicious subscribers (traitors) that make pirate receivers (PRs) to use the content illegally. However, solo use of these schemes does not necessarily work well. Traitor tracing encryption schemes are a type of broadcasting encryption and have been developed for broadcasting and multicast services. There are multiple distinct decryption keys for each encryption key, and each service subscriber is given a unique decryption key. Any subscriber that redistributes his or her decryption key to a third party or who uses it and maybe other keys to make a PR can be identified with using the tracing algorithm of the scheme that is used by the services. However, almost all previous schemes have the same weakness; that is, they are vulnerable to an attack (content comparison attack). This is a concrete example such that solo use of the scheme does not work well. The attack involves multiple distinct decryption keys and a content-data comparison mechanism. We have developed a method, called complementary traitor tracing method (CTT), that makes traitor tracing schemes secure against content comparison attacks. It makes it impossible for PRs to distinguish ordinary content data from test data and makes traitor tracing schemes effective against all PRs, even those with multiple distinct decryption keys. CTT is made with a simple combination of schemes that are absolutely necessary. It makes broadcasting or multicast services secure.

In the ordinary security model for signature schemes, we consider an adversary that tries to forge a signature on a new message using only his knowledge of other valid message and signature pairs. To take into account side channel attacks such as tampering or fault-injection attacks, Bellare and Kohno (Eurocrypt 2003) formalized related-key attacks (RKA), where stronger adversaries are considered. In the RKA security model for signature schemes, we consider an adversary that can also manipulate the signing key and obtain signatures computed under the modified key. RKA security is defined with respect to the related-key deriving functions which are used by an adversary to manipulate the signing key. This paper considers RKA security of three established signature schemes: the Schnorr signature scheme, a variant of DSA, and a variant of ElGamal signature scheme. First, we show that these signature schemes are secure against a weak notion of RKA with respect to polynomial functions. Second, we demonstrate that, on the other hand, none of the Schnorr signature scheme, DSA, nor the ElGamal signature scheme achieves the standard notion of RKA security with respect to linear functions, by showing concrete attacks on these. Lastly, we show that slight modifications of the Schnorr signature scheme, (the considered variant of) DSA, and the variant of ElGamal signature scheme yield fully RKA secure schemes with respect to polynomial functions.

By using Password-based Authenticated Key Exchange (PAKE), a server can authenticate a user who has only the same password shared with the server in advance and establish a session key with the user simultaneously. However, in the real applications, we may have a situation where a user needs to share a session key with server A, but the authentication needs to be done by a different server B that shares the password with the user. Further, to achieve higher security on the server side, it may be required to make PAKE tolerant of a server breach by having multiple authentication servers. To deal with such a situation, Abdalla et al. proposed a variant of PAKE called Gateway Threshold PAKE (GTPAKE) where a gateway corresponds to the aforementioned server A being an on-line service provider and also a potential adversary that may try to guess the passwords. However, the schemes of Abdalla et al. turned out to be vulnerable to Undetectable On-line Dictionary Attack (UDonDA). In this paper, we propose the first GTPAKE provably secure against UDonDA, and in the security analysis, we prove that our GTPAKE is secure even if an adversary breaks into parts of multiple authentication servers.

Homomorphic encryption (HE) is useful to analyze encrypted data without decrypting it. However, by using ordinary HE, a user who can decrypt a ciphertext that is generated by executing homomorphic operations, can also decrypt ciphertexts on which homomorphic evaluations have not been performed, since homomorphic operations cannot be executed among ciphertexts which are encrypted under different public keys. To resolve the above problem, we introduce a new cryptographic primitive called Homomorphic Proxy Re-Encryption (HPRE) combining the “key-switching” property of Proxy Re-Encryption (PRE) and the homomorphic property of HE. In our HPRE, original ciphertexts (which have not been re-encrypted) guarantee CCA2 security (and in particular satisfy non-malleability). On the other hand, re-encrypted ciphertexts only guarantee CPA security, so that homomorphic operations can be performed on them. We define the functional/security requirements of HPRE, and then propose a specific construction supporting the group operation (over the target group in bilinear groups) based on the PRE scheme by Libert and Vergnaud (PKC 2008) and the CCA secure public key encryption scheme by Lai et al. (CT-RSA 2010), and prove its security in the standard model. Additionally, we show two extensions of our HPRE scheme for the group operation: an HPRE scheme for addition and an HPRE scheme for degree-2 polynomials (in which the number of degree-2 terms is constant), by using the technique of the recent work by Catalano and Fiore (ACMCCS 2015).

In this paper, we put forward the notion of a token-based multi-input functional encryption (token-based MIFE) scheme - a notion intended to give encryptors a mechanism to control the decryption of encrypted messages, by extending the encryption and decryption algorithms to additionally use tokens. The basic idea is that a decryptor must hold an appropriate decryption token in addition to his secrete key, to be able to decrypt. This type of scheme can address security concerns potentially arising in applications of functional encryption aimed at addressing the problem of privacy preserving data analysis. We firstly formalize token-based MIFE, and then provide two basic schemes; both are based on an ordinary MIFE scheme, but the first additionally makes use of a public key encryption scheme, whereas the second makes use of a pseudorandom function (PRF). Lastly, we extend the latter construction to allow decryption tokens to be restricted to specified set of encryptions, even if all encryptions have been done using the same encryption token. This is achieved by using a constrained PRF.

Machine learning models inherently memorize significant amounts of information, and thus hiding not only prediction processes but also trained models, i.e., model obliviousness, is desirable in the cloud setting. Several works achieved model obliviousness with the MNIST dataset, but datasets that include complicated samples, e.g., CIFAR-10 and CIFAR-100, are also used in actual applications, such as face recognition. Secret sharing-based secure prediction for CIFAR-10 is difficult to achieve. When a deep layer architecture such as CNN is used, the calculation error when performing secret calculation becomes large and the accuracy deteriorates. In addition, if detailed calculations are performed to improve accuracy, a large amount of calculation is required. Therefore, even if the conventional method is applied to CNN as it is, good results as described in the paper cannot be obtained. In this paper, we propose two approaches to solve this problem. Firstly, we propose a new protocol named Batch-normalizedActivation that combines BatchNormalization and Activation. Since BatchNormalization includes real number operations, when performing secret calculation, parameters must be converted into integers, which causes a calculation error and decrease accuracy. By using our protocol, calculation errors can be eliminated, and accuracy degradation can be eliminated. Further, the processing is simplified, and the amount of calculation is reduced. Secondly, we explore a secret computation friendly and high accuracy architecture. Related works use a low-accuracy, simple architecture, but in reality, a high accuracy architecture should be used. Therefore, we also explored a high accuracy architecture for the CIFAR10 dataset. Our proposed protocol can compute prediction of CIFAR-10 within 15.05 seconds with 87.36% accuracy while providing model obliviousness.

This paper addresses the problem of designing an unconditionally secure conference system that fulfills the requirements of both traceability and dynamic sender. In a so-called conference system, a common key is shared among all authorized users, and messages are encrypted using the shared key. It is known that a straightforward implementation of such a system may present a number of security weaknesses. Our particular concern lies in the possibility that unauthorized users may be able to acquire the shared key by illegal means, say from one or more authorized but dishonest users (called traitors). An unauthorized user who has successfully obtained the shared key can now decrypt scrambled messages without leaving any evidence on who the traitors were. To solve this problem, in this paper we propose a conference system that admits dynamic sender traceability. The new solution can detect traitors, even if the sender of a message is dynamically determined after a shared key is distributed to authorized users. We also prove that this scheme is unconditionally secure.

We present a new methodology for constructing an efficient identification scheme, and based on it, we propose a lightweight identification scheme whose computational and storage costs are sufficiently low even for cheap devices such as RFID tags. First, we point out that the efficiency of a scheme with statistical zero-knowledgeness can be significantly improved by enhancing its zero-knowledgeness to perfect zero-knowledge. Then, we apply this technique to the Girault-Poupard-Stern (GPS) scheme which has been standardized by ISO/IEC. The resulting scheme shows a perfect balance between communication cost, storage cost, and circuit size (computational cost), which are crucial factors for implementation on RFID tags. Compared to GPS, the communication and storage costs are reduced, while the computational cost is kept sufficiently low so that it is implementable on a circuit nearly as small as GPS. Under standard parameters, the prover's response is shortened 80 bits from 275 bits to 195 bits and in application using coupons, storage for one coupon is also reduced 80 bits, whereas the circuit size is estimated to be larger by only 335 gates. Hence, we believe that the new scheme is a perfect solution for fast authentication of RFID tags.

In this paper, we formally define and analyze the security notions of authenticated encryption in unconditional security setting. For confidentiality, we define the notions, APS (almost perfect secrecy) and NM (non-malleability), in terms of an information-theoretic viewpoint along with our model where multiple senders and receivers exist. For authenticity, we define the notions, IntC (integrity of ciphertexts) and IntP (integrity of plaintexts), from a view point of information theory. And then we combine the above notions to define the security notions of unconditionally secure authenticated encryption. Then, we analyze relations among the security notions. In particular, it is shown that the strongest security notion is the combined notion of APS and IntC. Finally, we formally define and analyze the following generic composition methods in the unconditional security setting along with our model: Encrypt-and-Sign, Sign-then-Encrypt and Encrypt-then-Sign. Consequently, it is shown that: the Encrypt-and-Sign composition method is not always secure; the Sign-then-Encrypt composition method is not always secure; and the Encrypt-then-Sign composition method is always secure, if a given encryption meets APS and a given signature is secure.

We present an improved constant-round secure two-party protocol for integer comparison functionality, which is one of the most fundamental building blocks in secure computation. Our protocol is in the so-called client-server model, which is utilized in real-world MPC products such as Sharemind, where any number of clients can create shares of their input and distribute to the servers who then jointly compute over the shares and return the shares of the result to the client. In the client-aided client-server model, as mentioned briefly by Mohassel and Zhang (S&P'17), a client further generates and distributes some necessary correlated randomness to servers. Such correlated randomness admits efficient protocols since otherwise, servers have to jointly generate randomness by themselves, which can be inefficient. In this paper, we improve the state-of-the-art constant-round comparison protocols by Damgå rd et al. (TCC'06) and Nishide and Ohta (PKC'07) in the client-aided model. Our techniques include identifying correlated randomness in these comparison protocols. Along the way, we also use tree-based techniques for a building block, which deviate from the above two works. Our proposed protocol requires only 5 communication rounds, regardless of the bit length of inputs. This is at least 5 times fewer rounds than existing protocols. We implement our secure comparison protocol in C++. Our experimental results show that this low-round complexity benefits in high-latency networks such as WAN. We also present secure Min/Argmin protocols using the secure comparison protocol.

Public-key encryption with keyword search (PEKS) is a cryptographic primitive that allows us to search for particular keywords over ciphertexts without recovering plaintexts. By using PEKS in cloud services, users can outsource their data in encrypted form without sacrificing search functionality. Concerning PEKS that can specify logical disjunctions and logical conjunctions as a search condition, it is known that such PEKS can be (generically) constructed from anonymous attribute-based encryption (ABE). However, it is not clear whether it is possible to construct this types of PEKS without using ABE which may require large computational/communication costs and strong mathematical assumptions. In this paper, we show that ABE is crucial for constructing PEKS with the above functionality. More specifically, we give a generic construction of anonymous key-policy ABE from PEKS whose search condition is specified by logical disjunctions and logical conjunctions. Our result implies such PEKS always requires large computational/communication costs and strong mathematical assumptions corresponding to those of ABE.

Chosen-ciphertext security is a central goal in designing a secure public-key encryption scheme, and it is also important that the chosen-ciphertext security is tightly reduced to some well-established hard problem. Moreover, it is more important to have a tight reduction in the multi-user multi-challenge setting, since a tight security reduction in the single-user single-challenge setting generally does not imply a tight reduction to the multi-user multi-challenge setting. We propose the first fully tightly secure and practical public-key encryption scheme which is chosen-ciphertext secure in the multi-user multi-challenge setting in the random oracle model. The scheme is proven secure under the decisional Diffie-Hellman assumption in a pairing-free group. The ciphertext overhead of our scheme is two group elements and two exponents.

Homomorphic encryption allows computation over encrypted data, and can be used for delegating computation: data providers encrypt their data and send them to an aggregator, who can then perform computation over the encrypted data on behalf of a client, without the underlying data being exposed to the aggregator. However, since the aggregator is merely a third party, it may be malicious, and in particular, may submit an incorrect aggregation result to the receiver. Ohara et al. (APKC2014) studied secure aggregation of time-series data while enabling the correctness of aggregation to be verified. However, they only provided a concrete construction in the smart metering system and only gave an intuitive argument of security. In this paper, we define verifiable homomorphic encryption (VHE) which generalizes their scheme, and introduce formal security definitions. Further, we formally prove that Ohara et al.'s VHE scheme satisfies our proposed security definitions.