Abstract Old Maid is a popular card game. While typically played with three or more players, it is less enjoyable with only two people. To address this, we propose a protocol to create a virtual player, Carol, by making use of card-based cryptography when only two people, Alice and Bob, are available to play Old Maid. Specifically, we design a card-based protocol to remove any pair of cards having the same number in Carol’s hand (namely, the virtual player’s hand) without leaking any information about Carol’s hand (more than necessary); our protocol uses additional cards aside from playing cards that are used in Old Maid. Using our protocol, without any third human player, Alice and Bob can have fun with Old Maid!

Abstract Private Simultaneous Messages (PSM) model is a minimal model for secure multiparty computation. Feige, Kilian, and Naor (STOC 1994) and Ishai (Cryptology and Information Security Series 2013) constructed PSM protocols based on quadratic residues. In this paper, we define QR-PSM protocols as a generalization of these protocols. A QR-PSM protocol is a PSM protocol whose decoding function outputs the quadratic residuosity modulo p of what is computed from messages. We design a QR-PSM protocol for any symmetric function $$f: \{0,1\}^n \rightarrow \{0,1\}$$ f : { 0 , 1 } n → { 0 , 1 } of communication complexity $$O(n^2)$$ O ( n 2 ) . As far as we know, it is the most efficient PSM protocol for symmetric functions since the previously known best PSM protocol was of $$O(n^2\log n)$$ O ( n 2 log n ) (Beimel et al., CRYPTO 2014). We also study the sizes of the underlying finite fields $$\mathbb {F}_p$$ F p in the protocols since the communication complexity of a QR-PSM protocol is proportional to the bit length of the prime p. We show that there is a prime $$p \le (1+o(1))N^22^{2N-2}$$ p ≤ ( 1 + o ( 1 ) ) N 2 2 2 N - 2 such that any length-N pattern of quadratic (non)residues appears modulo p (and hence it can be used for general QR-PSM protocols), which improves the Peralta’s known result (Mathematics of Computation 1992) by a constant factor $$(1+\sqrt{2})^2$$ ( 1 + 2 ) 2 .

It is known that Bitcoin enables achieving fairness in secure computation by imposing monetary penalties on adversarial parties. This functionality is called secure computation with penalties. Bentov and Kumaresan (2014) [9] introduced the claim-or-refund functionality that can be implemented via Bitcoin. They achieved secure computation with penalties with O(n) rounds and O(n) broadcasts for any function, where n is the number of parties. After that, Kumaresan and Bentov (2014) [8] showed a constant-round protocol. Unfortunately, this protocol requires O(n2) broadcasts. As far as we know, no protocol achieves O(1) rounds and O(n) broadcasts based on Bitcoin. This work accomplishes such efficiency in secure computation with penalties. We first show a protocol in a slightly relaxed setting called secure computation with non-equivalent penalties. This setting is the same as secure computation with penalties except that every honest party receives more than a predetermined amount of compensation, while the previous one requires that every honest party receives the same amount of compensation. Namely, our setting allows the compensations for honest parties to be non-equivalent. Moreover, we present a technique to remove the non-equivalence of our protocol without sacrificing efficiency. We then propose a new ideal functionality called claim-refund-or-give that can be implemented via Bitcoin.

Secure computation enables a number of players each holding a secret input value to compute a function of the inputs without revealing the inputs. It is known that secure computation is possible physically when the inputs are given as a sequence of physical cards. This research area is called card-based cryptography. One of the important problems in card-based cryptography is to minimize the number of cards and shuffles, where a shuffle is the most important (and somewhat heavy) operation in card-based protocols. In this paper, we determine the minimum number of shuffles for achieving general secure computation. Somewhat surprisingly, the answer is just one, i.e., we design a protocol which securely computes any Boolean circuit with only a single shuffle. The number of cards required for our protocol is proportional to the size of the circuit to be computed.

Consider a group of people who want to know the “rich list” among them, namely the ranking in terms of their total assets, without revealing any information about the actual value of their assets. This can be achieved by a “secure ranking computation,” which was first considered by Jiang and Gong (2006) [2]; they constructed a secure ranking computation protocol based on a public-key cryptosystem. In this paper, instead of using a public-key cryptosystem, we use a deck of physical cards to provide secure ranking computation protocols. Therefore, our card-based protocols do not rely on computers, and they are simple and easy for humans to implement. Specifically, we design four protocols considering tradeoffs between the number of cards and the number of shuffles required to execute the protocols. We also present a guide to choose an appropriate protocol according to the number of people participating in the protocol and the size of the input range. To be precise, whereas our protocols make all players know the rich list, the Jiang–Gong scheme makes each player know his/her rank only; to achieve the same task (as the Jiang–Gong scheme) using a deck of cards is an intriguing open problem.

It has recently become apparent that both accidental and maliciously caused randomness failures pose a real and serious threat to the security of cryptographic primitives, and in response, researchers have begone the development of primitives that provide robustness against these. In this paper, however, we focus on standardized, widely available primitives. Specifically, we analyze the RSA-OAEP encryption scheme and RSA-PSS signature schemes, specified in PKCS #1, using the related randomness security notion introduced by Paterson et al. (PKC 2014) and its extension to signature schemes. We show that, under the RSA and Φ-hiding assumptions, RSA-OAEP encryption is related randomness secure for a large class of related randomness functions in the random oracle model, as long as the recipient is honest, and remains secure even when additionally considering malicious recipients, as long as the related randomness functions does not allow the malicious recipients to efficiently compute the randomness used for the honest recipient. We furthermore show that, under the RSA assumption, the RSA-PSS signature scheme is secure for any class of related randomness functions, although with a non-tight security reduction. However, under additional, albeit somewhat restrictive assumptions on the related randomness functions and the adversary, a tight reduction can be recovered. Our results provides some reassurance regarding the use of RSA-OAEP and RSA-PSS in environments where randomness failures might be a concern. Lastly, we note that, unlike RSA-OAEP and RSA-PSS, several other schemes, including RSA-KEM, part of ISO 18033-2, and DHIES, part of IEEE P1363a, are not secure under simple repeated randomness attacks.