Im Sommersemester 2009 wurde das Seminar vom Lehrstuhl für Kryptologie und IT-Sicherheit organisiert. Untenstehend finden Sie eine Liste der geplanten Termine und Vorträge für das ganze Semester.

**Jonas
Schrieb**

Effiziente Chosen-Ciphertext-Sicherheit aus selective-ID sicherer
identitätsbasierter Verschlüsselung

Identitätsbasierte Verschlüsselung (IBE) ist eine Variante der Public Key Verschlüsselung (PKE), bei der öffentliche Schlüssel aus beliebigen Bitstrings (= "Identität" des Empfängers, z.B. Emailadresse) abgeleitet werden können, statt sie von einem Schlüsselserver herunterzuladen. Ein beliebiges chosen-plaintext sicheres IBE kann mittels black-box Transformationen in chosen-ciphertext sicheres PKE verwandelt werden (Boneh, Canetti, Halevi, Katz), allerdings hat das resultierende PKE im Vergleich zum IBE längere Chiffretexte und eine erhöhte Laufzeit. Für zwei konkrete IBE wurde diese Konstruktion unter Ausnutzung spezieller struktureller Eigenschaften so weit optimiert, dass das Resultat keinerlei Effizienzverlust ausweist (Boyen, Mei, Waters), allerdings ist die Konstruktion nicht black-box und ihre Anwendbarkeit auf andere IBE unklar. Für das stärkere (adaptive-ID) dieser beiden IBE konnte diese effiziente Konstruktion zu einer black-box Transformation ausgehend von "partitioniertem" IBE verallgemeinert werden (Abe, Cui, Imai, Kiltz), nicht aber für das schwächere (selective-ID) IBE, welches statt einem PKE nur ein Key-Encapsulation Verfahren liefert. Diese Lücke soll in diesem Vortrag geschlossen werden.

# A Security Modeling Approach for
Web-Service-based Business Processes

Meiko Jensen

The rising need for security in SOA applications requires better
support for management of non-functional properties in web-based
business processes. Here, the model-driven approach may provide
valuable benefits in terms of maintainability and deployment. Apart
from modeling the pure functionality of a process, the
consideration of security properties at the level of a process
model is a promising approach.

In this talk, I present an extension to the ARIS SOA Architect that
is capable of modeling security requirements as a separate security
model view. Further I provide a transformation that automatically
derives WS-SecurityPolicy-conformant security policies from the
process model, which in conjunction with the generated WS-BPEL
processes and WSDL documents provides the ability to deploy and run
the complete security-enhanced process based on Web Service
technology.

# XML Similarity, Background, Applications
and Motivations

Stefania Marrara

In this talk I present a survey of the most important applications of XML in Information Retrieval, semi-structured databases and application interoperability (Web Services). Starting from IR and DB domains I motivate the need of similarity measures for XML documents and detail the main approaches available in literature. Then I show their application in XML retrieval and motivate their expected benefits in the field of Web Services security performance.

# RFID Security

Timo Kasper

RFID Technologie wird derzeit weit verbreitet angewendet, z.B. in der Logistik, in Wegfahrsperren, im elektronischen Reisepass oder in kontaktlosen Kreditkarten. Der Vortrag gibt einen Überblick über mögliche Risiken und Bedrohungen durch den Einsatz dieser eingebetteten Funksysteme, und erfasst den aktuellen Stand der Sicherheit anhand von Forschungsergebnissen und der Analyse kommerzieller, im alltäglichen Einsatz befindlicher RFID Produkte.

# Practical secure evaluation of
semi-private functions

Annika Paus

Two-party Secure Function Evaluation (SFE) is a very useful
cryptographic tool which allows two parties to evaluate a function
known to both parties on their private (secret) inputs. Some
applications with sophisticated privacy needs require the function
to be known only to one party and kept private (hidden) from the
other one. However, existing solutions for SFE of private functions
(PF-SFE) deploy Universal Circuits (UC) and are still very
inefficient in practice.

In this paper we bridge the gap between SFE and PF-SFE with SFE of
what we call {\em semi-private functions} (SPF-SFE), i.e., one
function out of a given class of functions is evaluated without
revealing which one.

We present a general framework for SPF-SFE allowing a fine-grained
trade-off and tuning between SFE and PF-SFE covering both extremes.
In our framework, semi-private functions can be composed from
several privately programmable blocks (PPB) which can be programmed
with one function out of a class of functions. The framework allows
efficient and secure embedding of constants into the resulting
circuit to improve performance. To demonstrate practicability of
the framework we have implemented a compiler for SPF-SFE based on
the Fairplay SFE framework.

SPF-SFE is sufficient for many practically relevant
privacy-preserving applications, such as privacy-preserving credit
checking which can be implemented using our framework and compiler
as described in the paper.

# Secure VPNs for Trusted Computing
Environments

Steffen Schulz

Virtual Private Networks are a popular mechanism to allow the
use of perimeter security measures for complex network
infrastructures. Enforcement of access restrictions on the
endpoints of the VPN becomes difficult however if the endpoints of
the VPN are, e.g, personal computers for remote user access.
Commonly employed measures like anti-virus or software agents fail
to defend against unanticipated or targeted attacks.

The Trusted Computing Group invested significant work into
platforms that are capable of secure integrity reporting. However,
trusted boot and remote attestation require a redesign of critical
software components in order to be useful. In this work, we design
and implement a VPN architecture for trusted platforms. We solve
the conflict between security and flexibility by implementing a
self-contained VPN service that is isolated from the operating
system environment visible to the user. We develop a hardened
version of the IPsec architecture and protocols by addressing known
security issues and by reducing the complexity of the underlying
protocols. The resulting prototype implements secure user
authentication, access control and secure channels via IPsec ESP
and IKEv2 in only 5,000 lines of code. We expect this focus on
security and reduced complexity to result in inherently more
reliable and therefore more trustworthy software.

# The Generic Hardness of Subset
Membership Problems under the Factoring Assumption

Tibor Jager

We analyze a large class of subset membership problems related to integer factorization. We show that there is no algorithm solving these problems efficiently without exploiting properties of the given representation of ring elements, unless factoring integers is easy. Our results imply that problems with high relevance for a large number of cryptographic applications, such as the quadratic residuosity and the subgroup decision problems, are generically equivalent to factoring.

# Secure Evaluation of Private Linear Branching Programs with Medical Applications

Mauro Barni, Pierluigi Failla, Vladimir Kolesnikov, Riccardo Lazzeretti, Ahmad-Reza Sadeghi, and **Thomas Schneider**

Diagnostic and classification algorithms play an important role in data analysis, with applications in areas such as health care, fault diagnostics, or benchmarking. Branching programs (BP) is a popular representation model for describing the underlying classification/diagnostics algorithms. Typical application scenarios involve a client who provides data and a service provider (server) whose diagnostic program is run on client's data. Both parties need to keep their inputs private.

We present new, more efficient privacy-protecting protocols for remote evaluation of such classification/diagnostic programs. In addition to efficiency improvements, we generalize previous solutions -- we securely evaluate private linear branching programs (LBP), a useful generalization of BP that we introduce. We show practicality of our solutions: we apply our protocols to the privacy-preserving classification of medical ElectroCardioGram (ECG) signals and present implementation results. Finally, we discover and fix a subtle security weakness of the most recent remote diagnostic proposal, which allowed malicious clients to learn partial information about the program.

Available as ePrint report at http://eprint.iacr.org/2009/195.

# Parallel Harvesting for Index Calculus

**Roberto Avanzi**, Nicolas Theriault, Anoosheh Zaerin

In some cases low genus hyperelliptic curves (HEC) can offer better performance than elliptic curves. It is thus interesting to assess their security, which relies on the difficulty of the underlying Discrete Logarithm Problem (DLP). The best known attacks on the DLP on HEC are of the index calculus family. An index calculus algorithm works similarly to the number field sieve, and in particular it calls for the solution of a large linear algebra system. Before the linear algebra is done, it is common to process the linear system to remove duplicate and superfluous relations. This intermediate stage is called filtering.

For the index calculus on Jacobians of low genus curves Avanzi and Th{\'e}riault suggested a filtering strategy called harvesting, which can reduce the running time of the whole index calculus by 30\%\ or more. However, this requires to redesign the whole index calculus algorithm and in particular to collect a much larger system to begin with, raising the question of feasibility because of the huge storage requirements.

We thus developed a parallel version of this filtering technique. This required a careful analysis of the original serial algorithm and separation of the harvesting process in a control part and in processes that carry the actual removal of the equations.

The version we introduce can be made massively parallel, making this the index-calculus-with-harvesting approach feasible. Furthermore, its time complexity is linear in the size of the system, making its running time negligible with respect to the whole index calculus method.

We also present test results of serial and distributed harvesting implementations.

# Side-Channel Analysis Resistant Implementation of AES on
Automotive Processors.

Andreas Hoheisel

The topic of side-channel attacks is one of the most important issues in applied cryptography. In the literature, one can find many results on high security systems like smart cards. However, until now we are not aware of any side-channel analysis resistant implementation of AES on automotive processors. For the first time, an efficient (32-bit optimized) and secured (countermeasures against timing and power analysis) AES implementation has been investigated on automotive platforms.

In this talk, i present an efficient and side-channel secured AES implementation for a typical automotive processor. The resulting implementation is very competitive in terms of program and memory size as well as performance. The security of the implementation is adapted to the current security level of automotive processors (low-cost countermeasures since we have no secure memory or tamper protection). Therefor i will peresent currently known masking methods and combine them with randomization to archive a first order DPA resistance.

# Twin Signature Schemes, Revisited

Sven Schäge

In this paper, we revisit the twin signature scheme by Naccache, Pointcheval and Stern from CCS 2001 that is secure under the Strong RSA (SRSA) assumption and improve its efficiency in several ways. First, we present a new twin signature scheme that is based on the Strong Diffie-Hellman (SDH) assumption in bilinear groups. Since bilinear groups can, at the same level of security, have a much compacter group representation than RSA groups, the new scheme allows for very short signatures and key material. Another advantage of the SDH based scheme is that, in contrast to the original scheme, it does not require a computationally expensive function which injectively maps messages to primes. We prove this new scheme secure under adaptive chosen message attacks. Second, we present a modification that allows to significantly increase efficiency when signing long messages. This construction uses collision-resistant hash functions as its basis. As a result, our improvements make the signature length independent of the message size. Our construction deviates from the standard hash-and-sign approach in which the hash value of the message is signed in place of the message itself. We show that in the case of twin signatures, one can exploit the collision-resistance property of the hash function as an integral part of the signature scheme. This improvement can be applied to both the SRSA based and SDH based twin signature scheme.

# Toward a Rigorous Generalization of Coppersmith's Methods for Finding

Small Roots of Multivariate Polynomial Equations

Aurelie Bauer

In
1996, Coppersmith introduced two lattice-based techniques for finding
small roots of polynomial equations. The first one works for the
univariate modular case, the other one for the bivariate case over the

integers. Since then, these techniques have been widely used
for cryptanalytic applications. As some of these applications use a
bigger number of variables, generalizations of Coppersmith's methods
have even

been proposed. Unfortunately, these extensions are only
heuristic as they rely on a well-known assumption concerning algebraic
independence between polynomials.

In this talk, we focus on multivariate
generalizations of Coppersmith's methods and especially on the validity
of the assumption concerning algebraic independence. Usually, this
assumption is not considered as a

problem because it is often satisfied in practice. In this
presentation, we first study the limits of using this type of
assumption by highlighting a real cryptographic counterexample. This
result emphasizes

the necessity of finding rigorous methods. In this purpose,
we propose a new construction which guarantees the algebraic
independence between polynomials and that uses Gröbner bases
computations. By applying this new technique on real cryptographic
schemes, we obtain some promising results. In particular, we manage to
prove how to make fully rigorous the attack initially proposed by Boneh
and Durfee on the RSA equation for a small private key.