Denis Migdal
email: denis.migdal@ensicaen.fr

Christian Johansen

Audun Jøsang
email: josang@ifi.uio.no

Offline Trusted Device and Proxy Architecture based on a new TLS Switching technique

Infection of client devices poses a significant threat to secure user authentication. Combining vulnerable client devices with special security devices, as often the case in e-banking, can increase significantly the security. However, these often incur usability hurdles. This paper describes a new architecture where an untrusted proxy on the client device communicates both with server applications, and a trusted application running on a trusted device. The proxy switches between two TLS channels, one from the client application, and another from the trusted device. The result is a highly usable and flexible architecture with strong security assurances which, moreover, is transparent to the client or server applications, thus allowing it to be deployed in existing systems. We have implemented a PoC (available open source) and demonstrated it using the OffPAD device. Various applications of our architecture can be imagined, some of which we present in the end of the paper, applicable to web services and IoT systems.

Introduction

Server applications (server apps) typically require user authentication based on user credentials, i.e., only registered, authorized and authenticated users are granted access to services. However, client devices are often infected with malware,1 e.g., false certificate installation could facilitate phishing attacks [START_REF] Leavitt | Internet security under attack: Undermining of digital certificates[END_REF] or a keylogger [START_REF] Sagiroglu | Keyloggers[END_REF] could be installed to intercept user input s.a. user credentials, and allow false authentication to server apps. Existing solutions for protecting online transactions with strong security typically involve an external trusted device, e.g., for the generation of OTPs (One-Time Password) in e-banking.

A common architecture is to put a secure intermediary between the client applications (client apps) and the server apps, e.g., the SSL proxy concept [START_REF] Freed | Secure sockets layer proxy architecture[END_REF] or the Bitdefender BOX 2 in Internet of Things. We call this a trusted proxy. Such a trusted proxy is transparent to both the client apps and the server apps, and is assumed secure. All data passes through the trusted proxy, allowing it to read, log, modify, or suppress transmitted data.

Note that the trusted proxy technically can perform actions without the user's approval or knowledge, but it is assumed (trusted) not to do so. Usually the trusted proxy is deployed on a trusted device as a black box, and therefore, the users cannot ensure the real behaviour of the trusted proxy. Thus users have to trust the provider of the trusted device. There is also no absolute guarantee that a trusted device will not fall pray to MitM (Man-in-the-Middle) attacks on the communication from the client device. Moreover, trusted proxies are unable to perform exhaustive verifications due to the usually limited capabilities (s.a. speed of network interfaces) of the trusted device on which they are deployed. Thus the use of trusted devices should be limited in practice.

An architecture that would limit the use of trusted devices is to let client apps communicate directly with server apps, and only query a trusted application (trusted app) for sensitive information. The communications are offline as defined in [START_REF] Migdal | DEMO: OffPAD -Offline Personal Authenticating Device with Applications in Hospitals and e-Banking[END_REF], "follow[ing] controlled formats, during short and restricted time periods, not involving wireless broadband capabilities". We call such a trusted device an offline trusted device (OTD). Since communications from the trusted app to server apps goes through the (possibly infected) client device, any sensitive information would need to be protected. This concept of using a separate trusted device for sensitive computations is used by HTTP XDAA [START_REF] Klevjer | Policies and Research in Identity Management (IDMAN)[END_REF], an extension of the standard HTTP DAA [START_REF] Franks | An Extension to HTTP : Digest Access Authentication[END_REF] where the credentials and the challenge-response computations are handled by a separate trusted device.

However, in such an architecture, the trusted app does not remain transparent to neither the client apps nor the server apps. This requires adaptations of existing client apps, or server apps, in order to use the trusted app. Such adaptations (writing, installing, and maintaining specific code), are costly and are detrimental to the adoption of the architecture.

The trusted device may be transparent to server apps, meaning that the trusted device handles, in place of client apps, sensitive security computations that must not be exposed to a possibly infected client device. However, client apps, must be especially programmed to use the trusted device, usually in form of plugins. The trusted device is then just an extra security feature, e.g., MP-Auth [START_REF] Mannan | Using a personal device to strengthen password authentication from an untrusted computer[END_REF] encrypts a password with the public key of the server app, for which it uses a trusted device, but does not require one, i.e., client apps knowing the password are able to respond to the server app without interacting with the trusted device.

Alternatively, the trusted app may be known to the server app and used in a protocol designed to require a trusted device. Banking applications are such examples [START_REF] Adham | How to attack two-factor authentication Internet banking[END_REF], where the trusted device holds a secret, for example a private key specific to the user and the trusted device. In this case the server app needs to be configured when provisioning trusted devices to users.

The idea of obtaining usable authentication using an offline and private trusted device has been described and motivated in [START_REF] Jøsang | Local user-centric identity management[END_REF], which argued for managing user credentials on such a device. Here we present an architecture and a prototype implementation that combines the above described traditional architectures, i.e., using a proxy on the client device and a peripheral OTD.

Contributions

• We present a new architecture called Offline Trusted Device and Proxy (OTDP) architecture in Section 2. • The OTDP architecture is based on a novel use of TLS, which we call TLS Switching and describe in Section 3, involving two interchangeable channels for communication between the server app respectively the trusted app and the Proxy. We compare in Section 3.3 our TLS Switching technique with related works, i.e., with TLS handshake proxying [START_REF] Stebila | An analysis of TLS Handshake proxying[END_REF], TLS splitting [START_REF] Lesniewski-Laas | SSL splitting: Securely serving data from untrusted caches[END_REF], and TruWalletM [START_REF] Bugiel | TruWalletM: Secure web authentication on mobile platforms[END_REF]. • The OTDP architecture can be applied for various authentication scenarios, some given in Section 4, for the Web domain in Section 4.1 and for the IoT domain in Section 4.2. • We also discuss in Section 5 security aspects of our proposal, as well as usability aspects in Section 6.

Our work focuses on user-side security, usability, ergonomics, and transparency of the used software and hardware for both the client apps and the server apps.

The Offline Trusted Device and Proxy architecture

We consider a traditional client-server architecture where it is assumed that the client device is infected with malware. Server apps on the other hand are assumed to be secure.

Existing protocols, as well as existing trusted devices, can be used on top of the OTDP architecture, enabling the use of a trusted device without the previously discussed drawbacks of existing architectures. For applications with high security requirements, such as e-banking, eHospitals, or various IoT applications in Smart Infrastructures, it is possible to use special hardware-enabled security solutions [START_REF] Laurie | Choose the red pill and the blue pill: a position paper[END_REF]. This can be a transportable device pluggable into the client device, like the OffPAD [START_REF] Migdal | DEMO: OffPAD -Offline Personal Authenticating Device with Applications in Hospitals and e-Banking[END_REF], or a secure part of the client device s.a., a secure element, a TPM (Trusted Platform Module) [START_REF] Arthur | A Practical Guide to TPM 2.0: Using the Trusted Platform Module in the New Age of Security[END_REF][START_REF] Bursuc | Automated Verification of Dynamic Root of Trust Protocols[END_REF], or a Trusted Execution Environment3 like Intel's SGX [START_REF] Anati | Innovative technology for CPU based attestation and sealing[END_REF][START_REF] Mckeen | Innovative instructions and software model for isolated execution[END_REF][START_REF] Severinsen | Securing the End-points of the Signal Protocol using Intel SGX based Containers[END_REF].

The OTDP architecture

We propose the Offline Trusted Device and Proxy (OTDP) architecture which combines a Proxy that is sitting on the untrusted client device, and communicates with a trusted app running on an offline trusted device, holding sensitive information like user credentials. This can be seen as a combination of the positive aspects from the two classical architectures mentioned in the introduction.

Proxy

Server App

Client App

Trusted App

Client device

Trusted device

Internet Client apps communicate with server apps through the Proxy. The implementation of the Proxy, based on our TLS Switching, makes sure our OTDP architecture is transparent to both the client apps and the server apps, while still allowing to read, log, modify, and suppress exchanged data. The trusted device is able to communicate with the server app only through the proxy which controls the communication format and the time when the trusted device is used. Thus the trusted device is assumed to be an OTD. The Proxy is also assumed to be open-source, so the user can read and modify the sources. Hence the Proxy is a white box. Thus spying on the user or doing actions without the user's approval is harder for the provider of the trusted device. More important, there is no false feeling of security since the Proxy is also considered untrusted as it runs on the client device.

Sensitive information is retrieved, computed, stored, or processed by the trusted app upon its initiative, or upon requests from the Proxy which, without the knowledge of the sensitive information, cannot correctly answer queries from the server apps.

To protect the sensitive information stored and maintained by the OTD, we develop the concept of TLS Switching, presented in Sec. 3, which does not require specific algorithms or protocols on neither client apps nor server apps. We only need the Proxy installed on the client device.

Design decisions and implementation of the Proxy

The Proxy was designed to be extensible through the use of filters and commands, making it easier, for example, to add support for a new communication protocol. The following design requirements on the Proxy were followed in the implementation (link to source code is provided in footnote on page 9).

• The communication interface towards client apps (called Client's interface in Figure 2) offers several proxy protocols such as SOCKS [START_REF] Leech | SOCKS Protocol Version 5[END_REF] or HTTP Proxy [START_REF] Fielding | Hypertext Transfer Protocol -HTTP/1.1. RFC 2068[END_REF]. SOCKS v5 supports TCP and UDP streams. HTTP Proxy only supports HTTP streams. For client apps non-compliant with proxy protocols, tools can be used to "socksify" them. 4 Static redirections can easily be offered as well.

• The client interface allows trivial insertion, substitution and deletion of proxy protocols, making the proxy architecture easy to extend.

• The communication interface towards server apps (Server's interface in Figure 2) is configurable to use a network proxy if the client device sits behind one.

• The communication interface towards the trusted app has two-layers. The first layer encapsulates the communication medium, and the second abstracts the format of the messages.

-The first layer allows trivial insertions, deletions and substitutions of communication mediums such as USB, WiFi, Bluetooth, or NFC.

-The second layer uses a slave/master communication: the master is the Proxy who sends a command and the slave (the trusted app) must immediately respond. The slave/master communication makes our OTDP architecture compliant with slave/master mediums, such as ISO7816-compliant smartcards, like MasterCard's Display Card5 .

• Incoming data from client apps or server apps are processed by a set of Filters in Figure 2. Thus, by adding or removing a filter, features can be added or removed from the Proxy. If needed during the processing of messages, a filter can request information or services from the trusted app via a command, such as asking the trusted app to send sensitive information to the server app.

• The trusted app listens to a set of Commands. Similarly, by adding or removing a command, features can be added or removed from the implementation of the trusted app or adapt to specific hardware.

• The implementation of the Commands follows a command design-pattern, whereas Filters follow the chain of responsibility design-pattern [START_REF] Gamma | Design Patterns: Elements of Reusable Object-Oriented Software[END_REF]Chap. 5].

• Commands and responses are human-readable to facilitate debugging operations. In consequence, a human may monitor and understand the communication between the Proxy and the trusted app with tools such as Wireshark 6 , or to simulate the Proxy (or the trusted app) to test the trusted app (respectively the Proxy) with tools such as netcat or openssl. 7Messages start with an ASCII command-name (or response-status) followed by optional arguments. Response-status uses the HTTP statuscodes [START_REF] Fielding | Hypertext Transfer Protocol -HTTP/1.1. RFC 2068[END_REF].

• Theses communications are configurable via an XML configuration file.

Ideally, the trusted device should be integrated into an object already carried by the user, e.g., as the OffPAD [START_REF] Migdal | DEMO: OffPAD -Offline Personal Authenticating Device with Applications in Hospitals and e-Banking[END_REF] which is a phone back-cover OTD connected through microUSB to a smart phone. In case multiple users are using the same device, or the same user uses it in different contexts, the secure external device also provides specific user profile management. 3 TLS Switching

Motivation

OTDP requires two TLS channels of communication with the server app: one from the Proxy (channel P) and one from the trusted app through the Proxy (channel T). Since the Proxy resides on the untrusted client device it must be unable to read or write on channel T. Since we want OTDP to be compliant with traditional client-server architectures, the channels should be seen as one on the server app (see Figure 3). To the authors' knowledge, no existing protocol enables to do so, and as we explain in Section 3.3, close related technologies fail to meet our goals.

Description

Our use of TLS (called TLS Switching) works in two modes (or states of operation): state T (trusted app) and state P (Proxy). In both states the TLS handshake and record protocols are used [START_REF] Dierks | The Transport Layer Security (TLS) Protocol Version 1.2[END_REF].

In state T the channel T is used to exchange sensitive information with the server app. State T is reached when the trusted app performs a renegotiation [START_REF] Rescorla | Trasnport Layer Security (TLS) Renegotiation Indication Extension[END_REF] to renew the TLS session keys and initialization vectors (IVs). Due to TLS's forward and backward secrecy [START_REF] Krawczyk | On the security of the tls protocol: A systematic analysis[END_REF], the Proxy cannot deduce keys and IVs from the ones it knows. Thus the Proxy is not able to read nor write records on the channel T during the state T.

In state P the channel P is used to transmit, in a more efficient way, information between the server app and the client app. State P is reached when the trusted app renegotiates the TLS session keys and IVs, and passes them to the Proxy, enabling it to read and write records though a standard TLS connection.

Transparency: TLS Switching operates as follows (shown in Figure 4). A secure connection pre-exists between the trusted app and the Proxy (0), e.g., through microUSB in the case of the OffPAD. The client app tries to establish a TLS connection with the server app, but is connected to the Proxy (1). Optionally, the Proxy might send information to the trusted app (s.a. the server's domain name, or the TLS extensions used by the client app) (2a). The Proxy then establishes a TCP connection with the server app (2b) over which the trusted app establishes a TLS connection [START_REF] Arends | DNS Security Introduction and Requirements[END_REF]. The TLS connection is then

Trusted App (0) (1) (2b) Server Client (3) (4) (2a)
(2a) (2b) (4) (3)
(5) in state T, ready to exchange messages between the trusted app and the server app, or to go into state P (4) to allow the client app to communicate with the server app [START_REF] Arthur | A Practical Guide to TPM 2.0: Using the Trusted Platform Module in the New Age of Security[END_REF]. TLS Switching requires:

• the server app to accept TLS renegotiations [START_REF] Rescorla | Trasnport Layer Security (TLS) Renegotiation Indication Extension[END_REF], which is rather common;

• the Proxy to support the cipher suite and TLS extensions [START_REF] Blake-Wilson | Transport Layer Security (TLS) Extensions[END_REF] used in state P (by our implementation);

• the trusted app to verify TLS certificates (by design);

• the trusted app and the Proxy must be able to exchange the current cipher suite, symmetric keys and IVs in a secure way (we assume this by construction).

Related work

TLS Handshake Proxying [START_REF] Stebila | An analysis of TLS Handshake proxying[END_REF] is a technique used with edge servers that cache content to reduce the connection latency between a client and a server, i.e., the client establishes a TLS connection to a local edge instead of the distant server. However, the edge is not trusted to share the server's private key. In consequence, during the local TLS handshake the edge will forward to the server the message involving the private key, i.e., only one long-distance communication. This TLS Handshake proxying technique may be used in our architecture, but only when in state P, as our proxy cannot generate TLS records during state T. Nevertheless, this requires to modify parts of TLS libraries, and makes the trusted app and the Proxy interdependent.

SSL Splitting [START_REF] Lesniewski-Laas | SSL splitting: Securely serving data from untrusted caches[END_REF] uses a proxy to split a non-encrypted SSL connection into two streams, one for the content and one for the content's integrity. The client establishes a non-encrypted SSL connection with the server through the proxy which forwards all messages. The server answers with the Message Authentication Code (MAC) of the content and a content identifier which the proxy replaces with the cached content before sending the SSL record to the client. For encrypted connections [START_REF] Lesniewski-Laas | SSL splitting: Securely serving data from untrusted caches[END_REF] proposes a work-around by sending the symmetric encryptions keys and IVs to the proxy so that it can read SSL records, and write records knowing the MAC. Thus, the proxy is trusted for confidentiality, but not for integrity.

In our case, the Proxy needs to be able to build complete TLS records when in state P, but is not trusted to read or write when in state T, i.e., when the channel T is used.

TruWalletM [START_REF] Bugiel | TruWalletM: Secure web authentication on mobile platforms[END_REF] presents a similar approach to OTDP and TLS Switching. Instead of TLS renegotiation, TLS resumption is used implying, roughly speaking, to close and open TCP connections at each state change. This is well suited for communications using TCP connections lasting only the time the server app responds to a client app query, s.a. in HTTP1.0, AJAX. However, this is less suited when the TCP connection aims to gather many queries and responses, s.a. in HTTP2.0, or when the communication is a stream, s.a. in WebSockets, often closed when the underlying TCP connection is closed.

Moreover, the trusted device is required to establish each connection, which might lead to privacy concerns as the trusted device would be then able to log user's browsing history. This breaks one of our main motivations for OTDP. Also, TruWalletM does not consider the possibility to receive sensitive information from the server app, or to propose additional trusted device-specific features to compliant server apps, s.a. authentication of the trusted device by the server app, which we do.

TruWalletM also requires a Trusted Execution Environment (TEE) whereas our proposed architecture is compliant not only with TEE but also with generic trusted devices, even those having limited UI allowing non-confidential sensitive information inputs and notifications on the client device. Moreover our Proxy enables easy implementation of additional features, not necessarily requiring a Proxy and TLS Switching, s.a. OTPs or password auto-typing for local authentications on the client device.

TLS Switching implementation

TLS is implemented by various libraries such as GnuTLS8 or OpenSSL9 in C, and JSSE10 in Java. We implemented a proof of concept of the TLS Switching and OTDP architecture in Java v1.7 with OpenJDK's TLS engine (see source code 11 ).

The Proxy and the trusted app exchange messages through TLS records over TCP. In state T, the Proxy simply forwards messages from the trusted app to the server app, and from the server app to the trusted app. In state P, the Proxy should only process application data messages, and forward the rest to the trusted app.

We use two new types of clear messages, enabling the Proxy and the trusted app to exchange information when changing state:

• 't' messages sent by the Proxy to the trusted app in order to go into state T. Theses messages are followed by a renegotiation performed by the trusted app.

• 'p' messages sent by the trusted app to the Proxy in order to go into state P. Theses messages are preceded by a renegotiation performed by the trusted app.

The p messages contain the current TLS parameters required to partially build a TLS engine on the Proxy: the cipher suite identifier, the TLS protocol version, and the symmetric keys. This allows the Proxy to build and read TLS records without exposing the trusted app private keys.

To return into state T, as the internal state of the Proxy TLS engine is modified after reading and writing records, the trusted app's TLS engine has to be updated through t messages before performing a renegotiation. This only requires two sequence numbers, incremented for each record sent or received under the current keys.

The p messages do not have to contain sequence numbers as they can be deduced by the Proxy. Moreover, p and t messages do not have to contain initialization vectors. Indeed, RC4 cipher suites are prohibited in TLS 1.2 [START_REF] Popov | Prohibiting RC4 Cipher Suites[END_REF] thus cipher suites only offer block ciphers (AES with CBC or 3DES with CBC) or NULL cipher. Yet, in block ciphered messages, initialization vectors are randomly chosen for each record and are included in the record's message.

Implementation discussions

Our implementation allows the Proxy and the trusted app to use different TLS libraries, thus making them more independent. In particular, we modify classes on the fly to extract symmetric keys when renegotiating.

With our implementation we tried to avoid modifying and rebuilding TLS libraries, as this would need to be repeated at each library update. Also, we avoid re-implementing a whole TLS layer, which could lead to several security threats due to implementation errors or slow reactivity.

To avoid performing TLS renegotiations when not required, the Proxy performs the initial handshake in place of the trusted app. Thus, TLS connections start in state P and do not require TLS Switching as long as no sensitive information are exchanged, or expected to be exchanged. Then, to go into state T for the first time, the Proxy sends a p (with additional content) instead of a t message to the trusted app.

As an alternative, instead of exchanging ciphers information, the Proxy and the trusted app could cooperate to perform a renegotiation. One could generate and read clear renegotiation messages and the other encrypt and decrypt them with the current keys. Such a feature would cost at least one renegotiation to go into state T, and two (asking to encrypt/decrypt a renegotiation message and receiving the result) to go into state P. We tested such an alternative implementation which proved to be more costly than our current implementation.

Applications of the OTDP and TLS Switching

Two applications of OTDP have been demonstrated at [START_REF] Migdal | DEMO: OffPAD -Offline Personal Authenticating Device with Applications in Hospitals and e-Banking[END_REF] using the OffPAD device [START_REF] Varmedal | The OffPAD: Requirements and usage[END_REF], namely: cognitive (i.e., by the human user) server authentication based on the petname system [START_REF] Ferdous | Entity Authentication & Trust Validation in PKI using Petname Systems[END_REF], and user authentication based on the extended challenge-response protocol XDAA [START_REF] Klevjer | Policies and Research in Identity Management (IDMAN)[END_REF] involving the trusted device. Other possible applications of the OTDP architecture and the TLS Switching are described below (and detailed in the technical report [START_REF] Migdal | Usable authentication with an offline trusted device proxy architecture (long version)[END_REF]).

Application in web systems

Server app authentication

OTDP strengthens server apps' authentication by verifying their certificates on the trusted device, thus preventing attacks by dubious certificates injected in client apps. Moreover, using a petname system and protocol (e.g., as implemented on the OffPAD) we can achieve cognitive server app authentication, i.e., where the user is actively aware of the identity of the server apps. Whitelists and blacklists on the trusted device, and similarity checks are used as an attempt to counter phishing attacks.

User authentication

The trusted device OffPAD allows user authentication through fingerprint biometrics. This can be used to unlock user credentials in various situations. We have demonstrated the use of user credentials stored on the trusted device for the XDAA authentication protocol.

Identifying messages

The Proxy is used to identify messages from client or server app matching a specific template. The Proxy, ignorant of the sensitive information, is unable to process such messages, and thus forwards them to the trusted app. The trusted app, might then force the connection into state T and send, after user confirmation, a reply to the server app. Such a reply is built from sensitive information stored (or inputed by the user) on the trusted device. Instead of asking them from the user, sensitive information can also be generated by the trusted app, s.a. strong passwords during registrations.

Identifying client apps' messages before sending them to the server apps could be coupled with whitelists and blacklists stored in the trusted device to block unwanted messages. Examples include blocking HTTP requests to phishing websites, or even HTTP requests to advertising servers.

We use the identification of server apps' messages in the HTTP XDAA. However, some client apps might block until users provide the sensitive information directly in a form inside the client app. In such cases, users have to fill the required fields with false sensitive information to submit the form without exposing sensitive information on the client device. The usage of client apps' messages identification would then be more appropriate.

Trusted app authentications

The standard TLS handshake protocol offers client and server authentications. Server apps may authenticate the trusted app using a handshake with client authentication. In this case the trusted device stores a private key or computes one from user information, such as passwords or biometric data. The public key may be certified by the trusted device's provider, given during registration on the server app, or trusted on the first usage. The trusted app may propose other authentication methods through TLS extensions [START_REF] Blake-Wilson | Transport Layer Security (TLS) Extensions[END_REF].

The trusted app must ensure the origin and destination of sensitive information by, e.g., authenticating server apps. For this, the trusted app checks the server apps' certificate and searches the requested IP and/or domain name in its blacklist and its whitelist. In order to prevent phishing attacks, the user can be warned by the trusted app when requesting for a domain-name syntactically too close to one from the whitelist. DNSSEC [START_REF] Arends | DNS Security Introduction and Requirements[END_REF][START_REF] Bau | A security evaluation of DNSSEC with NSEC3[END_REF] may also be used by the trusted app to prevent attacks against the DNS protocol [4].

Modifying web pages

The Proxy is used to improve ergonomics by adding warnings or information about the OTDP usage and features, and to enforce desired user behaviour, e.g., see Figure 5. We can prevent the user from filling in password fields on the untrusted client device. When the form is submitted, the Proxy uses message identification (as previously described) then asks the trusted app to complete the answer on the user's behalf.

Applications in IoT systems

Privacy watchdog in Smart Grid metering

Smart Meters are plagued by privacy considerations [START_REF] Eibl | Influence of data granularity on smart meter privacy[END_REF][START_REF] Félix | Do not snoop my habits: preserving privacy in the smart grid[END_REF], because the high frequency of real-time energy consumption that they report to the energy provider results in big data that can reveal information like behaviour patterns in the home, what devices are used (coffee machine vs. tea cooker) and when, or even what brand of devices (thus life style and wealth). Solutions often involve putting an intermediary between the meter and the energy provider. The OTDP can be used, with the smart meter as the client app behind the proxy implemented by Smart Meter manufacturers with the functionality of enforcing various privacy policies that a user can configure. Security critical functionalities can be done on a specific trusted device of the user, e.g., provided by some trusted entity like a governmental body that oversees data protection issues.

The trusted device can be in the form of a javacard or secure element inserted in the smart meter.

Secure authentication in eHospitals

In hospitals equipped various IT infrastructure (like NFC door openers, smart medicine storage, RFID tagged medical devices, indoor positioning located personnel, smart operation rooms, smart UIs, etc) it is important to have usable authentication that does not interfere with medical duties [START_REF] Bardram | Pervasive Computing in Healthcare[END_REF]. The OffPAD phone jacket device [START_REF] Migdal | DEMO: OffPAD -Offline Personal Authenticating Device with Applications in Hospitals and e-Banking[END_REF] can be used by hospital personnel (also given to patients) to put around their personal mobile phones. The OTDP enables to transform the personal phone into a highly versatile authentication device, by having on the mobile phone installed the proxy as a phone app, communicating with various client apps each doing different forms of medical IT functionality, e.g., alarms, search medical devices, open doors, continuous authentication, etc.

Secure applications in Smart Transportation

The trusted device can be implemented by a secure hardware like a TPM chip or a processor with functionalities like Intel SGX. These have limited connectivity, i.e., only with the computing unit, therefore can be regarded as offline. In Smart Car/Truck the Proxy and client can be part of the car's software, whereas the OTD can be part of the owner's key or a similar pluggable device. Communication and authentication protocols can be imagined based on OTDP for securing various sensitive communications. Examples include: communication with the smart road infrastructure could be secured with OTDP, or authentication and access to in-car services like road congestion alarm and guidance, or access to car's on-board information while in service.

Security considerations

We assume that the client device, and by extension the Proxy, are compromised, allowing attackers to arbitrarily listen and modify I/O interfaces (s.a. network, screen, keyboard). The trusted device, trusted app, server app, and the TLS protocol are assumed to be secure and trustworthy. Sensitive information might originate from user inputs (s.a. passwords or fingerprints), be stored, or generated, on the trusted device. They must never be exposed on the untrusted client device. However, non-confidential sensitive information might originate from untrusted sources (s.a. the client device) but must be confirmed by the user through the trusted device and not be exposed afterward.

Thus sensitive information must be exchanged exclusively between the trusted app and the server app, i.e., only during state T. Indeed in state P, the Proxy being able to read, modify, and write records, exchanged information would be exposed. In state T, the client device ignores the current session keys, protected by the forward and backward secrecy of the TLS handshake. Moreover, a Proxy cannot enforce state P as it cannot read nor write records in order to perform a renegotiation. In order to avoid phishing attacks, handshake server authentication is asked by, and performed by, the trusted app with TLS certificate verification (see Sec 4.1.1) guaranteeing the origin (or destination) of sensitive information during state T.

Although the client device is unable to read exchanged data between the trusted app and the server app, the client device is able to know when sensitive information are exchanged, as well as their length, more or less the cipher block size (or padding length) used.

However, the client device is still able to arbitrarily modify received, and sent, information during state P. Thus the integrity and origin (or destination) of the information printed, or inputed, on the client device cannot be trusted. Although message verifications and general computations are possible, the trusted device is not intended to replace the client device [START_REF] Laurie | Choose the red pill and the blue pill: a position paper[END_REF].

More problematic, the client device might send unwanted messages during state P, s.a. asking the server app to execute actions once the user is connected, or connecting the user on a different account to make her perform actions on the attacker account (e.g. crediting money on the attacker account). We argue that in such case, the server app is vulnerable to lunchtime attacks [START_REF] Conti | FADEWICH: Fast Deauthentication over the Wireless Channel[END_REF]. To prevent such attacks, server apps should require user authentication and confirmation for any sensitive action.

OTDP being transparent to server apps, standard server apps have no concept of state T, or state P, thus send sensitive information independently of the current state, and would trust information received both during state T as well as during state P. In a transparent architecture, the trusted app thus has to predict and anticipate when sensitive information might be sent by the server app. Such predictions are not possible in a generic way, and must be performed during state T, as the client device is untrusted.

For an improved security, server apps could be programmed to take into account the current state of the connection while remaining compliant with standard client apps. During a renegotiation initiated by either the trusted app or the server app, the trusted app might offer "State T" and "State P" in the Client Hello's TLS extensions list, and go into the state requested by the server app's answer (a missing TLS extension meaning that the server app does not support the concept of state T and state P). If the trusted app wants to force the state T, it can offer the "State T" TLS extension alone. Server apps might as well ask for client authentication during handshake to authenticate the trusted app (Sec. 4.1.4). The trusted app might respond with different certificates depending on the requested state, or send an empty certificate for state P. However this could lead to incompatibilities depending on the server app's implementation of TLS. Instead, we recommend the usage of an unique TLS certificate independently of the requested state with an indication of the requested state in the Client Hello's TLS extensions list. The certificate may be certified by the trusted device's provider, trusted at first use, or given during registration on the server app.

Since we assume the communication between the Proxy and the trusted app to be secure from a network attacker, (e.g., through microUSB or NFC), and the client device is considered untrusted, OTDP architecture does not add attack vectors compared to the traditional architectures. Moreover, the communications from server apps, and from client apps, are as in traditional architectures because of the transparency that the Proxy provides. However, new attacks can come from poor design of new protocols that OTDP enables. Therefore, we would encourage the use of formal verification tools and methods when designing security protocols, s.a. ProVerif [START_REF] Blanchet | Automatic verification of correspondences for security protocols[END_REF], CryptoVerif [START_REF] Blanchet | A computationally sound mechanized prover for security protocols[END_REF], Tamarin [START_REF] Schmidt | Automated analysis of diffie-hellman protocols and advanced security properties[END_REF], or Murphi [START_REF] Mitchell | Automated analysis of cryptographic protocols using Murphi[END_REF] (each being based on different theoretical foundations).

Usability considerations

A strong method of authentication is not always enough if users are not encouraged to use it. Moreover, when interacting with client apps running on a client device which can be corrupted, users should be prevented from revealing their credentials on the client apps. However, if the system lacks ergonomics and is too constraining, users might reject, and bypass, it [START_REF] Davis | User acceptance of information technology: System characteristics, user perceptions and behavioral impacts[END_REF].

The Proxy being located on the client device, which the user controls, and the trusted app mainly responding to queries from the Proxy, the users are more aware of the normal behaviour of the Proxy and, to a certain extent, of that of the trusted app. Actions, s.a. connecting the user to a server app, should not be performed without user's knowledge, for consent as well as for security reasons. Users should thus be able to give consent in full knowledge of the cause, thus limiting required user trust toward the provider of the trusted device.

User authentication to the trusted device

The trusted device must verify the user's identity before granting access to its services and allowing the Proxy to interact with the trusted app. This prevents an attacker from using the trusted app if the trusted device is stolen or lost. In our case, the OffPAD device uses biometric fingerprint for user authentication.

Still, if the user is authenticated and the trusted device is lost, then the user should be disconnected from it. This is done automatically by the trusted app when it detects that it cannot communicate with the Proxy, which is possible when the client device on which the Proxy resides is a different physical system than the trusted device. It is less probable that the attacker can obtain both devices, except when they are joined, e.g. like in the case of the OffPAD where the trusted device is a phone-jacket, and the client device is the phone. Alternatively, we could have the user's identity verified regularly through continuous authentication techniques based on biometrics [START_REF] Kwang | An usability study of continuous biometrics authentication[END_REF][START_REF] Traore | Continuous Authentication Using Biometrics: Data, Models, and Metrics[END_REF].

User interaction

Users are warned when the trusted app waits for user inputs or when messages are blocked, by generating notifications. To prevent users from disabling them, notifications must be used with care. At the same time, the Proxy displays explanations or security messages on the client device. This improves the ergonomics, but as the client device might be corrupted, these explanations must be used with care. For a web browser, a notification page is shown to the user, requesting her to check the trusted device. When the user has performed the requested actions on the trusted app, the page is automatically refreshed (using AJAX).

The Proxy also modifies the responses from the server apps to insert fields or informative messages. As shown in Figure 5, the Proxy inserts scripts in HTML pages to disable password inputs. In this way the user is prevented from filling, out of habit, the password input [START_REF] Verplanken | Interventions to break and create consumer habits[END_REF]. Alternatively, the user has the option to disable such interferences so to use the input field normally when needed. The Proxy could also be used to let the user input information (or commands) for the trusted app on the client device, which, is more ergonomic, especially if the trusted device has limited user inputs (e.g. no keyboard). The provided information must not be confidential, and must be verified and confirmed by the user on the trusted device.

User behaviour

Credentials, s.a. passwords, should not be exposed to users as they might write them on a post-it, or share them with colleagues or with social engineering attackers [START_REF] B Dawn Medlin | Analyzing the vulnerability of us hospitals to social engineering attacks: how many of your employees would share their password[END_REF]. Credentials could be generated by the trusted app at registration, and never shown to users. Since these do not need to be remembered, credentials can be safer, with more entropy, while being unique for each server app [START_REF] Gaw | Password management strategies for online accounts[END_REF].

Users typically do not change their credentials at reasonable intervals as they should do. Stored credentials and other sensitive information could have an expiration date which when reached would warn the user. With the user's approval, the trusted app could replace outdated information and update them on the server apps. Furthermore, this is not a generic way of doing this since each server app uses its own protocol to update credentials [START_REF] Mayer | Enabling automatic password change in password managers through crowdsourcing[END_REF].

The user should be warned when the trusted app logs her into a server app; the trusted app should at least ask for user confirmation. Since several identities can be suitable for a given authentication request, the trusted app can ask the user to choose the identity to use among the suitable identities and consider this choice as a confirmation.

Conclusion and Future Work

We have presented a novel architecture that combines the benefits of both having an OTD for helping with secure computations, thus providing stronger security, as well as an untrusted Proxy running on a client device to provide more usability, communicating with the trusted app when needed. This new OTDP architecture is enabled by a novel use of TLS channels, which we call TLS Switching because the Proxy and the trusted app collaborate to make two secure channels which they switch between, depending on whether information needs to be transmitted from the client app or from the trusted app. This architecture and the TLS Switching have been implemented in an extensible and open-source PoC. The architecture has also been demonstrated using the OffPAD as the trusted device, connected through microUSB to a Android phone [START_REF] Migdal | DEMO: OffPAD -Offline Personal Authenticating Device with Applications in Hospitals and e-Banking[END_REF]. We have considered (though not formally) the security aspects specific to this new architecture, as well as the usability that we aimed for. Another goal of the OTDP architecture was to be transparent to both client apps and server apps, which is not respected by the related work that we surveyed.

Future work could conduct more detailed user experiments about the usability of the OTDP architecture, whereas the security could be verified using formal methods. More widely used authentication methods than HTTP DAA (s.a. OAuth) may be implemented and tested, although we see no evident obstacle to their usage with OTDP and TLS Switching. Fully transparent client's interface (i.e. not requiring proxy configuration on client apps) may be implemented using TUN/TAP and iptables. OTDP architecture may as well be generalized for the specific needs of a company architecture and a centralized credentials management.

Figure 1 :

 1 Figure 1: Offline Trusted Device and Proxy (OTDP) Architecture.

Figure 2 :

 2 Figure 2: OTDP Proxy software architecture

Figure 3 :

 3 Figure 3: TLS Switching visualization: Proxy changing between two TLS channels T and P.

Figure 4 :

 4 Figure 4: Establishment of TLS Switching connections.

Figure 5 :

 5 Figure 5: Modifying a login form to inform and enforce user behaviour.

This paper is accompanied by the online technical report[START_REF] Migdal | Usable authentication with an offline trusted device proxy architecture (long version)[END_REF].

According to PandaLabs'

estimates, a third (32.13%) of the world's PCs are infected with some sort of malware, of which the majority (60.30%) are Trojans.2 http://www.bitdefender.com/box/

http://www.globalplatform.org/specificationsdevice.asp

http://linux.die.net/man/1/socksify

http://newsroom.mastercard.com/press-releases/mastercard-introduces-nextgeneration-display-card-technology-a-first-for-singapore/

[START_REF] Bardram | Pervasive Computing in Healthcare[END_REF] https://www.wireshark.

org/ 7 nc(1) / s client(1) -Linux man page, http://linux.die.net/man/1

http://www.gnutls.org/

https://www.openssl.org/

http://www.oracle.com/technetwork/java/javase/tech/index-jsp-136007.html

https://github.com/denis-migdal/OTDP-and-TLS-Switching

Acknowledgment

We thank reviewers from CCS'16 and IFIP-SEC'17 for helping improve this draft, and OffPAD project members (esp. Léonard Dallot) for their help during the developments.

* The first author was partially supported by the project OffPAD with number E!8324 part of the Eurostars program funded by the EUREKA. † The second author was partially supported by the project DiversIoT funded by the Norwegian Research Council. ‡ The third author was partially supported by the project Oslo Analytics funded by the IKTPLUSS program of the Norwegian Research Council.

1


Matthieu Fradelizi

Mokshay Madiman

Liyao Wang

Optimal Concentration of Information Content for Log-Concave Densities

Keywords: Mathematics Subject Classification (2010). Primary 52A40; Secondary 60E15, 94A17. Keywords. concentration, information, log-concave, varentropy

An elementary proof is provided of sharp bounds for the varentropy of random vectors with log-concave densities, as well as for deviations of the information content from its mean. These bounds significantly improve on the bounds obtained by Bobkov and Madiman (Ann.

Introduction

Consider a random vector Z taking values in R n , drawn from the standard Gaussian distribution γ, whose density is given by

φ(x) = 1 (2π) n 2 e -|x| 2 2
for each x ∈ R n , where | • | denotes the Euclidean norm. It is well known that when the dimension n is large, the distribution of Z is highly concentrated around the sphere of radius √ n; that √ n is the appropriate radius follows by the trivial observation that E|Z| 2 = n i=1 EZ 2 i = n. One way to express this concentration property is by computing the variance of |Z| 2 , which is easy to do using the independence of the coordinates of Z:

Var(|Z| 2 ) = Var n i=1 Z 2 i = n i=1 Var(Z 2 i ) = 2n.
In particular, the standard deviation of |Z| 2 is √ 2n, which is much smaller than the mean n of |Z| 2 when n is large. Another way to express this concentration property is through a deviation inequality:

P |Z| 2 n -1 > t ≤ exp - n 2 [t -log(1 + t)] (1.1)
for the upper tail, and a corresponding upper bound on the lower tail. These inequalities immediately follow from Chernoff's bound, since |Z| 2 /n is just the empirical mean of i.i.d. random variables.

It is natural to wonder if, like so many other facts about Gaussian measures, the above concentration property also has an extension to logconcave measures (or to some subclass of them). There are two ways one may think about extending the above concentration property. One is to ask if there is a universal constant C such that Var(|X| 2 ) ≤ Cn, for every random vector X that has an isotropic, log-concave distribution on R n . Here, we say that a distribution on R n is isotropic if its covariance matrix is the identity matrix; this assumption ensures that E|X| 2 = n, and provides the normalization needed to make the question meaningful. This question has been well studied in the literature, and is known as the "thin shell conjecture" in convex geometry. It is closely related to other famous conjectures: it implies the hyperplane conjecture of Bourgain [START_REF] Eldan | Approximately gaussian marginals and the hyperplane conjecture[END_REF][START_REF] Eldan | Bounding the norm of a log-concave vector via thinshell estimates[END_REF], is trivially implied by the Kannan-Lovasz-Simonovits conjecture, and also implies the Kannan-Lovasz-Simonovits conjecture up to logarithmic terms [START_REF] Eldan | Thin shell implies spectral gap up to polylog via a stochastic localization scheme[END_REF]. The best bounds known to date are those of Guédon and E. Milman [START_REF] Guédon | Interpolating thin-shell and sharp large-deviation estimates for isotropic log-concave measures[END_REF], and assert that Var(|X| 2 ) ≤ Cn 4/3 .

The second way that one may try to extend the above concentration property from Gaussians to log-concave measures is to first observe that the quantity that concentrates, namely |Z| 2 , is essentially the logarithm of the Gaussian density function. More precisely, since

-log φ(x) = n 2 log(2π) + |x| 2 2 ,
the concentration of |Z| 2 about its mean is equivalent to the concentration of -log φ(Z) about its mean. Thus one can ask if, for every random vector X that has a log-concave density

f on R n , Var(-log f (X)) ≤ Cn (1.2)
for some absolute constant C. An affirmative answer to this question was provided by Bobkov and Madiman [START_REF] Bobkov | Concentration of the information in data with log-concave distributions[END_REF]. The approach of [START_REF] Bobkov | Concentration of the information in data with log-concave distributions[END_REF] can be used to obtain bounds on C, but the bounds so obtained are quite suboptimal (around 1000). Recently V. H. Nguyen [START_REF] Nguyen | Inégalités fonctionnelles et convexité[END_REF] (see also [START_REF] Nguyen | Dimensional variance inequalities of Brascamp-Lieb type and a local approach to dimensional Prékopa's theorem[END_REF]) and L. Wang [START_REF] Wang | Heat capacity bound, energy fluctuations and convexity[END_REF] independently determined, in their respective Ph.D. theses, that the sharp constant C in the bound (1.2) is 1. Soon after this work, simpler proofs of the sharp variance bound were obtained independently by us (presented in the proof of Theorem 2.3 in this paper) and by Bolley, Gentil and Guillin [START_REF] Bolley | Dimensional improvements of the logarithmic sobolev, talagrand and brascamp-lieb inequalities[END_REF] (see Remark 4.2 in their paper). An advantage of our proof over the others mentioned is that it is very short and straightforward, and emerges as a consequence of a more basic log-concavity property (namely Theorem 2.9) of L p -norms of logconcave functions, which may be thought of as an analogue for log-concave functions of a classical inequality of Borell [START_REF] Borell | Complements of Lyapunov's inequality[END_REF] for concave functions.

If we are interested in finer control of the integrability of -log f (X), we may wish to consider analogues for general log-concave distributions of the inequality (1.1). Our second objective in this note is to provide such an analogue (in Theorem 4.1). A weak version of such a statement was announced in [START_REF] Bobkov | Dimensional behaviour of entropy and information[END_REF] and proved in [START_REF] Bobkov | Concentration of the information in data with log-concave distributions[END_REF], but the bounds we provide in this note are much stronger. Our approach has two key advantages: first, the proof is transparent and completely avoids the use of the sophisticated Lovasz-Simonovits localization lemma, which is a key ingredient of the approach in [START_REF] Bobkov | Concentration of the information in data with log-concave distributions[END_REF]; and second, our bounds on the moment generating function are sharp, and are attained for example when the distribution under consideration has i.i.d. exponentially distributed marginals.

While in general exponential deviation inequalities imply variance bounds, the reverse is not true. Nonetheless, our approach in this note is to first prove the variance bound (1.2), and then use a general bootstrapping result (Theorem 3.1) to deduce the exponential deviation inequalities from it. The bootstrapping result is of independent interest; it relies on a technical condition that turns out to be automatically satisfied when the distribution in question is log-concave.

Finally we note that many of the results in this note can be extended to the class of convex measures; partial work in this direction is done by Nguyen [START_REF] Nguyen | Dimensional variance inequalities of Brascamp-Lieb type and a local approach to dimensional Prékopa's theorem[END_REF], and results with sharp constants are obtained in the forthcoming paper [START_REF] Fradelizi | Concentration of information content and other functionals under convex measures[END_REF].

Optimal varentropy bound for log-concave distributions

Before we proceed, we need to fix some definitions and notation. Definition 2.1. Let a random vector X taking values in R n have probability density function f . The information content of X is the random variable h(X) = -log f (X). The entropy of X is defined as h(X) = E( h(X)). The varentropy of a random vector X is defined as V (X) = Var( h(X)).

Note that the entropy and varentropy depend not on the realization of X but only on its density f , whereas the information content does indeed depend on the realization of X. For instance, one can write h(X) = -R n f log f and

V (X) = Var(log f (X)) = R n f (log f ) 2 - R n f log f 2 .
Nonetheless, for reasons of convenience and in keeping with historical convention, we slightly abuse notation as above.

As observed in [START_REF] Bobkov | Concentration of the information in data with log-concave distributions[END_REF], the distribution of the difference h(X) -h(X) is invariant under any affine transformation of R n (i.e., h(T X) -h(T X) = h(X)-h(X) for all invertible affine maps T : R n → R n ); hence the varentropy V (X) is affine-invariant while the entropy h(X) is not.

Another invariance for both h(X) and V (X) follows from the fact that they only depend on the distribution of log(f (X)), so that they are unchanged if f is modified in such a way that its sublevel sets keep the same volume. This implies (see, e.g., [START_REF] Lieb | Analysis[END_REF]Theorem 1.13]) that if f is the spherically symmetric, decreasing rearrangement of f , and X is distributed according to the density f , then h(X) = h( X) and V (X) = V ( X). The rearrangement-invariance of entropy was a key element in the development of refined entropy power inequalities in [START_REF] Wang | Beyond the entropy power inequality, via rearrangements[END_REF].

Log-concavity is a natural shape constraint for functions (in particular, probability density functions) that represents an infinite-dimensional generalization of the class of Gaussian distributions.

Definition 2.2. A function f : R n → [0, ∞) is log-concave if f can be written as f (x) = e -U (x) , where U : R n → (-∞, +∞] is a convex function, i.e., U (tx + (1 -t)y) ≤ tU (x) + (1 -t)U (
y) for any x, y and 0 < t < 1. When f is a probability density function and is log-concave, we say that f is a log-concave density.

We can now state the optimal form of the inequality (1.2), first obtained by Nguyen [START_REF] Nguyen | Inégalités fonctionnelles et convexité[END_REF] and Wang [START_REF] Wang | Heat capacity bound, energy fluctuations and convexity[END_REF] as discussed in Section 1.

Theorem 2.3. [START_REF] Nguyen | Inégalités fonctionnelles et convexité[END_REF][START_REF] Wang | Heat capacity bound, energy fluctuations and convexity[END_REF] Given a random vector X in R n with log-concave density f , V (X) ≤ n Remark 2.4. The probability bound does not depend on f -it is universal over the class of log-concave densities.

Remark 2.5. The bound is sharp. Indeed, let X have density f = e -ϕ , with ϕ : R n → [0, ∞] being positively homogeneous of degree 1, i.e., such that ϕ(tx) = tϕ(x) for all t > 0 and all x ∈ R n . Then one can check that the random variable Y = ϕ(X) has a gamma distribution with shape parameter n and scale parameter 1, i.e., it is distributed according to the density given by x i on the cone of points with non-negative coordinates (which corresponds to X having i.i.d. coordinates with the standard exponential distribution), and 2. The case where ϕ(x) = inf{r > 0 : x ∈ rK} for some compact convex set K containing the origin (which, by taking K to be a symmetric convex body, includes all norms on R n suitably normalized so that e -ϕ is a density).

f Y (t) = t n-1 e -t (n -1)! .
Remark 2.6. Bolley, Gentil and Guillin [START_REF] Bolley | Dimensional improvements of the logarithmic sobolev, talagrand and brascamp-lieb inequalities[END_REF] in fact prove a stronger inequality, namely,

1 V (X) - 1 n ≥ E ∇U (X) • Hess(U (X)) -1 ∇U (X) -1
.

This gives a strict improvement of Theorem 2.3 when the density f = e -U of X is strictly log-concave, in the sense that Hess(U (X)) is, almost surely, strictly positive definite. As noted by [START_REF] Bolley | Dimensional improvements of the logarithmic sobolev, talagrand and brascamp-lieb inequalities[END_REF], one may give another alternative proof of Theorem 2.3 by applying a result of Hargé [19, Theorem 2].

In order to present our proof of Theorem 2.3, we will need some lemmata. The first one is a straightforward computation that is a special case of a well known fact about exponential families in statistics, but we write out a proof for completeness.

Lemma 2.7. Let f be any probability density function on R n such that f ∈ L α (R n ) for each α > 0, and define

F (α) = log R n f α .
Let X α be a random variable with density f α on R n , where

f α := f α R n f α .
Then F is infinitely differentiable on (0, ∞), and moreover, for any α > 0,

F (α) = 1 α 2 V (X α ).
Proof. Note that the assumption that f ∈ L α (R n ) (or equivalently that F (α) < ∞) for all α > 0 guarantees that F (α) is infinitely differentiable for α > 0 and that we can freely change the order of taking expectations and differentiation. Now observe that

F (α) = f α log f f α = f α log f ;
if we wish, we may also massage this to write

F (α) = 1 α [F (α) -h(X α )]. (2.1)
Differentiating again, we get

F (α) = f α (log f ) 2 f α - f α log f f α 2 = f α (log f ) 2 - f α log f 2 = Var[log f (X α )] = Var 1 α {log f α (X α ) + F (α)} = 1 α 2 Var[log f α (X α )] = V (X α ) α 2 , as desired.
The following lemma is a standard fact about the so-called perspective function in convex analysis. The use of this terminology is due to Hiriart-Urruty and Lemaréchal [20, p. 160] (see [START_REF] Boyd | Convex optimization[END_REF] for additional discussion), although the notion has been used without a name in convex analysis for a long time (see, e.g., [30, p. 35]). Perspective functions have also seen recent use in convex geometry [START_REF] Cordero-Erausquin | Volume of the polar of random sets and shadow systems[END_REF][START_REF] Bobkov | When can one invert Hölder's inequality? (and why one may want to)[END_REF][START_REF] Fradelizi | Concentration of information content and other functionals under convex measures[END_REF]) and empirical process theory [START_REF] Van Der Vaart | A local maximal inequality under uniform entropy[END_REF]. We give the short proof for completeness.

Lemma 2.8. If U : R n → R ∪ {+∞} is a convex function, then w(z, α) := αU (z/α) is a convex function on R n × (0, +∞).
Proof. First note that by definition, w(az, aα) = aw(z, α) for any a > 0 and any (z, α) ∈ R n × (0, +∞), which implies in particular that

1 α w(z, α) = w z α , 1 . Hence w(λz 1 + (1 -λ)z 2 , λα 1 + (1 -λ)α 2 ) = [λα 1 + (1 -λ)α 2 ] U λα 1 z1 α1 + (1 -λ)α 2 z2 α2 λα 1 + (1 -λ)α 2 ≤ λα 1 U z 1 α 1 + (1 -λ)α 2 U z 2 α 2 = λw(z 1 , α 1 ) + (1 -λ)w(z 2 , α 2 ), for any λ ∈ [0, 1], z 1 , z 2 ∈ R n , and α 1 , α 2 ∈ (0, ∞).
The key observation is the following theorem. Theorem 2.9. If f is log-concave on R n , then the function

G(α) := α n f (x) α dx is log-concave on (0, +∞).
Proof. Write f = e -U , with U convex. Make the change of variable x = z/α to get G(α) = e -αU (z/α) dz.

The function w(z, α) := αU (z/α) is convex on R n × (0, +∞) by Lemma 2.8, which means that the integrand above is log-concave. The log-concavity of G then follows from Prékopa's theorem [START_REF] Prékopa | On logarithmic concave measures and functions[END_REF], which implies that marginals of log-concave functions are log-concave.

Remark 2.10. An old theorem of Borell [8, Theorem 2]

states that if f is concave on R n , then G f (p) := (p + 1) • • • (p + n) f p
is log-concave as a function of p ∈ (0, ∞). Using this and the fact that a log-concave function is a limit of α-concave functions with α → 0, one can obtain an alternate, indirect proof of Theorem 2.9. One can also similarly obtain an indirect proof of Theorem 2.9 by considering a limiting version of [5, Theorem VII.2], which expresses a log-concavity property of (p -1) . . . (p -n) φ -p for any convex function φ on R n , for p > n + 1 (an improvement of this to the optimal range p > n is described in [START_REF] Fradelizi | Concentration of information content and other functionals under convex measures[END_REF][START_REF] Bobkov | When can one invert Hölder's inequality? (and why one may want to)[END_REF], although this is not required for this alternate proof of Theorem 2.9).

Proof of Theorem 2.3. Since f is a log-concave density, it necessarily holds that f ∈ L α (R n ) for every α > 0; in particular, G(α) := α n f α is finite and infinitely differentiable on the domain (0, ∞). By definition, log G(α) = n log α + log f α = n log α + F (α). Consequently,

d 2 dα 2 [log G(α)] = - n α 2 + F (α).
By Theorem 2.9, log G(α) is concave, and hence we must have that n α 2 + F (α) ≤ 0 for each α > 0. However, Lemma 2.7 implies that F (α) = V (X α )/α 2 , so that we obtain the inequality V (X α ) -n α 2 ≤ 0.

For α = 1, this implies that V (X) ≤ n.

Notice that if f = e -U , where U : R n → [0, ∞] is positively homogeneous of degree 1, then the same change of variable as in the proof of Theorem 2.9 shows that

G(α) = e -αU (z/α) dz = e -U (z) dz = f (z)dz = 1.
Hence the function G is constant. Then the proof above shows that V (X) = n, which establishes the equality case stated in Remark 2.5.

A general bootstrapping strategy

The purpose of this section is to describe a strategy for obtaining exponential deviation inequalities when one has uniform control on variances of a family of random variables. Log-concavity is not an assumption made anywhere in this section.

Theorem 3.1. Suppose X ∼ f , where f ∈ L α (R n ) for each α > 0. Let X α ∼ f α , where f α (x) = f α (x) f α . If K = K(f ) := sup α>0 V (X α ), then E e β{ h(X)-h(X)} ≤ e Kr(-β) , β ∈ R,
where

r(u) = u -log(1 + u) for u > -1 +∞ for u ≤ -1 .
Proof. Suppose X is a random vector drawn from a density f on R n , and define, for each α > 0,

F (α) = log f α . Set K = sup α>0 V (X α ) = sup α>0 α 2 F (α);
the second equality follows from Lemma 2.7. Since f ∈ L α (R n ) for each α > 0, F (α) is finite and moreover, infinitely differentiable for α > 0, and we can freely change the order of integration and differentiation when differentiating F (α).

From Taylor-Lagrange formula, for every α > 0, one has

F (α) = F (1) + (α -1)F (1) + α 1 (α -u)F (u)du.
Using that F (1) = 0, F (u) ≤ K/u 2 for every u > 0 and the fact that for 0 < α < u < 1, one has α -u < 0, we get

F (α) ≤ (α -1)F (1) + K α 1 α -u u 2 du = (α -1)F (1) + K - α u -log(u) α 1 .
Thus, for α > 0, we have proved that

F (α) ≤ (α -1)F (1) + K(α -1 -log α).
Setting β = 1 -α, we have for β < 1 that e F (1-β) ≤ e -βF (1) e K(-β-log(1-β)) .

(3.1)

Observe that e

F (1-β) = f 1-β = E[f -β (X)] = E[e -β log f (X) ] = E e β h(X)
and e -βF (1) = e βh(X) ; the latter fact follows from the fact that F (1) = -h(X) as is clear from the identity (2.1). Hence the inequality (3.1) may be rewritten as E e β{ h(X)-h(X)} ≤ e Kr(-β) , β ∈ R.

(3.2) Remark 3.2. We note that the function r(t) = t -log(1 + t) for t > -1, (or the related function h(t) = t log t -t + 1 for t > 0, which satisfies sh(t/s) = tr 1 (s/t) for r 1 (u) = r(u -1)) appears in many exponential concentration inequalities in the literature, including Bennett's inequality [START_REF] Bennett | Probability inequalities for the sum of independent random variables[END_REF] (see also [START_REF] Boucheron | Concentration inequalities[END_REF]), and empirical process theory [START_REF] Wellner | Limit theorems for the ratio of the empirical distribution function to the true distribution function[END_REF]. It would be nice to have a clearer understanding of why these functions appear in so many related contexts even though the specific circumstances vary quite a bit.

Remark 3.3. Note that the function r is convex on R and has a quadratic behavior in the neighborhood of 0 (r(u) ∼ 0

u 2
2 ) and a linear behavior at +∞ (r(u) ∼ ∞ u).

Corollary 3.4. With the assumptions and notation of Theorem 3.1, we have for any t > 0 that

P{ h(X) -h(X) ≥ t} ≤ exp -Kr t K P{ h(X) -h(X) ≤ -t} ≤ exp -Kr - t K
The proof is classical and often called the Cramér-Chernoff method (see for example section 2.2 in [START_REF] Boucheron | Concentration inequalities[END_REF]). It uses the Legendre transform ϕ * of a convex function ϕ : R → R ∪ {+∞} defined for y ∈ R by

ϕ * (y) = sup x xy -ϕ(x).
Notice that if min ϕ = ϕ(0) then for every y > 0, the supremum is reached at a positive x, that is ϕ * (y) = sup x>0 xy -ϕ(x). Similarly, for y < 0, the supremum is reached at a negative x.

Proof. The idea is simply to use Markov's inequality in conjunction with Theorem 3.1, and optimize the resulting bound.

For the lower tail, we have for β > 0 and t > 0,

P[ h(X) -h(X) ≤ -t] ≤ E e -β h(X)-h(X) e -βt ≤ exp K r(β) - βt K .
Thus minimizing on β > 0, and using the remark before the proof, we get

P[ h(X) -h(X) ≤ -t] ≤ exp -K sup β>0 βt K -r(β) = e -Kr * ( t K ) . (3.3)
Let us compute the Legendre transform r * of r. For every t, one has

r * (t) = sup u tu -r(u) = sup u>-1 (tu -u + log(1 + u)) .
One deduces that r * (t) = +∞ for t ≥ 1. For t < 1, by differentiating, the supremum is reached at u = t/(1 -t) and replacing in the definition we get

r * (t) = -t -log(1 -t) = r(-t).
Thus r * (t) = r(-t) for all t ∈ R. Replacing, in the inequality (3.3), we get the result for the lower tail.

For the upper tail, we use the same argument: for β > 0 and t > 0,

P[ h(X) -h(X) ≥ t] ≤ E e β h(X)-h(X) e -βt ≤ exp K r(-β) - βt K .
Thus minimizing on β > 0, we get

P[ h(X) -h(X) ≥ t] ≤ exp -K sup β>0 βt K -r(-β) . (3.4)
Using the remark before the proof, in the right hand side term appears the Legendre transform of the function r defined by r(u) = r(-u). Using that r * (t) = r(-t) = r(t), we deduce that (r) * = (r * ) * = r. Thus the inequality (3.4) gives the result for the upper tail.

Conclusion

The purpose of this section is to combine the results of Sections 2 and 3 to deduce sharp bounds for the moment generating function of the information content of random vectors with log-concave densities. Naturally these yield good bounds on the deviation probability of the information content h(X) from its mean h(X) = E h(X). We also take the opportunity to record some other easy consequences.

Theorem 4.1. Let X be a random vector in R n with a log-concave density f . For β < 1,

E e β[ h(X)-h(X)] ≤ E e β[ h(X * )-h(X * )] ,
where X * has density f * = e -n i=1 xi , restricted to the positive quadrant.

Proof. Taking K = n in Theorem 3.1 (which we can do in the log-concave setting because of Theorem 2.3), we obtain: E e β{ h(X)-h(X)} ≤ e nr(-β) , β ∈ R.

Some easy computations will show:

E e β{ h(X * )-h(X * )} = e nr(-β) , β ∈ R.

This concludes the proof.

As for the case of equality of Theorem 2.3, discussed in Remark 2.5, notice that there is a broader class of densities for which one has equality in Theorem 4.1, including all those of the form e -x K , where K is a symmetric convex body.

Remark 4.2. The assumption β < 1 in Theorem 4.1 is strictly not required; however, for β ≥ 1, the right side is equal to +∞. Indeed, already for β = 1, one sees that for any random vector X with density f ,

E e h(X)-h(X) = e -h(X) E 1 f (X) = e -h(X) supp(f ) dx = e -h(X) Vol n (supp(f )),
where supp(f ) = {x ∈ R n : f (x) > 0} is the support of the density f and Vol n denotes Lebesgue measure on R n . In particular, this quantity for X * , whose support has infinite Lebesgue measure, is +∞. Taking K = n in Corollary 3.4 (again because of Theorem 2.3), we obtain: Corollary 4.4. Let X be a random vector in R n with a log-concave density f . For t > 0, t) , where r(u) is defined in Theorem 3.1.

Remark 4.3. Since lim α→0 2 α 2 E e α(log f (X)-E[log f (X)]) = V (
P[ h(X) -h(X) ≤ -nt] ≤ e -nr(-t) , P[ h(X) -h(X) ≥ nt] ≤ e -nr(
The original concentration of information bounds obtained in [START_REF] Bobkov | Concentration of the information in data with log-concave distributions[END_REF] were suboptimal not just in terms of constants but also in the exponent; specifically it was proved there that

P 1 n h(X) -h(X) ≥ t ≤ 2 e -ct √ n (4.1)
for a universal constant c > 1/16 (and also that a better bound with ct 2 n in the exponent holds on a bounded range, say, for t ∈ (0, 2]). One key advantage of the method presented in this paper, apart from its utter simplicity, is the correct linear dependence of the exponent on dimension. Incidentally, we learnt from a lecture of B. Klartag [START_REF] Klartag | Eigenvalue distribution of optimal transportation[END_REF] that another proof of (4.1) can be given based on the concentration property of the eigenvalues of the Hessian of the Brenier map (corresponding to optimal transportation from one logconcave density to another) that was discovered by Klartag and Kolesnikov [START_REF] Klartag | Eigenvalue distribution of optimal transportation[END_REF]; however, the latter proof shares the suboptimal √ nt exponent of [START_REF] Bobkov | Concentration of the information in data with log-concave distributions[END_REF]. The following inequality is an immediate corollary of Corollary 4.4 since it merely expresses a bound on the support of the distribution of the information content. Corollary 4.5 was first explicitly proved in [START_REF] Bobkov | The entropy per coordinate of a random vector is highly constrained under convexity conditions[END_REF], where several applications of it are developed, but it is also implicitly contained in earlier work (see, e.g., the proof of Theorem 7 in [START_REF] Fradelizi | Increasing functions and inverse Santaló inequality for unconditional functions[END_REF]).

An immediate consequence of Corollary 4.5, unmentioned in [START_REF] Bobkov | The entropy per coordinate of a random vector is highly constrained under convexity conditions[END_REF], is a result due to [START_REF] Fradelizi | Sections of convex bodies through their centroid[END_REF]: Corollary 4.6. Let X be a random vector in R n with a log-concave density f . Then Exponentiating concludes the proof.

f ∞ ≤ e n f (E[X]).
Finally we mention that the main result may also be interpreted as a small ball inequality for the random variable f (X). As an illustration, we record a sharp form of [24, P{f (X) ≤ c n f ∞ } ≤ e -nr(-1-log c) . Elementary algebra concludes the proof.

Such "effective support" results are useful in convex geometry as they can allow to reduce certain statements about log-concave functions or measures to statements about convex sets; they thus provide an efficient route to proving functional or probabilistic analogues of known results in the geometry of convex sets. Instances where such a strategy is used include [START_REF] Klartag | Geometry of log-concave functions and measures[END_REF][START_REF] Bobkov | Reverse Brunn-Minkowski and reverse entropy power inequalities for convex measures[END_REF]. These and other applications of the concentration of information phenomenon are discussed in [START_REF] Madiman | Some applications of the nonasymptotic equipartition property of log-concave distributions[END_REF].

  Consequently E(Y ) = n and E(Y 2 ) = n(n + 1), and therefore V (X) = Var(Y ) = n. Particular examples of equality include: 1. The case where ϕ(x) = n i=1

  X), we can recover Theorem 2.3 from Theorem 4.1.

Corollary 4 . 5 .

 45 Let X have a log-concave probability density function f on R n . Then:h(X) ≤ -log f ∞ + n. Proof. By Corollary 4.4, almost surely, log f (X) ≤ E[log f (X)] + n, since when t ≥ 1, P[log f (X) -E[log f (X)] ≥ nt] = 0. Taking the supremum over all realizable values of X yields log f ∞ ≤ E[log f (X)] + n,which is equivalent to the desired statement.

  Proof. By Jensen's inequality,log f (EX) ≥ E[log f (X)]. By Corollary 4.5, E[log f (X)] ≥ log f ∞ -n. Hence, log f (EX) ≥ log f ∞ -n.

  Corollary 2.4] (cf., [21, Corollary 5.1] and [6, Proposition 5.1]).

Corollary 4 . 7 .

 47 Let f be a log-concave density on R n . ThenP{f (X) ≥ c n f ∞ } ≥ 1 -e • c • log 1 c n , where 0 < c < 1 e . Proof. Note that P{f (X) ≤ c n f ∞ } = P{log f (X) ≤ log f ∞ + n log c} = P{ h(X) ≥ -log f ∞ -n log c} ≤ P{ h(X) ≥ h(X) -n(1 + log c)}.using Corollary 4.5 for the last inequality. Applying Corollary 4.4 with t = -log c -1 yields

Acknowledgment

We are indebted to Paata Ivanisvili, Fedor Nazarov, and Christos Saroglou for useful comments on an earlier version of this paper. In particular, Christos Saroglou pointed out that the class of extremals in our inequalities is wider than we had realized, and Remark 2.5 is due to him. We are also grateful to François Bolley, Dario Cordero-Erausquin and an anonymous referee for pointing out relevant references.

This work was partially supported by the project GeMeCoD ANR 2011 BS01 007 01, and by the U.S. National Science Foundation through the grant DMS-1409504 (CAREER). A significant portion of this paper is based on the Ph.D. dissertation of L. Wang [32], co-advised by M. Madiman and N. Read, at Yale University.


Jiange Li
email: lijiange@udel.edu

Matthieu Fradelizi
email: matthieu.fradelizi@u-pem.fr

Mokshay Madiman
email: madiman@udel.edu

Information concentration for convex measures

To be considered for the 2016 IEEE Jack Keil Wolf ISIT Student Paper Award. Sharp exponential deviation estimates of the information content as well as a sharp bound on the varentropy are obtained for convex probability measures on Euclidean spaces. These provide, in a sense, a nonasymptotic equipartition property for convex measures even in the absence of stationarity-type assumptions.

I. INTRODUCTION

Let X = (X 1 , X 2 , • • • ) be a stochastic process with each X i taking values in R. Suppose that the joint distribution of X n = (X 1 , • • • , X n ) has a density f with respect to the Lebesgue measure on R n . We are interested in the random variable

h(X n ) = -log f (X n ), (1)
which may be thought of as the (random) information content of X n . In the discrete case, the quantity h(X n ) (using f for the probability mass function) is essentially the number of bits needed to represent X n by a coding scheme that minimizes the average code length [START_REF] Shannon | A mathematical theory of communication[END_REF]. In the continuous case, one may still call h(X n ) the information content even though this coding interpretation no longer holds. The quantity h(X n ) is of central interest in information theory and also naturally arises in several other areas such as probability theory, statistical physics and statistics. The average value of information content is known more commonly as the (differential) entropy. The entropy of X n is defined by

h(X n ) = - R n f (x) log f (x)dx = E h(X n ). (2)
A typical problem is to study the deviation estimate of information content from the entropy. The entropy rate of the stochastic process X is defined by

h(X) = lim n→∞ h(X n ) n , (3)
when the limit exists. The question of whether the information content per coordinate h(X n ) n converges to the entropy rate has been extensively studied. In the discrete case, the affirmative answer goes back to Shannon [START_REF] Shannon | A mathematical theory of communication[END_REF], McMillan [START_REF] Mcmillan | The basic theorems of information theory[END_REF] and Breiman [START_REF] Breiman | The individual ergodic theorem for information theory[END_REF] for stationary ergodic process. The theorem particularly implies the existence of a set of roughly e nh(X) typical sequences of length n all having roughly equal probability (a fact that plays a fundamental role in compressing discrete data from ergodic sources). McMillan [START_REF] Mcmillan | The basic theorems of information theory[END_REF] called this the asymptotic equipartition property (AEP). Extensions to more general (including continuous) settings were obtained independently in [START_REF] Barron | The strong ergodic theorem for densities: Generalized Shannon-Mcmillan-Breiman theorem[END_REF] and [START_REF] Orey | On the Shannon-Perez-Moy theorem[END_REF].

For processes that are not asymptotically mean stationary, the entropy rate typically does not exist; so there is no convergence question of h(X n )

n . With a global restriction on the joint distribution of the process, namely log-concavity, [START_REF] Bobkov | Concentration of the information in data with log-concave distributions[END_REF] proved that h(X n ) n is highly concentrated around the entropy rate. It demonstrates that high-dimensional log-concave measures are in a sense close to uniform distributions on the annulus between two nested convex sets. Their argument is non-trivial and depends on the rather heavy machinery of the so-called Lovász-Simonovits localization technique; optimal concentration bounds were recently obtained in [START_REF] Fradelizi | Optimal concentration of information content for log-concave densities[END_REF] using a particularly simple approach.

The purpose of this note is to extend the concentration property of the information content from log-concave measures to the more general class of "convex measures". It should not be surprising that in general we do not have AEP for convex measures, since this property tends to require exponential tails and convex measures generally posses only polynomial decay. But we can still say a lot of interesting things of convex measures in fixed dimensions, and the study is closely related to many interesting problems in convex geometry, information theory and probability theory as well. For example, Corollary IV.7 for log-concave measures was used in [START_REF]The entropy per coordinate of a random vector is highly constrained under convexity conditions[END_REF] to give an information-theoretic formulation of Bourgain's famous hyperplane conjecture [START_REF] Bourgain | On high-dimensional maximal functions associated to convex bodies[END_REF]; a weaker form of Corollary IV.7 is a key ingredients in [START_REF]Reverse Brunn-Minkowski and reverse entropy power inequalities for convex measures[END_REF] on the reverse entropy power inequality for convex measures; and the concentration property of information content for log-concave measures [START_REF] Bobkov | Concentration of the information in data with log-concave distributions[END_REF] also has applications in random matrix theory as outlined in [START_REF] Madiman | Some applications of the nonasymptotic equipartition property of log-concave distributions[END_REF]. Perhaps most importantly from the information theory point of view, we expect our results to have implications for the study of fundamental limits of finite-blocklength performance in contexts involving convexity, e.g., for additive noise channels where the noise is drawn from a convex measure. Let us note that a very special case of our results, namely information concentration for Gaussians (which can be proved by explicit computations), is a key ingredient in the results of Cover and Pombra [START_REF] Cover | Gaussian feedback capacity[END_REF] on feedback capacities of Gaussian channels.

The note is organized as follows. In Section 2, we show that the exponential deviation of a functional follows from the log-concavity of normalized moments of that functional. The log-concavity of the normalized moments of s-concave functions are studied in Section 3. Optimal concentration and sharp variance bound of the information content of κ-concave random variables are obtained in Section 4 by combining the results of the preceding two sections.

II. A GENERAL PRINCIPLE FOR EXPONENTIAL DEVIATION

Let X be a random variable taking values in R n . Suppose that it has density f with respect to the Lebesgue measure on R n . Let ϕ : R n → R be real-valued function. One natural way to show the exponential deviation of ϕ(X) from its mean is to prove the finiteness of the moment generating function Ee αϕ(X) for certain α. The logarithmic moment generating function L(α) is defined by

L(α) = log Ee αϕ(X) . (4)
The following observation is a well known fact about exponential families in statistics.

Lemma II.1. Let a, b > 0, and suppose L(α) < ∞ for α ∈ (-a, b). Then we have

L (α) = Eϕ(X α ), L (α) = Var(ϕ(X α )), (5)
where X α is a random variable with density

f α (x) = e αϕ(x) f (x) R n e αϕ(x) f (x)dx . (6)
For α = 0, one particularly has L (0) = Eϕ(X) and L (0) = Var(ϕ(X)).

Definition II.2. A function f : R n → R + is called log-concave if we have f ((1 -λ )x + λ y) ≥ f (x) 1-λ f (y) λ (7)
for all x, y ∈ R n and all λ ∈ [0, 1].

The following lemma tells us that the upper bound of Ee αϕ(X) emerges as a consequence of the log-concavity of L(α) after certain normalization.

Lemma II.3. Let c(α) be a smooth function such that e -c(α) Ee αϕ(X) is log-concave for -a < α < b. Then we have Ee α(ϕ(X)-Eϕ(X)) ≤ e ψ c (α) , (8)
where

ψ c (α) = c(α) -c(0) -c (0)α.
Proof. Since e -c(s) Ee sϕ(X) is log-concave, we have L (s) ≤ c (s). For any 0 < t < α < b, integrating the inequality over (0,t) we have

L (t) -L (0) ≤ c (t) -c (0).
Integrating both sides over (0, α), we have

L(α) -L(0) -L (0)α ≤ c(α) -c(0) -c (0)α. (9)
Similarly we can show that the estimate also holds for -a < α < 0. Notice that L(0) = 0 and L (0) = Eϕ(X). Then the lemma follows from exponentiating both sides of (9).

Remark II.4. From Lemma II.1 and Lemma II.3, we can see that the study of upper bound of Var(ϕ(X α )) is equivalent to that of the normalizing function for Ee αϕ(X) to be log-concave. We can get one from the other by differentiating or integrating twice. That is why variance bounds can imply exponential deviation inequalities when moment generating functions exist.

Let f : R → R ∪ {∞} be a real-valued function. For x ∈ R, the Fenchel-Legendre dual function f * (x) is defined by

f * (x) = sup y (xy -f (y)). ( 10
)
Let ψ c,+ (α) and ψ c,-(α) be the restrictions of ψ c (α) on the positive and negative half axis, respectively.

Corollary II.5. Under the assumptions and notations of Lemma II.3, we have for any t > 0 that

P(ϕ(X) -Eϕ(X) > t) ≤ e -ψ * c,+ (t) , (11)
P(ϕ(X) -Eϕ(X) < -t) ≤ e -ψ * c,-(-t) , (12)
where ψ * c,+ , ψ * c,-are Fenchel-Legendre dual functions of ψ c,+ , ψ c,-, respectively.

Proof. The proof follows from the so-called Cramér-Chernoff method: using Markov inequality in conjugation with optimization of the resulting bound. For the upper tail, we have for 0 < α < b and t > 0 that P(ϕ(X) -E(ϕ(X)) > t) = P(e α(ϕ(X)-Eϕ(X)) > e αt ) ≤ e -αt • Ee α(ϕ(X)-Eϕ(X))

≤ e -(αt-ψ c,+ (α)) .

We use Lemma II.3 in the second inequality. Then the upper tail estimate follows by taking the infimum of the right hand side over 0 < α < b. The lower tail estimate follows from the same argument for -a < α < 0.

III. R ÉNYI ENTROPIES OF s-CONCAVE FUNCTIONS

In this section, we study the log-concavity of the (normalized) moments of s-concave functions, which, in conjugation with the results from the previous section, will enable us to obtain optimal concentration of the information content for convex measures.

Definition III.1. For s ∈ R, a function f : R n → R + is called s-concave if we have f ((1 -λ )x + λ y) ≥ ((1 -λ ) f (x) s + λ f (y) s ) 1/s ( 13
)
for all x, y such that f (x) f (y) > 0 and for all λ ∈ [0, 1].

For s = 0, the right hand side is defined by continuity, which corresponds to log-concave functions defined before. For s > 0, the previous definition is equivalent to that f s is concave on its support; while for s < 0, it is equivalent to that f s is convex on its support.

Recall that for x > 0, the gamma function Γ(x) is defined by

Γ(x) = ∞ 0 t x-1 e -t dt.
For x, y > 0, the beta function B(x, y) is defined by

B(x, y) = 1 0 t x-1 (1 -t) y-1 dt.
The following result is proved by Borell [START_REF] Borell | Complements of Lyapunov's inequality[END_REF] for s > 0, except that the function ϕ is assumed to be decreasing. It was then noticed by some people and available for example in Guédon, Nayar and Tkocz [START_REF] Guédon | Concentration inequalities and geometry of convex bodies[END_REF] that the result remains true without any monotonicity hypothesis. For s < 0, it is proved by Fradelizi, Guédon and Pajor [START_REF] Fradelizi | Thin-shell concentration for convex measures[END_REF], and the case s = 0 follows by taking the limits (or reproducing the mechanics of the proof).

Proposition III.2. Let s ∈ R and let ϕ : [0, +∞) → [0, +∞) be an s-concave integrable function.

1) If s > 0, then p → B(p, s -1 + 1) -1 +∞ 0 t p-1 ϕ(t)dt is log- concave for p > 0. 2) If s = 0, then p → Γ(p) -1 +∞ 0 t p-1 ϕ(t)dt is log-concave for p > 0. 3) If s < 0, then p → B(p, -s -1 -p) -1 +∞ 0 t p-1 ϕ(t)dt is log- concave for 0 < p < -1/s.

Let us define the function ϕ s (t) = (1st)

1/s + 1 R + for s = 0, and ϕ 0 (t) = e -t 1 R + . Then the preceding proposition may be expressed in the following way: if ϕ : [0, +∞) → [0, +∞) is s-concave, then the function p → +∞ 0 t p-1 ϕ(t)dt +∞ 0 t p-1 ϕ s (t)dt is log-concave for p that 1/p > max(0, -s). Using the preceding proposition, we can prove the following theorem which unifies and partially extends previous results of [START_REF] Borell | Complements of Lyapunov's inequality[END_REF], [START_REF]The entropy per coordinate of a random vector is highly constrained under convexity conditions[END_REF], and [START_REF] Fradelizi | Optimal concentration of information content for log-concave densities[END_REF]. A weaker log-concavity statement was also obtained in [START_REF] Nguyen | Dimensional variance inequalities of Brascamp-Lieb type and a local approach to dimensional Prékopa's theorem[END_REF].

Theorem III.1. Let s ∈ R and let f : R n → R + be an integrable s-concave function. Then the function

p → (p + s) • • • (p + ns) R n f (x) p dx (14)
is log-concave for p > max(0, -ns).

Proof. The case s = 1 is due to Borell [START_REF] Borell | Complements of Lyapunov's inequality[END_REF] and the case s > 0 deduces directly by applying Borell's result to f s . The case s = 0 was proved by [START_REF] Fradelizi | Optimal concentration of information content for log-concave densities[END_REF]. The case s = -1 is due to [START_REF]The entropy per coordinate of a random vector is highly constrained under convexity conditions[END_REF] 1 , except that the range was p > n + 1. In the same way, the case s < 0 deduces from the case s = -1 by applying it to f |s| . So we only need to prove the extension of the range for s = -1. Let us assume that s = -1. Thus f is -1-concave, which means that g = f -1 is convex on its support. As done by [START_REF]The entropy per coordinate of a random vector is highly constrained under convexity conditions[END_REF], we write 1 The details of this proof were omitted from [START_REF]The entropy per coordinate of a random vector is highly constrained under convexity conditions[END_REF] because of space considerations, and are being presented here. A complete presentation will appear in [START_REF] Bobkov | When can one invert Hölder's inequality? (and why one may want to)[END_REF].

R n f (x) p dx = R n g(x) -p dx = +∞ 0 pt p-1 ψ(1/t)dt,
where ψ(t) = |{x ∈ R n : g(x) ≤ t}| n is the Lebesgue measure of the sub-level set {x ∈ R n : g(x) ≤ t}. Using Brunn-Minkowski theorem, we can see that ψ is a 1/n-concave function. Using the properties of the perspective function, we can deduce that the function ϕ(t) = t n ψ(1/t) is also a 1/n-concave function. Thus it follows that

R n f (x) p dx = p +∞ 0 t p-n-1 ϕ(t)dt.
Applying Proposition III.2 to s = 1/n and p replaced by pn we get that

B(p -n, n + 1) -1 +∞ 0 t p-1-n ϕ(t)dt
is log-concave on (n, +∞). Then we can conclude the proof using the following identity

B(p -n, n + 1) -1 = p(p -1) • • • (p -n) Γ(n + 1)
.

The fact that Theorem III.1 is optimal can be seen from the following example. Let U : R n → [0, ∞] be a positively homogeneous convex function of degree 1, i.e. that U(tx) = tU(x) for all x ∈ R n and all t > 0. We define f s,U = (1 -sU) 1/s + for s = 0 and f 0,U = e -U for s = 0. Then we have

R n f s,U (x) p dx = C U n! (p + s) • • • (p + ns)
,

where C U is the Lebesgue measure of the sub-level set {x ∈ R n : U(x) ≤ 1}. We only check the identity for s > 0, and the other two cases can be proved similarly.

R n f s,U (x) p dx = p 1 0 t p-1 |{x ∈ R n : (1 -sU(x)) 1/s + > t}|dt = p 1 0 t p-1 |{x ∈ R n : U(x) < (1 -t s )/s}|dt = C U p 1 0 t p-1 ((1 -t s )/s) n dt = C U s -n-1 pB(p/s, n + 1)
In the third equation, we use the homogeneity of U and the property of Lebesgue measure. Then we can prove the identity using the following fact

B(p/s, n + 1) = n! (p/s + n) • • • p/s .
Thus the preceding theorem can be written in the following way: if f : R n → R + is an integrable s-concave function, then

p → R n f (x) p dx R n f s,U (x) p dx
is log-concave for p > max(0, -ns).

IV. CONCENTRATION OF INFORMATION CONTENT

Now we are ready to study the concentration property of information content for convex measures introduced and studied by Borell [START_REF]Convex measures on locally convex spaces[END_REF], [START_REF]Convex set functions in d-space[END_REF].

Definition IV.1. Let -∞ ≤ κ ≤ ∞. A finite Borel measure µ on R n is called κ-concave if we have µ((1 -λ )A + λ B) ≥ ((1 -λ )µ(A) κ + λ µ(B) κ ) 1/κ ( 15
)
for all λ ∈ [0, 1] and all Borel sets A, B ⊆ R n such that µ(A)µ(B) > 0.

Here (1λ )A + λ B = {(1λ )x + λ y : x ∈ A, y ∈ B} stands for the Minkowski sum of two sets. The limit cases are interpreted by continuity. Thus the right hand side of ( 15) is equal to min(µ(A), µ(B)) for κ = -∞; µ(A) 1-λ µ(B) λ for κ = 0; and max(µ(A), µ(B)) for κ = ∞. Note that the inequality (15) becomes stronger as κ increases. For κ = -∞, we obtain the largest class, whose members are called convex or hyperbolic measures. The case κ = 0 describes log-concave measures. If µ is a convex measure on R n then it is absolutely continuous with respect to the Lebesgue measure on the subspace generated by its support and its density has a concavity property. For example, if µ is κ-concave and has a density

f on R n then κ ≤ 1/n and f is -1/β -concave with β = n -1/κ.
We say that a R n -valued random variable X is κ-concave if the probability measure induced by X is κ-concave. In this section, we let X be a κ-concave random variable with density f and κ < 0. Then Borell's characterization implies that there is a convex function V such that f = V -β . In the following, we will study the deviation of h(X) from its mean h(X), that is corresponding to taking ϕ =log f in Section 2. Then the moment generating function is

E f -α (X) = R n f (x) 1-α dx.
The integral is finite as long as (1α)β > n, i.e. that α < 1n/β . Proposition IV.2. Let β > n and let X be a random variable in R n with density f being -1/β -concave. Then the function

α → n ∏ i=1 ((1 -α)β -i)E f -α (X) (16)
is log-concave for α < 1n/β .

Proof. It easily follows from Theorem III.1 with p replaced by 1α and s replaced by -1/β . Following Lemma II.3, we can set

c(α) = - n ∑ i=1 log((1 -α)β -i). (17)
Corollary IV.3. Under the conditions and notations of Proposition IV.2, we have

Var( h(X)) ≤ β 2 n ∑ i=1 (β -i) -2 . ( 18
)
Proof. By Lemma II.1, we know that Var( h(X)) = L (α), where X α is a random variable with density proportional to f 1-α and L(α) = log E f -α (X) is the logarithmic moment generating function. By Proposition IV.2, we know that L (α) ≤ c (α), where c(α) is defined in [START_REF] Nguyen | Dimensional variance inequalities of Brascamp-Lieb type and a local approach to dimensional Prékopa's theorem[END_REF]. Then the variance bound [START_REF] Orey | On the Shannon-Perez-Moy theorem[END_REF] follows by differentiating c(α) twice and setting α = 0.

Remark IV.4. The variance bound is sharp. Suppose X has density f = (1 +U/β )

-β
+ with U being a positively homogeneous convex function of degree 1. In this case, the function in Proposition IV.2 is log-affine, i.e. L (α) = c (α). Then we have equality in the above variance bound. In particular, it includes the Pareto distribution with density

f (x) = 1 Z n (a, β ) (a + x 1 + • • • + x n ) -β , x i > 0, ( 19
)
where a > 0 and Z n (a, β ) is a normalizing constant.

Let β > n + 2 and let X be a random variable in R n with density f being -1/β -concave. In this case, we have E|X| 2 < ∞ and the covariance matrix Σ is defined by

Σ = E(X -EX) ⊗ (X -EX). (20)
Then we have

n = R n x -EX, -∇ log f (x) f (x)dx ≤ R n |x -EX| 2 f (x)dx • R n |∇ log f (x)| 2 f (x)dx 1/2 = tr(Σ)J(X),
where tr(Σ) is the trace of Σ and J(X) is the Fisher information defined by

J(X) = R n |∇ f | 2 f dx. (21)
Combining with Corollary IV.3 we have the following result.

Corollary IV.5. Let β > n + 2 and let X be a random variable in R n with density f being -1/β -concave. Then we have

Var( h(X)) ≤ tr(Σ)β 2 n 2 n ∑ i=1 (β -i) -2 J(X). (22)
In particular, if X is isotropic, i.e. that EX = 0 and Σ is the identity matrix, we have

Var( h(X)) ≤ β 2 n n ∑ i=1 (β -i) -2 J(X). (23)
Taking β → ∞ yields the analogue for log-concave random variables, namely

Var( h(X)) ≤ J(X), (24)
which was observed by [START_REF] Nguyen | Dimensional variance inequalities of Brascamp-Lieb type and a local approach to dimensional Prékopa's theorem[END_REF].

Theorem IV.1. Let β > n and let X be a random variable in R n with density f being -1/β -concave. Then we have Ee α( h(X)-h(X)) ≤ e ψ c (α) (25)

for α < 1n/β , where

ψ c (α) = -αβ n ∑ i=1 (β -i) -1 - n ∑ i=1 log (1 -α)β -i β -i . (26)
Particularly, we have equality for Pareto distributions.

Proof. The moment generating function bound (25) easily follows from Lemma II.3 and Proposition IV.2. Some easy calculations will show the equality case for Pareto distributions. Essentially that is due to the identity L (α) = c (α), where c(α) is defined in [START_REF] Nguyen | Dimensional variance inequalities of Brascamp-Lieb type and a local approach to dimensional Prékopa's theorem[END_REF].

Corollary IV.6. Under the conditions and notations of Theorem IV.1, we have for t > 0 that P( h(X)h(X) > t) ≤ e -ψ * c,+ (t) ,

P( h(X)h(X) < -t) ≤ e -ψ * c,-(-t) ,

where ψ * c,+ and ψ * c,-are Fenchel-Legendre dual functions of ψ c,+ and ψ c,-, respectively.

In general we do not have explicit expressions for ψ * c,+ or ψ * c,-.

The following result (obtained in [START_REF]The entropy per coordinate of a random vector is highly constrained under convexity conditions[END_REF] when β ≥ n + 1) says that the entropy of a κ-concave distribution can not exceed that of the Pareto distribution with the same maximal density value.

Corollary IV.7. Under the conditions and notations of Theorem IV.1, we have

h(X) ≤ -log f ∞ + β n ∑ i=1 (β -i) -1 , (29)
where we denote by f ∞ the essential supremum. We have equality for Pareto distributions.

Proof. As a function of α, we have

(-αt -ψ c (α)) = -t + β n ∑ i=1 (β -i) -1 -β n ∑ i=1 ((1 -α)β -i) -1 .
For any t > β ∑ n i=1 (βi) -1 , we can see that -αtψ c (α) is a decreasing function of α < 1n/β . It is clear that lim α→-∞ (-αtψ c (α)) = ∞. Therefore we have ψ * c,-(-t) = ∞ for t > β ∑ n i=1 (βi) -1 . Using the lower tail estimate in Corollary IV.6, almost surely we have

h(X) -h(X) ≥ -β n ∑ i=1 (β -i) -1 .
Taking the supremum over all realizable values of X yields

-log f ∞ -h(X) ≥ -β n ∑ i=1 (β -i) -1 .
That is equivalent to the desired statement.

Remark IV.8. We can get corresponding estimates for logconcave random variables (see [START_REF]The entropy per coordinate of a random vector is highly constrained under convexity conditions[END_REF], [START_REF] Fradelizi | Optimal concentration of information content for log-concave densities[END_REF]) by taking the limit β → ∞.

ACKNOWLEDGMENT M.F. was supported in part by the Agence Nationale de la Recherche, project GeMeCoD (ANR 2011 BS01 007 01), J.L. and M.M. were supported in part by the U.S. National Science Foundation through grants DMS-1409504 and CCF-1346564.