International Association
for Cryptologic Research

We describe a method to perform scalar multiplication on two classes of

ordinary elliptic curves, namely $E: y^2 = x^3 + Ax$ in prime characteristic

$p\\equiv 1$ mod~4, and $E: y^2 = x^3 + B$ in prime characteristic $p\\equiv 1$

mod 3. On these curves, the 4-th and 6-th roots of unity act as (computationally

efficient) endomorphisms. In order to optimise the scalar multiplication, we consider a width-$w$-NAF (non-adjacent form) digit expansion of positive integers to the complex base of $\\tau$, where $\\tau$ is a zero of the characteristic polynomial $x^2 - tx + p$ of the Frobenius endomorphism associated to the curve. We provide a precomputationless algorithm by means of a convenient factorisation of the unit group of residue classes modulo $\\tau$ in the endomorphism ring, whereby we construct a digit set consisting of powers of subgroup generators, which are chosen as efficient endomorphisms of the curve.

Evaluating side-channel attacks and countermeasures requires determining the amount of information leaked by a target device. For this purpose, information extraction procedures published so far essentially combine a \"leakage model\" with a \"distinguisher\". Fair evaluations ideally require exploiting a perfect leakage model (i.e. exactly corresponding to the true leakage distribution) with a Bayesian distinguisher. But since such perfect models are generally unknown, density estimation techniques have to be used to approximate the leakage distribution. This raises the fundamental problem that all security evaluations are potentially biased by both estimation and assumption errors. Hence, the best that we can hope is to be aware of these errors. In this paper, we provide and implement methodological tools to solve this issue. Namely, we show how sound statistical techniques allow both quantifying the leakage of a chip, and certifying that the amount of information extracted is close to the maximum value that would be obtained with a perfect model.

We present a polynomial-time reduction of the discrete logarithm problem in any periodic (a.k.a. torsion)

semigroup (SGDLP) to the same problem in a subgroup of the same semigroup.

It follows that SGDLP can be solved in polynomial time by quantum computers, and that

SGDLP has subexponential algorithms whenever the classic DLP in the corresponding groups has subexponential algorithms.

We revisit the classical problem of converting an imperfect source of randomness into a usable cryptographic key. Assume that we have some cryptographic application $P$ that expects a uniformly random $m$-bit key $R$ and ensures that the best attack (in some complexity class) against $P(R)$ has success probability at most $\\delta$. Our goal is to design a key-derivation function (KDF) $h$ that converts any random source $X$ of min-entropy $k$ into a sufficiently ``good\'\' key $h(X)$,

guaranteeing that $P(h(X))$ has comparable security $\\delta\'$ which is `close\' to $\\delta$.

Seeded randomness extractors provide a generic way to solve this problem for \\emph{all} applications $P$, with resulting security $\\delta\' = O(\\delta)$, provided that we start with entropy $k\\ge m+2\\logdel-O(1)$. By a result of Radhakrishnan and Ta-Shma, this bound on $k$ (called the ``RT-bound\'\') is also known to be tight in general. Unfortunately, in many situations the loss of $2\\logdel$ bits of entropy is unacceptable. This motivates the study KDFs with less entropy waste by placing some restrictions on the source $X$ or the application $P$.

In this work we obtain the following new positive and negative results in this regard:

- Efficient samplability of the source $X$ does not help beat the RT-bound for general applications. This resolves the SRT (samplable RT) conjecture of Dachman-Soled et al.~\\cite{DGKM12} in the affirmative, and also shows that the existence of computationally-secure extractors beating the RT-bound implies the existence of one-way functions.

- We continue in the line of work initiated by Barak et al. \\cite{BDK+11} and construct new information-theoretic KDFs which beat the RT-bound for large but restricted classes of applications. Specifically, we design efficient KDFs that work for all unpredictability applications $P$ (e.g., signatures, MACs, one-way functions, etc.) and can either: (1) extract \\emph{all} of the entropy $k = m$ with a very modest security loss $\\delta\'=O(\\delta\\cdot \\log (1/\\delta))$, or alternatively, (2) achieve essentially optimal security $\\delta\' = O(\\delta)$ with a very modest entropy loss $k \\ge m+\\log\\log(1/\\delta)$. In comparison, the best prior results from \\cite{BDK+11} for this class of applications would only guarantee $\\delta\'=O(\\sqrt{\\delta})$ when $k=m$, and would need $k\\ge m+\\logdel$ to get $\\delta\'=O(\\delta)$.

- The weaker bounds of \\cite{BDK+11} hold for a larger class of so-called ``square-friendly\'\' applications (which includes all unpredictability, but also some important indistinguishability, applications). Unfortunately, we show that these weaker bounds are tight for the larger class of applications.

- We abstract out a clean, information-theoretic notion of $(k,\\delta,\\delta\')$-unpredictability extractors, which guarantee ``induced\'\' security $\\delta\'$ for any $\\delta$-secure unpredictability application $P$, and characterize the parameters achievable for such unpredictability extractors. Of independent interest, we also relate this notion to the previously-known notion of (min-entropy) condensers, and improve the state-of-the-art parameters for such condensers.

We demonstrate how to construct statistical zero-knowledge authentication protocols for smart cards based on general assumptions. The main protocol is only secure against active attacks, but we present a modification based on trapdoor commitments which can resist concurrent attacks as well. Both protocols are instantiated using lattice-based constructs, which are secure against quantum attacks. We illustrate the practicality of our protocols on smart cards in terms of storage, computation, communication, and round complexity, and it is shown that our protocols are superior to known lattice-based zero-knowledge protocols in these aspects.

We introduce a hybrid homomorphic encryption by combining public key encryption (PKE) and somewhat homomorphic encryption (SHE) to reduce storage for most applications of somewhat or fully homomorphic encryption (FHE). In this model, one encrypts messages with a PKE and computes on encrypted data using a SHE or a FHE after homomorphic decryption.

To obtain efficient homomorphic decryption, our hybrid schemes is constructed by combining IND-CPA PKE schemes without complicated message paddings with SHE schemes with large integer message space. Furthermore, we remark that if the underlying PKE is multiplicative on a domain closed under addition and multiplication, this scheme has an important advantage that one can evaluate a polynomial of arbitrary degree without recryption.

We propose such a scheme by concatenating ElGamal and Goldwasser-Micali scheme over a ring $\\Z_N$ for a composite integer $N$ whose message space is $\\Z_N^\\times$.

To be used in practical applications, homomorphic decryption of the base PKE is too expensive. We accelerate the homomorphic evaluation of the decryption by introducing a method to reduce the degree of exponentiation circuit at the cost of additional public keys. Using same technique, we give an efficient solution to the open problem~\\cite{KLYC13} partially.

As an independent interest, we obtain another generic conversion method from private key SHE to public key SHE. Differently from Rothblum~\\cite{RothTCC11}, it is free to choose the message space of SHE.

Nominative Signature is a useful tool in situations where a signature has to be created jointly by two parties, a nominator (signer) and a nominee (user), while only the user can verify and prove to a third party about the validity of the signature. In this paper, we study the existing security models of nominative signature and show that though the existing models have captured the essential security requirements of nominative signature in a strong sense, especially on the unforgeability against malicious signers/users and invisibility, they are yet to capture a requirement regarding the privacy of the signer and the user, and this requirement has been one of the original ones since the notion of nominative signature was first introduced. In particular, we show that it is possible to build a highly efficient nominative signature scheme which can be proven secure in the existing security models, while in practice it is obvious to find out from the component(s) of a nominative signature on whether a particular signer or user has involved in the signature generation, which may not be desirable in some actual applications. We therefore propose an enhanced security property, named \"Ambiguity\", and also propose a new \\emph{one-move} nominative scheme for fulfilling this new security requirement without random oracles, and among the various types of nominative signature, one-move is the most efficient type. Furthermore, this new scheme is at least 33% more efficient during signature generation and 17% shorter in signature size when compared with the existing one-move signature schemes without random oracles even that the existing ones in the literature may not satisfy this new Ambiguity requirement.

RFID tags are getting their presence noticeable on smartphones,

credit cards, toll payment devices, and other objects. They are

expected to become an important tool for e-commerce, logistics,

point-of-sale transactions, and so on, representing ``things\'\' and

``human holding things\'\' in transactions. Since a huge amount of tags are expected to be needed to be attached to various ``objects,\'\' a low-cost tag manufacturing is necessary. Thus, it is hard to imagine they will implement hardware protection mechanisms (like co-processor, TPMs). Therefore, side-channel (leakage) attacks are a critical threat. Another threat that is well known in the RFID topic is tag tracing and violation of privacy.

In this paper, we consider physically unclonable functions (PUFs) as tamper resilient building block and propose security model with memory leaking adversary, trying to violate security and privacy of tags (we note that PUFs are structure-less and there is a hope they can be put on top of RFID chips more so than TPMs). We then design the first provably secure and provably private RFID authentication protocol withstanding information leakage from the non-volatile memory of the tag, and provides the two properties of: (1) security against impersonation, and (2) privacy protection against tag tracing.

At CHES 2013 was presented a new block cipher called Zorro. Although it uses only 4 S-boxes per round, the designers showed the resistance of the cipher against various attacks, and concluded the cipher has a large security margin. In this paper, we give a key recovery attack on the full cipher in the single-key model that works for $2^{64}$ out of $2^{128}$ keys. Our analysis is based precisely on the fact that the non-linear layer has only 4 S-boxes. We exploit this twice in a two-stage attack: first, we show that Zorro has an equivalent description that does not have constants in the rounds, and then, we launch an internal differential attack on the newly described cipher. With computer verifications we confirm the correctness of the analysis.

Our attack is the first to use internal differentials for block ciphers, thus we adapt Daemen\'s attack on Even-Mansour construction

to the case of internal differentials (instead of differentials), which allows us to recovery to full key.

This work provides as well insights on alternative descriptions of general Zorro-type ciphers (incomplete non-linear layers),

the importance of well chosen constants, and the advantages of Daemen\'s attack.

In this paper we propose a method which will preserve sum-

mary statistics of data organized in a two way table. We have shown that

fully homomorphic encryption is a powerful solution. However it has a

number of disadvantages which makes it impractical. We have proposed

a Restricted homomorphic encryption method which uses Pailier encryp-

tion and order preserving encryption. This new method can be used for

practical purposes owing to it\'s efficiency in terms of both speed and

storage.

We present RASP, a new protocol for privacy-preserving range

search and sort queries on encrypted data in the face of an

untrusted data store. The contribution of RASP over related work

is twofold: first, RASP improves privacy guarantees by ensuring

that after a query for range [a,b] any new record added to the

data store is indistinguishable from random, even if the new

record falls within range [a,b]. Second, RASP is highly

practical, abstaining from expensive asymmetric cryptography and

bilinear pairings. Instead, RASP only relies on hash and block

cipher operations. The main idea of RASP is to build upon a new

update-oblivious bucket-based data structure. We allow for data

to be added to buckets without leaking into which bucket it has

been added. As long as a bucket is not explicitly queried, the

data store does not learn anything about bucket

contents. Furthermore, no information is leaked about data

additions following a query. Besides formally proving RASP\'s

privacy, we also present a practical evaluation of RASP using

Amazon Dynamo.

As an internationally active and highly growth-oriented company in the field of embedded security, ESCRYPT supports all industry segments in need of security solutions for embedded systems, including automotive, industrial control systems, energy, and consumer electronics. In this area, ESCRYPT, a 100-percent subsidiary of ETAS GmbH, a member of the Bosch Group, is a leading system house.

YOUR TASKS

You will be the CEO/General Manager of ESCRYPT Inc., a branch of ESCRYPT with today around 10 people.

The position profile includes:

- Team leader to motivate the ESCRYPT employees

- Familiarity with small technology companies and ability to handle large stake-holders.

- Ability to effectively manage administrative tasks

- Commercial and sales orientation: ability to drive the business and to manage business development

- Technical background to understand fundamentals of ESCRYPT’s business

PROFESSIONAL REQUIREMENTS

You must have BS Degree in Computer Science, Engineering, or a related technical field, as well as experience in team leadership, sales and business strategy. MS in Computer Science or Engineering, or an MBA is strongly preferred.

PERSONAL REQUIREMENTS

- Willing to work in a flexible team

- Reliability

- Independent and thoughtful

- Pleasant communication skills

WE OFFER

We offer opportunities for working independently and with self-reliance in a dynamic team whose members are highly qualified and internationally experienced. Your work environment will feature challenging and diversified tasks, flat hierarchies, and performance based-compensation in an appealing and open-minded corporate climate. We offer generous benefits.

Send us your full application with key number USA-1310GM by email to jobs (at) escrypt.com. We look forward to hearing from you!

CONTACT

Dr. Thomas Wollinger

tho