*19:17* [Pub][ePrint]
Solving Random Subset Sum Problem by $l_{p}$-norm SVP Oracle, by Gengran Hu and Yanbin Pan and Feng Zhang
It is well known that almost all random subset suminstances with density less than 0.6463... can be solved with an

$l_{2}$-norm SVP oracle by Lagarias and Odlyzko. Later, Coster

\\emph{et al.} improved the bound to 0.9408... by using a different

lattice. In this paper, we generalize this classical result to

$l_p$-norm. More precisely, we show that for $p\\in \\mathbb{Z}^{+}$,

an $l_p$-norm SVP oracle can be used to solve almost all random

subset sum instances with density bounded by $\\delta_p$, where

$\\delta_1=0.5761$ and $\\delta_p =

1/(\\frac{1}{2^p}\\log_2(2^{p+1}-2)+\\log_2(1+\\frac{1}{(2^p-1)(1-(\\frac{1}{2^{p+1}-2})^{(2^p-1)})})))$

for $p\\geq 3$(asymptotically, $\\delta_p\\approx 2^p/(p+2)$). Since

$\\delta_p$ goes increasingly to infinity when $p$ tends to infinity,

it can be concluded that an $l_p$-norm SVP oracle with bigger $p$

can solve more subset sum instances. An interesting phenomenon is

that an $l_p$-norm SVP oracle with $p\\geq 3$ can help solve almost

all random subset sum instances with density one, which are thought

to be the most difficult instances.

*22:00* [PhD][Update]
Kwangsu Lee: Efficient Hidden Vector Encryptions and Its Applications
Name: Kwangsu Lee

Topic: Efficient Hidden Vector Encryptions and Its Applications

Category:public-key cryptography

Description:
Predicate encryption is a new paradigm of public key encryption that enables searches on encrypted data. Using the predicate encryption, we can search keywords or attributes on encrypted data without decrypting the ciphertexts. In predicate encryption, a ciphertext is associated with attributes and a token corresponds to a predicate. The token that corresponds to a predicate $f$ can decrypt the ciphertext associated with attributes $\vect{x}$ if and only if $f(\vect{x})=1$.

Hidden vector encryption (HVE) is a special kind of predicate encryption. HVE supports the evaluation of conjunctive equality, comparison, and subset operations between attributes in ciphertexts and attributes in tokens. Currently, several HVE schemes were proposed where the ciphertext size, the token size, and the decryption cost are proportional to the number of attributes in the ciphertext. In this thesis, we consider the efficiency, the generality, and the security of HVE schemes. The results of this thesis are described as follows.

The first results of this thesis are efficient HVE schemes where the token consists of just four group elements and the decryption only requires four bilinear map computations, independent of the number of attributes in the ciphertext. The construction uses composite order bilinear groups and is selectively secure under the well-known assumptions.

The second results are efficient HVE schemes that are secure under any kind of pairing types. To achieve our goals, we proposed a general framework that converts HVE schemes from composite order bilinear groups to prime order bilinear groups. Using the framework, we convert the previous HVE schemes from composite order bilinear groups to prime order bilinear groups.

The third results are fully secure HVE schemes with short tokens. Previous HVE schemes were proven to be secure only in the selective security model where the capabilities of the adversaries are severely restricted[...]

*10:17* [Pub][ePrint]
A Novel Modular Adder for One Thousand Bits and More Using Fast Carry Chains of Modern FPGAs, by Marcin Rogawski, Kris Gaj and Ekawat Homsirikamol
In this paper a novel, low latency family of addersand modular adders has been proposed. This family efficiently

combines the ideas of high-radix carry-save addition and the parallel

prefix networks. It also takes advantage of fast carry chains

of modern FPGAs. The implementation results reveal that these

hybrid adders have great potential for efficient implementation

of modular addition of long integers used in various public key

cryptography schemes.

*10:17* [Pub][ePrint]
Linkable Message Tagging: Solving the key distribution problem of signature schemes, by Felix Günther and Bertram Poettering
Digital signatures are one of the most extensively used cryptographic primitives today. It is well-understood that they guarantee practical security only if the corresponding verification keys are distributed authentically; however, arguably, satisfying solutions for the latter haven\'t been found yet, or at least aren\'t in large-scale deployment. This paper introduces a novel approach for cryptographic message authentication where this problem does not arise: A linkable message tagging scheme (LMT) identifies pairs of messages and accompanying authentication tags as related if and only if these tags were created using the same secret key. In other words, in contrast to signature schemes, our primitive does not aim at detecting whether individually considered messages originate from an explicitly specified entity, but instead decides whether all messages from a given collection originate from the same (possibly anonymous) source. The appealing consequence is that our primitive does not involve public keys at all, and hence elegantly sidesteps the key distribution problem of signature schemes.As an interesting application of LMT we envision an email authentication system with minimal user interaction. Email clients could routinely generate a secret LMT key upon their first invocation, and then equip all outgoing messages with corresponding tags. On the receiver\'s side, client software could automatically verify whether incoming messages originate from the same entity as previously or subsequently received messages with an (allegedly) identical sender address. Although this form of message authentication does not provide as strong guarantees of sender\'s origin as signature schemes would do, we do believe that trading the apparently discouraging obstacles implied by the authentic distribution of signature verification keys for the assumption that an attacker does not forge every message exchanged between parties is quite attractive.

On the technical side, we formalize the notions of LMT and its (more efficient) variant CMT (classifiable message tagging), including corresponding notions of unforgeability. For both variants we propose a range of provably secure constructions, basing on different hardness assumptions, with and without requiring random oracles.

*10:17* [Pub][ePrint]
Tight Security Bounds for Triple Encryption, by Jooyoung Lee
In this paper, we revisit the old problem asking the exact provable security of triple encryption in the ideal cipher model. For a blockcipher with key length k and block size n, triple encryption is known to be secure up to 2^{k+min{k/2,n/2}} queries, while the best attack requires 2^{k+min{k,n/2}} query complexity. So there is a gap between the upper and lower bounds for the security of triple encryption. We close this gap by proving the security up to 2^{k+min{k,n/2}} query complexity. With the DES parameters, triple encryption is secure up to 2^{82.5} queries, greater than the current bound of 2^{78.3} and comparable to 2^{83.5} for 2-XOR-cascade. We also analyze the security of two-key triple encryption, where the first and the third keys are identical. We prove that two-key triple encryption is secure up to 2^{k+min{k,n/2}} queries to the underlying blockcipher and 2^{min{k,n/2}} queries to the outer permutation. For the DES parameters, this result is interpreted as the security of two-key triple encryption up to 2^{32} plaintext-ciphertext pairs and 2^{81.7} blockcipher encryptions.