## CryptoDB

### Koji Nuida

#### Affiliation: AIST

#### Publications

**Year**

**Venue**

**Title**

2021

PKC

Cryptographic Pseudorandom Generators Can Make Cryptosystems Problematic
📺
Abstract

Randomness is an essential resource for cryptography. For practical randomness generation, the security notion of pseudorandom generators (PRGs) intends to automatically preserve (computational) security of cryptosystems when used in implementation. Nevertheless, some opposite case such as in computational randomness extractors (Barak et al., CRYPTO 2011) is known (but not yet systematically studied so far) where the security can be lost even by applying secure PRGs. The present paper aims at pushing ahead the observation and understanding about such a phenomenon; we reveal such situations at layers of primitives and protocols as well, not just of building blocks like randomness extractors. We present three typical types of such cases: (1) adversaries can legally see the seed of the PRGs (including the case of randomness extractors); (2) the set of "bad" randomness may be not efficiently recognizable; (3) the formulation of a desired property implicitly involves non-uniform distinguishers for PRGs. We point out that the semi-honest security of multiparty computation also belongs to Type 1, while the correctness with negligible decryption error probability for public key encryption belongs to Types 2 and 3. We construct examples for each type where a secure PRG (against uniform distinguishers only, for Type 3) does not preserve the security/correctness of the original scheme; and discuss some countermeasures to avoid such an issue.

2021

CRYPTO

Non-Interactive Secure Multiparty Computation for Symmetric Functions, Revisited: More Efficient Constructions and Extensions
Abstract

Non-interactive secure multiparty computation (NIMPC) is a variant of secure computation which allows each of $n$ players to send only a single message depending on his input and correlated randomness.
Abelian programs, which can realize any symmetric function, are defined as functions on the sum of the players' inputs over an abelian group and provide useful functionalities for real-world applications.
We improve and extend the previous results in the following ways:
\begin{itemize}
\item We present NIMPC protocols for abelian programs that improve the best known communication complexity.
If inputs take any value of an abelian group $\mathbb{G}$, our protocol achieves the communication complexity $O(|\mathbb{G}|(\log|\mathbb{G}|)^2)$ improving $O(|\mathbb{G}|^2n^2)$ of Beimel et al. (Crypto 2014).
If players are limited to inputs from subsets of size at most $d$, our protocol achieves $|\mathbb{G}|(\log|\mathbb{G}|)^2(\max\{n,d\})^{(1+o(1))t}$ where $t$ is a corruption threshold.
This result improves $|\mathbb{G}|^3(nd)^{(1+o(1))t}$ of Beimel et al. (Crypto 2014), and even $|\mathbb{G}|^{\log n+O(1)}n$ of Benhamouda et al. (Crypto 2017) if $t=o(\log n)$ and $|\mathbb{G}|=n^{\Theta(1)}$.
\item We propose for the first time NIMPC protocols for linear classifiers that are more efficient than those obtained from the generic construction.
\item We revisit a known transformation of Benhamouda et al. (Crypto 2017) from Private Simultaneous Messages (PSM) to NIMPC, which we repeatedly use in the above results.
We reveal that a sub-protocol used in the transformation does not satisfy the specified security.
We also fix their protocol with only constant overhead in the communication complexity.
As a byproduct, we obtain an NIMPC protocol for indicator functions with asymptotically optimal communication complexity with respect to the input length.
\end{itemize}

2010

EPRINT

On the Security of Pseudorandomized Information-Theoretically Secure Schemes
Abstract

In this article, we discuss a naive method of randomness reduction for cryptographic schemes, which replaces the required perfect randomness with output distribution of a computationally secure pseudorandom generator (PRG). We propose novel ideas and techniques for evaluating the indistinguishability between the random and pseudorandom cases, even against an adversary with computationally unbounded attack algorithm. Hence the PRG-based randomness reduction can be effective even for information-theoretically secure cryptographic schemes, especially when the amount of information received by the adversary is small. In comparison to a preceding result of Dubrov and Ishai (STOC 2006), our result removes the requirement of generalized notion of ``nb-PRGs'' and is effective for more general kinds of protocols. We give some numerical examples to show the effectiveness of our result in practical situations, and we also propose a further idea for improving the effect of the PRG-based randomness reduction.

2008

EPRINT

An improvement of discrete Tardos fingerprinting codes
Abstract

It has been known that the code lengths of Tardos's collusion-secure fingerprinting codes are of theoretically minimal order with respect to the number of adversarial users (pirates). However, the code lengths can be further reduced, as some preceding studies on Tardos's codes already revealed. In this article we improve a recent discrete variant of Tardos's codes, and give a security proof of our codes under an assumption weaker than the original assumption (Marking Assumption).
Our analysis shows that our codes have significantly shorter lengths than Tardos's codes. For example, in a practical setting, the code lengths of our codes are about 3.01%, 4.28%, and 4.81% of Tardos's codes if the numbers of pirates are 2, 4, and 6, respectively.

#### Coauthors

- Reo Eriguchi (1)
- Satoshi Fujitsu (1)
- Manabu Hagiwara (1)
- Goichiro Hanaoka (2)
- Hideki Imai (1)
- Takashi Kitagawa (1)
- Kaoru Kurosawa (1)
- Takashi Nishide (1)
- Kazuto Ogawa (1)
- Kazuma Ohara (1)
- Eiji Okamoto (1)
- Kazumasa Shinagawa (1)
- Hajime Watanabe (1)
- Shota Yamada (1)