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

15:17 [Pub][ePrint] How to Garble RAM Programs, by Steve Lu and Rafail Ostrovsky


Yao\'s Garbled Circuits is one of the central and one of the most widely used tools in cryptography, both in theory and in practice. It has numerous applications and multiple implementations, as well as over 1800 scientific citations (according to Google Scholar). It\'s applicability comes from multiple desirable features: it can be based on any one-way function (which yields efficient implementations based on block-ciphers such as AES), has minimal interaction, and garbled inputs can be generated given only the knowledge of the cryptographic keys used for garbling inputs and thus input garbling is independent of the garbled circuit structure. However, one of the major drawbacks of Yao\'s Garbled Circuit method is the need to \"compile\" Random Access Machine (RAM) programs into circuits, which often leads to exponential increases both in the garbled program size and in the garbled program running time, compared to the RAM program. Consider, for example, binary search: while the RAM program for binary search can be executed in logarithmic time in its input size, a circuit computation requires a linear-sized representation and work. Nevertheless, the non-interactive nature of Yao\'s Garbled Circuits can sometimes far outweigh the need to compile programs into circuits.

The question that we consider in this paper is this: is it possible to retain all of the desirable features of Yao\'s Garbled Circuits mentioned above, including its non-interactive feature without taking a potentially exponential hit in unrolling RAM programs into circuits? We affirmatively answer this question. In particular, we show how to garble any RAM program (where once garbled, the Garbled RAM program can be executed non-interactively on a single garbled input, just like Yao) so that its garbled program running time increases by a fixed polynomial in the security parameter (just like Yao) times poly-logarithmic quantity both in the input size and the original program running time. The garbled program sizeis proportional to the original program running time times a fixed polynomial in the security parameter times poly-log of the input size. The garbled input (compared to the original input) grows by poly-log in its size times the security parameter.

Just like Garbled Circuits, the input encoding is independent from the specific RAM program that is garbled, and only depends on the input encoding keys, and the recipient of the garbled program can select (parts of) the garbled input via Oblivious Transfer.

As an illustrative example, consider binary search: our result shows that Bob can give data consisting of $n$ sorted private-key encrypted numbers using $O(n * polylog(n))$ encryptions to Alice (assuming each encrypted number fits into a word). Later, Bob can garble any binary search into non-interactive garbled program of size $k^{O(1)} * polylog(n)$, where $k^{O(1)}$ is a fixed polynomial in the security parameter. The binary search query can be chosen and garbled by Bob after he uploaded his data to Alice and without having to remember the data. Alice can execute garbled binary search non-interactively in $k^{O(1)} * polylog(n)$ steps. We stress that the size of our garbled RAM program as well as its running time is only poly-logarithmic in the input size. In contrast, all previous secure protocols for binary search required either programs that were at least linear in the input size or, if sub-linear, required at least logarithmic number of rounds of interaction.

Our result is very general: an arbitrary garbled RAM program can be executed non-interactively with only poly-logarithmic increase in the running time (compared to insecure execution) and the garbled program will retain its compact size even if the program has multiple loops, multiple nested execution branches, recursion, etc.

Our techniques generalize and unify several previous results, including Oblivious RAMs and Yao\'s Garbled Circuits. As a stepping stone towards our general result, under the assumptions that one-way functions exist, we show how to make a one-round Oblivious RAM with poly-log overhead per read/write. Previous poly-log overhead, constant-round RAMs were either not secure or based on pairing-based hardness assumptions. In contrast, our result is based on the necessary assumption of any one way function. In fact, we need only PRFs or any symmetric-key encryption in our construction.

15:17 [Pub][ePrint] A note on invariant linear transformations in multivariate public key cryptography, by Andreas Wiemers

  Imai and Matsumoto introduced a public key cryptosystem based on

multivariate quadratic polynomials. In a simplified way, the essence of their cryptosystem can be described in the following way: Start with a central monomial F. The secret key comprises

two invertible linear transformations T and L such that TFL is the public key. In order to study equivalent public keys it is natural to ask for the \"invariant\" secret keys (T,L), i.e. TFL=F. Lin, Faugere, Perret and Wang give a partial answer to this question by considering such L which fulfill FL=F. In this paper we will determine all invariant invertible linear transformations (T,L).

15:17 [Pub][ePrint] Collecting Data while Preserving Individuals\' Privacy: A Case Study, by Alexis Bonnecaze and Robert Rolland

  Several companies exploit medical data to better understand medication consumption patterns.

Their analyses are useful to various health actors in order to enhance health care management.

In this article, we focus on a configuration which allows a network of pharmacies to forward medical data to

a private company in order to construct a database. Pharmacies must operate in full compliance with legal requirements in terms of confidentiality and privacy. We show that our solution fulfills all the requirements. Our work leads us to introduce the concept of generalized discrete logarithm problem which is proven to be as hard as the discrete logarithm problem.

15:17 [Pub][ePrint] Leakage-Resilient Cryptography from Minimal Assumptions, by Carmit Hazay and Adriana Lopez-Alt and Hoeteck Wee and Daniel Wichs

  We present new constructions of leakage-resilient cryptosystems, which remain provably secure even if the attacker learns some arbitrary partial information about their internal secret key. For any polynomial $\\ell$, we can instantiate these schemes so as to tolerate up to $\\ell$ bits of leakage. While there has been much prior work constructing such leakage-resilient cryptosystems under concrete number-theoretic and algebraic assumptions, we present the first schemes under general and minimal assumptions. In particular, we construct:

- Leakage-resilient public-key encryption from any standard public-key encryption.

- Leakage-resilient weak pseudorandom functions, symmetric-key encryption}, and message-authentication codes from any one-way function.

These are the first constructions of leakage-resilient symmetric-key primitives that do not rely on public-key assumptions. We also get the first constructions of leakage-resilient public-key encryption from ``search assumptions\'\', such as the hardness of factoring or CDH. Although our schemes can tolerate arbitrarily large amounts of leakage, the tolerated rate of leakage (defined as the ratio of leakage-amount to key-size) is rather poor in comparison to prior results under specific assumptions.

As a building block of independent interest, we study a notion of weak hash-proof systems in the public-key and symmetric-key settings. While these inherit some of the interesting security properties of standard hash-proof systems, we can instantiate them under general assumptions.

12:35 [Event][New] ICT-EurAsia 2013: Information Communication Technology-Eurasia Conference 2013

  Submission: 20 November 2012
Notification: 15 December 2012
From March 25 to March 29
Location: Yogyakarta, Indonesia
More Information:

05:41 [Job][New] Senior Cryptographic Systems Engineer - 35824 - , Raytheon, Goleta, CA, US

  Job Duties:

• Model Cryptographic systems for adherence to specific requirements

• Interact with customers to address questions on impacts of implementation

• Provide guidance to program engineering teams on cryptographic implementation

• Supporting system engineers and designers in architecture trade-offs

Required Skills:

• Minimum of 10 years direct related experience with System Engineering Analysis and Development of Cryptographic Systems.

• Technical experience in developing complex software and/or hardware systems for cryptographic systems

• Demonstrated background in System Modeling, System Simulation, and/or Design of Experiments

• Experience architecting, designing, implementing, testing real-time, embedded solutions

• Active DoD Secret clearance with ability to secure special access

Desired Skills:

• Knowledge of security concerns with real-time operating systems.

• Knowledge of security standards, methods, and policies; risk and threat analysis; technical security safeguard; and operational security measures.

• Experience with all aspects of system design and development process

• Knowledge of Raytheon’s customer needs and organization

• DoD Top Secret clearance preferred

Required Education:

• Bachelor’s of Science (B.S.) in Science, Math, Engineering or related technical field

06:15 [Event][New] FSE 2010: The 17th International Workshop on Fast Software Encryption

  Submission: 9 November 2009
Notification: 6 January 2010
From February 7 to February 10
Location: Seoul, South Korea
More Information:

19:12 [Job][New] Postdoctoral Researcher, Department of Computer Science, University of Helsinki

  The CS department at the University of Helsinki is building up a new secure systems research group in our NODES research unit. The initial focus of the group will be on mobile security. We want to explore security and privacy problems of mobile users and develop solutions that are simultaneously secure, easy-to-use and cost-effective to deploy. In particular, we are interested in figuring out how to use the wealth of contextual and historical information on mobile devices can be used in novel ways to solve these problems. Prof. N. Asokan, who recently joined the department after a long career in industrial research laboratories at IBM and Nokia will be leading the group.

We are looking for a post-doctoral researcher who will play an active role in building up the research program of the group. The successful candidate will have the unique opportunity of helping to shape the direction of a new research group as it is being set up. The researcher will be identifying potential research topics, helping to organize research seminars on those topics, carrying out research, and advising student research.

The ideal candidate will have the following attributes: You have recently completed (or are about to complete) a doctorate on a system security topic (e.g., platform security, network and protocol security) preferably focusing on mobility and mobile devices and users. You have a strong publication record. You also have research experience in one or more of the following areas: cloud computing, usability evaluations, user interaction design or data analytics. You enjoy and take pride in prototyping your research ideas and experimenting with them. You can communicate fluently in written and spoken English.

00:17 [Pub][JoC] A Note on Constant-Round Zero-Knowledge Proofs of Knowledge


Abstract  In this note, we show the existence of constant-round computational zero-knowledge proofs of knowledge for all . The existence of constant-round zero-knowledge proofs was proven by Goldreich and Kahan (Journal of Cryptology, 1996), and the existence of constant-round zero-knowledge arguments of knowledge was proven by Feige and Shamir (CRYPTO, 1989). However, the existence of constant-round zero-knowledge proofs of knowledge for all is folklore, to the best of our knowledge, since no proof of this fact has been published.

  • Content Type Journal Article
  • Pages 1-17
  • DOI 10.1007/s00145-012-9132-7
  • Authors

    • Yehuda Lindell, Department of Computer Science, Bar-Ilan University, Ramat Gan, Israel

    • Journal Journal of Cryptology
    • Online ISSN 1432-1378
    • Print ISSN 0933-2790

From: Mon, 15 Oct 2012 16:40:04 GMT

18:17 [Pub][ePrint] Symbolic computation in block cipher with application to PRESENT, by Changyong Peng and Chuangying zhu and Yuefei Zhu and Fei Kang

  In this paper,we give an example of how symbolic computation are used to analyze the block cipher

PRESENT,an ultra-lightweight block cipher proposed by Bogdanov et al. at CHES\'07.The

block size is 64 bits and the key size can be 80 bit or 128 bit.Using Mathematica 7.0,this paper

obtains the unexpanded polynomial expressions of the output of round 1-6 of PRESENT-80(80-

bit key variant).The time complexity of getting these expressions is 4 minutes on a PC with a

2.6GHz CPU and 8G RAM.Then we expand the expressions of the output of round 1-2 and the

LSB(least significant bit) of the output of round 3 and obtain the ANFs(Algebraic Normal Form)

of these 129(=2*64+1) expressions. The time complexity of getting these ANFs is 22 minutes.It

it known that the time complexity of the classical method of computing the ANF of an n-ary

Boolean function from its truth table is O(n*2^n),with total time complexity of obtaining these 129

ANFs O(129*144*2^144) = O(2^158)(each of the 129 ANFs can be viewed as a 144-ary Boolean

function,where 144=64+80,the sum of the block size and the key size).As an application,we give

a side channel attack on PRESENT-80 under the single bit leakage model proposed by Dinur and

Shamir.If the LSB bit of the output of the 3rd round can be obtained without error,then with 200

known plaintexts,we can set up an equation system in terms of the master key bits and can recover

43 bits key by the Gr¨obner Basis method.Compared with the previous side channel attack

on PRESENT,such as Yang et al. in CANS 2009,Abdul-Latip et al. in ASIACCS 2011 and Zhao

et al. in 2011,each of which needs at least 2^13 chosen plaintexts,the data complexity of our attack

is the best.

15:17 [Pub][ePrint] Nanoelectronic Solutions for Hardware Security, by Jeyavijayan Rajendran, Ramesh Karri, James B. Wendt, Miodrag Potkonjak, Nathan McDonald, Garrett S. Rose, and Bryant Wysocki

  Information security has emerged as an important system and application metric. Classical security solutions use algorithmic mechanisms that address a small subset of emerging security requirements, often at high energy and performance overhead. Further, emerging side channel and physical attacks can compromise classical

security solutions. Hardware based security solutions overcome many of the limitations of classical security while consuming less energy and improving performance. Nanoelectronics based hardware security preserves all of these advantages while enabling conceptually new security mechanisms and security applications. This paper highlights

nanoelectronics based security capabilities and challenges. The paper describes nanoelectronics based hardware security primitives for device identification, digital forensics, and tamper detection. These primitives can be developed using the unique characteristics of emerging nanoelectronic devices such as complex device and system models, bidirectional operation, and temporal drift of the state variable. We conclude by identifying important desiderata and outstanding challenges in nanoelectronics based security.