International Association for Cryptologic Research

# IACR News Central

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

2014-08-27
09:17 [Pub][ePrint]

In this paper, We find a way to construct FSRs. The constructed FSRs can be depicted in many ways.

They are just the FSRs whose characteristic polynomial can be written as $g=(x_0+x_1)*f$ for some $f$.

Their adjacency graphs do not contain self-loops. Further more, we can divide the vertexes in their adjacency graphs into two sets such that

the edges are all between the two sets. The number of this class of FSRs is also considered. Besides, some applications in

LFSRs and constructing full cycles are presented.

09:17 [Pub][ePrint]

In this paper, we

explore the primitivity of trinomials over small finite fields. We

extend the results of the primitivity of trinomials $x^{n}+ax+b$

over ${\\mathbb{F}}_{4}$ \\cite{Li} to the general form

$x^{n}+ax^{k}+b$. We prove that for given $n$ and $k$, one of all the trinomials

$x^{n}+ax^{k}+b$ with $b$ being the primitive element of

${\\mathbb{F}}_{4}$ and $a+b\\neq1$ is primitive over

${\\mathbb{F}}_{4}$ if and only if all the others are primitive over

${\\mathbb{F}}_{4}$. And we can deduce that if we find one primitive

trinomial over ${\\mathbb{F}}_{4}$, in fact there are at least four primitive

trinomials with the same degree. We give the necessary conditions if

there exist primitive trinomials over ${\\mathbb{F}}_{4}$. We study

the trinomials with degrees $n=4^{m}+1$ and $n=21\\cdot4^{m}+29$,

where $m$ is a positive integer. For these two cases, we prove that

the trinomials $x^{n}+ax+b$ with degrees $n=4^{m}+1$ and

$n=21\\cdot4^{m}+29$ are always reducible if $m>1$. If some results

are obviously true over ${\\mathbb{F}}_{3}$, we also give it.

09:17 [Pub][ePrint]

We consider the task of constructing interactive proofs for NP which can provide meaningful security for a prover even in the presence of continual memory leakage. We imagine a setting where an adversarial verifier participates in multiple sequential interactive proof executions for a fixed NP statement x. In every execution, the adversarial verifier is additionally allowed to leak a fraction of the (secret) memory of the prover. This is in contrast to the recently introduced notion of leakage-resilient zero-knowledge (Garg-Jain-Sahai\'11) where there is only a single execution. Under multiple executions, in fact the entire prover witness might end up getting leaked thus leading to a complete compromise of prover security.

Towards that end, we define the notion of non-transferable proofs for all languages in NP. In such proofs, instead of receiving w as input, the prover will receive an \"encoding\'\' of the witness w such that the encoding is sufficient to prove the validity of x; further, this encoding can be \"updated\'\' to a fresh new encoding for the next execution. We then require that if (x,w) are sampled from a \"hard\'\' distribution, then no PPT adversary A* can gain the ability to prove x (on its own) to an honest verifier, even if A* has participated in polynomially many interactive proof executions (with leakage) with an honest prover whose input is (x,w). Non-transferability is a strong security guarantee which suffices for many cryptographic applications (and in particular, implies witness hiding).

We show how to construct non-transferable proofs for all languages in NP which can tolerate leaking a constant fraction of prover\'s secret-state during each execution. Our construction is in the common reference string (CRS) model. To obtain our results, we build a witness-encoding scheme which satisfies the following continual-leakage-resilient (CLR) properties:

- The encodings can be randomized to yield a fresh new encoding,

- There does not exist any efficient adversary, who receiving only a constant fraction of leakage on polynomially many fresh encodings of the same witness w, can output a valid encoding provided that the witness w along with its corresponding input instance x were sampled from a hard distribution.

Our encoding schemes are essentially re-randomizable non-interactive zero-knowledge (NIZK) proofs for circuit satisfiability, with the aforementioned CLR properties. We believe that our CLR-encodings, as well as our techniques to build them, may be of independent interest.

2014-08-26
18:47 [Event][New]

Submission: 21 November 2014
From May 2 to May 5
Location: Lugano, Switzerland

2014-08-25
03:14 [Event][New]

From January 12 to January 16
Location: New Brunswik, USA

2014-08-22
03:47 [Event][New]

From May 31 to June 5
Location: Sibenik, Croatia

03:28 [Event][New]

From May 31 to June 5
Location: Sibenik, Croatia

2014-08-21
15:56 [Event][New]

From February 4 to February 7
Location: Goa, India

03:17 [Pub][ePrint]

03:17 [Pub][ePrint]

We introduce a formal model for order queries on lists in zero knowledge in the traditional authenticated data structure model.

We call this model Privacy-Preserving Authenticated List (PPAL).

In this model, the queries are performed on the list stored in the (untrusted) cloud where data integrity and privacy have to

be maintained. To realize an efficient authenticated data structure, we first adapt consistent data query model.

To this end we introduce a formal model called Zero-Knowledge List (ZKL) scheme which generalizes consistent membership queries in zero-knowledge

to consistent membership and order queries on a totally ordered set in zero knowledge. We present a construction of ZKL based on zero-knowledge set

and homomorphic integer commitment scheme. Then we discuss why this construction is not as efficient as desired in cloud applications and

present an efficient construction of PPAL based on bilinear accumulators and bilinear maps which is provably secure and zero-knowledge.

03:17 [Pub][ePrint]

The traditional setting for concurrent zero knowledge considers a server that proves a statement in zero-knowledge to multiple clients in multiple concurrent sessions, where the server\'s actions in a session are independent of all other sessions. Persiano and Visconti [ICALP 05] show how keeping a limited amount of global state across sessions allows the server to significantly reduce the overall complexity while retaining the ability to interact concurrently with an unbounded number of clients. Specifically, they show a protocol that has only slightly super-constant number of rounds; however the communication complexity in each session of their protocol depends on the number of other sessions and has no a priori bound. This has the drawback that the client has no way to know in advance the amount of resources required for completing a session of the protocol up to the moment where the session is completed.

We show a protocol that does not have this drawback. Specifically, in our protocol the client obtains a bound on the communication complexity of each session at the start of the session. Additionally the protocol is constant-rounds. Our protocol is fully concurrent, and assumes only collision-resistant hash functions. The proof requires considerably different techniques than those of Persiano and Visconti. Our main technical tool is an adaptation of the \"committed-simulator\" technique of Deng et. al [FOCS 09].