



01994nas a2200121   4500008004100000245005200041210005100093260001500144300001200159520164800171100001601819856003701835       2013                        eng d00aBuilding one-time memories from isolated qubits0 aBuilding onetime memories from isolated qubits  c2013/04/18  a269-2863 a  One-time memories (OTM's) are simple tamper-resistant cryptographic devices,
which can be used to implement one-time programs, a very general form of
software protection and program obfuscation. Here we investigate the
possibility of building OTM's using quantum mechanical devices. It is known
that OTM's cannot exist in a fully-quantum world or in a fully-classical world.
Instead, we propose a new model based on "isolated qubits" -- qubits that can
only be accessed using local operations and classical communication (LOCC).
This model combines a quantum resource (single-qubit measurements) with a
classical restriction (on communication between qubits), and can be implemented
using current technologies, such as nitrogen vacancy centers in diamond. In
this model, we construct OTM's that are information-theoretically secure
against one-pass LOCC adversaries that use 2-outcome measurements.
  Our construction resembles Wiesner's old idea of quantum conjugate coding,
implemented using random error-correcting codes; our proof of security uses
entropy chaining to bound the supremum of a suitable empirical process. In
addition, we conjecture that our random codes can be replaced by some class of
efficiently-decodable codes, to get computationally-efficient OTM's that are
secure against computationally-bounded LOCC adversaries.
  In addition, we construct data-hiding states, which allow an LOCC sender to
encode an (n-O(1))-bit messsage into n qubits, such that at most half of the
message can be extracted by a one-pass LOCC receiver, but the whole message can
be extracted by a general quantum receiver.
1 aLiu, Yi-Kai  uhttp://arxiv.org/abs/1304.5007v201845nas a2200145   4500008004100000245005400041210005100095260001500146300001200161520139800173100001601571700002401587700002401611856006401635       2006                        eng d00aOn Bounded Distance Decoding for General Lattices0 aBounded Distance Decoding for General Lattices  c2006/01/01  a450-4613 aA central problem in the algorithmic study of lattices is the closest vector problem: given a lattice L represented by some basis, and a target point y⃗ , find the lattice point closest to y⃗ . Bounded Distance Decoding is a variant of this problem in which the target is guaranteed to be close to the lattice, relative to the minimum distance λ1(L) of the lattice. Specifically, in the α-Bounded Distance Decoding problem (α-BDD), we are given a lattice L and a vector y⃗  (within distance α⋅λ1(L) from the lattice), and we are asked to find a lattice point x⃗ ∈L within distance α⋅λ1(L) from the target. In coding theory, the lattice points correspond to codewords, and the target points correspond to lattice points being perturbed by noise vectors. Since in coding theory the lattice is usually fixed, we may “pre-process” it before receiving any targets, to make the subsequent decoding faster. This leads us to consider α-BDD with pre-processing. We show how a recent technique of Aharonov and Regev [2] can be used to solve α-BDD with pre-processing in polynomial time for α=O((logn)/n−−−−−−−√). This improves upon the previously best known algorithm due to Klein [13] which solved the problem for α=O(1/n). We also establish hardness results for α-BDD and α-BDD with pre-processing, as well as generalize our results to other ℓ p norms.1 aLiu, Yi-Kai1 aLyubashevsky, Vadim1 aMicciancio, Daniele  uhttp://link.springer.com/chapter/10.1007/11830924_41#page-1