International Association
for Cryptologic Research

Name: Ferucio Laurentiu Tiplea

Name: Ruxandra F. Olimid
Topic: Secret Sharing-based Group Key Establishment
Category: (no category)

Description: Group applications permit multiple users to share resources or perform collaborative tasks while providing differentiate rights or responsibilities within the group. Examples include text communication, audio, video or web conferences, data sharing or collaborative computing.\r\n\r\n
\r\nSecurity represents an important aspect for group applications. It is a challenging task to deal with, especially when the group size is large and the members are spread across different (location or networks) areas, with diverse protection mechanisms. In order to obtain the main cryptographic properties as confidentiality, authenticity and integrity it is usually required that the group members previously share a common secret group key. This is achieved as theoutput of a group key establishment protocol.\r\n\r\n
\r\nThe thesis restricts to group key establishment protocols based on secret sharing, a primitive that divides a secret into multiple shares such that only authorized subset of shares allow reconstruction. Although secret sharing brings several advantages when it is used as a building block of group key establishment protocols, two important shortcomings currently exist: (1) several insecure proposals were published in the last years and (2) very few constructions rely on a security proof. We address both this issues in the present work.\r\n\r\n
\r\nThe first part of the dissertation focuses on the underlying secret sharing schemes. We review a non-classical approach of secret sharing, dene a new visual secret sharing scheme and analyze the possibility of malicious manufacturing of the sharing device. The second part of the thesis concentrates on group key establishment constructions that use secret sharing. We introduce a multitude of attacks against recent protocols and therefore highlight the necessity of security proofs. We review the properties that impose a sufficient level of security and briefly analyze the formal models of security. Finally, we introduc[...]

Name: Adrian Atanasiu

Microsoft Research invites applications from graduate students and recent Ph.D.s for Postdoctoral and Internship positions in the Microsoft Research Cryptography Group. Number Theory candidates should have interest/experience in one or more of the following areas: algorithmic/arithmetic/algebraic number theory, elliptic and hyperelliptic curve cryptography, pairing-based cryptosystems, lattice-based cryptography. Cryptography candidates should have research interests in at least one of the following: protocols, security models, cryptanalysis, hash functions, applied or theoretical cryptography.

Post-docs and interns will be in residence at Microsoft Research Redmond, the main campus of Microsoft\\\'s basic research division with over four hundred researchers in dozens of areas of computer science research. Researchers benefit from close proximity to Microsoft product units, collaborative relations and joint seminars with University of Washington, and an active research environment. For more information about MSR Redmond and the Cryptography group see: http://research.microsoft.com/aboutmsr/labs/redmond/ and http://research.microsoft.com/crypto/

The post-doctoral positions offer a competitive salary, benefits, and a relocation allowance. The term is for two years; the start date is July 1, 2014. Post-docs will report to Dr. Kristin Lauter, Research Manager for the MSR Crypto Group. Internships for graduate students will be for 10-12 weeks in Summer 2014, with flexible start date.

Submission: 28 February 2014
Notification: 21 April 2014
From July 14 to July 16
Location: Vienna, Austria
More Information: http://dbsec2014.sba-research.org

In TPM2.0, a single signature primitive is proposed to sup-

port various signature schemes including Direct Anonymous Attestation

(DAA), U-Prove and Schnorr signature. This signature primitive is im-

plemented by several APIs. In this paper, we show these DAA-related

APIs can be used as a static Diffie-Hellman oracle thus the security

strength of these signature schemes can be weakened by 14-bit. We pro-

pose a novel property of DAA called forward anonymity and show how

to utilize these DAA-related APIs to break forward anonymity. Then we

propose new APIs which not only remove the Static Diffie-Hellman oracle

but also support the forward anonymity, thus significantly improve the

security of DAA and the other signature schemes supported by TPM2.0.

We prove the security of our new APIs under the discrete logarithm

assumption in the random oracle model. We prove that DAA satisfy for-

ward anonymity using the new APIs under the Decision Diffie-Hellman

assumption. Our new APIs are almost as efficient as the original APIs

in TPM2.0 specification and can support LRSW-DAA and SDH-DAA

together with U-Prove as the original APIs.

The Fibonacci-to-Galois transformation is useful for reducing the propagation delay of feedback shift register-based stream ciphers and hash functions. In this paper, we extend it to handle Galois-to-Galois case as well as feedforward connections. This makes possible transforming Trivium stream cipher and increasing its keystream data rate by 27\\% without any penalty in area. The presented transformation might open new possibilities for cryptanalysis of Trivium, since it induces a class of stream ciphers which generate the same set of keystreams as Trivium, but have a different structure.

In this paper we study the problem that when a Boolean function can

be represented as the sum of two bent functions. This problem was

recently presented by N. Tokareva in studying the number of bent

functions. Firstly, many functions, such as

quadratic Boolean functions, Maiorana-MacFarland bent functions,

partial spread functions etc, are proved to be able to be

represented as the sum of two bent functions. Methods to construct

such functions from low dimension ones are also introduced. N.

Tokareva\'s main hypothesis is proved for $n\\leq 6$. Moreover,

two hypotheses which are equivalent to N. Tokareva\'s main hypothesis

are presented. These hypotheses may lead to new ideas or methods to

solve this problem. At last, necessary and sufficient conditions on

the problem when the sum of several bent functions is again a bent

function are given.

Technological advancements in cloud computing due to increased connectivity and exponentially proliferating data has resulted in migration towards cloud architecture. Cloud computing is technology where the users\' can use high end services in form of software that reside on different servers and access data from all over the world. Cloud storage enables users to access and store their data anywhere. It also ensures optimal usage of the available resources. There is no need for the user to maintain the overhead of hardware and software costs. With a promising technology like this, it certainly abdicates users\' privacy, putting new security threats towards the certitude of data in cloud. The user relies entirely for his data protection on the cloud providers, making them solely responsible for safeguarding it. The security threats such as maintenance of data integrity, data hiding and data safety dominate our concerns when the issue of cloud security come up. The voluminous data and time consuming encryption calculations related to applying any encryption method have been proved as a hindrance in this field.

In this research paper, we have contemplated a design for cloud architecture which ensures secured movement of data at client and server end. We have used the non breakability of Elliptic curve cryptography for data encryption and Diffie Hellman Key Exchange mechanism for connection establishment. The proposed encryption mechanism uses the combination of linear and elliptical cryptography methods. It has three security checkpoints: authentication, key generation and encryption of data.

Menezes--Qu--Vanstone key agreement (MQV) is intended to provide implicit key authentication (IKA) and several other security objectives. MQV is approved and specified in five standards.

This report focuses on the IKA of two-pass MQV, without key confirmation. Arguably, implicit key authentication is the most essential security objective in authenticated key agreement. The report examines various necessary or sufficient formal conditions under which MQV may provide IKA.

Incidentally, this report defines, relies on, and inter-relates various conditions on the key deriviation function and Diffie--Hellman groups. While it should be expected that most such definitions and results are already well-known, a reader interested in these topics may be interested in this report as a kind of review, even if they have no interest in MQV whatsoever.

Submission: 16 March 2014
Notification: 23 May 2014
From September 25 to September 26
Location: Aveiro, Portugal
More Information: http://cms2014.web.ua.pt

Random number generators have direct applications in information security, online

gaming, gambling, and computer science in general. True random number generators

need an entropy source which is a physical source with inherent uncertainty, to ensure

unpredictability of the output. In this paper we propose a new indirect approach to

collecting entropy using human errors in the game play of a user against a computer. We

argue that these errors are due to a large set of factors and provide a good source of

randomness. To show the viability of this proposal, we design and implement a game,

conduct a user study in which we collect user input in the game, and extract randomness

from it. We measure the rate and the quality of the resulting randomness that clearly

show effectiveness of the approach. Our work opens a new direction for construction of

entropy sources that can be incorporated into a large class of video games.

Recently, Fan et al. proposed a user efficient recoverable off-line e-cash scheme with fast anonymity revoking. They claimed that their scheme could achieve security requirements of an e-cash system such as, anonymity, unlinkability, double spending checking, anonymity control, and rapid anonymity revoking on double spending. They further formally prove the unlinkability and the un-forgeability security features. However, after crypto-analysis, we found that the scheme cannot attain the two proven security features, anonymity and unlinkability. We, therefore, modify it to comprise the two desired requirements which are very important in an e-cash system.

The paper is about methodology to detect and demonstrate impossible differentials in a block cipher. We were inspired by the shrinking technique proposed by Biham et al. in 1999 which recovered properties of scalable block cipher structures from numerical search on scaled down variants. Attempt to bind all concepts and techniques of impossible differentials together reveals a view of the search for impossible differentials that can benefit from the computational power of a computer. We demonstrate on generalized Feistel networks with internal permutations an additional clustering layer on top of shrinking which let us merge numerical data into relevant human-readable information to be used in an actual proof. After that, we show how initial analysis of scaled down TEA-like schemes leaks the relevant part of the design and the length and ends of the impossible differentials. We use that initial profiling to numerically discover 4 15-round impossible differentials (beating the current 13-round) and thousands of shorter ones.

Even as data and analytics driven applications are becoming increasingly popular, retrieving data from shared databases poses a threat to the privacy of their users. For example, investors/patients retrieving records about interested stocks/diseases from a stock/medical database leaks sensitive information to the database server. PIR (Private Information Retrieval) is a promising security primitive to protect the privacy of users\' interests. PIR allows the retrieval of a data record from a database without letting the database server know which record is being retrieved. The privacy guarantees could either be information theoretic or computational. Ever since the first PIR schemes were proposed, a lot of work has been done to reduce the communication cost in the information-theoretic settings - particularly the question communication cost, i.e., the traffic from the user to the database server. The answer communication cost (the traffic from the database server to the user) has however barely been improved. When question communication cost is much lower than the record length, reducing question communication cost has marginal benefit on lowering overall communication cost. In contrast, reducing answer cost becomes very important. In this paper we propose ramp secret sharing based mechanisms that reduce the answer communication cost in information-theoretic PIR. We have designed four information-theoretic PIR schemes, using three ramp secret sharing approaches, achieving answer communication cost close to the cost of non-private information retrieval. Evaluation shows that our PIR schemes can achieve lower communication cost and the same level of privacy compared with existing schemes. Our PIR schemes\' usages are demonstrated for realistic settings of outsourced data sharing and P2P content delivery scenarios. Thus, our approach makes PIR a viable communication efficient technique to protect user interest privacy.

In this paper, we propose a new algorithm for solving the approximate common divisors problems, which is based on LLL reduction algorithm of certain special lattice and linear equation solving algorithm over integers. Through both theoretical argument and experimental data, we show that our new algorithm is a polynomial time algorithm under reasonable assumptions on the parameters. We use our algorithm to solve concrete problems that no other algorithm could solve before. Further more, we show that our algorithm can break

the fully homomorphic encryption schemes, which are based on the approximate common divisors problem, in polynomial time in terms of the system parameter $\\lambda$.

When represented as a bit string in a standard way, even using point compression, an elliptic curve point is easily distinguished from a random bit string. This property potentially allows an adversary to tell apart network traffic that makes use of elliptic curve cryptography from random traffic, and then intercept, block or otherwise tamper with such traffic.

Recently, Bernstein, Hamburg, Krasnova and Lange proposed a partial solution to this problem in the form of Elligator: an algorithm for representing around half of the points on a large class of elliptic curves as close to uniform random strings. Their proposal has the advantage of being very efficient, but suffers from several limitations:

* Since only a subset of all elliptic curve points can be encoded as a string, their approach only applies to cryptographic protocols transmitting points that are rerandomizable in some sense.

* Supported curves all have non-trivial $2$-torsion, so that Elligator cannot be used with prime-order curves, ruling out standard ECC parameters and many other cryptographically interesting curves such as BN curves.

* For indistinguishability to hold, transmitted points have to be uniform in the whole set of representable points; in particular, they cannot be taken from a prime order subgroup, which, in conjunction with the non-trivial $2$-torsion, rules out protocols that require groups of prime order.

In this paper, we propose an approach to overcome all of these limitations. The general idea is as follows: whereas Bernstein et al. represent an elliptic curve point P as the bit string \\iota^{-1}(P), where \\iota is an injective encoding to the curve (which is only known to exist for some curve families, and reaches only half of all possible points), we propose to use a randomly sampled preimage of P under an admissible encoding of the form f^{\\otimes 2}: (u,v)\\mapsto f(u)+f(v), where f is essentially any algebraic encoding. Such encodings f exist for all elliptic curves, and the corresponding admissible encodings f^{\\otimes 2} are essentially surjective, inducing a close to uniform distribution on the curve.

As a result, our bit string representation is somewhat less compact (about twice as long as Elligator), but it has none of the limitations above, and can be computed quite efficiently when the function f is suitably chosen.

We provide new provable polynomial time solutions

of a number of problems in noncommutative-algebraic cryptography.

In contrast to the linear centralizer method of \\cite{LinCent}, the new method is

very simple: In order to solve linear equations on matrices

restricted to matrix groups, solve them over the generated

algebras. We name this approach the \\emph{algebraic span method}.

The resulting algorithms are have substantially better performance than those of \\cite{LinCent}.

These algorithms constitute cryptanalyses of the motivating protocols that

cannot be foiled by changing the distributions used in the protocols, and are

practical for most affordable parameter settings.

We put forth a lookup-table-based modular reduction method which partitions the binary string of an integer to be reduced into blocks according to its runs. Its complexity depends on the amount of runs in the binary string. We show that the new reduction is almost twice as fast as the popular Barrett\'s reduction, and provide a thorough complexity analysis of the method.

Since its introduction more than a decade ago the homomorphic properties of the NTRU encryption scheme have gone largely ignored. A variant of NTRU proposed by Stehle and Steinfeld was recently extended into a full fledged multi-key fully homomorphic encryption scheme by Alt-Lopez, Tromer and Vaikuntanathan (ATV). This NTRU based FHE presents a viable alternative to the currently dominant BGV style FHE schemes. While the scheme appears to be more efficient, a full implementation and comparison to BGV style implementations has been missing in the literature. In this work, we develop a customized implementation of the ATV scheme. First parameters are selected to yield an efficient and yet secure ATV instantiation. We present an analysis of the noise growth that allows us to formulate a modulus cutting strategy for arbitrary circuits. Furthermore, we introduce a specialization of the ring structure that allows us to drastically reduce the public key size making evaluation of deep circuits such as the AES block cipher viable on a standard computer with a reasonable amount of memory. Moreover, with the modulus specialization the need for key switching is eliminated. Finally, we present a generic bit-sliced implementation of the ATV scheme that embodies a number of optimizations. To assess the performance of the scheme we homomorphically evaluate the full 10 round AES circuit in 31 hours with 2048 message slots resulting in 55 sec per AES block evaluation time.