BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Takeshi Koshiba

Takeshi Koshiba appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
quant-phCryptography and SecurityComputational ComplexityInformation Theorymath.IT

Catalog footprint

What is connected

10works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

10 published item(s)

preprint2022arXiv

Guesswork of a quantum ensemble

The guesswork of a quantum ensemble quantifies the minimum number of guesses needed in average to correctly guess the state of the ensemble, when only one state can be queried at a time. Here, we derive analytical solutions of the guesswork problem subject to a finite set of conditions, including the analytical solution for any qubit ensemble with uniform probability distribution. As explicit examples, we compute the guesswork for any qubit regular polygonal and polyhedral ensemble.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Classical simulatability of the one clean qubit model

Deterministic quantum computation with one quantum bit (DQC1), or the one clean qubit model, [E. Knill and R. Laflamme, Phys. Rev. Lett. {\bf81}, 5672 (1998)] is a model of quantum computing where the input is the tensor product of a single pure qubit and many completely-mixed states, and only the single qubit is measured at the end of the computation. In spite of its naive appearance, the DQC1 model can efficiently solve some problems for which no classical efficient algorithms are known, and therefore it has been conjectured that the DQC1 model is more powerful than classical computing (under the assumption of $\mbox{BPP}\subsetneq\mbox{BQP}$). Here we show that the output probability distribution of the DQC1 model cannot be classically efficiently approximated (exactly within a polynomial bit length or in the fully polynomial randomized approximation scheme (FPRAS) with at most a constant error) unless $\mbox{BQP}\subseteq\mbox{BPP}$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Linear Programming Relaxations for Goldreich's Generators over Non-Binary Alphabets

Goldreich suggested candidates of one-way functions and pseudorandom generators included in $\mathsf{NC}^0$. It is known that randomly generated Goldreich's generator using $(r-1)$-wise independent predicates with $n$ input variables and $m=C n^{r/2}$ output variables is not pseudorandom generator with high probability for sufficiently large constant $C$. Most of the previous works assume that the alphabet is binary and use techniques available only for the binary alphabet. In this paper, we deal with non-binary generalization of Goldreich's generator and derives the tight threshold for linear programming relaxation attack using local marginal polytope for randomly generated Goldreich's generators. We assume that $u(n)\in ω(1)\cap o(n)$ input variables are known. In that case, we show that when $r\ge 3$, there is an exact threshold $μ_\mathrm{c}(k,r):=\binom{k}{r}^{-1}\frac{(r-2)^{r-2}}{r(r-1)^{r-1}}$ such that for $m=μ\frac{n^{r-1}}{u(n)^{r-2}}$, the LP relaxation can determine linearly many input variables of Goldreich's generator if $μ>μ_\mathrm{c}(k,r)$, and that the LP relaxation cannot determine $\frac1{r-2} u(n)$ input variables of Goldreich's generator if $μ<μ_\mathrm{c}(k,r)$. This paper uses characterization of LP solutions by combinatorial structures called stopping sets on a bipartite graph, which is related to a simple algorithm called peeling algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Ancilla-Driven Universal Blind Quantum Computation

Blind quantum computation is a new quantum secure protocol, which enables Alice who does not have enough quantum technology to delegate her computation to Bob who has a fully-fledged quantum power without revealing her input, output and algorithm. So far, blind quantum computation has been considered only for the circuit model and the measurement-based model. Here we consider the possibility and the limitation of blind quantum computation in the ancilla-driven model, which is a hybrid of the circuit and the measurement-based models.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Composable security of measuring-Alice blind quantum computation

Blind quantum computing [A. Broadbent, J. Fitzsimons, and E. Kashefi, Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science 517 (2009)] is a secure cloud quantum computing protocol which enables a client (who does not have enough quantum technology at her disposal) to delegate her quantum computation to a server (who has a universal quantum computer) without leaking any relevant information to the server. In [T. Morimae and K. Fujii, Phys. Rev. A {\bf87}, 050301(R) (2013)], a new blind quantum computing protocol, so called the measuring-Alice protocol, was proposed. This protocol offers several advantages over previous protocols, such as the device-independent security, less demanding requirements for the client, and a simpler and stronger security based on the no-signaling principle. In this paper, we show composable security of the measuring-Alice protocol by using the formalism of the constructive cryptography [U. Maurer, Proceedings of Theory of Security and Applications, TOSCA 2011, pages 33-56. Springer (2011)]. The above advantages of measuring-Alice protocol enable more intuitive and transparent proofs for the composable security.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Computational Indistinguishability between Quantum States and Its Cryptographic Application

We introduce a computational problem of distinguishing between two specific quantum states as a new cryptographic problem to design a quantum cryptographic scheme that is "secure" against any polynomial-time quantum adversary. Our problem, QSCDff, is to distinguish between two types of random coset states with a hidden permutation over the symmetric group of finite degree. This naturally generalizes the commonly-used distinction problem between two probability distributions in computational cryptography. As our major contribution, we show that QSCDff has three properties of cryptographic interest: (i) QSCDff has a trapdoor; (ii) the average-case hardness of QSCDff coincides with its worst-case hardness; and (iii) QSCDff is computationally at least as hard as the graph automorphism problem in the worst case. These cryptographic properties enable us to construct a quantum public-key cryptosystem, which is likely to withstand any chosen plaintext attack of a polynomial-time quantum adversary. We further discuss a generalization of QSCDff, called QSCDcyc, and introduce a multi-bit encryption scheme that relies on similar cryptographic properties of QSCDcyc.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Non-Interactive Statistically-Hiding Quantum Bit Commitment from Any Quantum One-Way Function

We provide a non-interactive quantum bit commitment scheme which has statistically-hiding and computationally-binding properties from any quantum one-way function. Our protocol is basically a parallel composition of the previous non-interactive quantum bit commitment schemes (based on quantum one-way permutations, due to Dumais, Mayers and Salvail (EUROCRYPT 2000)) with pairwise independent hash functions. To construct our non-interactive quantum bit commitment scheme from any quantum one-way function, we follow the procedure below: (i) from Dumais-Mayers-Salvail scheme to a weakly-hiding and 1-out-of-2 binding commitment (of a parallel variant); (ii) from the weakly-hiding and 1-out-of-2 binding commitment to a strongly-hiding and 1-out-of-2 binding commitment; (iii) from the strongly-hiding and 1-out-of-2 binding commitment to a normal statistically-hiding commitment. In the classical case, statistically-hiding bit commitment scheme (by Haitner, Nguyen, Ong, Reingold and Vadhan (SIAM J. Comput., Vol.39, 2009)) is also constructible from any one-way function. While the classical statistically-hiding bit commitment has large round complexity, our quantum scheme is non-interactive, which is advantageous over the classical schemes. A main technical contribution is to provide a quantum analogue of the new interactive hashing theorem, due to Haitner and Reingold (CCC 2007). Moreover, the parallel composition enables us to simplify the security analysis drastically.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A Weak Quantum Oblivious Transfer

Due to the commonly known impossibility results, information theoretic security is considered impossible for oblivious transfer (OT) in both the classical and the quantum world. In this paper, we proposed a weak version of the all-or-nothing OT. In our protocol the honest parties do not need long term quantum memory, entanglements, or sophisticated quantum computations. We observe some difference between the classical and quantum OT impossibilities.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Asymptotically Secure Quantum Oblivious Transfer

Due to the commonly known impossibility results, unconditional security for oblivious transfer is seen as impossible even in the quantum world. In this paper, we try to overcome these impossibility results by proposing a protocol which is asymptotically secure. The protocol makes use of the basic properties of non-orthogonal quantum states. Apart from security, the advantages of our protocol include the fact that the honest players do not need to have quantum memory or create entanglement between individual qubits. The relation of our work to the known impossibility results is also discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2004arXiv

Universal Test for Quantum One-Way Permutations

The next bit test was introduced by Blum and Micali and proved by Yao to be a universal test for cryptographic pseudorandom generators. On the other hand, no universal test for the cryptographic one-wayness of functions (or permutations) is known, though the existence of cryptographic pseudorandom generators is equivalent to that of cryptographic one-way functions. In the quantum computation model, Kashefi, Nishimura and Vedral gave a sufficient condition of (cryptographic) quantum one-way permutations and conjectured that the condition would be necessary. In this paper, we affirmatively settle their conjecture and complete a necessary and sufficient for quantum one-way permutations. The necessary and sufficient condition can be regarded as a universal test for quantum one-way permutations, since the condition is described as a collection of stepwise tests similar to the next bit test for pseudorandom generators.

0 citations0 reviewsNo code linkedOpen access