diff --git a/service-t/src/com/android/server/NsdService.java b/service-t/src/com/android/server/NsdService.java
index 0adb290..fe1db3b 100644
--- a/service-t/src/com/android/server/NsdService.java
+++ b/service-t/src/com/android/server/NsdService.java
@@ -1943,6 +1943,8 @@
                 .setCachedServicesRetentionTime(mDeps.getDeviceConfigPropertyInt(
                         MdnsFeatureFlags.NSD_CACHED_SERVICES_RETENTION_TIME,
                         MdnsFeatureFlags.DEFAULT_CACHED_SERVICES_RETENTION_TIME_MILLISECONDS))
+                .setIsShortHostnamesEnabled(mDeps.isTetheringFeatureNotChickenedOut(
+                        mContext, MdnsFeatureFlags.NSD_USE_SHORT_HOSTNAMES))
                 .setOverrideProvider(new MdnsFeatureFlags.FlagOverrideProvider() {
                     @Override
                     public boolean isForceEnabledForTest(@NonNull String flag) {
diff --git a/service-t/src/com/android/server/connectivity/mdns/MdnsAdvertiser.java b/service-t/src/com/android/server/connectivity/mdns/MdnsAdvertiser.java
index 9c52eca..54f7ca3 100644
--- a/service-t/src/com/android/server/connectivity/mdns/MdnsAdvertiser.java
+++ b/service-t/src/com/android/server/connectivity/mdns/MdnsAdvertiser.java
@@ -46,6 +46,7 @@
 import com.android.server.connectivity.ConnectivityResources;
 import com.android.server.connectivity.mdns.util.MdnsUtils;
 
+import java.security.SecureRandom;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.List;
@@ -117,7 +118,7 @@
          * Generates a unique hostname to be used by the device.
          */
         @NonNull
-        public String[] generateHostname() {
+        public String[] generateHostname(boolean useShortFormat) {
             // Generate a very-probably-unique hostname. This allows minimizing possible conflicts
             // to the point that probing for it is no longer necessary (as per RFC6762 8.1 last
             // paragraph), and does not leak more information than what could already be obtained by
@@ -127,10 +128,24 @@
             // Having a different hostname per interface is an acceptable option as per RFC6762 14.
             // This hostname will change every time the interface is reconnected, so this does not
             // allow tracking the device.
-            // TODO: consider deriving a hostname from other sources, such as the IPv6 addresses
-            // (reusing the same privacy-protecting mechanics).
-            return new String[] {
-                    "Android_" + UUID.randomUUID().toString().replace("-", ""), LOCAL_TLD };
+            if (useShortFormat) {
+                // A short hostname helps reduce the size of APF mDNS filtering programs, and
+                // is necessary for compatibility with some Matter 1.0 devices which assumed
+                // 16 characters is the maximum length.
+                // Generate a hostname matching Android_[0-9A-Z]{8}, which has 36^8 possibilities.
+                // Even with 100 devices advertising the probability of collision is around 2E-9,
+                // which is negligible.
+                final SecureRandom sr = new SecureRandom();
+                final String allowedChars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
+                final StringBuilder sb = new StringBuilder(8);
+                for (int i = 0; i < 8; i++) {
+                    sb.append(allowedChars.charAt(sr.nextInt(allowedChars.length())));
+                }
+                return new String[]{ "Android_" + sb.toString(), LOCAL_TLD };
+            } else {
+                return new String[]{
+                        "Android_" + UUID.randomUUID().toString().replace("-", ""), LOCAL_TLD};
+            }
         }
     }
 
@@ -825,7 +840,7 @@
         mCb = cb;
         mSocketProvider = socketProvider;
         mDeps = deps;
-        mDeviceHostName = deps.generateHostname();
+        mDeviceHostName = deps.generateHostname(mDnsFeatureFlags.isShortHostnamesEnabled());
         mSharedLog = sharedLog;
         mMdnsFeatureFlags = mDnsFeatureFlags;
         final ConnectivityResources res = new ConnectivityResources(context);
@@ -943,7 +958,7 @@
         mRegistrations.remove(id);
         // Regenerates host name when registrations removed.
         if (mRegistrations.size() == 0) {
-            mDeviceHostName = mDeps.generateHostname();
+            mDeviceHostName = mDeps.generateHostname(mMdnsFeatureFlags.isShortHostnamesEnabled());
         }
     }
 
diff --git a/service-t/src/com/android/server/connectivity/mdns/MdnsFeatureFlags.java b/service-t/src/com/android/server/connectivity/mdns/MdnsFeatureFlags.java
index c4a9110..1cf5e4d 100644
--- a/service-t/src/com/android/server/connectivity/mdns/MdnsFeatureFlags.java
+++ b/service-t/src/com/android/server/connectivity/mdns/MdnsFeatureFlags.java
@@ -81,6 +81,12 @@
     public static final String NSD_CACHED_SERVICES_REMOVAL = "nsd_cached_services_removal";
 
     /**
+     * A feature flag to control whether to use shorter (16 characters + .local) hostnames, instead
+     * of Android_[32 characters] hostnames.
+     */
+    public static final String NSD_USE_SHORT_HOSTNAMES = "nsd_use_short_hostnames";
+
+    /**
      * A feature flag to control the retention time for cached services.
      *
      * <p> Making the retention time configurable allows for testing and future adjustments.
@@ -130,6 +136,9 @@
     // Flag for accurate delay callback
     public final boolean mIsAccurateDelayCallbackEnabled;
 
+    // Flag to use shorter (16 characters + .local) hostnames
+    public final boolean mIsShortHostnamesEnabled;
+
     @Nullable
     private final FlagOverrideProvider mOverrideProvider;
 
@@ -225,6 +234,10 @@
                 NSD_CACHED_SERVICES_RETENTION_TIME, (int) mCachedServicesRetentionTime);
     }
 
+    public boolean isShortHostnamesEnabled() {
+        return mIsShortHostnamesEnabled || isForceEnabledForTest(NSD_USE_SHORT_HOSTNAMES);
+    }
+
     /**
      * Indicates whether {@link #NSD_ACCURATE_DELAY_CALLBACK} is enabled, including for testing.
      */
@@ -248,6 +261,7 @@
             boolean isCachedServicesRemovalEnabled,
             long cachedServicesRetentionTime,
             boolean isAccurateDelayCallbackEnabled,
+            boolean isShortHostnamesEnabled,
             @Nullable FlagOverrideProvider overrideProvider) {
         mIsMdnsOffloadFeatureEnabled = isOffloadFeatureEnabled;
         mIncludeInetAddressRecordsInProbing = includeInetAddressRecordsInProbing;
@@ -261,6 +275,7 @@
         mIsCachedServicesRemovalEnabled = isCachedServicesRemovalEnabled;
         mCachedServicesRetentionTime = cachedServicesRetentionTime;
         mIsAccurateDelayCallbackEnabled = isAccurateDelayCallbackEnabled;
+        mIsShortHostnamesEnabled = isShortHostnamesEnabled;
         mOverrideProvider = overrideProvider;
     }
 
@@ -285,6 +300,7 @@
         private boolean mIsCachedServicesRemovalEnabled;
         private long mCachedServicesRetentionTime;
         private boolean mIsAccurateDelayCallbackEnabled;
+        private boolean mIsShortHostnamesEnabled;
         private FlagOverrideProvider mOverrideProvider;
 
         /**
@@ -303,6 +319,7 @@
             mIsCachedServicesRemovalEnabled = false;
             mCachedServicesRetentionTime = DEFAULT_CACHED_SERVICES_RETENTION_TIME_MILLISECONDS;
             mIsAccurateDelayCallbackEnabled = false;
+            mIsShortHostnamesEnabled = true; // Default enabled.
             mOverrideProvider = null;
         }
 
@@ -439,6 +456,16 @@
         }
 
         /**
+         * Set whether the short hostnames feature is enabled.
+         *
+         * @see #NSD_USE_SHORT_HOSTNAMES
+         */
+        public Builder setIsShortHostnamesEnabled(boolean isShortHostnamesEnabled) {
+            mIsShortHostnamesEnabled = isShortHostnamesEnabled;
+            return this;
+        }
+
+        /**
          * Builds a {@link MdnsFeatureFlags} with the arguments supplied to this builder.
          */
         public MdnsFeatureFlags build() {
@@ -454,6 +481,7 @@
                     mIsCachedServicesRemovalEnabled,
                     mCachedServicesRetentionTime,
                     mIsAccurateDelayCallbackEnabled,
+                    mIsShortHostnamesEnabled,
                     mOverrideProvider);
         }
     }
diff --git a/tests/unit/java/com/android/server/connectivity/mdns/MdnsAdvertiserTest.kt b/tests/unit/java/com/android/server/connectivity/mdns/MdnsAdvertiserTest.kt
index df48f6c..ba62114 100644
--- a/tests/unit/java/com/android/server/connectivity/mdns/MdnsAdvertiserTest.kt
+++ b/tests/unit/java/com/android/server/connectivity/mdns/MdnsAdvertiserTest.kt
@@ -42,17 +42,20 @@
 import java.util.Objects
 import java.util.concurrent.CompletableFuture
 import java.util.concurrent.TimeUnit
+import kotlin.test.assertTrue
 import org.junit.After
 import org.junit.Assert.assertEquals
 import org.junit.Before
 import org.junit.Test
 import org.junit.runner.RunWith
 import org.mockito.ArgumentCaptor
+import org.mockito.ArgumentMatchers.anyBoolean
 import org.mockito.ArgumentMatchers.eq
 import org.mockito.Mockito.any
 import org.mockito.Mockito.anyInt
 import org.mockito.Mockito.argThat
 import org.mockito.Mockito.atLeastOnce
+import org.mockito.Mockito.doCallRealMethod
 import org.mockito.Mockito.doReturn
 import org.mockito.Mockito.mock
 import org.mockito.Mockito.never
@@ -185,12 +188,12 @@
     @Before
     fun setUp() {
         thread.start()
-        doReturn(TEST_HOSTNAME).`when`(mockDeps).generateHostname()
+        doReturn(TEST_HOSTNAME).`when`(mockDeps).generateHostname(anyBoolean())
         doReturn(mockInterfaceAdvertiser1).`when`(mockDeps).makeAdvertiser(eq(mockSocket1),
-                any(), any(), any(), any(), eq(TEST_HOSTNAME), any(), any()
+                any(), any(), any(), any(), any(), any(), any()
         )
         doReturn(mockInterfaceAdvertiser2).`when`(mockDeps).makeAdvertiser(eq(mockSocket2),
-                any(), any(), any(), any(), eq(TEST_HOSTNAME), any(), any()
+                any(), any(), any(), any(), any(), any(), any()
         )
         doReturn(true).`when`(mockInterfaceAdvertiser1).isProbing(anyInt())
         doReturn(true).`when`(mockInterfaceAdvertiser2).isProbing(anyInt())
@@ -578,11 +581,59 @@
     fun testRemoveService_whenAllServiceRemoved_thenUpdateHostName() {
         val advertiser =
             MdnsAdvertiser(thread.looper, socketProvider, cb, mockDeps, sharedlog, flags, context)
-        verify(mockDeps, times(1)).generateHostname()
+        verify(mockDeps, times(1)).generateHostname(anyBoolean())
         postSync { advertiser.addOrUpdateService(SERVICE_ID_1, SERVICE_1,
                 DEFAULT_ADVERTISING_OPTION, TEST_CLIENT_UID_1) }
         postSync { advertiser.removeService(SERVICE_ID_1) }
-        verify(mockDeps, times(2)).generateHostname()
+        verify(mockDeps, times(2)).generateHostname(anyBoolean())
+    }
+
+    private fun doHostnameGenerationTest(shortHostname: Boolean): Array<String> {
+        doCallRealMethod().`when`(mockDeps).generateHostname(anyBoolean())
+        val flags = MdnsFeatureFlags.newBuilder().setIsShortHostnamesEnabled(shortHostname).build()
+        val advertiser =
+            MdnsAdvertiser(thread.looper, socketProvider, cb, mockDeps, sharedlog, flags, context)
+        postSync { advertiser.addOrUpdateService(SERVICE_ID_1, SERVICE_1,
+            DEFAULT_ADVERTISING_OPTION, TEST_CLIENT_UID_1) }
+
+        val socketCbCaptor = ArgumentCaptor.forClass(SocketCallback::class.java)
+        verify(socketProvider).requestSocket(eq(TEST_NETWORK_1), socketCbCaptor.capture())
+
+        val socketCb = socketCbCaptor.value
+        postSync { socketCb.onSocketCreated(TEST_SOCKETKEY_1, mockSocket1, listOf(TEST_LINKADDR)) }
+
+        val hostnameCaptor = ArgumentCaptor.forClass(Array<String>::class.java)
+        verify(mockDeps).makeAdvertiser(
+            eq(mockSocket1),
+            eq(listOf(TEST_LINKADDR)),
+            eq(thread.looper),
+            any(),
+            any(),
+            hostnameCaptor.capture(),
+            any(),
+            any()
+        )
+        return hostnameCaptor.value
+    }
+
+    @Test
+    fun testShortHostnameGeneration() {
+        val hostname = doHostnameGenerationTest(shortHostname = true)
+        // Short hostnames are [8 uppercase letters or digits].local
+        assertEquals(2, hostname.size)
+        assertTrue(Regex("Android_[A-Z0-9]{8}").matches(hostname[0]),
+            "Unexpected hostname: ${hostname.contentToString()}")
+        assertEquals("local", hostname[1])
+    }
+
+    @Test
+    fun testLongHostnameGeneration() {
+        val hostname = doHostnameGenerationTest(shortHostname = false)
+        // Long hostnames are Android_[32 lowercase hex characters].local
+        assertEquals(2, hostname.size)
+        assertTrue(Regex("Android_[a-f0-9]{32}").matches(hostname[0]),
+            "Unexpected hostname: ${hostname.contentToString()}")
+        assertEquals("local", hostname[1])
     }
 
     private fun postSync(r: () -> Unit) {