International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) You can also receive updates via:

To receive your credentials via mail again, please click here.

You can also access the full news archive.

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

09:17 [Pub][ePrint] A Class of FSRs and Their Adjacency Graphs, by Ming Li and Dongdai Lin

  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] On the Primitivity of Trinomials over Small Finite Fields, by YUjuan Li and Jinhua Zhao and Huaifu Wang

  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] Interactive Proofs under Continual Memory Leakage, by Prabhanjan Ananth and Vipul Goyal and Omkant Pandey

  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.

18:47 [Event][New] ICITS 2015: 8th International Conference on Information Theoretic Security

  Submission: 21 November 2014
Notification: 30 January 2015
From May 2 to May 5
Location: Lugano, Switzerland
More Information:

03:14 [Event][New] DIMACS Workshop on The Mathematics of Post-Quantum Cryptography

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

03:47 [Event][New] Design and security of crypto algorithms and devices for real-world applications

  From May 31 to June 5
Location: Sibenik, Croatia
More Information:

03:28 [Event][New] Design and security of crypto algorithms and devices for real-world applic.

  From May 31 to June 5
Location: Sibenik, Croatia
More Information:

15:56 [Event][New] nullcon International Security Conference

  From February 4 to February 7
Location: Goa, India
More Information:

03:17 [Pub][ePrint] Zipf\'s Law in Passwords, by Ding Wang, Gaopeng Jian, Haibo Cheng, Qianchen Gu, Chen Zhu, Ping Wang

  Despite more than thirty years of research efforts, textual passwords are still enveloped in mysterious veils. In this work, we make a substantial step forward in understanding the distributions of passwords and measuring the strength of password datasets by using a statistical approach. We first show that Zipf\'s law perfectly exists in real-life passwords by conducting linear regressions on a corpus of 56 million passwords. As one specific application of this observation, we propose the number of unique passwords used in regression and the slope of the regression line together as a metric for assessing the strength of password datasets, and prove it in a mathematically rigorous manner. Furthermore, extensive experiments (including optimal attacks, simulated optimal attacks and state-of-the-art cracking sessions) are performed to demonstrate the practical effectiveness of our metric. To the best of knowledge, our new metric is the first one that is both easy to approximate and accurate to facilitate comparisons, providing a useful tool for the system administrators to gain a precise grasp of the strength of their password datasets and to adjust the password policies more reasonably.

03:17 [Pub][ePrint] Verifiable Member and Order Queries on a List in Zero-Knowledge, by Esha Ghosh and Olga Ohrimenko and Roberto Tamassia

  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] Client-Server Concurrent Zero Knowledge with Constant Rounds and Guaranteed Complexity, by Ran Canetti and Abhishek Jain and Omer Paneth

  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].