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}\approx 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^{116}\) 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.
29 August 2017 in IEEE Transactions on Information Theory
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.
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.”
Card-based cryptography is a variant of multi-party computation 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, 2ncards are necessary for every protocol withn-bit input since at least two cards are required to express a bit. In this paper, we proposen-bit input protocols with fewer than 2ncards 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.