研究成果

Information-theoretic security and computational security are fundamental paradigms of security in the theory of cryptography. The two paradigms interact with each other but have shown different progress, which motivates us to explore the intersection between them. In this paper, we focus on Multi-Party Computation (MPC) because the security of MPC is formulated by simulation-based security, which originates from computational security, even if it requires information-theoretic security. We provide several equivalent formalizations of the security of MPC under a semi-honest model from the viewpoints of information theory and statistics. The interpretations of these variants are so natural that they support the other aspects of simulation-based security. Specifically, the variants based on conditional mutual information and sufficient statistics are interesting because security proofs for those variants can be given by information measures and factorization theorem, respectively. To exemplify this, we show several security proofs of BGW (Ben-Or, Goldwasser, Wigderson) protocols, which are basically proved by constructing a simulator.

Card-based cryptography realizes secure multiparty computation using physical cards. In 2018, Watanabe et al. proposed a card-based three-input majority voting protocol using three cards. In a card-based cryptographic protocol with n-bit inputs, it is known that a protocol using shuffles requires at least 2n cards. In contrast, as Watanabe et al.'s protocol, a protocol using private permutations can be constructed with fewer cards than the lower bounds above. Moreover, an n-input protocol using private permutations would not even require n cards in principle since a private permutation depending on an input can represent the input without using additional cards. However, there are only a few protocols with fewer than n cards. Recently, Abe et al. extended Watanabe et al.'s protocol and proposed an n-input majority voting protocol with n cards and n + \floor{n/2} + 1 private permutations. This paper proposes an n-input majority voting protocol with \ceil{n/2}+1 cards and 2n-1 private permutations, which is also obtained by extending Watanabe et al.'s protocol. Compared with Abe et al.'s protocol, although the number of private permutations increases by about n/2, the number of cards is reduced by about n/2. In addition, unlike Abe et al.'s protocol, our protocol includes Watanabe et al.'s protocol as a special case where n=3.

Searchable symmetric encryption (SSE) enables clients to search encrypted data. Curtmola et al. (ACM CCS 2006) formalized a model and security notions of SSE and proposed two concrete constructions called SSE-1 and SSE-2. After the seminal work by Curtmola et al., SSE becomes an active area of encrypted search. In this paper, we focus on two unnoticed problems in the seminal paper by Curtmola et al. First, we show that SSE-2 does not appropriately implement Curtmola et al.'s construction idea for dummy addition. We refine SSE-2's (and its variants') dummy-adding procedure to keep the number of dummies sufficiently many but as small as possible. We then show how to extend it to the dynamic setting while keeping the dummy-adding procedure work well and implement our scheme to show its practical efficiency. Second, we point out that the SSE-1 can cause a search error when a searched keyword is not contained in any document file stored at a server and show how to fix it.

Card-based cryptography is a variety of secure multiparty computation (MPC). Recently, a new technique called private operations was introduced because the protocol can be implemented with fewer cards than that by using the conventional technique called the shuffle. For example, Nakai et al. showed that if the private operations are available, secure computations of AND and OR operations for two inputs can be realized simultaneously by using four cards, and the protocol is applied to a four-card majority voting protocol with three inputs. This paper shows that only three cards are sufficient to construct a majority voting protocol with three inputs. Specifically, we propose two constructions of three-input majority voting protocols. One is a protocol assuming that players can announce their output, and the other is not allowed. Compared to Nakai et al.'s protocol, the protocol with the announcement is realized without any additional private operations and communications. On the other hand, the second construction requires two more private operations and communications because it removes the assumption on the announcement from the first construction. More importantly, the idea of the second protocol can be extended to an n-input majority voting protocol with n cards, which is the main result of this paper.

Card-based cryptography is a variant of multi-party computation by using physical cards like playing cards. There are two models on card-based cryptography, called public and private models. The public model assumes that all operations are executed publicly, while the private model allows the players private operations called private permutations (PP, for short). Much of the existing card-based protocols were developed under the public model. Under the public model, 2n cards are necessary for every protocol with n-bit input since at least two cards are required to express a bit. In this paper, we propose n-bit input protocols with fewer than 2n cards by utilizing PP, which shows the power of PP. In particular, we show that a protocol for (n-bit input) threshold function can be realized with only n+1 cards by reducing the threshold function to the majority voting. Toward this end, we first offer that two-bit input protocols for logic gates can be realized with fewer than four cards. Furthermore, we construct a new protocol for three-input majority voting with only four cards by observing the relationship between AND/OR operations. This protocol can be easily extended to more participants, and to the protocol for threshold functions.

Card-based cryptography, introduced by den Boer aims to realize multiparty computation (MPC) by using physical cards. We propose several efficient card-based protocols for the millionaires’ problem by introducing a new operation called Private Permutation (PP) instead of the shuffle used in most of existing card-based cryptography. Shuffle is a useful randomization technique by exploiting the property of card shuffling, but it requires a strong assumption from the viewpoint of arithmetic MPC because shuffle assumes that public randomization is possible. On the other hand, private randomness can be used in PPs, which enables us to design card-based protocols taking ideas of arithmetic MPCs into account. Actually, we show that Yao’s millionaires’ protocol can be easily transformed into a card-based protocol by using PPs, which is not straightforward by using shuffles because Yao’s protocol uses private randomness. Furthermore, we propose entirely novel and efficient card-based millionaire protocols based on PPs by securely updating bitwise comparisons between two numbers, which unveil a power of PPs. As another interest of these protocols, we point out they have a deep connection to the well-known logical puzzle known as “The fork in the road.”

Laser fault injection (LFI) attacks on cryptographic processor ICs are a critical threat to information systems. This paper proposes an IC-level integrated countermeasure employing an information leakage sensor against an LFI attack. Distributed bulk current sensors monitor abnormal bulk current density caused by laser irradiation for LFI. Time-interleaved sensor operation and sensitivity tuning can obtain partial secret key leakage bit information with small layout area penalty. Based on the leakage information, the secret key can be securely updated to realize high-availability resilient systems. The test chip was designed and fabricated in a 0.18 μm standard CMOS, integrating a 128-bit advanced encryption standard cryptographic processor with the proposed information leakage sensor. This evaluation successfully demonstrated bulk current density and leakage bit monitoring.

In recent years, multi-party computation (MPC) frameworks based on replicated secret sharing schemes (RSSS) have attracted the attention as a method to achieve high efficiency among known MPCs. However, the RSSS-based MPCs are still inefficient for several heavy computations like algebraic operations, as they require a large amount and number of communication proportional to the number of multiplications in the operations (which is not the case with other secret sharing-based MPCs). In this paper, we propose RSSS-based three-party computation protocols for modular exponentiation, which is one of the most popular algebraic operations, on the case where the base is public and the exponent is private. Our proposed schemes are simple and efficient in both of the asymptotic and practical sense. On the asymptotic efficiency, the proposed schemes require O(n)-bit communication and O(1) rounds,where n is the secret-value size, in the best setting, whereas the previous scheme requires O(n²)-bit communication and O(n) rounds. On the practical efficiency, we show the performance of our protocol by experiments on the scenario for distributed signatures, which is useful for secure key management on the distributed environment (e.g., distributed ledgers). As one of the cases, our implementation performs a modular exponentiation on a 3,072-bit discrete-log group and 256-bit exponent with roughly 300ms, which is an acceptable parameter for 128-bit security, even in the WAN setting.

Paral and Devadas introduced a simple key generation scheme with a physically unclonable function (PUF) that requires no error correction, e.g., by using a fuzzy extractor. Their scheme, called a pattern matching key generation (PMKG) scheme, is based on pattern matching between auxiliary data, assigned at the enrollment in advance, and a substring of PUF output, to reconstruct a key. The PMKG scheme repeats a round operation, including the pattern matching, to derive a key with high entropy. Later, to enhance the efficiency and security, a circular PMKG (C-PMKG) scheme was proposed. However, multiple round operations in these schemes make them impractical. In this paper, we propose a single-round circular PMKG (SC-PMKG) scheme. Unlike the previous schemes, our scheme invokes the PUF only once. Hence, there is no fear of information leakage by invoking the PUF with the (partially) same input multiple times in different rounds, and, therefore, the security consideration can be simplified. Moreover, we introduce another hash function to generate a check string which ensures the correctness of the key reconstruction. The string enables us not only to defeat manipulation attacks but also to prove the security theoretically. In addition to its simple construction, the SC-PMKG scheme can use a weak PUF like the SRAM-PUF as a building block if our system is properly implemented so that the PUF is directly inaccessible from the outside, and, therefore, it is suitable for tiny devices in the IoT systems. We discuss its security and show its feasibility by simulations and experiments.

In secret image sharing (SIS) schemes, a secret image is shared among a set of n images called stego-images. Each stego-image is preserved by a participant. In the recovery stage, at least k out of n stego-images are required to obtain the secret image, while k−1 cannot reveal the secret in the sense of perfect secrecy. Hence, SIS guarantees long-term security. However, as the longer the stego-images remain stored, the higher is the probability of being vulnerable against steganalysis. To resolve this issue, this paper proposes the use of proactive secret sharing in an SIS scheme (P-SIS). P-SIS allows the stego-images to be renewed frequently while these are stored, without changing both cover and secret images. However, direct implementation of a proactive SIS requires more embedding rate (ER), causing high steganalysis accuracy detection and loss of quality in the stego-images. Our proposal addresses this issue and presents the combination of a (k, L, n)-threshold ramp secret sharing scheme and least significant bit matching (LSBM) steganography to reduce the steganalysis accuracy detection. The results of the evaluation show effectiveness of the proposal in terms of good quality of the stego-images, accurate recovery of the secret, and reduce the ER. Note that, despite the extensive research of SIS presented until now, only a few previous work is found on steganalysis in SIS. Not only constructing P-SIS scheme, but we also experimented the tolerance of the proposed P-SIS scheme against stganalysis in this paper. As a result, it is shown that the proposed scheme can withstand steganalysis based on machine learning (i.e., based on subtractive pixel adjacency matrix, SPAM).

This paper analyzes the formalizations of information-theoretic security for the fundamental primitives in cryptography: symmetric-key encryption and key agreement. Revisiting the previous results, we can formalize information-theoretic security using different methods, by extending Shannon's perfect secrecy, by information-theoretic analogues of indistinguishability and semantic security, and by the frameworks for composability of protocols. We show the relationships among the security formalizations and obtain the following results. First, in the case of encryption, there are significant gaps among the formalizations, and a certain type of relaxed perfect secrecy or a variant of information-theoretic indistinguishability is the strongest notion. Second, in the case of key agreement, there are significant gaps among the formalizations, and a certain type of relaxed perfect secrecy is the strongest notion. In particular, in both encryption and key agreement, the formalization of composable security is not stronger than any other formalizations. Furthermore, as an application of the relationships in encryption and key agreement, we simultaneously derive a family of lower bounds on the size of secret keys and security quantities required under the above formalizations, which also implies the importance and usefulness of the relationships.

Physically Unclonable Function (PUF) is a cryptographic primitive that is based on physical property of each entity or Integrated Circuit (IC) chip. It is expected that PUF be used in security applications such as ID generation and authentication. Some responses from PUF are unreliable, and they are usually discarded. In this paper, we propose a new PUF-based authentication system that exploits information of unreliable responses. In the proposed method, each response is categorized into multiple classes by its unreliability evaluated by feeding the same challenges several times. This authentication system is named Q-class authentication, where Q is the number of classes. We perform experiments assuming a challenge-response authentication system with a certain threshold of errors. Considering 4-class separation for 4-1 Double Arbiter PUF, it is figured out that the advantage of a legitimate prover against a clone is improved form 24% to 36% in terms of success rate. In other words, it is possible to improve the tolerance of machine-learning attack by using unreliable information that was previously regarded disadvantageous to authentication systems.

In general, conventional Arbiter-based Physically Unclonable Functions (PUFs) generate responses with low unpredictability. The N-XOR Arbiter PUF, proposed in 2007, is a well-known technique for improving this unpredictability. In this paper, we propose a novel design for Arbiter PUF, called Double Arbiter PUF, to enhance the unpredictability on field programmable gate arrays (FPGAs), and we compare our design to conventional N-XOR Arbiter PUFs. One metric for judging the unpredictability of responses is to measure their tolerance to machine-learning attacks. Although our previous work showed the superiority of Double Arbiter PUFs regarding unpredictability, its details were not clarified. We evaluate the dependency on the number of training samples for machine learning, and we discuss the reason why Double Arbiter PUFs are more tolerant than the N-XOR Arbiter PUFs by evaluating intrachip variation. Further, the conventional Arbiter PUFs and proposed Double Arbiter PUFs are evaluated according to other metrics, namely, their uniqueness, randomness, and steadiness. We demonstrate that 3-1 Double Arbiter PUF archives the best performance overall.

Physically unclonable functions (PUFs) are expected to provide a breakthrough in anti-counterfeiting devices for secure ID generation and authentication, etc. Factory-manufactured PUFs are generally more secure if the number of outputs (the variety of responses) is larger (e.g., a 256-bit full-entropy response is more secure than a 128-bit response). In Yamamoto et al. (J. Cryptogr. Eng. 3(4):197–211, 2013), we presented a latch-based PUF structure, which enhances the variety of responses by utilizing the location information of the RS (Reset-Set) latches outputting random numbers. We confirmed the effectiveness of this method using two kinds of different Xilinx FPGA chips: Spartan-3E and Spartan-6. In this paper, we propose a novel method of further enhancing the variety of responses while maintaining the reliability of responses, i.e., consistency over repeated measurements. The core idea in this method is to effectively utilize the information on the proportion of `1’s in the random number sequence output by the RS latches. This proportion information is determined during the manufacturing process, making it relatively stable and reliable once PUFs are manufactured. We estimated the variety of responses generated by the PUFs to which the proposed method was applied. According to our experiment with 73 ASIC chips fabricated by a 0.18-㎛ CMOS process, latch-based PUFs with 256 RS latches can improve the variety of responses to as much as 2³⁷⁹. This is much larger than 2²²⁰ for conventional methods, and 2³¹⁴ for our previous method presented in Yamamoto et al., (J. Cryptogr. Eng. 3(4):197–211, 2013). The average error rate (reliability) of responses is only 0.064 when both temperature and voltage are changed to −20∼60℃ and 1.80 ± 0.15V, respectively. Our proposed PUF enhances the variety of responses dramatically while maintaining reliability.

クロック間衝突を用いた電磁波解析 (CC-EMA)は2クロック間のデータ衝突を漏洩モデルとする新たなサイドチャネル解析 (SCA)である．CC-EMAでは，クロック間衝突時の磁界強度が極めて小さくなること利用し解析を行う．一方で，相関電磁波解析 (CEMA)のようなハミング距離 (HD)を漏洩モデルに利用するSCAでは2クロック間のデータのHDと消費電力に相関があると仮定している．本論文では，クロック間衝突を漏洩モデルとしたSCAとHDを漏洩モデルとしたSCAが鍵復元時に必要とする波形数をシミュレーションを用いて比較する．また，並列実装AES暗号ハードウェアの最終ラウンドでは，鍵の値によりS-box回路でのクロック間衝突の発生頻度が変化する．本論文では，鍵の値を変化させ，クロック間衝突の発生頻度の差とSCAコストの関係を明らかにする．最後に，並列実装AES暗号ハードウェアにはCC-EMAに対して弱い鍵が存在することを示す．

Secret data in embedded devices can be revealed by injecting computational faults using the fault analysis attacks.The fault analysis researches on a cryptographic implementation by far first assumed a certain fault model, and then discussed the key recovery method under some assumptions. We note that a new remote-fault injection method has emerged, which is threatening in practice. Due to its limited accessibility to cryptographic devices, the remote-fault injection, however, can only inject uncertain faults. In this surroundings, this paper gives a general strategy of the remote-fault attack on the AES block cipher with a data set of faulty ciphertexts generated by uncertain faults. Our method effectively utilizes all the information from various kinds of faults, which is more realistic than previous researches. As a result, we show that it can provide a decent success probability of key identification even when only a few intended faults are available among 32 millions fault injections.

Physical Unclonable Functions (PUFs) are expected to represent an important solution for secure ID generation and authentication etc. In general, manufactured PUFs are considered to be more secure when the pattern of outputs (the variety of responses) is larger, i.e., the response bit length is longer (e.g., 192-bit response is more secure than 128-bit one). However, the actual bit length is reduced because some response bits are inconsistent (random) for repeated measurements, which are regarded as unnecessary for ID generation and discarded. Latch-based PUFs with N RS latches, for example, generate ideally 2^N responses depending on binary values output from RS latches (0/1). However, some RS latches output random responses which are inconsistent and cannot be used for reliable ID generation, so the variety of responses becomes smaller than 2^N. In this paper, we propose a novel Latch-based PUF structure, which outputs larger variety of responses by utilizing location information of the RS latches outputting the random responses. Differently from random responses themselves, this location information is determined during a manufacturing process, so almost fixed once PUFs are manufactured. The proposed PUF generates 3^N≈ 2^1.58N responses by considering random responses as the third stable value: using ternary values (0/1/random). We estimate the variety of responses generated by the proposed PUFs. According to our experiment with 40 FPGAs, a Latch-based PUF with 128 RS latches can improve it from 2¹¹⁶ to 2^192.7, this being maximized when the 128 latches outputs 0s, 1s, or random outputs with equal probability. We also show the appropriate RS latch structure for satisfying this condition, and validate it using two kinds of different Xilinx FPGAs: Spartan-3E and Spartan-6. The average error rate of responses is only 5.3% when the core voltage is changed within the rated voltage range of the FPGAs. Our proposed PUF using ternary values enhances dramatically the variety of responses while keeping the reliability.

In this paper, we discuss coding theorems on a (2,2)–threshold scheme in the presence of an opponent who impersonates one of the two shareholders in an asymptotic setup. We consider a situation where n secrets S_n from a memoryless source is blockwisely encoded to two shares and the two shares are decoded to S_n with permitting negligible decoding error. We introduce correlation level of the two shares and characterize the minimum attainable rates of the shares and a uniform random number for realizing a (2,2)–threshold scheme that is secure against the impersonation attack by an opponent. It is shown that, if the correlation level between the two shares equals to an ℓ≥0, the minimum attainable rates coincide with H(S)+ℓ, where H(S) denotes the entropy of the source, and the maximum attainable exponent of the success probability of the impersonation attack equals to ℓ. We also give a simple construction of an encoder and a decoder using an ordinary (2,2)–threshold scheme where the two shares are correlated and attains all the bounds.

Visual Cryptography (VC), proposed by Naor and Shamir in 1994, is a variation of the conventional secret sharing scheme. In VC, instead of a numerical secret key, a secret image is shared among participants in the form of images called shares. Each participant possesses his own share which cannot reveal the secret image being alone, making it necessary to stack more than one share of a qualified participant in order to reveal the secret image. Thus in VC the stacking of shares is equivalent to the decryption process, where neither extra computations nor previous knowledge are required to reveal the secret image. Until now some important VC schemes, such as the (k,n)-VC scheme, the general access structure for VC and the extended VC (EVC), have been proposed. Unfortunately all schemes can be cheated, if one or more participants try to generate their fake shares to force the revealed secret image to be a faked one. In this paper, we propose a cheating prevention VC scheme, in which the shares can be identified and authenticated using the EVC scheme and watermarking techniques. In the proposed VC scheme, the share of each participant can be identified by its meaningful appearance instead of noise-like image used in the conventional VC scheme. For the purpose of authentication of each share two binary watermark images are encrypted using shift operation. Before the secret image is revealed, the validation of the shares must be carried out, extracting two watermark images. If they can be extracted correctly, the revealed secret image is considered as authentic; otherwise it is determined as a faked one. The simulation results show the desirable performance of the proposed EVC scheme.

We propose a weak security notion for visual secret sharing (VSS) schemes. Under such a weak security notion, VSS schemes are designed to be secure against attackers' eyesight, but are not unconditionally secure, in general. In this paper, we theoretically discuss the relation between unconditionally secure (US) and weakly secure (WS) VSS schemes and present two constructions of WS-VSS schemes for color images. We show that WS-VSS schemes can achieve clearer color reproduced images with a smaller pixel expansion compared to those using US-VSS schemes, while we clarify that the basis matrices in both types of VSS schemes for black-white binary images are the same. These results suggest that the proposed VSS schemes can be regarded as ramp (or nonperfect) VSS schemes for color secret images.

This paper presents a comprehensive analysis of differential fault analysis (DFA) attacks on the Advanced Encryption Standard (AES) from an information-theoretic perspective. Injecting faults into cryptosystems is categorized as an active at tack where attackers induce an error in operations to retrieve the secret internal information, e.g., the secret key of ciphers. Here, we consider DFA attacks as equivalent to a special kind of passive attack where attackers can obtain leaked information without measurement noise. The DFA attacks are regarded as a conversion process from the leaked information to the secret key. Each fault model defines an upper bound for the amount of leaked information. The optimal DFA attacks should be able to exploit fully the leaked information in order to retrieve the secret key with a practical level of complexity. This paper discusses a new DFA methodology to achieve the optimal DFA attack by deriving the amount of the leaked information for various fault models from an information-theoretic perspective. We review several previous DFA at tacks on AES variants to check the optimality of their attacks. We also propose improved DFA attacks on AES-192 and AES-256 that reach the theoretical limits.

It is known that for any general access structure, a secret sharing scheme (SSS) can be constructed from an (m,m)-threshold scheme by using the so-called cumulative map or from a (t,m)-threshold SSS by a modified cumulative map. However, such constructed SSSs are not efficient generally. In this paper, a new method is proposed to construct a SSS from a (t,m)-threshold scheme for any given general access structure. In the proposed method, integer programming is used to derive the optimal (t,m)-threshold scheme and the optimal distribution of the shares to minimize the average or maximum size of the distributed shares to participants. From the optimality, it can always attain lower coding rate than the cumulative maps because the cumulative maps cannot attain the optimal distribution in many cases. The same method is also applied to construct SSSs for incomplete access structures and/or ramp access structures.

In this paper, a method is proposed to construct a visual secret sharing (VSS) scheme for multiple secret images in which each share can be rotated with 180 degrees in decryption. The proposed VSS scheme can encrypt more number of secret images compared with the normal VSS schemes. Furthermore, the proposed technique can be applied to the VSS scheme that allows to turn over some shares in decryption. From the theoretical point of view, it is interesting to note that such VSS schemes cannot be obtained from so-called basis matrices straightforwardly.

Ramp secret sharing (SS) schemes can be classified into strong ramp SS schemes and weak ramp SS schemes. The strong ramp SS schemes do not leak out any part of a secret explicitly even in the case that some information about the secret leaks out from some set of shares, and hence, they are more desirable than the weak ramp SS schemes. In this paper, it is shown that for any feasible general access structure, a strong ramp SS scheme can be constructed from a partially decryptable ramp SS scheme, which can be considered as a kind of SS scheme with plural secrets. As a byproduct, it is pointed out that threshold ramp SS schemes based on Shamir's polynomial interpolation method are not always strong.

Quantum secret sharing schemes encrypting a quantum state into a multipartite entangled state are treated. The lower bound on the dimension of each share given by Gottesman [Phys. Rev. A 61, 042311 (2000)] is revisited based on a relation between the reversibility of quantum operations and the Holevo information. We also propose a threshold ramp quantum secret sharing scheme and evaluate its coding efficiency.

In this paper, a new method is proposed to construct a visual secret sharing scheme with a general access structure for plural secret images. Although the proposed scheme can be considered as an extension of Droste's method that can encode only black-white images, it can encode plural gray-scale and/or color secret images.

In this paper, a method is proposed to construct an n-out-of-n visual secret sharing scheme for gray-scale images, for short an (n, n)-VSS-GS scheme, which is optimal in the sense of contrast and pixel expansion, i.e., resolution. It is shown that any (n, n)-VSS-GS scheme can be constructed based on the so- called polynomial representation of basis matrices treated in (15), (16). Furthermore, it is proved that such construction can attain the optimal (n, n)-VSS-GS scheme.

This paper proposed a new construction of the visual secret sharing scheme for the (n, n)-threshold access structure applicable to color images. The construction uses matrices with n rows that can be identifield with homogeneous polynomials of degree n. It is shown that, if we find a set of homogeneous polynomials of degree n satisfying a certain system of simultaneous partial differential equations, we can construct a visual secret sharing scheme for the (n, n)-threshold access structure by using the matrices corresponding to the homogeneous polynomials. The construction is easily extended to the cases of the (t, n)-threshold access structure and more general access structures.

Secure lottery is a cryptographic protocol that allows multiple players to determine a winner from them uniformly at random, without any trusted third party. Bitcoin enables us to construct a secure lottery to guarantee further that the winner receives reward money from the other losers. Many existing works for Bitcoin-based lottery use deposits to ensure that honest players never be disadvantaged in the presence of adversaries. Bartoletti and Zunino (FC 2017) proposed a Bitcoin-based lottery protocol with a constant deposit, i.e., the deposit amount is independent of the number of players. However, their scheme is limited to work only when the number of participants is a power of two. We tackle this problem and propose a lottery protocol applicable to an arbitrary number of players based on their work. Furthermore, we generalize the number of winners; namely, we propose a secure (k, n)- lottery protocol. To the best of our knowledge, this is the first work to address Bitcoin-based (k, n)-lottery protocol. Notably, our protocols maintain the constant deposit property.

Card-based cryptography refers to a secure computation with physical cards, and the number of cards and shuffles measures the efficiency of card-based protocols. This paper proposes new card-based protocols for any Boolean circuits with only a single shuffle. Although our protocols rely on Yao’s garbled circuit as in previous single-shuffle card-based protocols, our core construction idea is to encode truth tables of each Boolean gate with fewer cards than previous works while being compatible with Yao’s garbled circuit. As a result, we show single-shuffle card-based protocols with six cards per gate, which are more efficient than previous single-shuffle card-based protocols.

Dynamic searchable symmetric encryption (SSE) realizes efficient update and search operations for encrypted databases, and there has been an increase in this line of research in the recent decade. Dynamic SSE allows the leakage of insignificant information to ensure efficient search operations, and it is important to understand and identify what kinds of information are insignificant. In this paper, we propose an efficient dynamic SSE scheme Laura under the small leakage, which leads to appealing security requirements such as forward privacy, (Type- II) backward privacy, and result hiding. Laura is constructed based on Aura (NDSS 2021) and is almost as efficient as Aura while only allowing less leakage than Aura. We also provide experimental results to show the concrete efficiency of Laura.

The two sheriffs problem is the following problem. There are two sheriffs, and each of them has their own list of suspects. Assuming that these lists are the result of a proper investigation, we can say that a culprit is the intersection of them even if the sheriffs do not know who the culprit is. Now, they wish to identify the culprit through an open channel, i.e., to compute the intersection of two lists, without letting an eavesdropper know the culprit who observed all communications. This cryptographic problem was proposed by Beaver et al., and a combinatorial solution using a bipartite graph was proposed. In this paper, we propose a formulation of the two sheriffs problem by introducing a secrecy evaluation based on the eavesdropper’s attack success probability. Furthermore, we propose an improved version of Beaver et al.’s protocol that an arbitrary number of players can execute and has less attack success probability.

Cyber attacks on control system communication are increasing. In information systems, a lot of security counter-measure focusing on the distribution of communication packets has been studied so far. Such attack detection methods evaluate normal and abnormal packets based on the likelihood and the relative entropy. Whether the methods for information systems are also effective for control systems is another question. Then, this paper conducts attack detection experiments based on the likelihood and the relative entropy of DoS and spoofing attacks on Modbus TCP communication used in industrial control systems.

Internet of things (IoT) systems consist of many devices that send their sensor data to cloud servers. Cryptographic authentication is essential for maintaining the consistency of these systems, and lightweight authentication in particular is required because most IoT devices are resource-constrained. Physically unclonable functions (PUF) are promising tools for protecting such devices from cyber-attacks. It can naturally generate a unique but noisy (i.e., erroneous) key for a device without implementing costly secure key storage in the device. However, a costly error correction technique is required to remove the noise. In this paper, we propose a lightweight authentication scheme with a noisy key (i.e., an uncorrected key) {\em naturally} derived from a PUF. The security of our scheme is based on a combinatorial problem with small noise. We also discuss its security and feasibility.

Card-based cryptography is a cryptographic technique that realizes Multi-Party Computation (MPC) using physical cards. Although various protocols have been studied in card-based cryptography, there is no research on card-based Private Set Intersection (PSI). PSI is one of the well-studied MPC protocols which enables parties to compute the set intersection while keeping their data sets secret. This paper focuses on PSI in card-based cryptography for the first time, and shows several card-based PSI protocols. In card-based cryptography, there are two operation models: one assumes that all operations are performed publicly, and the other allows private operations. We propose PSI protocols under each model. We first show that PSI can be realized under each model by utilizing the existing card-based AND protocols. Furthermore, we propose more efficient PSI protocols than the PSI protocols based on AND protocols under each model.

Multi-party private set intersection (PSI) allows parties to compute the set intersection of their private data sets without revealing outside of the intersection. Kolesnikov et al. (ACM CCS 2017) introduced Oblivious Programmable Pseudorandom Function (OPPRF) and showed a practical multi-party PSI protocol secure for arbitrary collusion of parties under the semi-honest model. We point out that their protocol contains some overkill OPPRFs for the required functionality. On the basis of this finding, we improve their PSI protocol by replacing these OPPRFs with more lightweight procedures. More precisely, we introduce a new functionality called Extended Programmable Pseudorandom Function (EPPRF). It provides functionality that excludes an expensive public-key operation from the OPPRF. We show that a multi-party PSI protocol can be realized even if the OPPRFs are replaced with EPPRFs. As a result of the replacement, we reduce the number of public-key operations n-1 times from Kolesnikov et al.'s protocol, where n is the number of parties.

Dynamic searchable symmetric encryption (SSE) enables clients to update and search encrypted data stored on a server and provides efficient search operations instead of leakages of inconsequential information. The amount of permitted leakage is a crucial factor of dynamic SSE; more leakage allows us to design an efficient scheme, while leakage attacks tell us that the leakage has a real-world impact. Leakage-abuse attacks (NDSS 2012) and subsequent works suggest that dynamic SSE schemes should not unnecessarily reveal extra information during the search procedure, and in particular, file-injection attacks (USENIX Security 2016) showed that forward privacy, which restricts the leakage during the addition procedure, is a vital security notion for dynamic SSE. In this paper, we propose a new dynamic SSE scheme with a good balance of efficiency and security levels; our scheme achieves both high efficiency and forward-privacy and only requires the decent leakage, i.e., only allows the leakage of search and access patterns during search operations. Specifically, we first show there is still no such scheme by uncovering a flaw in the security proof of Etemad et al.'s scheme (PoPETs 2018) and showing that extra leakage is required to fix it. We then propose the first forward-private dynamic SSE scheme that only requires symmetric-key primitives and the standard, decent leakage to prove the security. Although the client's information is slightly larger than existing schemes, our experimental results show that our scheme is comparable to Etemad et al.'s scheme, which is the most-efficient-ever scheme with forward privacy, in terms of efficiency.

A key recovery algorithm using parts of the key schedules is proposed for evaluating the threat of probing attack. Suppose that we have an information leakage sensor, and we can detect a leak (attacked) point where an attacker makes electrical/physical contact with a laser, a probe, etc. We assume that the attacked bits (leaked bits) are completely known to the attacker, whereas the other non-attacked bits are not leaked at all. We also assume that each bit leaks with a constant probability. Our key recovery algorithm is constructed by modifying the pruning phase that for cold boot attacks proposed by Tsow. Experimental result shows that, using our algorithm, more than 15% leakage recovers the key with almost probability 1, whereas less than 10% is recovered with small probability close to 0.

Card-based protocol is a multi-party computation using cards. The card-based protocol using operations called private operation has an advantage that the number of cards and the number of times of communication are smaller than the card-based protocol using operations called shuffle. However, there is a disadvantage that private operation allows dishonest players to perform malicious behaviors. Although the method to detect malicious behaviors in private operations was proposed, the method was available only in committed-format protocols, where inputs and outputs are represented by a pair of cards called commitment. In this paper, we show how to detect malicious behaviors in non-committed-format protocol with an example of a three-input majority voting protocol using private operations. Our majority voting protocol requires a smaller number of cards than the minimum number of cards required for committed-format protocols.

A private PEZ protocol is a variant of secure multi-party computation performed using a (long) PEZ dispenser. The original paper by Balogh et al. presented a private PEZ protocol for computing an arbitrary function with n inputs. This result is interesting, but no follow-up work has been presented since then, to the best of our knowledge. We show herein that it is possible to shorten the initial string (the sequence of candies filled in a PEZ dispenser) and the number of moves (a player pops out a specified number of candies in each move) drastically if the function is symmetric. Concretely, it turns out that the length of the initial string is reduced from O(2ⁿ!) for general functions in Balogh et al.’s results to O(n·n!)$ for symmetric functions, and 2ⁿ moves for general functions are reduced to n² moves for symmetric functions. Our main idea is to utilize the recursive structure of symmetric functions to construct the protocol recursively. This idea originates from a new initial string we found for a private PEZ protocol for the three-input majority function, which is different from the one with the same length given by Balogh et al. without describing how they derived it.

A multiple assignment scheme (MAS) is a method to construct secret sharing schemes (SSSs) for general access structures. There are MASs using threshold and ramp SSSs. The paper proposes new MASs using ideal SSSs realizing compartmented access structures and those using SSSs realizing multi-level access structures. Since the ideal SSSs realizing compartmented access structures and SSSs realizing multi-level access structures are natural generalizations of threshold and ramp SSSs, respectively, the new MASs cannot be less efficient than those using threshold or ramp SSSs.

The threat of physical attacks on crypto devices has been reported. Attack efficiency is determined by the attacker's ability to measure the physical information leaked from the device, for example, side-channel information, or to control physical disturbance against a device, for example, laser fault injection. Intuitively, the higher the ability of the attacker, the more information can be retrieved. In order to assess attack efficiency, this paper focuses on the 1-bit probing attack, which is one of the strongest attacks in a real-world setting. In the 1-bit probing attack, the attacker can observe a specific 1-bit intermediate value at a certain timing in the cryptographic operation. Firstly, we explain previous studies on an abstraction model for physical attacks. Secondly, we introduce a new model with an ideal property with regard to the probing attacks. Finally, we compare the attack efficiency of seven reported block ciphers with the proposed model value.

Private operations (private permutations) were independently introduced by Nakai et al. and Marcedone et al. for implementing card-based cryptographic protocols efficiently. Recently, Nakai et al. showed that, if the private operations are available, secure computations of AND and OR operations for two inputs can be realized simultaneously by using four cards, and the protocol is applied to four-card majority voting protocol with three inputs. In this paper, it is shown that only three cards are sufficient to construct the majority voting protocol with three inputs. Specifically, we propose two constructions of three-input majority voting protocols. First, assuming that players are allowed to announce their outputs, we show that one card can be reduced from Nakai et al.'s protocol without any additional private operations and communications. Our second construction requires two more private operations and communications, whereas it removes the assumption on announcement from the first construction.

The card-based cryptographic protocol is a variant of multi-party computation that enables us to compute a certain function securely by using playing cards. In existing card-based cryptographic protocols, a special operation of cards called a shuffle is used to achieve the information-theoretic security. Recently, card-based cryptographic protocols have been reconsidered from the viewpoint of multi-party computations. In this direction, a new model of card-based cryptographic protocol including a new assumption called Private Permutations (PP, for short) is introduced and succeeds in constructing efficient protocols for the millionaires’ protocol. In this paper, we construct efficient card-based cryptographic OR and XOR protocols based on the existing AND protocol. Furthermore, by unifying AND and OR protocols, it is shown that a majority voting protocol with three inputs is efficiently obtained. Our construction requires only four cards thanks to PPs, whereas the previous work requires eight cards.

We propose several efficient card-based cryptographic protocols for the millionaires’ problem by introducing a new operation called Private Permutation (PP) instead of the shuffle used in existing card-based cryptographic protocols. Shuffles are useful randomization techniques for designing card-based cryptographic protocols for logical gates, and this approach seems to be almost optimal. This fact, however, implies that there is room for improvements if we do not use logical gates as building blocks for secure computing, and we show that such an improvement is actually possible for the millionaires’ problem. Our key technique, PP, is a natural randomization operation for permuting a set of cards behind the player’s back, and hence, a shuffle can be decomposed into two PPs with one communication between them. Thus PP not only allows us to transform Yao’s seminal protocol into a card-based cryptographic protocol, but also enables us to propose entirely novel and efficient protocols by securely updating bitwise comparisons between two numbers. Furthermore, it is interesting to remark that one of the proposed protocols has a remarkably deep connection to the well-known logical puzzle known as “The fork in the road”.

Searchable symmetric encryption (SSE) enables a user to outsource a collection of encrypted documents in the cloud and to perform keyword searching without revealing information about the contents of the documents and queries. On the other hand, the information (called search pattern) whether or not the same keyword is searched in each query is always leaked in almost all previous schemes whose trapdoors are generated deterministically. Therefore, reducing the search pattern leakage is outside the scope of almost all previous works. In this paper, we tackle to the leakage problem of search pattern, and study methodology to reduce this leakage. Especially, we discuss that it might be possible to reduce the search pattern leakage in cases where a trapdoor does not match any encrypted document. We also point out that the same search pattern is leaked regardless of probabilistic or deterministic generation of trapdoors when the user searches using a keyword which has already searched and matched a certain encrypted document. Thus, we further aim to construct SSE schemes with fast “re-search” process, in addition to reducing the search pattern leakage. In order to achieve the above, we introduce a new technique “trapdoor locked encryption” which can extract a deterministic trapdoor from a probabilistic trapdoor, and then propose a new SSE scheme which can generate trapdoors probabilistically and reduce the search pattern leakage. Our scheme is constructed by applying our technique to the well-known and influential scheme SSE-2 (ACM CCS 2006) and can be proved secure in the standard model.

In searchable symmetric encryption (SSE), adding documents to a database is an indispensable functionality in real situations, and there are two approaches for executing the process: One approach is to update the encrypted index, and the other is to generate a new encrypted index. The former approach is called dynamic SSE, which has been extensively studied recently due to its importance. The latter approach has an advantage such that it can be directly applied to any existing SSE scheme without degrading its original functionalities, but previous methods are not satisfactory from a viewpoint of security, storage size, or efficiency. In this paper, we propose a simple document adding method that resolve the problem occurred in the latter approach. Our method is quite generic, and therefore can be applied to any existing SSE scheme (e.g. non-dynamic one with useful functionalities). Our key idea is to utilize publicly available information and hash chains in construction of encrypted indexes. In order to exhibit the ability of our method, we present a concrete scheme which is led by applying our method to the well-known and influential scheme SSE-2 (ACM CCS 2006). Thanks to the simplicity of our method, the scheme can be easily proved secure under a naturally generalized setting of the most widely used security model.

Fake integrated circuit (IC) chips are in circulation on the market, which is considered a serious threat in the era of the Internet of Things (IoTs). A physically unclonable function (PUF) is expected to be a fundamental technique to separate the fake IC chips from genuine ones. Recently, the arbiter PUF (APUF) and its variants are intensively researched aiming at using for a secure authentication system. However, vulnerability of APUFs against machine-learning attacks was reported. Upon the situation, the double arbiter PUF (DAPUF), which has a tolerance against support vector machine (SVM)-based machine-learning attacks, was proposed as another variant of APUF in 2014. In this paper, we perform a security evaluation for authentication systems using APUF and its variants against Deep-learning (DL)-based attacks. DL has attracted attention as a machine-learning method that produces better results than SVM in various research fields. Based on the experimental results, we show that these DAPUFs could be used as a core primitive in a secure authentication system if setting an appropriate threshold to distinguish a legitimate IC tags from fake ones.

Constructions of symmetric-key encryption with guessing secrecy are discussed. In the previous works, only a construction of symmetric-key encryption with average guessing secrecy is proposed for one-bit plaintexts. In this paper, we analyze a symmetric-key encryption with average guessing secrecy through OTP (one-time pad) constructions for a wide class of probability distributions of plaintexts and keys. As a result, we show a necessary and sufficient condition that such class of distributions satisfies average guessing secrecy in OTP constructions. On the other hand, we prove that optimal guessing secrecy is essentially equivalent to perfect secrecy under several natural restrictions. Therefore, only average guessing secrecy is meaningful for considering guessing secrecy other than perfect secrecy.

Low uniqueness and vulnerability to machine-learning attacks are known as two major problems of Arbiter-Based Physically Unclonable Function (APUF) implemented on FPGAs. In this paper, we implement Double APUF (DAPUF) that duplicates the original APUF in order to overcome the problems. From the experimental results on Xilinx Virtex-5, we show that the uniqueness of DAPUF becomes almost ideal, and the prediction rate of the machine-learning attack decreases from 86% to 57%.

In auction theory, little attention has been paid to a situation where the tie-break occurs because most of auction properties are not affected by the way the tie-break is processed. Meanwhile, in secure auctions where private information should remain hidden, the information of the tie can unnecessarily reveal something that should remain hidden. Nevertheless, in most of existing secure auctions, ties are handled outside the auctions, and all the winning candidates or only the non-tied partial bidders are identified in the case of ties, assuming that a subsequent additional selection (or auction) to finalize the winners is held publicly. However, for instance, in the case of the (M+1) st-price auction, the tied bidders in the (M+1)st-price need to be identified for such a selection, which implies that their bids (unnecessary private information) are revealed. Hence it is desirable that secure auctions reveal neither the existence of ties nor the losing tied bidders.
To overcome these shortcomings, we propose a secure (M+1)st-price auction protocol with automatic tie-breaks and no leakage of the tie information by improving the bit-slice auction circuit without increasing much overhead.

A new model for a Client-Server Communication (CSC) system satisfying information theoretic security is proposed, and its fundamental properties are discussed. Our CSC allows n users to upload their respective messages to a server securely by using symmetric key encryptions with their own keys, and all ciphertexts are decrypted by the server. If we require all messages to be perfectly secure in CSC against the corrupted clients and adversaries without any keys, it is proved that a one time pad or more inefficient encryption must be used for each communication link between a client and the server. This means that, in order to realize more efficient CSC, it is necessary to leak out some information of each message. Based on these observations, we introduce a new model for such a secure CSC formally, and discuss its fundamental properties. In addition, we propose the optimal construction of CSC under several constraints on security parameters called security rates.

Cheating on a (2, n)-threshold visual secret sharing (VSS) schemes is discussed under a realistic scenario. Horng et al. pointed out an ordinary VSS scheme is vulnerable against a certain kind of cheating, and they proposed a countermeasure against it. In their work, so-called Kerckhoffs's principle and availability of computing power are implicitly assumed in cheating detection. Namely, this work follows a scenario where a victim knows basis matrices and can use computational ability in cheating detection. Under this scenario, Horng et al. showed that their countermeasure attains negligible success probability of generating the victim's share. However, recalling the fact that the decryption of VSS schemes does not depend on computations but depends on human visual system, we can naturally assume a realistic scenario where the victim does not know the basis matrices and has no computing power. Under this scenario, we show that the cheaters can make the victim recover an arbitrary forged secret image in Horng et al.'s countermeasure with probability 1.

Arbiter-based Physically Unclonable Function (PUF) is one kind of the delay-based PUFs that use the time difference of two delay-line signals. One of the previous work suggests that Arbiter PUFs implemented on Xilinx Virtex-5 FPGAs generate responses with almost no difference, i.e. with low uniqueness. In order to overcome this problem, Double Arbiter PUF was proposed, which is based on a novel technique for generating responses with high uniqueness from duplicated Arbiter PUFs on FPGAs. It needs the same costs as 2-XOR Arbiter PUF that XORs outputs of two Arbiter PUFs. Double Arbiter PUF is different from 2-XOR Arbiter PUF in terms of mode of operation for Arbiter PUF: the wire assignment between an arbiter and output signals from the final selectors located just before the arbiter. In this paper, we evaluate these PUFs as for uniqueness, randomness, and steadiness. We consider finding a new mode of operation for Arbiter PUF that can be realized on FPGA. In order to improve the uniqueness of responses, we propose 3-1 Double Arbiter PUF that has another duplicated Arbiter PUF, i.e. having 3 Arbiter PUFs and output 1-bit response. We compare 3-1 Double Arbiter PUF to 3-XOR Arbiter PUF according to the uniqueness, randomness, and steadiness, and show the difference between these PUFs by considering the mode of operation for Arbiter PUF. From our experimental results, the uniqueness of responses from 3-1 Double Arbiter PUF is approximately 50%, which is better than that from 3-XOR Arbiter PUF. We show that we can improve the uniqueness by using a new mode of operation for Arbiter PUF.

Fundamental results are clarified with respect to secret sharing schemes (SSSs) in which security and each share size are measured by (conditional) min-entropies. We first formalize a unified framework of SSS based on conditional Rényi entropies, which includes SSSs based on Shannon and min entropies etc., as special cases. By deriving the lower bound of share sizes in terms of Rényi entropies, we can derive the lower bounds of share sizes measured by Shannon and min entropies in a unified manner. Then, we focus on the existence of SSSs based on min-entropies for several important settings. In the traditional SSSs based on (conditional) Shannon entropies, it is known that; (1) there exists a SSS for arbitrary secret information and arbitrary access structure, and; (2) for every integers k and n (k ≤ n), the ideal (k,n)-threshold scheme exists when secret information is uniform or deterministic. Corresponding to these results, we clarify the following: (1') there exists a SSS for arbitrary binary secret information and arbitrary access structure, and; (2') for every integers k and n (k ≤ n), the ideal (k,n)-threshold scheme exists even if the secret is neither uniform nor deterministic.

In smart grid systems, security and privacy prevention is great concerns. The suppliers of the power in smart grid systems demand to know the consumption of each customer for correctly calculating billing price and the total amount of consumption in a certain region for managing energy supply adopted real-time needs. On the other hand, the customer of the power desires to hide his/her own consumption profile, since it contains privacy information of the customer. However, hiding the consumption allows customers to reduce billing price. Previous privacy-preserving smart metering schemes provide only one of billing or energy management functionality, or even if both of them are achieved, these schemes cannot verify the integrity of the consumption issued by the smart meter. We propose a novel smart metering scheme that provides both of billing and energy management functionality, as well as verifiability of the integrity of total amount of the consumption or billing price.

In this paper, we study the security of AES-like permutations against the improved rebound attack proposed by Jean et al. at FSE 2012 which covers three full-active rounds in the inbound phase. The attack is very complicated and hard to verify its optimality when the state size is large and rectangle, namely the numbers of rows and columns are different. In the inbound phase of the improved rebound attack, several SuperSBoxes are generated for each of forward analysis and backward analysis. The attack searches for paired values that are consistent with all SuperSBoxes. The attack complexity depends on the order of the SuperSBoxes to be analyzed, and detecting the best order is hard. In this paper, we develop an automated complexity evaluation tool with several fast implementation techniques. The tool enables us to examine all the possible orders of the SuperSBoxes, and provides the best analysis order and complexity. We apply the tool to large block Rijndael in the known-key setting and the Grøstl-512 permutation. As a result, we obtain the first 9-round distinguisher for Rijndael-192 and Rijndael-224. It also shows the impossibility of the improved rebound attack against 9-round Rijndael-160 and 10-round Rijndael-256, and the optimality of the previous distinguisher against the 10-round Grøstl-512 permutation. Moreover, the efficiency of the improved rebound attack depends on the parameter of the ShiftRows operation. Our tool can exhaustively examine all the possible ShiftRows parameters to search for the ones that can resist the attack. We show new parameters for the Grøstl-512 permutation obtained by our tool, which can resist a 10-round improved rebound attack while the specification parameter cannot resist it.

In this article, we investigate the use of limited-birthday distinguishers to the context of hash functions. We first provide a proper understanding of the limited-birthday problem and demonstrate its soundness by using a new security notion Differential Target Collision Resistance (dTCR) that is related to the classical Target Collision Resistance (TCR) notion. We then solve an open problem and close the existing security gap by proving that the best known generic attack proposed at FSE 2010 for the limited-birthday problem is indeed the best possible method.
Moreover, we show that almost all known collision attacks are in fact more than just a collision finding algorithm, since the difference mask for the message input is usually fixed. A direct and surprising corollary is that these collision attacks are interesting for cryptanalysis even when their complexity goes beyond the 2^n/2 birthday bound and up to the 2ⁿ preimage bound, and can be used to derive distinguishers using the limited-birthday problem. Interestingly, cryptanalysts can now search for collision attacks beyond the 2^n/2 birthday bound.
Finally, we describe a generic algorithm that turns a semi-free-start collision attack on a compression function (even if its complexity is beyond the birthday bound) into a distinguisher on the whole hash function when its internal state is not too wide. To the best of our knowledge, this is the first result that exploits classical semi-free-start collisions on the compression function to exhibit a weakness on the whole hash function. As an application of our findings, we provide distinguishers on reduced or full version of several hash functions, such as RIPEMD-128, SHA-256, Whirlpool, etc.

In this paper, information theoretic cryptography is discussed based on conditional Rényi entropies. Our discussion focuses not only on cryptography but also on the definitions of conditional Rényi entropies and the related information theoretic inequalities. First, we revisit conditional Rényi entropies, and clarify what kind of properties are required and actually satisfied. Then, we propose security criteria based on Rényi entropies, which suggests us deep relations between (conditional) Rényi entropies and error probabilities by using several guessing strategies. Based on these results, unified proof of impossibility, namely, the lower bounds on key sizes are derived based on conditional Rényi entropies. Our model and lower bounds include the Shannon’s perfect secrecy, and the min-entropy based encryption presented by Dodis, and Alimomeni and Safavi-Naini at ICITS2012. Finally, a new optimal symmetric key encryption protocol achieving the lower bounds is proposed.

In this paper, we revisit previous meet-in-the-middle preimage attacks on hash functions. We firstly present a technical improvement for the existing local-collision and initial-structure techniques. With applying some equivalent transformation, we can significantly reduce the memory requirement from the original proposals. We then revisit the previous preimage attacks on MD5 and HAVAL with recent techniques. Consequently, we can improve the memory complexity of the previous preimage attack on full MD5 from 2⁴⁵ to 2¹³ and on full 4-pass HAVAL from 2⁶⁴ to 2³² . Moreover, we extend the preimage attack on 5-pass HAVAL from 151 steps to 158 steps, and present the first preimage attack with a single block message for 3-pass HAVAL.

In 2011, Li et al. proposed a series of side-channel attacks that are related to a fundamental side-channel leakage source called clockwise collision. This paper discloses the fact that hardware implementations of AES-based ciphers could have weak keys assuming that the leakage of clockwise collision is distinguishable. In order to explain this, we firstly set up an evaluation method by introducing a threshold-based distinguisher that takes an advantage of the locality of ElectroMagnetic (EM) measurements. Secondly, we discuss that the probability of clockwise collision depends on the key values and the byte positions in the AES states. Thirdly, based on practical EM measurements and mathematical analysis, we quantitatively evaluate the relationship between the probability of clockwise collision and the vulnerability to the side-channel attack. Finally, the discussion is extended to the design methodology of AES-based ciphers, i.e., the parameter selection for S-box and ShiftRows.

Physical Unclonable Functions (PUFs) are expected to represent an important solution for secure ID generation and authentication etc. In general, PUFs are considered to be more secure the larger their output entropy. However, the entropy of conventional PUFs is lower than the output bit length, because some output bits are random numbers, which are regarded as unnecessary for ID generation and discarded. We propose a novel PUF structure based on a Butterfly PUF with multiple RS latches, which generates larger entropy by utilizing location information of the RS latches generating random numbers. More specifically, while conventional PUFs generate binary values (0/1), the proposed PUF generates ternary values (0/1/random) in order to increase entropy. We estimate the entropy of the proposed PUF. According to our experiment with 40 FPGAs, a Butterfly PUF with 128 RS latches can improve entropy from 116 bits to 192.7 bits, this being maximized when the frequency of each ternary value is equal. We also show the appropriate RS latch structure for satisfying this condition, and validate it through an FPGA experiment.

This paper is concerned with several security notions for information theoretically secure encryptions defined by the variational (statistical) distance. To ensure the perfect secrecy (PS), the mutual information is often used to evaluate the statistical independence between a message and a cryptogram. On the other hand, in order to recognize the information theoretically secure encryptions and computationally secure ones comprehensively, it is necessary to reconsider the notion of PS in terms of the variational distance. However, based on the variational distance, three kinds of definitions for PS are naturally introduced, but their relations are not known. In this paper, we clarify that one of three definitions for PS with the variational distance, which is a straightforward extension of Shannon's perfect secrecy, is stronger than the others, and the weaker two definitions of PS are essentially equivalent to the statistical versions of indistinguishability and semantic security.

Visual Cryptography, proposed by Naor-Shamir in 1994, is also called a Visual Secret Sharing (VSS) scheme since it can be regarded as one realization of secret sharing scheme. In VSS schemes, an image is encrypted into a set of images called shares, which look like random noise. In decryption, the secret image is perceived from stacked shares by human visual system, and hence no extra computations and prior knowledge are required. The VSS scheme proposed by Naor-Shamir is a (k,n) or less threshold VSS scheme for binary image, where a secret image is decrypted by stacking arbitrary k out of n shares, but any (k−1) or less shares must not leak out any information of the secret image. In this paper a variant of the VSS Scheme is proposed, where three binary secret images are encrypted into two shares, at the same time these shares looks like innocent image. Furthermore The first secret image is decrypted by a typical stacking process, while the other two secret images are decrypted using the shifting, that is moving one of the shares respect to the other share in a appropriate position.

In this paper, we focus on a (2,2)-threshold scheme in the presence of an opponent who impersonates one of the two participants. We consider an asymptotic setting where two shares are generated by an encoder blockwisely from an n-tuple of secrets generated from a stationary memoryless source and a uniform random number available only to the encoder. We introduce a notion of correlation level of the two shares and give coding theorems on the rates of the shares and the uniform random number. It is shown that, for any (2,2)-threshold scheme with correlation level r, none of the rates can be less than H(S) + r, where H(S) denotes the entropy of the source. We also show that the impersonation by the opponent is successful with probability at least 2^-nr+o(n). In addition, we prove the existence of an encoder and a decoder of the (2, 2)-threshold scheme that asymptotically achieve all the bounds on the rates and the success probability of the impersonation.

It is known that a secret sharing scheme (SSS) with perfect cheating detection cannot be realized because such a SSS requires infinite share rates. However, this impossibility comes from the fact that block coding is not used and any decoding error is not allowed in the SSS. Hence, in this paper, we consider a SSS constructed by block coding with an arbitrarily small decoding error probability. It is shown that the perfect cheating detection with finite rates is possible for the 2-out-of-2 SSS in a certain asymptotic sense. Furthermore, the supremum of the achievable exponent in the maximum success probability of impersonation attack turns out to be the mutual information between the two shares.

We introduce a visual secret sharing (VSS) scheme with a new security condition, called a weakly secure VSS scheme, which is not unconditionally secure in general, but is designed to be secure for human eyesight. It is shown in this paper that the weakly secure VSS scheme is equivalent to the unconditional one for black-white binary secret images although they are different for color secret images. This fact implies that, at the sacrifice of security, the clearer color images can be reproduced by the weakly secure VSS schemes compared with the unconditional ones. Furthermore, some constructions of weakly secure VSS schemes are presented.

Recently, a visual secret sharing scheme for q multiple secret images allowing the rotation of shares, a VSS-q-MI-R schemes for short, is proposed by Iwamoto et al. In this paper, another definition of VSS-q-MI-R schemes is given, which is simpler than that by Iwamoto et al.

Quantum secret sharing schemes encrypting a quantum state into a multipartite entangled state are treated. The lower bound on the dimension of each share given by Gottesman [Phys. Rev. A 61, 042311 (2000)] is revisited based on a relation between the reversibility of quantum operations and the Holevo information. We also propose a threshold ramp quantum secret sharing scheme and evaluate its coding efficiency.

Ramp secret sharing (SS) schemes can be classified into strong ramp SS schemes and weak ramp SS schemes. The strong ramp SS schemes do not leak out any part of a secret explicitly even in the case where some information about the secret leaks from a non-qualified set of shares, and hence, they are more desirable than weak ramp SS schemes. However, it is not known how to construct the strong ramp SS schemes in the case of general access structures. In this paper, it is shown that a strong ramp SS scheme can always be constructed from a SS scheme with plural secrets for any feasible general access structure. As a byproduct, it is pointed out that threshold ramp SS schemes based on Shamir's polynomial interpolation method are not always strong.

This paper shows the derivation procedure of optimal secret sharing scheme (SSS) for a given access structure in the multiple assignment schemes based on integer programming.

Visual secret sharing schemes with q plural images, for short VSS-q-PI schemes, are studied for general access structures and gray-scale and/or color secret images.

Because performance disparity between processor and main memory is serious, it is necessary to reduce off-chip memory accesses by exploiting temporal locality. Loop tiling is a well-known optimization which enhances data locality. In this paper, we show a new cost model to select the best tile size in 3D partial differential equations. Our cost model carefully takes account of the effect of cache line. We present performance evaluation of our cost models. The evaluation results reveal the superiority of our cost model to other cost models proposed so far.

高機能暗号は，個人情報等の機密情報を保護したまま，データ分析やアクセス制御等を実行可能とする暗号技術（の総称）であり，データの利活用の更なる推進を促すうえで極めて有効と考えられている．しかしながら，高機能暗号は，用途に応じた多様な技術に細分化がなされており，また，それらの個別の技術によって提供される機能や安全性は複雑であるため，理解が容易ではない．そのため，高機能暗号の利用により利益が得られる潜在的な利用者であっても，技術的な理解が不十分なため，利用を躊躇する場合も少なくないものと思われる．したがって，高機能暗号の社会実装を進めるうえで，その機能や安全性についての理解を促すための技術の研究開発が別途必要である．本論文では，そのような高機能暗号の機能や安全性をわかりやすく説明することを可能とするツールである物理・視覚暗号やその関連技術について紹介を行う．物理・視覚暗号を適切に用いた説明を行うことで，それらに対応した高機能暗号に関する潜在的な利用者への技術的な理解が促され，高機能暗号の社会実装が促進されるものと考えられる．

In this paper, a review for threshold-based visual cryptography (VC), a visual representation of the secret sharing scheme is presented. The VC has potential applications in the electronic banking system, as well as in personal identification systems. En la VC a binary image such as letters, logotypes or halftone images are shared among a group of participants using a set of images, so called shares. Until now several VC schemes, such as threshold-based VC, the general access VC and the extended VC, have been proposed. The conditions that must be satisfied for a correct recovery of the secret message, as well as the most relevant security issues of this scheme are also analyzed.

Research in the area of secure multi-party computation with an unconventional method of using a physical deck of playing cards began in 1989 when den Boar proposed a protocol to compute the logical AND function using five cards. Since then, the area has gained interest from many researchers and several card-based protocols to compute various functions have been developed. In this paper, we propose a card-based protocol called the overwriting protocol that can securely compute the k-candidate n-variable equality function f: {0,1,…,k−1}^{n} \to {0,1}. We also apply the technique used in this protocol to compute other similar functions.

A thread of physical attacks that try to obtain secret information from cryptographic modules has been of academic and practical interest. One of the concerns is determining its efficiency, e.g., the number of attack trials to recover the secret key. However, the accurate estimation of the attack efficiency is generally expensive because of the complexity of the physical attack on a cryptographic algorithm. Based on this background, in this study, we propose a new abstraction model for evaluating the attack efficiency of the probing and DFA attacks. The proposed model includes an abstracted attack target and attacker to determine the amount of leaked information obtained in a single attack trial. We can adapt the model flexibly to various attack scenarios and can get the attack efficiency quickly and precisely. In the probing attack on AES, the difference in the attack efficiency is only approximately 0.3% between the model and experimental values, whereas that of a previous model is approximately 16%. We also apply the probing attack on DES, and the results show that DES has a high resistance to the probing attack. Moreover, the proposed model works accurately also for the DFA attack on AES.